Javaの巡回セールスマン問題

投稿日: 2019-10-18 2022-11-10
タグ: Algorithms, Java

1. 序章

このチュートリアルでは、シミュレーテッドアニーリングアルゴリズムについて学習し、巡回セールスマン問題（TSP）に基づく実装例を示します。

2. 焼き鈍し法

シミュレーテッドアニーリングアルゴリズムは、大きな探索空間の問題を解決するためのヒューリスティックです。

インスピレーションと名前は冶金学での焼きなましから来ました。これは、材料の加熱と制御された冷却を伴う技術です。

一般に、シミュレーテッドアニーリングは、ソリューションスペースを探索し、システムの温度を下げるため、より悪いソリューションを受け入れる可能性を減らします。次のanimationは、シミュレーテッドアニーリングアルゴリズムを使用して最適なソリューションを見つけるメカニズムを示しています。

観察できるように、アルゴリズムはシステムの高温でより広い解の範囲を使用し、グローバルな最適値を検索します。温度を下げながら、グローバルな最適値が見つかるまで、検索範囲は狭くなります。

アルゴリズムには、使用するいくつかのパラメーターがあります。

反復回数–シミュレーションの停止条件
初期温度–システムの開始エネルギー
冷却速度パラメーター–システムの温度を下げるパーセンテージ
最低温度–オプションの停止条件
シミュレーション時間–オプションの停止条件

これらのパラメータの値は、プロセスのパフォーマンスに大きな影響を与える可能性があるため、慎重に選択する必要があります。

3. 巡回セールスマン問題

巡回セールスマン問題（TSP）は、現代の世界で最もよく知られているコンピューターサイエンスの最適化問題です。

簡単に言えば、グラフ内のノード間の最適なルートを見つけることの問題です。総移動距離は、最適化基準の1つになります。 TSPの詳細については、こちらをご覧ください。

4. Javaモデル

TSP問題を解決するには、CityとTravelの2つのモデルクラスが必要です。最初のものでは、ノードの座標をグラフに保存します。

@Data
public class City {

    private int x;
    private int y;

    public City() {
        this.x = (int) (Math.random() * 500);
        this.y = (int) (Math.random() * 500);
    }

    public double distanceToCity(City city) {
        int x = Math.abs(getX() - city.getX());
        int y = Math.abs(getY() - city.getY());
        return Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2));
    }

}

City classのコンストラクターを使用すると、都市のランダムな場所を作成できます。 distanceToCity（..）ロジックは、都市間の距離に関する計算を担当します。

次のコードは、巡回セールスマンツアーのモデル化を担当します。旅行中の都市の最初の順序を生成することから始めましょう：

public void generateInitialTravel() {
    if (travel.isEmpty()) {
        new Travel(10);
    }
    Collections.shuffle(travel);
}

最初の注文を生成することに加えて、移動順序でランダムな2つの都市を交換するためのメソッドが必要です。これを使用して、シミュレーテッドアニーリングアルゴリズム内のより良いソリューションを検索します。

public void swapCities() {
    int a = generateRandomIndex();
    int b = generateRandomIndex();
    previousTravel = new ArrayList<>(travel);
    City x = travel.get(a);
    City y = travel.get(b);
    travel.set(a, y);
    travel.set(b, x);
}

さらに、新しいソリューションがアルゴリズムで受け入れられない場合は、前のステップで生成されたスワップを元に戻す方法が必要です。

public void revertSwap() {
    travel = previousTravel;
}

カバーしたい最後の方法は、最適化基準として使用される総移動距離の計算です。

public int getDistance() {
    int distance = 0;
    for (int index = 0; index < travel.size(); index++) {
        City starting = getCity(index);
        City destination;
        if (index + 1 < travel.size()) {
            destination = getCity(index + 1);
        } else {
            destination = getCity(0);
        }
            distance += starting.distanceToCity(destination);
    }
    return distance;
}

それでは、主要部分であるシミュレーテッドアニーリングアルゴリズムの実装に焦点を当てましょう。

5. シミュレーテッドアニーリングの実装

次のシミュレーテッドアニーリングの実装では、TSP問題を解決します。簡単に言うと、目的はすべての都市を移動するための最短距離を見つけることです。

プロセスを開始するには、 startingTemperature 、 numberOfIterations 、coolingRateの3つの主要なパラメーターを指定する必要があります。

public double simulateAnnealing(double startingTemperature,
  int numberOfIterations, double coolingRate) {
    double t = startingTemperature;
    travel.generateInitialTravel();
    double bestDistance = travel.getDistance();

    Travel currentSolution = travel;
    // ...
}

シミュレーションを開始する前に、都市の初期（ランダム）順序を生成し、移動の合計距離を計算します。これは最初に計算された距離であるため、currentSolution。とともにbestDistance変数内に保存します。

次のステップでは、メインのシミュレーションループを開始します。

for (int i = 0; i < numberOfIterations; i++) {
    if (t > 0.1) {
        //...
    } else {
        continue;
    }
}

ループは、指定した反復回数だけ続きます。さらに、温度が0.1以下になる場合にシミュレーションを停止する条件を追加しました。低温では最適化の違いがほとんど見えないため、シミュレーションの時間を節約できます。

シミュレーテッドアニーリングアルゴリズムの主なロジックを見てみましょう。

currentSolution.swapCities();
double currentDistance = currentSolution.getDistance();
if (currentDistance < bestDistance) {
    bestDistance = currentDistance;
} else if (Math.exp((bestDistance - currentDistance) / t) < Math.random()) {
    currentSolution.revertSwap();
}

シミュレーションの各ステップで、移動順に2つの都市をランダムに入れ替えます。

さらに、currentDistanceを計算します。新しく計算されたcurrentDistanceがbestDistanceよりも小さい場合、それを最良として保存します。

それ以外の場合は、確率分布のボルツマン関数が0〜1の範囲でランダムに選択された値よりも低いかどうかを確認します。はいの場合、都市の入れ替えを元に戻します。そうでない場合は、ローカルの最小値を回避するのに役立つため、都市の新しい順序を維持します。

最後に、シミュレーションの各ステップで、 coolingRate：を指定して温度を下げます。

t *= coolingRate;

シミュレーション後、シミュレーテッドアニーリングを使用して見つけた最良のソリューションを返します。

最適なシミュレーションパラメータを選択する方法に関するいくつかのヒントに注意してください。

小さなソリューションスペースの場合、品質を損なうことなくシミュレーション時間を短縮できるため、開始温度を下げて冷却速度を上げることをお勧めします。
より大きなソリューションスペースの場合は、より高い極小値が存在するため、より高い開始温度と小さな冷却速度を選択してください
システムの高温から低温までシミュレーションするのに十分な時間を常に提供します

メインのシミュレーションを開始する前に、より小さな問題のインスタンスでアルゴリズムの調整に時間を費やすことを忘れないでください。これにより、最終結果が向上します。シミュレーテッドアニーリングアルゴリズムの調整は、たとえばこの記事のに示されています。

6. 結論

このクイックチュートリアルでは、シミュレーテッドアニーリングアルゴリズムについて学ぶことができ、巡回セールスマン問題を解決しました。これは、特定のタイプの最適化問題に適用した場合に、この単純なアルゴリズムがいかに便利であるかを示してくれることを願っています。

この記事の完全な実装は、GitHubのにあります。

getdocs

13036