乱数のたのしい話と遺伝アルゴリズム

金曜日の「プログラマのための数学勉強会＠福岡」で乱数の話をしてきました。
プログラマのための数学勉強会@福岡 #3 - connpass

で、乱数の生成だとか、クイックソートや素数判定などの乱択アルゴリズムの話とかをしました。
乱数タノシイヨ

乱数のたのしい話 from なおき きしだ

その中で、遺伝アルゴリズムで巡回セールスマン問題(TSP)を解くというのをやってみました。遺伝アルゴリズム、すいぶん昔から名前は知ってて、どういうアルゴリズムかも知ってて、実装もそんな難しくないと知りつつ、書く機会がありませんでした。なので、この機会に書いてみようと。

とりあえず最初に完全にランダムでTSPを解いてみます。
TSP with random

ぐちゃぐちゃですね。

下部のグラフはその時点での最短距離。最初に距離が短いものをみつけていくけどだんだんみつかりにくくなる、という感じになっています。
1万5千回試行して、最短距離3602。

一方で遺伝アルゴリズム。
TSP with GA
交配は１ヶ所を切り替えるだけで、淘汰は上位３位までは必ず残しつつあとは上位をランダムに選ぶ、という感じにしてます。

だいぶスッキリした経路をみつけています。

下部のグラフは、各世代の最長・平均・最短です。
50遺伝子を300世代。最短は2367。ランダムの3602よりもかなり良くなってます。

で、一部をランダムに変える突然変異は、１ヶ所だけにしてるんですけど、多くしたらどうなるかと思って２ヶ所にすると2886に。ちょっと悪くなりました。かといって突然変異なしだと3307。ランダムにやるのとあまり変わらない。

と書いてて、突然変異をふやしつつ試行回数増やしたらどうなるだろう？と、突然変異を３ヶ所にして試行回数を100倍して3万にしたら、1889まで最適化されました。ランダムの半分近くまで。

グラフを見ても、一旦定常状態になってから、つまり局所最適を求めてからさらに良い解をみつけれています。
突然変異１ヶ所のときは、３万世代までまわしても2330くらいにしかならなかったので、突然変異によって局所最適から抜け出せてるようです。

と、やっぱり自分の手でコード書いていろいろ試すと楽しいですね。
あと、遺伝アルゴリズムのコード自体は2時間くらいで書けたのだけど、こんな感じで、一度コード書いたあとの数値の調整にすごく時間がかかります。楽しい。

機械学習もそうなんですけど、乱数を使うコードは調整点が多くて、それによって結果が大きくかわることが多いので、コードを書くだけじゃなくその後の調整でも楽しめて２度おいしい。

乱数を使うアルゴリズムについては、とりあえず数学ガールが入り口。

数学ガール/乱択アルゴリズム (数学ガールシリーズ 4)

あと、アルゴリズム・サイエンス・シリーズの乱択アルゴリズム。

乱択アルゴリズム (アルゴリズム・サイエンス・シリーズ―数理技法編)

そもそもなんで乱数使うかというと、計算が難しい問題に対処するためなので、その一般的な話。

計算困難問題に対するアルゴリズム理論 (組合せ最適化・ランタ゛マイセ゛ーション・近似・ヒューリスティクス)

遺伝アルゴリズムは古いけどこの本。つまりずっと本だけ持ってた。

遺伝的アルゴリズムの基礎―GAの謎を解く

いまはもっといい本があるのかも。

で、この著者の人、最近おもしろそうな本を出してる。見てみよう。

進化計算と深層学習 -創発する知能―