遺伝的アルゴリズムで巡回セールスマン問題
2015/7/27 追記
記事とコードが非常に雑ですので,コーディングをするために巡回セールスマンや遺伝的アルゴリズムの詳細が知りたいという方には時間の無駄になる可能性が高いので読むことをお勧めしません。巡回セールスマンについては,以下の記事で様々なアルゴリズムを用いての解決例を挙げており,非常に丁寧に書かれていますので,こちらをおすすめします。
最近機械学習とCommon Lispの勉強をしていたので、これでなにかできないかなと思いやってみました。
1.1 巡回セールスマン問題とは
1.2 遺伝的アルゴリズムとは
かなり大雑把にいうと、解法がわからない問題を、プログラム内でデータを成長変化させて答えを見つけてもらおう。というもの。 ちょうど巡回セールスマンを例にしたわかりやすい記事があったので拝借します。 こちら
これとは交叉の実装が違っており、また終了条件を実装していません。
1.3 簡単に実験した
街はランダムに作り、たとえば10の街だとこうなります。(graph-utilを利用しています)
円の中の数値が街の番号で、町と町をつなぐ線の横の数値が距離を現します。
線の長さと距離は対応していません。この画像は10個の都市です。20だと
こんな感じになります。10ならまだしも、20の最短経路を普通に探そうとしたら骨が折れそうです(全ての街がつながっているので総当りで20!通り)
20で適当にぶん回してみると、
min: 73 ((8 5 7 12 9 18 2 10 1 3 14 6 15 20 16 19 4 11 13 17))
という数値がでました。これが最適解である保証はありませんが、かなり短い距離にみえます。 (図で表示できればわかりやすいのですが、残念ながらありません)
1000で適当な数回してみると、
min: 10233
という数値が出ました。短いようにみえますね(?)。
端折りましたがいろいろやってみました。
- ペアの選択 確率 = 適用度/全体の適用度の総和
これで回すと適応度が0.5付近のの遺伝子が残りやすい。
-> 適応度が高いものが一瞬で淘汰されてしまう。
逆に、適応度が高いものが生き残る確率を上げすぎると極端に最適解から遠い値に収束する可能性が高いので調整の目安が難しそう。
- セールスマンの数は10人くらいが良い結果が多かった気がする。
1.4 課題
実験について
- 遺伝的アルゴリズムではなにが最適解かを完全に判断できないが、もっと精度の高いものが作れるようになりたい。
-> 機械学習について知識を付ける(うまいこと最適解に導く方法など)
- 確率の問題でうまく適応度が高い遺伝子が残らず、ほとんどランダムに試しているようなものになってしまったので、もっと改良を加えたい。
コードについて
- 関数の奥でsetfをするなどしているので、関数は値を返すだけにして、update-worldにまとめたい。
-> やってみると、一つひとつがほぼ同じだが微妙に異なる(引数の数など)関数群になり、それをマクロで差異を吸収する方法が分からず断念した。
-> マクロについてもっと詳しく勉強する。
- asdfについて何となくで書いているので、しっかり勉強したい。(asdfの詳細な日本語の資料があまり見つからなかった)
- テストを全くしていないので次になにか作る時は意識したい(TDDというものの存在を知ったので試してみたい)
なにかあればtwitterかコメントにおねがいします。