遺伝的アルゴリズム

遺伝的アルゴリズムとは、生物群が環境へ適応するときの遺伝学的変化の諸概念（染色体の交叉・突然変異・自然淘汰）を問題解決方法に見立ててその解を探る手法である。英語ではGenetic Algorithm（略語でGA）。

概要

問題の解の候補を生物の各個体の遺伝子に見立て、ランダムに生成した各個体の遺伝子を交換や突然変異により解にふさわしい遺伝子を持つ個体を生み出すように処理を進めていく。各個体が環境にどの程度適応しているかを算出し、遺伝子の適応度が高い個体は子孫を残しやすく、適応度が低い個体は子孫を残しにくくすることから遺伝的アルゴリズムと呼ばれる。

厳密解よりも適度に厳密解に近いものを最適解として探索するアルゴリズムの1つである。問題の解を求めるのに通常の全検索手法では非現実的に長時間を要する問題、あるいは極度に煩雑な手続きを必要とする問題に対して用いられる。

分かりやすい例

1. 少年少女を100人ずつ用意します。
2. 一生懸命歌っていただきます。
3. 歌の上手い上位5人ずつを残して残りは抹殺します。
4. 互いに交配して彼らの子供を男女100人ずつ用意します。
5. 2〜4を何回も繰り返します。
6. どっかで停止し、その時一番うまかった一組を残して抹殺します。
7. 残った2人が鏡音リン・レンです。
8. なんだってー！？

- 本掲示板>>3より

具体的にやってみよう

遺伝的アルゴリズムでは、冒頭にもあるように生命の進化の概念によって問題の最適化を行っている。
以下では、問題が与えられてからこれを遺伝的アルゴリズムによって解くまでのごく単純な流れを解説する。

問題設定

ここでは、単純な例として

「a*(10-a)*b*(10-b)*c*(10-c)を最大にするa,b,cの組（a,b,cは0以上10未満の整数）を求める」

というものを考えてみる。この程度の問題であれば総当たりでもコンピュータを使えば一瞬で解けるが、変数の種類や値の範囲が増えていくとかかる時間が爆発的に増えていくため、遺伝的アルゴリズムほかいろいろな手法が必要となってくるのである。

「遺伝子」による記述

遺伝的アルゴリズムでは、変数を遺伝子として記述する。その方法は問題によってさまざまなものがあり、記述の仕方を変えることで問題が解きやすくも解きにくくもなったりする。

今回の問題では変数が3つなので、3つのハコからなる遺伝子を考えるのが簡単だろう。例えばa=1, b=2, c=5なら

1

2

5

といったように、数字の入ったハコの列を考えることにする。

初期状態としては、ランダムに数字の入ったハコ列がたくさん用意されている。生物っぽく言えば多様な「個体」がたくさんいるような状態になっている。とりあえず例として、上の1体と下の9体の計10体がいるとする。

0

3

8

1

9

6

5

2

5

4

0

7

7

0

5

1

3

3

6

4

4

7

5

8

6

5

8

遺伝的操作

これ以降の操作は、やり方によって順番が違ったり細かい設定があったりするが、とりあえずそれぞれを簡単に説明をしていく。

自然淘汰

それぞれの個体について、「適応度」を計算する。適応度とは、与えられた問題に対してどの程度有能な個体であるかという指標であり、今回の例で言えば、実際に「a*(10-a)*b*(10-b)*c*(10-c)」をそれぞれ計算してみた結果が「適応度」ということになる。

適応度が高い個体の遺伝子は、次の世代で生き残る可能性が高い。そんなわけで、上記10個体の中から次の世代で生き残る個体を計算すると、以下の人たちが残る（とりあえずここでは5個体を残すということにした）。他の人たちは自然の力で抹殺されました。

5

2

5

1

3

3

6

4

4

7

5

8

6

5

8

ここで、生き残る個体を決定するための手法について、代表的なものに絞って解説する。

エリート選択

かっこいい名前がついているが、やっていることは単純に「適応度が高い順にn個生き残らせる」というもの。実装が簡単な上、結果の収束が早いのが利点。その代わり、遺伝子の多様性が失われやすいため、後述のローカルミニマム・ローカルマキシマムに陥りやすくなってしまう。遺伝的アルゴリズムの成功のためには、ダメな子の存在が不可欠なのである。

これ単品ではあまり役に立たないが、後述の手法と上手く組み合わせて使うことで、解を求める速度を上げることができる。

ルーレット選択

割とよく使われる選択手法。東京フレンドパークのルーレットのようなものを用意し、適応度の高い個体には広い面積、適応度の低い個体には狭い面積を割り当てる。そしてこのルーレットにダーツをn本投げて、当たった個体が生き残る(選択済みの個体が選ばれたらやり直し)という手法。

収束の速度はエリート選択に比べて落ちる。しかし適応度の低い個体にも生き残りの目があるため、ローカルミニマムなどには陥りにくい。

この選択手法では必然的に乱数を多く用いるため、個体数が多い場合や世代数を重ねる場合には、使っている環境の乱数生成方法にも気を配るとよい。もし線形合同法などのあまり素性のよくない方法を採用している場合は、メルセンヌツイスターやXORShiftなどのある程度きちんとした手法を導入しよう。

