遺伝的アルゴリズムで巡回セールスマン問題

 2015/7/27 追記

　記事とコードが非常に雑ですので，コーディングをするために巡回セールスマンや遺伝的アルゴリズムの詳細が知りたいという方には時間の無駄になる可能性が高いので読むことをお勧めしません。巡回セールスマンについては，以下の記事で様々なアルゴリズムを用いての解決例を挙げており，非常に丁寧に書かれていますので，こちらをおすすめします。

www.geocities.jp

最近機械学習とCommon Lispの勉強をしていたので、これでなにかできないかなと思いやってみました。

github

1.1 巡回セールスマン問題とは

wiki

複数ある街を、全て回った時の最小コストの経路を割り出すことを目的としたもの。 街が全てつながっているとすると、(街の数)! の組み合わせになるため、数が多くなると単純な総当りではとても求められません。

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の詳細な日本語の資料があまり見つからなかった)

  ASDF - Common LISP users jp

  ASDF Manual

• テストを全くしていないので次になにか作る時は意識したい(TDDというものの存在を知ったので試してみたい)

なにかあればtwitterかコメントにおねがいします。