遺伝的アルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』

遺伝的アルゴリズム（いでんてき-、Genetic Algorithm、GA）とは、1975年にミシガン大学のジョン・ホランド（John Holland）によって提案された近似解を探索するメタヒューリスティックアルゴリズムである。4つの主要な進化的アルゴリズムの一つであり、その中でも最も一般的に使用されている。

[編集] 概要

遺伝的アルゴリズムはデータ（解の候補）を遺伝子で表現した「個体」を複数用意し、適応度の高い個体を優先的に選択して交叉・突然変異などの操作を繰り返しながら解を探索する。

この手法の利点は評価関数の可微分性や単峰性などの知識がない場合であっても、適用可能なことである。必要とされる条件は評価関数の全順序性と、探索空間が位相（トポロジー）を持っていることである。

また遺伝子の表現の仕方によっては組合せ最適化問題やNP困難な問題などのさまざまな問題に適用可能である。

[編集] アルゴリズムの流れ

遺伝的アルゴリズムは一般に以下の流れで実装される。なお、下記では個体数を N 最大世代数を G と置く。

あらかじめ N 個の個体が入る集合を二つ用意する、以降この二つの集合は「現世代」と「次世代」と呼ぶことにする。
現世代に N 個の個体をランダムに生成する。
現世代の各個体の適応度をそれぞれ計算する。
ある確率で次の3つの動作のどれかを行い、その結果を次世代に保存する。
1. 個体を二つ選択（選択方法は後述）して交叉（後述）を行う。
2. 個体を一つ選択して突然変異（後述）を行う。
3. 個体を一つ選択してそのままコピーする。
次世代の個体数が N 個になるまで上記の動作を繰り返す。
次世代の個体数が N 個になったら次世代の内容を全て現世代に移す。
3. 以降の動作を最大世代数 G 回まで繰り返し、最終的に「現世代」の中で最も適応度の高い個体を「解」として出力する。

[編集] 遺伝的操作

遺伝的アルゴリズムでは一般的に次の遺伝的操作が用いられる。

選択（淘汰、再生）
交叉
突然変異

交叉する確率を交叉率、突然変異する確率を突然変異率という。一般には（交叉率）>>（突然変異率）とすることが望ましいとされる。また上記のアルゴリズムの流れからわかるとおり（交叉率）+（突然変異率）< 1である必要がある。

[編集] 選択

選択は自然淘汰をモデル化したもので、適応度にもとづいて個体を増やしたり削除したりする操作である。選択のアルゴリズムには次のようなものがある。

[編集] ルーレット選択

ルーレット選択は個体 i を選ぶ確率を p_i と置いたとき、

$p_i = \frac{f_i}{\sum^{N}_{k=1}f_k}$

とする選択方式である。上記の式の f_i は個体 i の適応度を表す。この方式はホランドが最初に提案したときに使われた選択方式であり、最も有名な選択方式であるが適応度が負の数を取らないことが前提になっている。また適応度が高いことが前提になっているため最小値を求める問題では使いづらい。さらにもし個体間の適応度の格差が激しい場合は適応度の高い個体の選ばれる確率が非常に高くなり初期収束（後述）の原因にもなる。このため実際には適応度をスケーリングした値を使用することが多い。

[編集] ランキング選択

ランキング選択は各個体をランク付けして、「１位なら確率 0.3 ２位なら確率 0.2 ３位なら…」というふうにランク別にあらかじめ確率を決めておく方式である。

この方法はルーレット選択と違い適応度の格差で選択確率が影響されない。しかし、これは逆に適応度にあまり差がない個体でも選択確率に大きな差がでる可能性がある。また、個体にランク付けをするため次世代が揃うたびにソートを行う必要がある。

[編集] トーナメント選択

トーナメント選択はあらかじめ決めた数（トーナメントサイズという）だけ集団の中からランダムで個体を取り出し、その中で最も適応度の高い個体を選択する方式である。

[編集] その他

上記の選択とは別に適応度が高い個体を一定個数、次世代に残すことがある（エリート選択）。これを利用することで、選択によって解が悪い方向に向かわないことを保証できる。

[編集] 交叉

交叉は生物が子孫を残すことをモデル化したもので、個体の遺伝子の一部を入れ換える操作である。交叉はその性質上、最も重要な遺伝的操作と言うことができる。

交叉のアルゴリズムには次のようなものがある。

例として次の二つの個体を交叉する。

個体A：0100111010

個体B：1010101011

[編集] 一点交叉

一点交叉

遺伝子が交叉する場所（交叉点）をランダムで一つ選び、その場所より後ろを入れ換える方式である。ホランドが最初に提案したときの交叉であるが効率は低く、現在ではあまり使われていない。

