セールスマン問題を遺伝的アルゴリズムで解いてみた
セールスマン問題
セールスマン問題はWikipediaに説明があるのでそちらを見ていただければと思います。
巡回セールスマン問題 - Wikipedia
いくつかの都市を少ないコストで周るにはどの順番でいけばよいか、という問題です。人がやるよりプログラムにやらせたほうが楽そうです。
遺伝的アルゴリズム
今もよくわかっていません。生き物の進化を参考にして、いい個体といい個体を混ぜて新しい個体を作り、たまに突然変異で中身変えてより良い個体を作ろう、みたいなのが遺伝的アルゴリズムの大まかな認識です。
人が頑張って考えんでもプログラムが勝手に色々試行錯誤してくれるとか最高やん。遺伝的アルゴリズムを使ってなんか解きてぇと考え、セールスマン問題を見つけました。
こういった内容の記事はたくさんありますが、せっかく解いたので載せてみます。言語はClojureです。
書く
書いたソースコードを示します。
英語がさっぱりなので Google 翻訳を頼りに関数名つけてるけど、めんどくさいです。圧倒的英語力がほしい。
都市の数は20(要素の数も同様)、1世代100体を1000世代行いました。
都市間の距離は固定するためにそのままリストとして埋めました。
コストが最も少なくなるものを求めます。選択方式はルーレット方式が良さそうだったのでこれに決めました。
突然変異、交叉の確率についてはいくつか試してこれくらいがいい結果を速く得られたので、特に値に理由はありません。(交叉は9割程度がよいと書いてあったところもあったのですが、あまり良い結果を得られませんでした）
実行毎に結果は変わりますが、大体最初は Cost: 50000 くらいから始まっていました。
実行
最も良かった結果としては
$ lein run
problem: (2138 1198 2667 8293 644 2644 9025 7551 2313 200 1176 501 1364 3016 525 4364 1576 6120 2672 4621 5656 6575 352 5682 6825 6858 1607 2881 3879 3760 424 2627 2055 7930 2642 97 4653 9971 2097 5441 4536 3917 710 195 405 7861 1482 5260 58 4534 5229 696 1711 1696 278 5341 4892 3356 9323 1288 4441 8054 9194 4144 4698 9673 7337 5133 6095 9610 3524 5142 3050 6517 6484 4033 319 1267 2949 751 4784 340 952 1083 1013 387 134 249 1874 368 9259 6963 9 5394 5200 4081 2004 8132 8228 8474 4734 9493 5628 9426 2566 197 9341 479 4821 8767 3667 4413 5249 9557 5846 4856 9110 6405 5826 848 8933 3772 1401 2623 6982 7329 1519 7881 1075 276 3602 7835 470 9977 414 1444 283 1931 8191 4425 6096 4485 589 6870 5281 8295 2284 9578 7887 9042 2033 4587 7949 623 7421 9818 5490 8671 2585 1229 640 1111 5785 8392 3857 3187 5869 1094 464 9391 5375 5128 3439 3601 3306 5301 5746 1784 2485 2367 2325 8722 4754 8540 2342 1308 2295 3124 4279 6214 4874 5791 6 8973 887 96 9121 4863 4767 3908 1518 9347 4525 6652 4397 7324 968 5432 9755 5909)
第 0 世代
DNA: [14 18 7 4 17 6 12 8 1 16 15 19 9 3 13 5 10 2 0 11]
Cost: 55250
第 2 世代
DNA: (14 18 4 10 9 6 1 12 17 16 2 7 13 3 19 8 5 15 0 11)
Cost: 49160
第 10 世代
DNA: (14 18 4 10 9 6 17 12 1 16 5 8 13 3 19 7 2 15 0 11)
Cost: 39874
第 14 世代
DNA: (14 18 4 10 9 6 7 12 19 16 2 8 13 3 17 1 5 0 15 11)
Cost: 38202
第 29 世代
DNA: (14 18 4 10 9 6 7 12 19 3 2 8 13 16 17 1 5 0 15 11)
Cost: 33456
第 35 世代
DNA: (14 18 4 10 9 6 7 12 13 16 2 8 19 3 17 1 5 0 15 11)
Cost: 33019
第 37 世代
DNA: (14 18 4 1 9 6 7 12 19 3 2 8 13 16 17 10 5 0 15 11)
Cost: 31189
第 43 世代
DNA: (14 18 4 1 9 6 2 12 19 3 7 8 13 16 17 10 5 0 15 11)
Cost: 28580
第 66 世代
DNA: (14 18 4 1 9 6 2 12 19 3 7 8 13 17 16 10 5 0 15 11)
Cost: 27075
第 69 世代
DNA: (14 18 4 1 9 6 2 12 19 3 7 8 13 17 10 16 5 0 15 11)
Cost: 26202
第 157 世代
DNA: (14 18 4 1 9 6 2 12 19 3 7 8 13 17 10 0 5 16 15 11)
Cost: 25333
第 196 世代
DNA: (14 18 4 1 9 6 2 12 19 3 7 8 13 17 10 16 15 0 5 11)
Cost: 25181
第 221 世代
DNA: (14 18 7 8 9 6 2 12 19 3 4 1 13 17 10 0 5 16 15 11)
Cost: 24208
第 230 世代
DNA: (14 18 7 8 9 6 2 12 19 3 4 1 13 17 10 16 15 0 5 11)
Cost: 24056
第 252 世代
DNA: (14 18 7 6 9 8 2 12 19 3 4 1 13 17 10 0 5 16 15 11)
Cost: 23252
第 270 世代
DNA: (14 18 7 6 9 8 2 12 19 3 4 1 13 17 10 16 15 0 5 11)
Cost: 23100
第 296 世代
DNA: (14 18 7 6 9 8 2 12 19 3 4 13 1 17 10 16 15 0 5 11)
Cost: 22489
第 330 世代
DNA: (14 18 7 6 9 8 5 12 19 3 4 13 1 17 10 0 2 16 15 11)
Cost: 21722
第 455 世代
DNA: (14 18 7 6 9 8 5 12 19 3 4 13 17 1 0 10 2 16 15 11)
Cost: 21714
第 471 世代
DNA: (14 18 7 6 9 8 5 12 19 3 4 13 1 17 2 0 10 16 15 11)
Cost: 21236
第 525 世代
DNA: (14 18 7 6 9 8 5 0 19 3 4 13 1 17 12 2 10 16 15 11)
Cost: 21154
第 536 世代
DNA: (14 18 7 6 9 8 5 0 19 3 4 13 1 17 10 2 12 16 15 11)
Cost: 20924
第 572 世代
DNA: (14 18 7 6 9 0 5 8 19 3 4 13 1 17 10 2 12 16 15 11)
Cost: 20684
第 587 世代
DNA: (14 18 7 6 3 0 5 8 19 9 4 13 1 17 10 2 12 16 15 11)
Cost: 19013
第 608 世代
DNA: (14 18 7 6 3 0 5 8 9 19 4 13 1 17 10 2 12 16 15 11)
Cost: 17819
第 623 世代
DNA: (14 18 7 6 3 0 5 8 9 19 4 13 1 17 10 16 12 2 15 11)
Cost: 17577
第 642 世代
DNA: (14 18 7 6 3 0 5 8 9 19 13 4 1 17 10 16 12 2 15 11)
Cost: 16552
第 707 世代
DNA: (14 18 7 6 3 0 5 8 9 19 13 17 1 4 10 16 12 2 15 11)
Cost: 16548
第 731 世代
DNA: (14 18 7 6 3 0 5 8 9 19 4 13 17 1 12 2 10 16 15 11)
Cost: 14669
FINISH
となりました。一番最初はランダムですが最終的にその1/4程度になるのはすごい。 ちゃんと値が1対1で対応して交換されていて（交叉したものが残って、あとの世代で突然変異しているものもあります）、交叉、突然変異しているのが目に見て取れます。
すごいけどもしかして…
たしかにすごいけど、これってランダムで同じくらいの時間まわしたらもっといい結果を得られるんじゃ…？
ということで試してみました。気づいた方もおられると思いますが、ソースコードの(cond (< prob 0) ~となってる部分がランダムの確率の部分です（このままではランダムにはならない)。これを(< prob 1)に変更するとすべてランダムに次世代を生成します。
一世代は同じく100体で、遺伝的アルゴリズムと時間が同じくらいになるよう10000世代にしました。
こちらも何度か試し、最もよかった結果は以下のようになりました。
$ lein run
problem: (2138 1198 2667 8293 644 2644 9025 7551 2313 200 1176 501 1364 3016 525 4364 1576 6120 2672 4621 5656 6575 352 5682 6825 6858 1607 2881 3879 3760 424 2627 2055 7930 2642 97 4653 9971 2097 5441 4536 3917 710 195 405 7861 1482 5260 58 4534 5229 696 1711 1696 278 5341 4892 3356 9323 1288 4441 8054 9194 4144 4698 9673 7337 5133 6095 9610 3524 5142 3050 6517 6484 4033 319 1267 2949 751 4784 340 952 1083 1013 387 134 249 1874 368 9259 6963 9 5394 5200 4081 2004 8132 8228 8474 4734 9493 5628 9426 2566 197 9341 479 4821 8767 3667 4413 5249 9557 5846 4856 9110 6405 5826 848 8933 3772 1401 2623 6982 7329 1519 7881 1075 276 3602 7835 470 9977 414 1444 283 1931 8191 4425 6096 4485 589 6870 5281 8295 2284 9578 7887 9042 2033 4587 7949 623 7421 9818 5490 8671 2585 1229 640 1111 5785 8392 3857 3187 5869 1094 464 9391 5375 5128 3439 3601 3306 5301 5746 1784 2485 2367 2325 8722 4754 8540 2342 1308 2295 3124 4279 6214 4874 5791 6 8973 887 96 9121 4863 4767 3908 1518 9347 4525 6652 4397 7324 968 5432 9755 5909)
第 0 世代
DNA: [19 2 7 18 11 1 8 13 6 3 0 17 4 10 14 15 9 16 5 12]
Cost: 56356
第 1 世代
DNA: [15 1 4 19 3 2 16 9 14 18 13 17 12 0 10 6 7 5 8 11]
Cost: 49941
第 5 世代
DNA: [12 11 15 16 10 2 0 17 9 19 8 1 13 14 4 5 3 18 7 6]
Cost: 49602
第 16 世代
DNA: [14 9 6 2 7 3 4 19 8 11 15 0 5 12 17 1 18 13 16 10]
Cost: 38679
第 583 世代
DNA: [3 11 7 18 9 19 8 5 12 1 0 2 15 16 10 17 4 14 13 6]
Cost: 35524
第 6787 世代
DNA: [10 18 14 4 12 11 15 16 17 13 1 8 5 0 9 19 2 7 6 3]
Cost: 32775
FINISH
うそだろ…？時間かかる上に効果も得られない、と言う結果になりました。最初の半分以下のコストにもならないとは思わなかったです。遺伝的アルゴリズムすごい。
終わりに
突然変異をどうすればよいか調べると、現在の個体から選んで突然変異させたり、交叉でできた個体を突然変異させると書いてたり、よくわかりませんでした。なので、現在の個体から選び、要素を2つ選んで順番を交換させる方法を選びました。
わからないなりにも、遺伝的アルゴリズムのすごさが分かりよかったです。
