artificial-intelligence - TSP 問題で、最も短いツアーを生成するアプローチはどれですか?最近傍または遺伝的アルゴリズム?

Question

ここ数日、遺伝的アルゴリズムを使用した TS ソリューションを紹介しているいくつかのWeb サイトに注目しました。

TSP 問題で、最も短いツアーを生成するアプローチはどれですか?最近傍または遺伝的アルゴリズム?

Answer 1

どちらの手法も最適なソリューションを保証するものではないため、マイレージは異なります。少し運が良ければ、どちらの手法も他の手法よりも優れたパフォーマンスを発揮する可能性があります。どちらの手法にも長所と短所があります。

最近傍: +高速、+シンプル、-通常は最適ではない

遺伝的アルゴリズム: -遅い、 -複雑、+ソリューションは時間の経過とともに最適化される傾向にある

大きな違いは、シミュレーテッド アニーリングや遺伝的アルゴリズムなどのランダム化されたアルゴリズムは、時間の経過とともに改善し続ける可能性があることです。それらを長く実行すればするほど、最適なソリューションが得られる可能性が高くなります (ただし、保証はありません)。

NN は高速なので、テクニックを組み合わせることを妨げるものは何もありません。NN を実行して、おそらくランダムよりも優れた開始ソリューションを見つけます。次に、そのソリューションを遺伝的アルゴリズムにフィードし、適切と思われる限り実行します。

最適解に興味がある場合は、Lin-Kernighan ヒューリスティックと線形計画法を調べてください。両方とも、85,900 都市ツアーと24,978 都市スウェーデン ツアーのこのソリューションを含む、大規模なツアーに最適なソリューションを見つけるために使用されました。

ジョージア工科大学のTSP サイトは優れたリソースです。