巡回セールスマン問題(3)

| コメント(0) | トラックバック(0)

前回の記事でちょろっと述べた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サイクルになるまで続ける」ということになる。


図にするとこんな感じか

nearest_insertion_method.png

一番距離が短くなるような箇所に3を挿入してそれが終わったら今度は5番のノードを距離が短くなるように新しくできた4つのノードの中に加えて更に今度は2を...(以下略
よーするに評価基準が距離なだけで挿入ソートと動きは同じ。

当然最初の3サイクルとその後に続くノード列によって大きく巡回路は変わる。
実際にさっき挙げたページに

変形Kruscal法が最も精度が良く、最近傍法がその次で、最近挿入法は全く精度が良くない。

とある。だけどGAで近似解を求めるなら初期世代は多様性を持った方が嬉しいのでコレ使うことにする。
幸いランダムなノード列を持つ遺伝子の生成はできてるのでこれからこれを実装してみます(´・ω・`)

トラックバック(0)

トラックバックURL: https://hoge.sub.jp/blog-cgi/mt/mt-tb.cgi/1021

このブログ記事について

このページは、Lyoが2005年12月 7日 13:51に書いたブログ記事です。

ひとつ前のブログ記事は「FreeBSDでもCool'n'Quiet」です。

次のブログ記事は「大改造!!劇的ビフォーアフター」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。

月別 アーカイブ

OpenID対応しています OpenIDについて
Powered by Movable Type 7.9.3