トーナメント選択

名前の通り、各個体同士でトーナメント戦を行い、上位n個が生き残るという手法。トーナメント表によっては適応度が低めの個体でも生き残るため、これもエリート選択よりはいい結果を出しやすい。また、本当にどうしようもなくダメな子は生き残らないため、収束率もそれほど悪くない。

交叉

個体同士が遺伝子の交わりによって新しい個体を生み出す操作。とりあえずオスとかメスとかはあまり気にしないことになっている。ｱｯｰ!

例えば上の5体の中で、左から1番目と2番目が交わることを考える。3か所のハコについて、どちらの数字を使うかというのは、ランダムだったりちょっとしたテクニックを使ったりとやり方によってさまざまである。例えばこの交叉によって、下のように新たな個体が生まれる。

5 2 5

×

1 3 3

→

5 3 5

また、競走馬などで能力の高い優秀な個体は交配の人気が高かったりするように、適応度の高い遺伝子が交叉に使われやすくするというようなテクニックもあったりする。

突然変異

ある個体の遺伝子の一部がいきなり変わること。交叉だけでは親となる個体の性質しか伝わらないために、場合によってはあまり適応度が高くないのに同じような個体ばかりが生き残って、それ以降の適応度の向上が見られなくなってしまったりするので、突然変異によるランダムな変化が重要となることがある。

ただしその確率があまり高くなると、交叉によって優秀な遺伝子を残していくという遺伝的アルゴリズムの本質から外れたただのランダムサーチになってしまうため、突然変異の確率については工夫が必要である。

例えば、上で生き残っていた5個体の一番右の個体の遺伝子が以下のように突然変異してみたりする。

6 5 8

→

1 5 8

繰り返し、そして終焉

上記の遺伝的操作をぐるぐると繰り返していくにつれて、適応度の高い人たちが多く残っていくようになる。

そして、ある程度進めていくと「a=5, b=5, c=5」という個体が最も適応度の高いものとして現れ、それがずっと生き残っていくこととなる（はずである）。突然変異により多少ぶれることがあっても、個体群が全体的にこの最適解に近い遺伝子を持っている（はずな）ので、もう少し世代を進めていけばまた同じ遺伝子が現れてくる。そうやって、今回の問題の答えがこの個体の表す数値である、と結論付けることになる。

---

総じて遺伝的アルゴリズムは「いいものといいものを掛け合わせればいいものが出来る」という信念に基づく手法であり、決定論的なものではないので「絶対に最適なものが求められる」という確証が得られたものではない。しかし冒頭にもあるように、「最適に近い解を求める」ための手法としては、やり方が簡単であり比較的それっぽい結果も得られるということから、比較的有用なものだということは出来るだろう。

利点と欠点

利点

• 複雑な問題でもそれなりの時間でそれっぽい結果を得ることができる。

欠点

• 偶然見つけられた場合を除いて、厳密な解が得られない。
• 単純な総当りよりもアルゴリズムが複雑になる。
• 「どのくらい個体を生き残らせるか」「どのくらい突然変異を起こすか」「初期個体の遺伝子をどのように設定するか」等、問題とは直接関係ないパラメータの調節が必要になる。
• ローカルミニマム、ローカルマキシマムに個体が偏ってしまい、本当の最小値や最大値とはかけ離れた値を解としてしまうことがある。
  
  • 遺伝的アルゴリズムは言うなれば目の見えない人に複数の山頂がある山々を登れ、と言っているようなものである。一度ある山頂に到達してしまえば、もっと高い地点があるのにそこにたどり着けなくなってしまうという状態になってしまう。
    そこでさらに良質の解を得るために行うことといえば、その人を山頂から蹴落とすこと…つまり、1回時間を巻き戻して再演算を行うとか、適応度の評価方法や個体の選抜方法を一時的に変更する(環境を変えて今まで進化の頂点にいた奴らを抹殺する)、突然変異率を一時的に変更したりなどして退化させることである。

遺伝的アルゴリズムは特徴をきちんと理解した上で、用量・用法を守って正しくご利用ください。

遺伝的アルゴリズムが深く関わる諸作品

• 『アストロノーカ』(旧エニックス販売のPS用ゲーム)
  作物を荒らす害獣「バブー」のAI進化に使われている。早い話が、対バブー用に罠とかを仕掛けても遺伝的アルゴリズムで進化してしまうため同じ罠だと突破される、と言うわけ。
  これはゲームアーカイブスで現在配信中(600円)なのでPSP、またはPS3を持っていたらやってみるのもいいかもしれない。
• 『神は沈黙せず』(小説、山本弘作)
  「この世界はコンピューターシミュレーションだった」というSF的には古くさすぎるネタをリアルに見せようとするための最初の鍵として、遺伝的アルゴリズムを利用した「ダーウィンズ・ガーデン」というゲームが登場する。
  (「ダーウィンズ・ガーデン」は「anilife」の進化版と考えたほうがわかりやすいだろう)

関連動画

関連商品

関連項目

• ×
• むにむに教授
• N700系新幹線電車（先頭車両の形状は遺伝的アルゴリズムで設計された）
• 遺伝的アルゴリズムで最高にエッチな画像を作ろう！