遺伝的アルゴリズムで最適化できるもの
実用的な時間で厳密解を求めるのが難しいような問題によく使われる手法として、遺伝的アルゴリズムというものがある。
遺伝的アルゴリズム（いでんてき-、Genetic Algorithm、GA）とは、1975年にミシガン大学のジョン・H・ホランド（John Henry Holland）によって提案された近似解を探索するメタヒューリスティックアルゴリズムである。人工生命同様、偶然の要素でコンピューターの制御を左右する。
（中略）
遺伝的アルゴリズムはデータ（解の候補）を遺伝子で表現した「個体」を複数用意し、適応度の高い個体を優先的に選択して交叉（組み換え）・突然変異などの操作を繰り返しながら解を探索する。適応度は適応度関数によって与えられる。
学習理論などをやってるうちの研究室でも馴染みはあり、群衛星のパラメータ最適化に使った論文を出した人もいる。つい先日には、「衛星運用する人が増えてシフト割り当ての最適解が計算しづらくなってきたのでGA使うよ」「いいねー」みたいなノリで研究室のシステムにGAをさっくり組み込んだ。
GAの流れを以下に簡単に示す。
-神は最初になんとかかんとか
まず問題の答えをランダムに沢山作り（第一世代）、それらを何らかの評価関数で評価する。たとえば参加者の希望日を集計してシフトを割り当てる例であれば、各人の第一希望が通れば100点、第二希望なら80点、希望外に割り当てられたら0点などとし、全員の点数を合計した値を評価する。この評価方法だと、当然点数が高いような解ほど「良い解（＝遺伝子）」と言える。
-子作り（※ただしイケメンに限る）
そして、これら第一世代の遺伝子どうしを「交叉」、つまりうまいことミックスさせてやることで、次の世代の解集団を作る。このときに優秀な遺伝子から重点的に子供を作るようなバイアスをかけてやることが大事である。評価値に比例した確率で親になれる（ルーレット戦略）だとか、評価順位に基づいて一定の数の子供を作る（ランキング戦略）とかいった方法がよく使われる。悲しいことに、アルゴリズムの中でもモテるやつとモテないやつがいるらしい。しょっぱい。
-進化
そんでその子供たちも評価にかけられ、交叉され、次の世代をつくる。そうやって何世代も何世代も交叉を繰り返すことで、だんだんと「優秀な遺伝子」持ちの奴が増えてくる。これを収束するまで眺めていると、いつの間にか最適解に近いものが勝手に生み出されているという寸法である。進化論バンザイ！
-井の中の蛙、イケメンを知らず
ところが、これには一つ落とし穴がある。それは遺伝子が最適に程遠い解に陥りやすいことである。交叉のコーディングにも依存するが、基本的に子供は親と似た方向性を持っている。複数の局所最適解をもつような問題設定の場合、親が一たびある解の周辺に固まるや否や、そこから永久に抜け出せなくなる。これは収束値の初期値依存性と言い換えることもできる。たとえば第一世代の親が全員同じ遺伝子持ちだったとすれば、GAはそれ以外の答えを生み出せなくなってしまう。
また別の例だけども、「俺達100人で手分けしてかわいい子をさがすぜ！」「「「おー！！」」」みたいな人たちが居たとして、彼らが出発地として東京を選ぶのか、大阪を選ぶのか、はたまたニューヨークを選ぶのかで得られる答えは全く違ったものになってしまうだろう。
-もう一つの鍵
そこで、今一度生物にインスパイアを得る。それが「突然変異」である。たとえば遺伝子の2か所を組み替えるとか、1か所を反転させるとか、1個ずつずらすだとか、様々な手法で局所解を脱出した奴を紛れ込ませる。突然変異は頻繁に起こると単なるランダム探索になるので、一般に非常に低い確率で起こるようにしておく。さっきの例でいえば東京周辺に固まった100人のうち数人を、日本全国にワープさせるわけである。ワープ先が芳しくない感じであれば飛ばされた奴はまた東京に戻るだろうし、「こっち来てみろよ、かわいい子ばっかりだって」「え、マジで」となれば、何人かがそちらに移動するかもしれない。
GAの鍵を握るのは「交叉」と「突然変異」のバランスである。これをうまく取ってやることで、総当たりでは難しい問題に対して、いとも簡単によい答えをはじき出してくれる。だからといってGAが万能なわけではなく、GAが得意としているような問題のジャンルは限られる。その特徴を2つだけ挙げると、
1.最適解じゃなくてもいい
GAで得られた結論は、必ずしも最適解である保証はない。最適解から少しでも外れるとアウトなケースではGAを適用できない。
2.まじめに解こうとしても解けない
シフト問題のようなN個の順列並べ替えで全部のケースを調べ上げるとすると、必要な計算量はNの階乗に比例する。Nが大きくなれば莫大な時間が要するようになり、現実的にはGAのような妥協手段を求めることになる。逆に、実用的な時間内に厳密解が求められる手立てがあるのであれば、GAの出番はまったくない。
で、これが良く当て嵌まる問題って何だろなーとぼんやり考えていると、一つ思い当たるものがあった。
人生、だ。
唯一最適の解があるわけじゃないし、取りうる選択肢をぜんぶ試すような時間もない。
まさにGAを使うのにうってつけじゃないか。
-大事なのはパラメータ
GAでいい答えを出すためには、「交叉」と「突然変異」のバランスがとても大事になる。交叉に比重を置きすぎると、最適と程遠い地点に収束するリスクが増える。かといって突然変異ばかりやっていると、いつまで経っても解が収束しない。これも人生に変換するとちょっと面白い。一つのことばかりに集中すると、運が悪ければとてもつまらない地点に収まってしまうし、あまりに色んなことに手を出しすぎると、何も手にすることができずに時間切れを起こす。適量というものがあるらしい。
厄介なのは、交叉と突然変異の最適なパラメータというものが、解く問題によって異なってくるということである。ただ、一般的な問題に対しては突然変異が1％前後に置かれる場合が多いようである。
-日常に1％の変異を
自分の人生を省みると、これまで一直線に交叉を繰り返してきたように思う。今日できることを組み合わせて、明日やることを決める。その結果宇宙をやるために大学を決めて、学科を決めて、大学院入学を決めて、とまっすぐな道を進んでいる。そして、博士への進学を視野の片隅に捉えつつある。今のところこの選択に後悔は全く無いし、それほど悪い解に収束しているようにも見えない。ただ、あまりに突然変異のようなものを取り入れない人生を送ってきているような気がすることが少し気がかりに思えてくる。胸を貼って、「これが最適解なんだ」と言えるために、幾つかの突然変異を、取り入れてみたいと思う。
目の前でGAが収束していく様を眺めながら、そんなことを考えた。
