RubyでGAを書く
GAは，ゴリラアルゴリズムの略で確率的最適化手法の一種だ．
ゴリラの群れの動きを模倣して，複雑な解空間から最適解を探索する．
嘘だけど．
遺伝的アルゴリズム（いでんてきアルゴリズム、英語：genetic algorithm、略称：GA）とは、1975年にミシガン大学のジョン・H・ホランド（John Henry Holland）によって提案された近似解を探索するメタヒューリスティックアルゴリズムである。人工生命同様、偶然の要素でコンピューターの制御を左右する。4つの主要な進化的アルゴリズムの一つであり、その中でも最も一般的に使用されている。
よく端的に，生命進化を模倣した確率的な解探索のアルゴリズムと説明するけど，最近の遺伝的アルゴリズムは生命進化なんてどうでもいい方向に向かっている．*1
あくまでも着想が生命進化にあるというだけという認識が一番だと思う．
詳しい説明は，ほかのサイトに譲るけど，GAには多種多様なアルゴリズムがあるので変なサイト見て覚えると変なことになるよ．*2
それで，この前Rubyを試してみたので，せっかくだからRubyで単純GAとよばれるアルゴリズムを実装してみることにした．
Rubyの材料になった
— ゆえまし/Motoki Tano (@yuemashi) 2016年7月4日
取り組むのはOne max問題と呼ばれるもので，最も単純な問題のひとつ．
The OneMax Problem [SE91] (or BitCounting) is a simple problem consisting in maximizing the number of ones of a bitstring.
Formally, this problem can be described as finding a string
, with
, that maximizes the following equation:
端的に言うとバイナリ列を持った個体について，その1の数を最大化する問題のこと．
最適解は x = [ 1, 1, 1, ... , 1] という個体になる．
解がわかりやすいし，試しに組んでみるときによく使うよ．
gistfb112e75a3bdd8068da09896c47c18e8
この問題を定式化するとこんな感じになった．
GenotypeはGAでいうところの遺伝子型．生物学でも遺伝子型と表現型というけどそれと同じ．個体そのものを指す．
Populationは複数の個体を含んだ集団，言い換えると遺伝子型が示す解候補の集団のこと．ゴリラでいうところのゴリラの群れ．*3
fitnessは個体の適応度を計算する．統計学では適合度 goodnessだけど，これは適応度 fitness．本来は生物学の用語で，生物個体が環境にどれだけ適応しているかを示す値．GAでは，適応度の高い個体がより子孫を残すと仮定して計算する．*4
OneMax問題では1の数だけど，問題が複雑になると適応度も複雑になっていく．
gistb1d7b6ee2a71281deb2853af81bb58b6
GAは，交叉・突然変異・選択というオペレータを使って計算を進める．
交叉は任意の個体を二つ選択して，それぞれの遺伝子を混ぜて，新しい個体を生成するオペレータ．生物学における交叉と同じように見えるけど，生物の交叉は遺伝子修復に端を発しているのに対して，これにはそういった機能はない．
今回は一点交叉．交差点は一点で，リストを真っ二つにして再度つなげるだけ．
突然変異は読んで字のごとく，遺伝子型をランダムに変更する．
いままでの二つのオペレータは，分子生物学の仕組みをもとにしてるけど，次の選択は集団生物学（集団遺伝学）の自然選択説をもとにしている．*5
単純に言うと，適合度が高い個体を優先的に次世代に保存し，低い個体を淘汰していく仕組み．適合度が低い個体を除き，適合度が高い個体が増えていくように圧力をかけていく．
gistb5908a1ded4949709d7ae55c412fba88
あとはこの一連のオペレーションを経て，集団を更新するだけ．
このアルゴリズムも世代交代アルゴリズムといって，GAによってはいろいろ工夫がある．nextPopが次世代の集団を示している．
eliteは現世代で一番適応度の高い個体で，これは無条件で次世代に引き継ぐ．エリート保存戦略っていう．
重要なのは結果．
gist0f70a09ef570809254e2be55eb69386b
遺伝子型の長さは50，集団のサイズは100で挑戦．
打ち切り世代数は100なので，100世代集団を更新して最終世代で最も高い適応度の遺伝子型を出力してみた．
全体を見てみると，こんな感じ．
どうせだから関数型プログラミングで書いてみたよ．*6
giste73ac06a2e3ab37dd3d0c126c49ea376
ｸﾞｯ(๑•̀ㅂ•́)و✧
— ゆえまし/Motoki Tano (@yuemashi) 2016年7月3日
