2016-02-07(日) 乱数のたのしい話と遺伝アルゴリズム
■乱数のたのしい話と遺伝アルゴリズム 
金曜日の「プログラマのための数学勉強会＠福岡」で乱数の話をしてきました。
プログラマのための数学勉強会@福岡 #3 - connpass
で、乱数の生成だとか、クイックソートや素数判定などの乱択アルゴリズムの話とかをしました。
乱数タノシイヨ
で、その中で、遺伝アルゴリズムで巡回セールスマン問題(TSP)を解くというのをやってみました。遺伝アルゴリズム、すいぶん昔から名前は知ってて、どういうアルゴリズムかも知ってて、実装もそんな難しくないと知りつつ、書く機会がありませんでした。なので、この機会に書いてみようと。
で、とりあえず最初に完全にランダムでTSPを解いてみます。
ぐちゃぐちゃですね。
下部のグラフはその時点での最短距離。最初に距離が短いものをみつけていくけどだんだんみつかりにくくなる、という感じになっています。
1万5千回試行して、最短距離3602。
一方で遺伝アルゴリズム。
交配は１ヶ所を切り替えるだけで、淘汰は上位３位までは必ず残しつつあとは上位をランダムに選ぶ、という感じにしてます。
だいぶスッキリした経路をみつけています。
下部のグラフは、各世代の最長・平均・最短です。
50遺伝子を300世代。最短は2367。ランダムの3602よりもかなり良くなってます。
で、一部をランダムに変える突然変異は、１ヶ所だけにしてるんですけど、多くしたらどうなるかと思って２ヶ所にすると2886に。ちょっと悪くなりました。かといって突然変異なしだと3307。ランダムにやるのとあまり変わらない。
と書いてて、突然変異をふやしつつ試行回数増やしたらどうなるだろう？と、突然変異を３ヶ所にして試行回数を100倍して3万にしたら、1889まで最適化されました。ランダムの半分近くまで。
グラフを見ても、一旦定常状態になってから、つまり局所最適を求めてからさらに良い解をみつけれています。
突然変異１ヶ所のときは、３万世代までまわしても2330くらいにしかならなかったので、突然変異によって局所最適から抜け出せてるようです。
と、やっぱり自分の手でコード書いていろいろ試すと楽しいですね。
あと、遺伝アルゴリズムのコード自体は2時間くらいで書けたのだけど、こんな感じで、一度コード書いたあとの数値の調整にすごく時間がかかります。楽しい。
機械学習もそうなんですけど、乱数を使うコードは調整点が多くて、それによって結果が大きくかわることが多いので、コードを書くだけじゃなくその後の調整でも楽しめて２度おいしい。
乱数を使うアルゴリズムについては、とりあえず数学ガールが入り口。
- 作者: 結城浩
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2011/03/02
- メディア: 単行本
- 購入: 19人 クリック: 779回
- この商品を含むブログ (102件) を見る
あと、アルゴリズム・サイエンス・シリーズの乱択アルゴリズム。
乱択アルゴリズム (アルゴリズム・サイエンス・シリーズ―数理技法編)
- 作者: 玉木久夫
- 出版社/メーカー: 共立出版
- 発売日: 2008/08/08
- メディア: ハードカバー
- 購入: 4人 クリック: 52回
- この商品を含むブログ (8件) を見る
そもそもなんで乱数使うかというと、計算が難しい問題に対処するためなので、その一般的な話。
計算困難問題に対するアルゴリズム理論 (組合せ最適化・ランタ゛マイセ゛ーション・近似・ヒューリスティクス)
- 作者: J.ホロムコヴィッチ,和田幸一,増澤利光,元木光雄
- 出版社/メーカー: 丸善出版
- 発売日: 2012/02/29
- メディア: 単行本
- クリック: 1回
- この商品を含むブログ (3件) を見る
遺伝アルゴリズムは古いけどこの本。つまりずっと本だけ持ってた。
- 作者: 伊庭斉志
- 出版社/メーカー: オーム社
- 発売日: 1994/09
- メディア: 単行本
- 購入: 1人 クリック: 7回
- この商品を含むブログ (4件) を見る
いまはもっといい本があるのかも。
で、この著者の人、最近おもしろそうな本を出してる。見てみよう。
- 作者: 伊庭斉志
- 出版社/メーカー: オーム社
- 発売日: 2015/10/21
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (2件) を見る