前回の記事でちょろっと述べたLinとKernighanの算法、改善する前の巡回路の影響を受けにくいってことはGAに適用した場合、似たような遺伝子だらけになるのであんまよろしくないような気がしてきた。
とりあえずnearest insertion methodの動きが分かったので忘れないうちのめもっておく。
TSPの論文を見てみると
nearest insertion method...(2つの都市i,jの距離をd(i,j)で表すとする。)
d(i,k)+d(i,j)-d(k,j)が最小となる都市k,jの間に都市iを挿入するように枝を繋ぎ変える
らしいのだがこれじゃ全然イメージできない。(;´Д`)
ぐぐってみたらもっと分かりやすい説明をしてくれるページがあったのでそこから引用すると...
簡単に言えば、「3-サイクルから始めて、サイクルに含まれない点のうち、そのサイクルに追加して新しいサイクルを作る時最もコストが小さくなるものを選び、その頂点を追加する。この操作をHamiltonサイクルになるまで続ける」ということになる。
図にするとこんな感じか
一番距離が短くなるような箇所に3を挿入してそれが終わったら今度は5番のノードを距離が短くなるように新しくできた4つのノードの中に加えて更に今度は2を...(以下略
よーするに評価基準が距離なだけで挿入ソートと動きは同じ。
当然最初の3サイクルとその後に続くノード列によって大きく巡回路は変わる。
実際にさっき挙げたページに
変形Kruscal法が最も精度が良く、最近傍法がその次で、最近挿入法は全く精度が良くない。
とある。だけどGAで近似解を求めるなら初期世代は多様性を持った方が嬉しいのでコレ使うことにする。
幸いランダムなノード列を持つ遺伝子の生成はできてるのでこれからこれを実装してみます(´・ω・`)