遺伝的アルゴリズムをExcelに実装して最小値問題を解いてみた。
遺伝的アルゴリズムは交配や突然変異させながら最適値を探す
コンピュータで数値問題を解かせる処理方法をアルゴリズムといいます。
機械学習ではいろいろなアルゴリズムを使います。
アルゴリズムにはある程度数学の知識が必要で難解なものもあれば、簡単なものもあります。
勾配降下法はどちらかというと難解な部類に入るかな。
>> 【Excelでわかりやすく】勾配降下法で最小値が見つかる理由を視覚的に理解する
遺伝的アルゴリズムは簡単な部類に入ります。
微分積分や行列などの数学知識は不要です。
管理人は以前メーカーに勤めていた時、隣に遺伝的アルゴリズムを生産工程に適用する研究をしてた人がいました。
何かとても先進的なことをしているなと思っていたのですが、ある日やり方を聞いてみたらとても簡単で拍子抜けしたことを思い出します。
遺伝的というと、遺伝子とかDNAとか難しそうな感じがしますが、遺伝的アルゴリズムでいう遺伝とは進化のことです。
ダーウィンの進化論では生存競争と自然淘汰が進化の原動力であるとしていますね。
たまたま偶然良い遺伝子を持って生まれてきた種が生存競争で勝ち、負けた種は自然淘汰されます。
コロナウィルスも同じで、たまたま突然変異してできたデルタ株だけが生き残り、他は自然淘汰されつつあります。
これはウィルスが賢くて、人間の免疫を潜り抜けるように考えてカイゼンした結果ではありません。
ランダムに起こる突然変異で「たまたま」環境に適応できた種がデルタ株だっただけのことです。
遺伝的アルゴリズムの考え方も同じで、比較的良さそうな種をザックリ選んで、後はそれをランダムに交配させたり、ランダムに突然変異させたりして、もっと良い種ができたかどうかを判定します。
後は、それを何回も繰り返して最強の種に育て上げるのです。
遺伝的アルゴリズムで最小値問題を解く計算方法
初期値を複数テキトーに選ぶ
面白そうだと思いませんか？
実際にどのようにやるのかを、関数の最小値を求める問題で見てみましょう。
次のような関数を想定します。
グラフに描くと、このような複雑な形状になります。
この関数の最小値は、グラフを見れば分かるように-50くらいで、その時のxの値は1くらいです。
勾配降下法でもそうでしたが、まずは初期値を1点テキトーに決めて、アルゴリズムに則って動かしながらこれ以上動かない点（収束点）が見つかるまで繰り返します。
違いは、遺伝的アルゴリズムでは初期値を複数点選ぶことです。
そうしないと、交配できませんからね。
二進法を使う
あと、ここでもう一工夫します。
xの値を二進法で表すのです。
私たちが日頃使っている数字は十進法です。
何気に使っているので意識はしませんが、1桁は0から9までで、それ以上は桁を一つ繰り上げます。
二進法も同じで、1桁は0と1だけ、2を表したい時は桁を一つ繰り上げて10のように表します。
1桁が0か1しか取れませんので、目まぐるしく桁が繰り上がります。
例えば、3は11、4は100、5は101、6は110のようにどんどん桁が増えていきます。
このように二進法で表すことにより、DNAを表す数字の羅列のようになり交配や突然変異がやり易いのです。
初期値は何でも良いのですが、x=30、25、10、5としてみます。
これを二進法で表すと、それぞれ11110、11001、01010、00101になります。
優秀な種を選択する
まずはこの中から比較的優秀そうな種を2つ選びましょう。
優秀かどうかの判断は、それぞれのxに対応するf(x)の値で見ればよいでしょう。
xが30の場合は、
f(30)=302+30+50sin(5√30)=969
同様に計算すると、f(25)=643、f(10)=105、f(5)=-19となります。
f(x)の最小値を見つけたいので、x=10、5の2つが優秀な種になります。
交配させる
次にこの2つの種を交配させます。
二進法で表すとx=01010、00101ですから、交配させたら5桁のうちの最初の3桁と最後の2桁の子供が生まれるとしましょう。
これで最初の種11110、11001、01010、00101が01010、00101、01001、00110に置き換わりました。
01010と00101は次世代では生き残れず淘汰されます。
残酷ですが、これが自然の摂理です。
突然変異させる
次に残った4種の中で1種だけ突然変異が起きます。
これはDNAの複製ミスでたまたま起こる出来事なので、どれに起こるかは全く予想がつきません。
ですので、4つの中からランダムに選ぶことにします。
これはExcel関数を使って
=ROUNDUP(RAND()*4,0)
のようにして選べば良いでしょう。
>> エクセルを使って正規分布の【疑似乱数】を生成する方法を具体例で実演！
ランダムに選んだ結果、00101が選ばれたとしましょう。
この5つの数字の中の1つだけを、突然変異ということで逆の数字に変えます。
0ならば1に、1ならば0に変えます。
何番目の数字が変わるかも偶然起こる出来事なので、全く予想がつきません。
ですので、これもエクセル関数で1から5の乱数を発生させます。
例えばエクセル関数からの乱数が3となった場合、3番目の数字は1ですので0に変えます。
これにより、次の世代は01010、00001、01001、00110になります。
これで第一世代から第三世代にまで進化しました。
まとめると次のようになります。
収束するまで選択⇒交配⇒突然変異を繰り返す
第三世代の数字を十進法で表すと10、1、9、6になります。
これらに対応するf(x)を計算するとf(10)=105、f(1)=-46、f(9)=123、f(6)=26になりますので、最初のステップに戻ってまた優秀な2つの種を選びます。
この場合、関数値が小さいのはf(1)=-46とf(6)=26ですので、1と6が選択されます。
そして交配⇒突然変異⇒選択⇒交配⇒突然変異⇒選択、、、というように4つの数字のうち3つの数字が変わらなくなるまで繰り返します。
なぜ3つかというと、4つの数字のうち1つは突然変異でいつも変わるからです。
3つの数字が変わらなくなれば、収束したと見なすことができます。
遺伝的アルゴリズムをExcelに実装する
このアルゴリズムをExcelに実装すると次のように書けます。
このシートで第一世代から第三代世代までが計算できます。
あとは、第三世代の数字を第一世代にコピペして同じように繰り返します。
そして第三世代の4つの関数値のうち3つが10回連続で変わらなければ収束したと見なして終了です。
この繰り返しと収束判定は、次のようなマクロを組むことでできます。
実際にマクロを実行してみると、次のように16回繰り返したところで収束しました。
初期値をいろいろ変えてやってみても、早かれ遅かれ同じ値に収束します。
突然変異のところで乱数を発生させているので、毎回違う突然変異が発生しますが、最終的には同じ値に収束します。
これは、地球の歴史をもう一度始めからやり直したとしても、やはり私たち人間が支配しているだろうと言われることと同じです。
途中の交配や突然変異は違うパターンになったとしても、それらはランダムに起こるため、何億世代も繰り返せば同じ結果に収束するのです。
ちなみに遺伝的アルゴリズムでは交配というと生々しいので、交叉といいます。