サルでもわかる遺伝的アルゴリズム
サルでもわかる遺伝的アルゴリズム
こんにちわ。numaです。
基本的な遺伝的アルゴリズムについてまとめたいと思いたちました。
サルでもわかるようにまとめるつもりですので、温かく読んでいただけると幸いです。
(ウキウキーーウキーーー)
サルでもわかるはそういうわけではないです、、笑
ご指摘や改善案、感想などは絶賛募集中です。(たたくのだけはやめてください笑)
遺伝的アルゴリズム(Genetic Algorithm:通称GA)
遺伝的アルゴリズムとは生物の進化から着想を得た人工知能です。これは1975年にミシガン大学のJohn Hollandが考案しました。
人工知能と言えば数年前から有名なDeepLearningや機械学習といったワードがが思い浮かぶと思います。DeepLearningは人間の脳を模倣したモデルですが、遺伝的アルゴリズムは生物の進化を模倣してその時の環境(評価関数)に対して最適な解(なるべく良い答え)を求めることが可能な手法です。
雑に言うと、たまたま良いものが出たら後世に伝えていこう、といったイメージです。
(伝われ！！！雑、、)
では、実際のアルゴリズムです。
基本的なアルゴリズム
①初期集団生成
プログラマが決めた集団数個の個体をランダムに生成します。
②評価
集団内のそれぞれの個体に評価値をつけます。
③選択
評価値の高い個体を選択します。
④交叉
選択された個体同士を交叉させて新たな個体を生みます。
⑤突然変異
ある一定の確率で突然変異を起こします。これは良い方向や悪い方向さまざまです。
⑥条件を満たしていれば終了、満たしていなければ②～⑤を繰り返す。
試行回数がプログラマが指定した回数に達していたり、最良の評価値が最適解に達したりしたら終了します。
(http://home.interlink.or.jp/~kumagai/genealg.htm から引用)
逆上がりを例にイメージしてみる
ここでは小難しい話や複雑な話は割愛します。実際とは多少異なることがあるかもしれないですがわかりやすさを重視するためご了承ください。逆上がりの習得を例に考えてみましょう。
①初期集団生成
わかりやすく言うと何百人の子供が鉄棒に初めて触れて坂上がりのやり方を知らずに1回やってみる感覚に近いと思います。
②評価
逆上がりを知っている教師がそれぞれの子供たちに決められたルールに従って点数をつけていく作業です。
③選択
点数の高い子供を選びます。
④交叉
本来は交叉させて新たな個体を生みますが、例が下手なため表現を変えます。
選択された子供が他の子供たちにどうやったら点数が上がったのか口頭で一回教えるイメージです。つまり子供たちがレベルアップしたのです。これで多少はより高い評価がもらえるかもしれません。
⑤突然変異
突然子供がコツを掴んだり感覚が狂ったりするイメージに近いですかね。
⑥終了条件判断
子供たちの逆上がりチャレンジ回数やきれいに成功した人がいたら終了です。満たしていなければ繰り返します。
これにより、何も知らない子供たちが先生の評価に従って最適な逆上がりを探索できました。
研究例
・スケジューリング問題
・巡回セールスマン問題
・実数値関数最適化
・ナップザック問題
等さまざまな複雑な問題に対して最適化の研究が行われています。
GAで生まれた実際の例
・新幹線N700系
詳しくはこちら https://plaza.rakuten.co.jp/sugowaza/diary/200707060000/
まとめ
GAはまるで自分でサンプルを生成して学習しているような挙動が興味深く感じてきませんか？そうでしょう。そうであってほしいです。
GAのイメージの手助けになっていると嬉しいです。また、ここで得られる最適解はいままでの最適解とは一味違った見たこともない結果が出てくる可能性があるので面白いですね。
参考資料
楽天ブログhttps://plaza.rakuten.co.jp/sugowaza/diary/200707060000/
Kumagai's PAGE~GAとは~ http://home.interlink.or.jp/~kumagai/genealg.htm