個体A：01001｜11010⇒01001 01011

個体B：10101｜01011⇒10101 11011

[編集] 二点交叉

二点交叉

交叉点をランダムで二つ選び、二つの交差点に挟まれている部分を入れ換える方式。

個体A：010|01110|10⇒010 01010 10

個体B：101|01010|11⇒101 01110 11

[編集] 多点交叉

一般に3点以上の交叉点をもつ方法を多点交叉あるいは n点交叉という。しかしながら一部の問題を除き、多点交叉は二点交叉と下記で述べる一様交叉のどちらかよりも良い値が出ることはほとんどなく、あまり使われていない。

[編集] 一様交叉

一様交叉

各要素ごと独立に1/2の確率で入れ換える交叉である。後述するヒッチハイキングの問題をおさえることが可能である。一般に二点交叉が得意とする問題を苦手とし、二点交叉と逆の性質を示すことが知られている。

個体A：0 1 0 0 1 1 1 0 1 0⇒0 0 1 0 1 1 1 0 1 1

個体B：1 0 1 0 1 0 1 0 1 1⇒1 1 0 0 1 0 1 0 1 0

[編集] 突然変異

突然変異は生物に見られる遺伝子の突然変異をモデル化したもので、個体の遺伝子の一部を変化させる操作である。

例えば、遺伝子型がビット列の場合はある遺伝子座の0と1を入れ換える。数字の場合は乱数と置き換える。他にも遺伝子座の位置を変更するなどの方法がとられる。

[編集] GAの問題点

GA はさまざまな問題に適用できる手法であるが、問題と使う方式によっては上手く探索しない場合がある、ここではよく起きるGAの問題点をまとめる。

[編集] 初期収束

初期収束は最初の方の世代で「偶然」他の個体より適応度が圧倒的に高い個体が生まれたとき、その個体が集団中に爆発的に増えて探索をかなり早い段階で収束させてしまう現象である。ルーレット選択の設定が甘い場合や突然変異の効果が上手く表れないときに起こりやすい。

対策としてはルーレット選択を使う場合の適切な設定や適用する問題に合わせて効果的になるように突然変異の操作を変更したり、突然変異率を増やしたり、または集団の数を増やすなどの設定を行うことで防ぐことができる。しかしながら明確な解決法というものはなく、各パラメータを何度も繰り返し設定しなおすしかない。

[編集] ヒッチハイキング

例えば最適解が

～101～

という問題があるとする。このとき

～111～

～000～

という二つの個体が交叉して最適解を得る確率を求める。交叉の方式が二点交叉の場合は交差点が

～1|1|1～⇒～101～

～0|0|0～⇒～010～

で最適解が得られる。このとき遺伝子型の長さを l とおくと最適解が得られる確率 p は

$p=\frac{2}{l(l-1)}$

と求められる。これは l が長くなるにつれ加速度的に確率が低くなる。つまりl が長いとほとんどの確率で上記の二つの個体は最適解と一致しないビットを新しく生成した個体に受け継がせてしまうことになる。このように最適解と一致するビットの近くにいて最適解の生成を妨げる現象をヒッチハイキングといい、そのビットをヒッチハイカーという。

このヒッチハイキングは一様交叉によって防ぐことができる。一様交叉は各要素が独立で交叉するので、上記の場合は

～111～⇒～101～

～000～⇒～010～

か

～111～⇒～010～

～000～⇒～101～

で最適解を得るこのとき、最適解を生成する確率は

$p=\frac{2}{2^3}=\frac{1}{4}$

であり、この確率は l の長さが長くなっても変化しない。

[編集] GA の理論

遺伝的アルゴリズムは他のメタヒューリスティックスに比べて、主要な探索手段である交叉が局所探索ではないことに大きな特徴がある。この性質のため GA は提唱されて以来有効性に関して多くの疑問が投げかけられた。しかし GA の有効性を理論的に検証するのは難しく、この事から思考停止して応用の探索を進めているのが初期の現状であった。

1980年代後半から以上の反省を踏まえて GA の理論的な考察が盛んに行われるようになった。ここではその基本的な部分をいくつか紹介する。

[編集] SGA

SGA とは Simple Genetic Algorithm （単純 GA）の略である。GAを通常のまま解析するとあまりにも複雑なので、処理を単純にした GA を用いて解析を進めるのが一般的になっている。SGA は具体的には

遺伝子表現は 1 と 0 のみ
ルーレット選択
一点交叉
突然変異は 1箇所の遺伝子座の値を反転させる

という実装の遺伝的アルゴリズムである。

[編集] スキーマ理論

