遺伝的アルゴリズムで組み合わせ最適化問題とお遊びする

最近まで高専でやってて，ちょっと大事だなと思ったので自分でアウトプットして理解促進につなげます．

遺伝的アルゴリズム(Genetic Algorithm)ってご存知ですか?

簡単に説明すると，機械にやって欲しい事を学習させるアルゴリズムみたいなものです．

詳しく説明するとこんな感じ↓↓

Genetic Algorithm(以降GA)とは，「生物は，交叉，突然変異，淘汰を繰り返しながら環境に適するように進化する」という理念の基，適合度を最適化問題の目的関数として設定することで，進化とともに目的関数を最大にする最適化問題の準最適解を求めるアルゴリズムを指す．
以下にGAの手順を示す．

(1)初期化 N個の個体からなる初期集団を生成する．そして，初期集団の適合度を計算する．通常遺伝子の値はランダムに設定する．

(2)生物集団の評価 目的関数があるしきい値より大きくなった場合や，世代交代回数が規定の回数を超えた場合などで評価を行う．評価基準を満たしていれば終了する．

(3)交叉 あるM個の親のペアを選択し，子個体を生成するプロセスである．子の生成方法は親ペアの染色体のある部分から遺伝子を交叉する1点交叉法やそれを拡張した多点交叉法がある．選択方法にはルーレット選択やエリート選択などが存在する．今回はこれらの説明は省略する．

(4)突然変異 ある与えられた突然変異率によって突然変異を起こす．突然変異には局所最適解からの脱出に効果がある．

(5) (3)と(4)のプロセスを個体数N個分繰り返して，再び(2)に戻る．

※自筆した文章より引用

で，こいつは結局何に使えるのって話なんですが，

Genetic Algorithm(以降GA)とは，「生物は，交叉，突然変異，淘汰を繰り返しながら環境に適するように進化する」という理念の基，適合度を最適化問題の目的関数として設定することで，進化とともに目的関数を最大にする最適化問題の準最適解を求めるアルゴリズムを指す． 

 ようするに，やりたい出来事のゴールを決めて，そのゴールに最も近くなるように学習させることが出来るということです．

例えば，有名なものにスーパーマリオブラザーズを学習させてみたというのがあります．

この場合の目的は時間内にゴールすることなので，これを目的関数として設定し，機械がゴールするように頑張ってあげるのが人間のすることです．

マリオの場合は，最初にランダムに行動するマリオを初期集団として100体とか1000体とか用意します．

その中で優秀なマリオ(今回の場合は，短い時間でよりゴールに近づいたマリオ)を基に，このマリオに近い子供マリオを数100体数1000体ほど作成し，その中でさらに優秀なマリオを選抜しry

といった作業をしていきます．

これを何回も繰り返す事で，機械が「どうするのが一番早くゴールできるのか」という内容を学習してくれます．

今回はこの遺伝的アルゴリズムで組み合わせ最適化問題の一つであるナップザック問題に適応する例を挙げたいと思います．

ナップザック問題とは，あるN個の価値，重量をもった品物を制限重量内で最も価値が大きくなるような組み合わせを探索する問題です．
これを遺伝的アルゴリズムで適用するためには，最も価値が高くなる品物の組み合わせを探すことを目的として，初期集団をランダムに生成し，初期集団の中で最も価値が高くなる品物の組み合わせを親として第2世代の子供集団を生成ry

といった感じで繰り返していきます．

今回は品物のデータ数を100で，各品物は適当に重量と価値を決定させて実験します．

このグラフは，横軸が世代数，縦軸が品物の価値になります．

POP100は，個体数100体，MUT001は突然変異率0.001%という意味です．*1

このグラフでは，個体数を100とし，突然変異率を0.001%とした際に最も価値の高い組み合わせを見つけられたということが分かります．

しかし，この場合はこの組み合わせがうまくいった一例であり，実際には初期集団の質や突然変異の起こる箇所などが原因で変化する事があります．

従って，この遺伝的アルゴリズムのミソは，比較的短い時間で準最適解を求められるということです．

参考までに，他のアルゴリズムと比較してみます．

1. 線形探索は，取りうる全てのパターンを探索するものです．全ての探索を行うので必ず最適解は求まるが，この実験ではパターンが多すぎ，測定する事ができませんでした．
2. ランダム探索は，ランダムに遺伝子列を決定し，ある評価関数の基準を満たすまで探索を行うものです．今回は35万以上で終了するように設定しました．ランダム探索では文字通り組み合わせのパターン決定がランダムであるため，比較的短い時間で価値の高い遺伝子列を発見する事ができるが，最適解は求まらず，良い値が求まるのもランダムという欠点があります．
3. 貪欲法とは，コストパフォーマンスの優れる順にソートし，最大重量になるまで上位から順に適用していくアルゴリズムです．最も速い速度で求まっているが，どの探索方法よりも価値は少ないのが分かります．
4. 動的計画法とは，対象となる問題を複数の部分問題に分割し，部分問題の計算結果を記録しながら解いていく手法である．このプログラムではメモ化再帰を用いた．これは最適解が求まり，かつ速度も優れている．しかし，部分問題ごとに分割してプログラムを考える必要があるので実装は困難です．

 この表からも分かるように，遺伝的アルゴリズムは比較的短い時間で準最適解を求める事ができます．

基本的には引用形式で記述した内容のものを，そのままプログラムとして書くだけで実装は出来ます．遺伝的アルゴリズムの問題は，目的関数を適切に決めることが難しいというところにあると思います．

動的計画法が早くて最適解が求められるので非常に強力な手法ですが，僕の頭では中々実装するのが難しいです．

動的計画法を教えてくれる優しい方々を募集しています．

*1:

突然変異率というのは，文字通り突然変異を起こす確率のことで，親世代から子世代を生成する際に活用します．

親世代とほとんど同じ遺伝子を受け取っても，親の遺伝子のみの進化には限界があります．

したがって，遺伝子を意図的にいじる事でより進化させようという意図が突然変異率には存在します．