私はこれについてさまざまなものを読み、関連する原理と概念を理解していますが、直接接続されていない隣接する都市 (染色体内) を含む染色体 (ルートを表す) の適合度を計算する方法の詳細について言及している論文はありません。 (グラフ内の) エッジによって。
たとえば、各遺伝子がグラフ/マップ上の都市のインデックスを表す染色体 1|3|2|8|4|5|6|7 が与えられた場合、その適合度 (つまり、たとえば、都市 2 と 8 の間に直接のエッジ/リンクがない場合。2 と 8 の間のルートを計算し、このルートの距離を合計に追加するために、ある種の貪欲なアルゴリズムに従いますか?
この問題は、GA を TSP に適用する場合によく見られます。やったことがある方、感想を教えてください。ありがとう。
グラフ上で 2 と 8 の間にリンクがない場合、2|8 または 8|2 を含む染色体は、古典的な巡回セールスマン問題では無効です。2 から 8 の間に他のルートを見つけた場合、おそらく「各場所を 1 回訪問する」という要件に違反することになります。
非常に危険ではあるが実用的な解決策の 1 つは、これらのノード間に距離が非常に長いエッジを含めるか、言語がサポートしている場合は +INF を含めることです。そうすれば、標準の最小化フィットネス関数は自然にそれらを刈り込みます。
問題の元の定式化にはすべてのノード間のエッジが含まれていると思うので、これは問題ではありません。
染色体が有効な解決策を表していない場合、問題を解決することは完全に不適切です。したがって、フィットネスの注文方法によって異なります。つまり、数値が小さいほど適応度が高いことを表す場合 (適応度が総コストを表す場合はおそらく良い考えです)、最大値を割り当てて、無効な遺伝子配列に到達したときにそのクロモゾンのそれ以上の適応度計算を中断します。
(または逆に、適合度が高いほどクロモソンがその仕事により適していることを意味する場合は、ゼロの適合度を割り当てます)
ただし、他の人が指摘しているように、無効な染色体が発生しないようにする方がよい場合があります。ただし、それ自体が過度に複雑なプロセスである場合は、それらを許可し、壊れた染色体が次の世代になる可能性が低いことを確認することは、受け入れられるアプローチになる可能性があります.
これはまさにその種類の問題であり、TSP 問題に対する GA ベースのソリューションには、特殊なクロスオーバーおよび突然変異手法が適用されています。この質問を参照してください。