はじめに
前回、キリンを例に遺伝的アルゴリズムを見てみました。
今回はOneMax問題という簡単な数学的問題を例に見ることで、プログラムに寄せた観点から説明しようと思います。
OneMax問題とは
まずはOneMax問題とは何かについて説明します。非常に簡単なので敬遠しないでください😄
OneMax問題とは、例えば10個の0と1の数字からなる、[1, 0, 1, 0, 0, 1, 1, 1, 0, 1]の様な数列の和を最大化するにはどうすればいいかという問題です。
人間からするとあまりに簡単ですよね。全部を1にして[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]となればこの数列の和は最大になります。
この超簡単な問題を敢えて遺伝的アルゴリズムを使って解いてみようというのがこの記事の主旨です。
#vOneMax問題を遺伝的アルゴリズムで解く流れ
前回の記事「キリンを例に遺伝的アルゴリズムを見る」と同じ流れで説明していきますので適宜見比べてみてください。
① 個体集団の作成
まずは個体集団を作ります。
ランダムに0と1を持つ配列をたくさん作成します。
本当はもっとたくさん作りますが、今回は説明の都合上6個としましょう。
② 個体の評価
それぞれの個体を評価して点数をつけます。
今回の評価ポイントは数列の合計ですので、それぞれの数列の合計を算出した値を点数とします。例えば、[0, 0, 0, 1, 0, 0, 0, 0, 0, 1]の点数は2点です。
③ 個体の選択
評価の高いものを次の世代へ受け継ぐために残します。
④ 交叉
③で選択された個体から子供を作ります。
2つの個体をある場所で2つに分け、それらの後半同士を交換します。
分ける場所はランダムに選びます。
最初に6個の個体を作ったので同じく6個の個体を作ります。
一部の個体に関しては敢えて交叉させずに③で選択された個体をそのまま残すのもありです。
交叉によってできたのがこちら
⑤ 突然変異
進化の多様性を保つために一部の個体に対して突然変異を起こします。
突然変異が起きる場所も変異後の値もランダムです。
これで次の世代の個体集団ができました。
最初に比べて1が多くなっているのがわかると思います。↓
⑥ ②〜⑤を繰り返す
新しくできた個体集団に②から⑤までを繰り返し行います。
もう一度②から⑤をやるとこんな感じになります。↓（ランダム要素が多いためあくまでもイメージです。）
最初の個体集団と比べてだんだん1が多くなってきましたね。
あと10世代も繰り返せばこんな感じになるんじゃないでしょうか。↓
こうするとほとんどの個体が10点や9点となり、これ以上点数が上がることがなくなります。
そして最後の世代で最も良い個体を最適解として導き出します。
こうして[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]が答えとなるんですね。
まとめ
人間からしたら「いや全部1にすればいいやん」て話なんですが、敢えて遺伝的アルゴリズムを使って解くとこの様な流れになります。
遺伝的アルゴリズムのすごいところは、これと同じ手順を踏むだけで人間には到底計算できない様な問題も答えが出せてしまうところです。
実装が簡単というところが遺伝的アルゴリズムの最大のメリットと言えます。