スキーマ理論とは遺伝子型の部分集合（スキーマ）の有無が適合度に大きな影響を与えることを前提とした解析理論である。現在の GA の理論の根幹を成している。スキーマとは例えば

H = * * 0 1 * 1 *

のような形で表す。ここで "*"（アスタリスク）はワイルドカードのことであり、この部分には0と1のどちらが入っても良いことを意味している。このとき

0 1 0 1 1 1 0
1 1 0 1 0 1 0

のように * 以外の部分が一致している遺伝子型を持つ個体のことを「スキーマ H を含む個体」と表現する。スキーマ理論特有の用語として定義長とオーダがある。定義長とはスキーマの一番左のアスタリスク以外の文字と一番右のアスタリスク以外の文字との距離のことである。これはδ(H)という形で表す。上記の例の場合は δ(H) = 4 である。オーダとはスキーマ内のアスタリスク以外の文字の数のことである。これは O(H) という形で表す。上記の例の場合は O(H) = 3 である。

[編集] スキーマ定理と積み木仮説

スキーマ定理とはある世代 t でスキーマ H を含む個体の数を m(H, t) と表したとき、次の世代のスキーマ H を含む個体の数 m(H, t+1) は SGA においては以下のように表すことができるという定理である。

$m(H, t+1) \geq m(H, t) \cdot \frac{f(H)}{\overline{f}} \cdot \left[ 1 - p_c \cdot \frac{\delta(H)}{l-1} - O(H) \cdot p_m\right]$

ここで、 f(H) はスキーマ H を含む個体の適合度の平均、 $\overline{f}$ は全個体の適合度の平均、l は遺伝子型の長さ、 $p c, p m$ は交叉率と突然変異率である。

このとき $p_c \gg p_m$ 、 $δ(H) > O (H)$ であるので括弧内の $O(H)\cdot p_m$ はほとんど無視できる。そのため、この定理は

定義長 δ(H) が小さく
f(H) が全体の平均より常に大きい

となるようなスキーマ H の数は指数関数的に増大していくことを表している。

ここから上記の条件を満たすスキーマを保持することが最適解を導くことになるような問題に対しては GA は最適解を導き出すことが可能であるという考え方ができる。このようなスキーマを積み木(Bilding Block)といい、この考え方を積み木仮説という。

[編集] GA の拡張

GA にはさまざまな拡張手法が存在する、ここでは有名なものをいくつか挙げる。

[編集] 遺伝的プログラミング

遺伝的プログラミング（genetic programming;GP）は、J.Kozaによって提案された遺伝的アルゴリズムを拡張した物の一つである。遺伝子を木構造にすることで式やプログラムなどを扱えるようにした。工学分野だけではなく、経済分野などにも広く活用されている。

[編集] Messy GA

Messy GA とは積み木仮説、特に定義長 δ(H) が小さくなければならないという弱点を克服するために Goldberg により提案された遺伝的アルゴリズムの拡張手法である。遺伝子表現は遺伝子座の位置とその値のペアで表現する。これに「カット」と「スライス」という手法で探索を進める。Goldberg はこれを用いて GA では非常に探索しにくい関数の最適解の導出に成功している。しかしこの手法は問題に対するかなり詳しい事前知識が必要なため実際面での応用例はほとんどない。

[編集] CHC

CHC は1990年、Eshelman によって提案された GA の拡張手法である、この名前は

2世代エリート選択（Cross generational elitist selection）
異種間交叉（Heterogeneous recombination）
大変動突然変異（Cataclysmic mutation）

のそれぞれの頭文字をとったものであり、それぞれ選択、交叉、突然変異を詳細に再検討してより効率的なアルゴリズムにしたものである。

[編集] 関連項目

進化的計算
最適化問題
人工生命
アストロノーカ（遺伝的アルゴリズムを利用したゲーム）

[編集] 参考文献

伊庭斉志『遺伝的アルゴリズムの基礎』、オーム社、1994年、ISBN 4-274-07802-7
伊庭斉志『進化論的計算の方法』、東京大学出版会、1999年、ISBN 4-13-061401-0
北野宏明他『遺伝的アルゴリズム』、産業図書、1993年、ISBN 4-7828-5136-7
坂和正敏・田中雅博『遺伝的アルゴリズム』、朝倉書店、1995年、ISBN 4-254-20990-8
三宮信夫・喜多一・玉置久・岩本貴司『遺伝アルゴリズムと最適化』、朝倉書店、1998年、ISBN 4-254-20977-0

"http://ja.wikipedia.org../../../%E9%81%BA/%E4%BC%9D/%E7%9A%84/%E9%81%BA%E4%BC%9D%E7%9A%84%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0.html" より作成

カテゴリ: 複雑系 | 最適化アルゴリズム