巡回セールスマンに遺伝的アルゴリズムを適用する際の詳細な質問

Question

私はこれについてさまざまなものを読み、関連する原則と概念を理解していますが、直接接続されていない隣接する都市（染色体内）が関与する染色体（ルートを表す）のフィットネスを計算する方法の詳細については、紙のいずれも言及していませんエッジによって（グラフ内）。

たとえば、各遺伝子がグラフ/マップ上の都市のインデックスを表す染色体1 | 3 | 2 | 8 | 4 | 5 | 6 | 7を与えられた場合、そのフィットネスをどのように計算しますか（つまりの合計の合計たとえば、都市2と8の間に直接的なエッジ/リンクがない場合）。何らかの貪欲なアルゴリズムに従って2〜8の間のルートを作成し、このルートの距離を合計に追加しますか？

この問題は、GAをTSPに適用する場合、かなり一般的であるようです。以前にやったことがある人なら誰でもあなたの経験を共有してください。ありがとう。

Answer 1

グラフに2〜8の間にリンクがない場合、2 | 8または8 | 2の染色体が無効です 古典的な旅行セールスマンの問題について. 。 2〜8の間に他のルートが見つかった場合、おそらく「各場所に訪問する」要件に違反するでしょう。

本当に危険ですが、物語的な解決策の1つは、信じられないほど高い距離を持つノードの間にエッジを含めること、または言語がサポートする場合は +infさえ含めることです。そうすれば、フィットネス関数を最小化する標準の最小化機能は自然にそれらを剪定します。

問題の元の定式化には、すべてのノード間のエッジが含まれていると思うので、これは問題ではありません。

Answer 2

これは正確な種類の問題であり、TSP問題に対するGAベースのソリューションには専門的なクロスオーバーおよび突然変異法が適用されています。これを参照してください 質問.

Answer 3

クロモソンが有効なソリューションを表していない場合、問題を解決するのは完全に不適当です。したがって、フィットネスを注文する方法に応じて。つまり、より低い数がより多くのフィットネスを表す場合（フィットネスが総コストを表す場合はおそらく良いアイデア）、最大値を割り当てて、無効な遺伝子配列に到達すると、そのクロモソンのフィットネスの計算を破壊します。

（またはその逆、より高いフィットネスがクロモソンが仕事に適していることを意味する場合、ゼロのフィットネスを割り当てます）

しかし、他の人が指摘しているように、無効なクロモソンが発生しないようにする方が良いかもしれません。ただし、それ自体が過度にコンププロセスである場合、それらを許可し、壊れたクロモソーンが連続した世代になる可能性が低いことを保証することが許容可能なアプローチになる可能性があります。