前のページ 1/2 次のページ

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

◆ 概要

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

この手法の利点は、評価関数の可微分性や単峰性などの知識がない場合であっても適用可能なことである。

必要とされる条件は評価関数の全順序性と、探索空間が位相(トポロジー)を持っていることである。

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

◆ アルゴリズムの流れ

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

# あらかじめ N 個の個体が入る集合を二つ用意する。以下、この二つの集合を「現世代」、「次世代」と呼ぶことにする。

# 現世代に N 個の個体をランダムに生成する。

# 評価関数により、現世代の各個体の適応度をそれぞれ計算する。

# ある確率で次の3つの動作のどれかを行い、その結果を次世代に保存する。

## 個体を二つ選択(選択方法は後述)して交叉(後述)を行う。

## 個体を一つ選択して突然変異(後述)を行う。

## 個体を一つ選択してそのままコピーする。

# 次世代の個体数が N 個になるまで上記の動作を繰り返す。

# 次世代の個体数が N 個になったら次世代の内容を全て現世代に移す。

# 3. 以降の動作を最大世代数 G 回まで繰り返し、最終的に「現世代」の中で最も適応度の高い個体を「解」として出力する。

◆ 遺伝的操作

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

・ 選択(淘汰、再生)

・ 交叉(組み換え)

・ 突然変異

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

◇ 選択

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

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

  ルーレット選択

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

:

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

  ランキング選択

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

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

  トーナメント選択

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

  その他

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

◇ 交叉(組み換え)

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

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

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

個体A: 0100111010

個体B: 1010101011

  一点交叉

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

個体A: 01001|11010 ⇒ 01001 01011

個体B: 10101|01011 ⇒ 10101 11010

  二点交叉

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

個体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〜

前のページ 1/2 次のページ

・遺伝的アルゴリズム page1

・遺伝的アルゴリズム page2