TSPの最近のブログ記事

paper_2007.jpg

昨年のこの時期、学会に出発する直前に教授から「元気が出るから、な!」と言われて腐りかけのバナナを渡されたり、私服で一人浮いた発表者になったりとひどい思い出満載のあのGAの論文が載ったようです。

高2の時、部活顧問のO先生に頼まれてマッチ箱の脳(AI)(この本、AIの入門書としては最高だと思う。もう新しく刷ってないのが残念だ。)に載っていたGAのプロセスを自分なりにperlスクリプトに落としこんだのがGAとの出会いだったが、まさか数年後に学会論文に載せるほど長いつき合いになるとは思ってもみなかったな。そう思うと感慨深いものがある。

さぁ、あとは学内論文だけか。( ´Д`)-3

#追記
マッチ箱の脳(AI)、ほぼ日でタダで読めるようだ!素晴らしい!
ほぼ日刊イトイ新聞 - がんばれ森川くんの遺伝子くん

ni_2.jpeg

今日中に組めなかったら研究室泊まるかなぁ~と思っていたのだが、なんとかうまく動いてくれたっぽい。
前回のヤツと比べて明らかに距離だけではなく時間の制約も考慮してくれてるっぽいし。

とりあえずCの方で吐き出された遺伝子と比べてみなければ...。
検証が無事終わったらようやくGAっぽいプログラミングができそう。

before_ni.png

前回の記事でちょろっと述べた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で近似解を求めるなら初期世代は多様性を持った方が嬉しいのでコレ使うことにする。
幸いランダムなノード列を持つ遺伝子の生成はできてるのでこれからこれを実装してみます(´・ω・`)

前回のエントリーで紹介した本が読み終わったので(後半、数理計画問題とか知らなかったから読むのつらかったー。とりあえず近似解方のあたりが特に知りたかったので後半は斜め読み(;´Д`))、とりあえず自分に関係ありそうなところだけまとめておく。

:近似解法
nearest neighbor method
とりあえず最も近い拠点からどんどん繋げていきましょうと言う古典的な方法。途中まではイイ感じに進むが、最後ら辺でコスト大な経路が発生する。

:改善法
2-opt,3-opt
経路をいくつか(2or3本)選んで繋ぎ変える。

opt.png

もし繋ぎ変えた結果、全体の経路が短くなってればそれ採用。
が、図を書いて気づいたのだが、繋ぎ変えてない箇所の順路の向きが変わる場合があるのね。図の2-optの例で言うと3→4だったのが繋ぎ変えた後だと4→3になる。

ちなみにもっと繋ぎ変える本数を大きくしたのをλ-optと言うらしい。が、3より大きくなると繋ぎ変えるパターンを把握するのが大変なのでプログラミングしづらい。なので実用的な範囲は2~3らしい。

ちなみにλを動的に変化させる手法もあり(LinとKernighanの算法)、こちらは改善する前の巡回路の影響を受けにくい性質を持つため、よく使われる。(これをベースとして改良した様々な手法が出てるがこれは後々調べることにする。)

---

んでさっきのnearest neighbor methodの話に戻るけど、この手法で求められた巡回路は最適巡回路と多くの枝を共有していると言われているので改善法と組み合わせれば最後の詰めで発生したコスト大な経路が無くなり、ナイスな答えになる。

個人的に知りたかったnearest insertion methodについての話がなかったのが残念(´・ω・`)
とりあえずそろそろプログラムの方に取りかかることにしよう。

このアーカイブについて

このページには、過去に書かれたブログ記事のうちTSPカテゴリに属しているものが含まれています。

前のカテゴリはTechnologyです。

次のカテゴリはゲームです。

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

月別 アーカイブ

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