昨年のこの時期、学会に出発する直前に教授から「元気が出るから、な!」と言われて腐りかけのバナナを渡されたり、私服で一人浮いた発表者になったりとひどい思い出満載のあのGAの論文が載ったようです。
高2の時、部活顧問のO先生に頼まれてマッチ箱の脳(AI)(この本、AIの入門書としては最高だと思う。もう新しく刷ってないのが残念だ。)に載っていたGAのプロセスを自分なりにperlスクリプトに落としこんだのがGAとの出会いだったが、まさか数年後に学会論文に載せるほど長いつき合いになるとは思ってもみなかったな。そう思うと感慨深いものがある。
さぁ、あとは学内論文だけか。( ´Д｀)-3
#追記
マッチ箱の脳(AI)、ほぼ日でタダで読めるようだ!素晴らしい!
ほぼ日刊イトイ新聞 - がんばれ森川くんの遺伝子くん
今日中に組めなかったら研究室泊まるかなぁ～と思っていたのだが、なんとかうまく動いてくれたっぽい。
前回のヤツと比べて明らかに距離だけではなく時間の制約も考慮してくれてるっぽいし。
とりあえずCの方で吐き出された遺伝子と比べてみなければ...。
検証が無事終わったらようやくGAっぽいプログラミングができそう。
前回の記事でちょろっと述べた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を挿入してそれが終わったら今度は5番のノードを距離が短くなるように新しくできた4つのノードの中に加えて更に今度は2を...(以下略
よーするに評価基準が距離なだけで挿入ソートと動きは同じ。
当然最初の3サイクルとその後に続くノード列によって大きく巡回路は変わる。
実際にさっき挙げたページに
変形Kruscal法が最も精度が良く、最近傍法がその次で、最近挿入法は全く精度が良くない。
とある。だけどGAで近似解を求めるなら初期世代は多様性を持った方が嬉しいのでコレ使うことにする。
幸いランダムなノード列を持つ遺伝子の生成はできてるのでこれからこれを実装してみます（´・ω・｀）
前回のエントリーで紹介した本が読み終わったので(後半、数理計画問題とか知らなかったから読むのつらかったー。とりあえず近似解方のあたりが特に知りたかったので後半は斜め読み(;´Д｀))、とりあえず自分に関係ありそうなところだけまとめておく。
:近似解法
nearest neighbor method
とりあえず最も近い拠点からどんどん繋げていきましょうと言う古典的な方法。途中まではイイ感じに進むが、最後ら辺でコスト大な経路が発生する。
:改善法
2-opt,3-opt
経路をいくつか(2or3本)選んで繋ぎ変える。
もし繋ぎ変えた結果、全体の経路が短くなってればそれ採用。
が、図を書いて気づいたのだが、繋ぎ変えてない箇所の順路の向きが変わる場合があるのね。図の2-optの例で言うと3→4だったのが繋ぎ変えた後だと4→3になる。
ちなみにもっと繋ぎ変える本数を大きくしたのをλ-optと言うらしい。が、3より大きくなると繋ぎ変えるパターンを把握するのが大変なのでプログラミングしづらい。なので実用的な範囲は2～3らしい。
ちなみにλを動的に変化させる手法もあり(LinとKernighanの算法)、こちらは改善する前の巡回路の影響を受けにくい性質を持つため、よく使われる。(これをベースとして改良した様々な手法が出てるがこれは後々調べることにする。)
---
んでさっきのnearest neighbor methodの話に戻るけど、この手法で求められた巡回路は最適巡回路と多くの枝を共有していると言われているので改善法と組み合わせれば最後の詰めで発生したコスト大な経路が無くなり、ナイスな答えになる。
個人的に知りたかったnearest insertion methodについての話がなかったのが残念（´・ω・｀）
とりあえずそろそろプログラムの方に取りかかることにしよう。
GAについての知識はある程度持っていると自負しているのだが、巡回セールスマン問題そのものについてはまだ勉強不足だなぁと感じたので...
生協で見つけた「巡回セールスマン問題への招待 シリーズ「現代人の数理」」(Amazon)
を研究室で購入しまして、今現在この本を読んでます。
途中まで読んでるんだけど、この本結構お勧めです。
1行だけ引用すると...
だから大和言葉にせえへんと読者さんから苦情が出るといってまっしゃろ.
と書いてあるように英語嫌いな技術屋さんにも大変優しい本となっております。(´Д｀*)
内容も上の1文見てくれれば分かると思うけど堅苦しくなく、軽い感じ。
コツコツ基幹部分を作って1週間。ようやく形になるものができた━━（゜∀゜*）━━!!!
早速前の記事に書いた近似解法を用いたCのプログラムが吐き出したデータと乱数を頼りに作ったデータを比べてみた。
[近似解法を用いた場合]
[乱数のみで初期化した場合]
||
|| ⊂⊃
|| ∧ ∧
|| （ ⌒ ヽ
∧||∧ ∪ ﾉ
（ ⌒ ヽ 彡 Ｖ
∪ ﾉ ﾌﾜｰﾘ
∪∪
どちらも初期世代の遺伝子である。なので乱数のみの方がぐっちゃぐっちゃなのは理解できるが、近似解法を用いた方は想像以上の性能だなぁ。初期世代だし、近似解法使ってもひどいルート通るんじゃないの?と思っていたのだが。こりゃぁ、ちゃんと近似解法も取り入れないと元々のプログラムに絶対勝てなさそうだ(;´Д｀)
とりあえずボタンの部分の実装をさっさとやってしまうかぁ。SWTのときのように白く化けないことを祈りながら(´Д｀;)
研究室:GAのC->Java化計画
なんとか遺伝子オブジェクトが初期化できるところまで完了。とりあえず遺伝子評価を行う部分が間違っていないかどうかCのプログラムで吐き出した遺伝子情報をJavaの方で読み込ませて、内部情報が全く同じ状態の遺伝子オブジェクトを作り、デバッグモードにて色々な値を調査。とりあえず5回分しかまだやってないけど、評価値や内部情報は全て一致!(絶対どっかポカしてそうだなぁと移植しながら思っていたのですが)多分問題なく動いているとみてｲｲはず!!
問題はこれからだなぁ。今のところ、小細工無しで純粋にGAとして問題を解くような感じなんだよねぇ。具体的に言うと、ただ乱数使って初期化してるだけなので激しく遺伝子の質が悪い。(初期世代だから仕方ないと言えば仕方ないが...)
---
(これからやるべきコト)
TSPに関する論文を読んで(googleで調べたらこの辺(pdf)とかこの辺(ppt)とか)もっと効率のイイ方法を調べる。
初期化が終わったら今度は遺伝集団に関するところの実装だなぁ。
今期中に終わる気がしません...・゜・(ノ∀｀)・゜・
確実に一歩ずつ進んでいると言えば進んでいるのだが...。う～むぅ...。
