6

場所のコレクションから最も分散した 3 つの場所を選択できるように、Microsoft Solver Foundation を使用しようとしています。モデルに 2 つの目標を追加しました。1 つは 3 つの場所が選択されるようにすること、もう 1 つはそれらが最も分散された 3 つの場所であることを確認することです。

static void Main(string[] args)
    {
        Location candidate1 = new Location(0, 43.432, -79.432);
        Location candidate2 = new Location(1, 43.0, -79.0);
        Location candidate3 = new Location(2, 23.0, 29.0);
        Location candidate4 = new Location(3, 43.0, -79.0);
        Location candidate5 = new Location(4, 43.0, -79.0);
        Location[] candidates = {candidate1, candidate2, candidate3, candidate4, candidate5};
        SolverContext solver = new SolverContext();
        Model model = solver.CreateModel();
        model.Name = "LocationModel";
        Set items = new Set(Domain.Any, "candidates");
        Decision take = new Decision(Domain.Boolean, "candidate", items);
        model.AddDecision(take);
        Parameter locations = new Parameter(Domain.RealNonnegative, "locations", items);
        locations.SetBinding(candidates, "ID", "ID");
        model.AddParameter(locations);


        var dist = from l1 in candidates from l2 in candidates select new { ID1 = l1.ID, ID2 = l2.ID, dist = Geography.GetDistance(l1.Latitude, l1.Longitude, l2.Latitude, l2.Longitude) };
        Parameter distance = new Parameter(Domain.RealNonnegative, "Location", items, items);
        distance.SetBinding(dist, "dist", "ID1", "ID2");
        model.AddParameter(distance);            
        Term goal = Model.Sum(Model.ForEach(items, i => Model.ForEach(items, j => take[i]*take[j]* distance[i, j])));

        model.AddConstraint("LocationsQuantityMax", Model.Sum(Model.ForEach(items, item => take[item])) == 3);
        model.AddGoal("Dispersion", GoalKind.Maximize, goal); 

        Directive directive = new HybridLocalSearchDirective();            
        Solution solution = solver.Solve(directive);
        List<Location> locations1 = new List<Location>();
        if (solution.Decisions.Any())
        {
            var selections = solution.Decisions.First().GetValues()
                .Where(d => (bool) d[0])
                .Select(d => Convert.ToInt32(d[1]));

            locations1.AddRange(
                from c in candidates
                join s in selections on c.ID equals s
                select c);
        }

        foreach (Location location in locations1)
        {
            Console.WriteLine("ID: {0}, Latitude: {1}, Longitude: {2}", location.ID, location.Latitude, location.Longitude);
        }

さらに、私の Location クラスは次のようになります。

class Location
{
    public int ID { get; private set; }
    public double Latitude { get; private set; }
    public double Longitude { get; private set; }

    public Location(int LocationID, double latitude, double longitude)
    {
        this.ID = LocationID;
        this.Latitude = latitude;
        this.Longitude = longitude;
    }
}

私の距離計算は次のとおりです。

    public static double ToRad(this double num)
    {
        return num * Math.PI / 180;
    }

    public static double GetDistance(double lat1, double lon1, double lat2, double lon2)
    {
        const int r = 6371; // Radius of earth in KM

        // Convert to Radians
        lat1 = lat1.ToRad();
        lon1 = lon1.ToRad();
        lat2 = lat2.ToRad();
        lon2 = lon2.ToRad();

        // Spherical Law of Cosines
        var resultCos =
            Math.Acos(
                Math.Sin(lat1) * Math.Sin(lat2) +
                Math.Cos(lat1) * Math.Cos(lat2) * Math.Cos(lon2 - lon1)
                ) * r;

        return resultCos;
    }

今、私のコードには2つの問題があり、それらがどこから来たのかわかりません.

まず、

現状の私のコードは、5 つの場所のほとんどの順列で機能し、そのうちの 3 つが同じ経度緯度 (つまり、この例では候補 2、候補 4、および候補 5) ですが、特定の候補の順列では、最も分散した 3 を返しません (つまり、同じ問題インスタンスは、候補宣言の順序を変更するだけです)。理由がわかりません。

第二に、

少なくとも 3 つの場所を選択するように制約をコメント アウトすると、すべての場所が選択されるのではなく、何も選択されません。

私の目標がほとんどの場合に機能するという事実は、それが正しいことを示しているようです。

これは宿題ではありません。返信してくれた人に感謝します。

4

1 に答える 1

1

を指定していることに問題があると思いますHybridLocalSearchDirective。投稿されたコードからそれを削除し、最適な答えを得ました：

ID: 0, Latitude: 43.432, Longitude: -79.432
ID: 1, Latitude: 43, Longitude: -79
ID: 2, Latitude: 23, Longitude: 29

用語を並べ替えたり、新しい場所を追加したりしても、最適なソリューションが得られます。

さらに、制約を削除すると、コードは 5 つLocationのオブジェクトすべてをソリューションとして選択しました。

なぜこれが機能するのかについて少し説明できればと思いますが、MSF に関して言えば、私は週末の戦士にすぎません。 これは、私が見つけることができる最も多くの情報HybridLocalSearchDirectiveであり、それが解決策に到達する方法です。重要なことに、最初に指摘された制限は次のとおりです。

最適な結果を保証するものではありません。

これが、最初の質問に対する答えになる可能性があります (最大分散位置が返されない理由)。

2 番目の質問 (制約を削除しても、より多くの場所が選択されないのはなぜですか) については、はっきりとは言えません。理由はわかりませんが、問題の仕様はそのディレクティブの退化したケースである可能性があります。

ベストアンサーではありませんが、参考になれば幸いです！

于 2013-02-09T15:46:19.883 に答える