遺伝的アルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』
2013年10月23日 (水) 01:54時点における42.125.160.178 (トーク)による版
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先: 案内、 検索

遺伝的アルゴリズム（いでんてきアルゴリズム、英語：genetic algorithm、略称：GA）とは、1975年にミシガン大学のジョン・H・ホランド（John Henry Holland）によって提案された近似解を探索するメタヒューリスティックアルゴリズムである。人工生命同様、偶然の要素でコンピューターの制御を左右する。4つの主要な進化的アルゴリズムの一つであり、その中でも最も一般的に使用されている。

概要

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

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

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

アルゴリズムの流れ

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

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

遺伝的操作

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

  • 選択（淘汰、再生）
  • 交叉（組み換え）
  • 突然変異

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

選択

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

ルーレット選択

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

<math>p_i = \frac{f_i}{\sum^{N}_{k=1}f_k}</math>

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

ランキング選択

ランキング選択は各個体を適応度によってランク付けして、「1位なら確率 p1, 2位なら確率 p2, 3位なら…」というふうにランクごとにあらかじめ確率を決めておく方式である。

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

トーナメント選択

トーナメント選択はあらかじめ決めた数（トーナメントサイズという）だけ集団の中からランダムで個体を取り出し、その中で最も適応度の高い個体を選択する方式である。トーナメントサイズを変更する事で選択圧をコントロールできる特徴がある。すなわち、トーナメントサイズを大きくする事で選択圧を高める事ができるが、初期収束による局所（的）最適解に陥りやすくなる。

その他

上記の選択とは別に適応度が高い個体（エリート）を一定個数、次世代に残すことがある（エリート選択）。これを利用することで、選択によって解が悪い方向に向かわない（適応度の最大値が下がらない）ことを保証できる。しかし、エリートの遺伝子が集団の中に広まりすぎて解の多様性が失われるという恐れもある。

交叉（組み換え）

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

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

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

個体A: 0100111010

個体B: 1010101011

一点交叉

ファイル:Computational.science.Genetic.algorithm.Crossover.One.Point.svg
一点交叉

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

個体A: 01001｜11010 ⇒ 01001 01011

個体B: 10101｜01011 ⇒ 10101 11010

二点交叉

ファイル:Computational.science.Genetic.algorithm.Crossover.Two.Point.svg
二点交叉

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

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

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

多点交叉

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

一様交叉

ファイル:Computational.science.Genetic.algorithm.Crossover.Uniform.Crossover.svg
一様交叉

各要素ごと独立に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を入れ換える。数字の場合は乱数と置き換える。他にも遺伝子座の位置を変更するなどの方法がとられる。

突然変異の確率は0.1%～1%、高くても数%である。確率が低すぎると局所（的）最適解に陥りやすくなり、高すぎるとランダム探索に近づいてしまう（解が収束しにくくなる）。

GAの問題点

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

初期収束

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

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

ヒッチハイキング

例えば最適解が

～101～

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

～111～

～000～

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

～1|1|1～ ⇒ ～101～

～0|0|0～ ⇒ ～010～

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

<math>p=\frac{2}{l(l-1)}</math>

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

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

～111～⇒～101～

～000～⇒～010～

か

～111～⇒～010～

～000～⇒～101～

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

<math>p=\frac{2}{2^3}=\frac{1}{4}</math>

であり、この確率は 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) = 3 である。オーダとはスキーマ内のアスタリスク以外の文字の数のことである。これは O(H) という形で表す。上記の例の場合は O(H) = 3 である。

スキーマ定理と積み木仮説

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

<math>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]</math>

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

このとき、pc >> pm, δ(H) > O(H) であるので、括弧内の O(H)⋅pm はほとんど無視できる。そのため、この定理は

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

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

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

GA の拡張

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

Messy GA

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

CHC

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

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

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

分布推定アルゴリズム

Estimation of Distribution Algorithm (EDA)。GAは個体の集合に対して、交叉や突然変異を行い、個体の集合が進化するが、EDA では、個体生成の確率分布を進化させる。アルゴリズムは、Population-based incremental learning (PBIL)など。

遺伝的プログラミング

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

参考文献

  • 伊庭斉志 『遺伝的アルゴリズムの基礎』、オーム社、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://wikippe.e-do-match.com/index.php?title=遺伝的アルゴリズム&oldid=20195」から取得