TSPの進化的最適化

メタヒューリスティクスの授業課題

Carlos Requena Doña avatar

Carlos Requena Doña

AI・3Dグラフィックス・ゲーム開発

このプロジェクトは、巡回セールスマン問題 (TSP) を解決するためのメタヒューリスティクスアルゴリズムの実装と実験的分析を文書化したものです。これは、Carlos Requena Doña と Yessin Mohamed によって大学の実習の一環として開発されました。

主な目的は、異なる構成と交叉演算子を使用して、遺伝的アルゴリズム (GA) と 差分進化アルゴリズム (EDA/EDB) の性能を比較することです。

🧠 アルゴリズムと問題

この問題は、一連の都市を正確に1 回ずつ訪問し、出発点に戻る最短ルートを見つけることです。地点間の距離はユークリッド距離の公式を使用して計算されます。

プロジェクトでは主に2つのタイプのアルゴリズムを実装しています:

  1. 遺伝的アルゴリズム(世代交代モデル): 個体(ルート)の集団を用いて自然進化をシミュレートします。
  2. 差分進化アルゴリズム: 順列に基づく差分変異演算子を使用します。

主要コンポーネント

  • FileLoader (Singleton): ファイルからの都市座標の読み込みと設定パラメータを管理します。「マジックナンバー」を避け、実験を容易にします。
  • 解の表現: 集団内の各個体はルート(都市のベクトル)を表します。
  • 適応度関数: ルートの総距離として計算されます。目標はこのコストを最小化することです。

🧬 遺伝的アルゴリズム (GA)

世代交代型遺伝的アルゴリズムは、選択、交叉、変異の古典的なサイクルに従います:

  1. 選択: 親を選ぶためにトーナメント選択が使用されます。
  2. 交叉: OX2 (Order Crossover 2) や MOC (Maximal Preservative Crossover) などの演算子が実装されています。
  3. エリート保存: 解の質が低下しないように、最良の個体(エリート)が次の世代に保存されます。
  4. 置換: 新しい世代が古い世代を完全に置き換えます。

🧪 差分進化

差分アルゴリズムは、三項再結合戦略を使用します:

  • 「親」、2つのランダムな個体、および「ターゲット」個体を選択します。
  • 新しい解を生成するために差分変異演算子(EDA/EDB)を適用します。
  • 新しい個体は、適応度(コスト)を改善する場合にのみ、古い個体を置き換えます。

📊 実験と結果

5つの異なる乱数シードと複数のパラメータ構成(集団サイズ、エリート数、確率)を使用して、広範なテストが行われました。

比較分析

  • MOC vs OX2: MOC 演算子は一般的に OX2 よりも優れた結果を示し、特に早期収束において優れていました。MOC は初期に非常に速く改善し、その後安定する傾向がありますが、OX2 はより一定の改善率を維持します。
  • EDA vs EDB: EDA 選択戦略は、結果の平均と標準偏差の両方において EDB よりも優れていることが証明されました。
  • 全体的なパフォーマンス: 実施されたテストにおいて、MOC は EDA を大幅に上回り、より良い平均コストを達成しました。

結論

アルゴリズムの挙動は、MOC は初期収束が速いため、反復回数が少ないシナリオに理想的であることを示唆しています。一方、OX2 は、早期の停滞なしに一定の改善が必要とされる非常に長い実行において、より堅牢である可能性があります。


メタヒューリスティクスのコースのために開発されたプロジェクトです。