きしだのはてな このページをアンテナに追加 RSSフィード

2016-02-07(日) 乱数のたのしい話と遺伝アルゴリズム

乱数のたのしい話と遺伝アルゴリズム 10:39 乱数のたのしい話と遺伝アルゴリズムを含むブックマーク

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

プログラマのための数学勉強会@福岡 #3 - connpass


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

乱数タノシイヨ


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


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

TSP with random


ぐちゃぐちゃですね。

f:id:nowokay:20160208095911p:image

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

1万5千回試行して、最短距離3602。


一方で遺伝アルゴリズム

TSP with GA

交配は1ヶ所を切り替えるだけで、淘汰は上位3位までは必ず残しつつあとは上位をランダムに選ぶ、という感じにしてます。


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

f:id:nowokay:20160208095912p:image

下部のグラフは、各世代の最長・平均・最短です。

50遺伝子を300世代。最短は2367。ランダムの3602よりもかなり良くなってます。


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


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

f:id:nowokay:20160208101829p:image

グラフを見ても、一旦定常状態になってから、つまり局所最適を求めてからさらに良い解をみつけれています。

突然変異1ヶ所のときは、3万世代までまわしても2330くらいにしかならなかったので、突然変異によって局所最適から抜け出せてるようです。


と、やっぱり自分の手でコード書いていろいろ試すと楽しいですね。

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


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


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

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

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


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

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

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


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


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

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

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

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


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

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

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