遺伝的アルゴリズム

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

概要

遺伝的アルゴリズムはデータ（解の候補）を遺伝子で表現した「個体」を複数用意し、適応度の高い個体を優先的に選択して交叉・突然変異などの操作を繰り返しながら解を探索する。適応度は適応度関数によって与えられる。
この手法の利点は、評価関数の可微分性や単峰性などの知識がない場合であっても適用可能なことである。
必要とされる条件は評価関数の全順序性と、探索空間が位相（トポロジー）を持っていることである。
また、遺伝子の表現の仕方によっては組合せ最適化問題やNP困難な問題などのさまざまな問題に適用可能である。

選択

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

ランキング選択

ランキング選択は各個体を適応度によってランク付けして、「1位なら確率 p₁, 2位なら確率 p₂, 3位なら…」というふうにランクごとにあらかじめ確率を決めておく方式である。
この方法は、ルーレット選択と違い選択確率が適応度の格差に影響されない。しかし、これは逆に適応度にあまり差がない個体間でも選択確率に大きな差が生じる可能性がある。また、個体にランク付けをするため次世代が揃うたびにソートを行う必要がある。

トーナメント選択

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

その他

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

交叉（組み換え）

交叉（組み換え）は生物が交配によって子孫を残すことをモデル化したもので、個体の遺伝子の一部を入れ換える操作である。交叉はその性質上、最も重要な遺伝的操作と言うことができる。
交叉のアルゴリズムには次のようなもの、その場所より後ろを入れ換える方式である。ホランドが最初に提案したときの交叉方法であるが、効率は低く現在ではあまり使われていない。
個体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を入れ換える。数字の場合は乱数と置き換える。他にも遺伝子座の位置を変更するなどの方法がとられる。
突然変異の確率は0.1%～1%、高くても数%である。確率が低すぎると局所（的）最適解に陥りやすくなり、高すぎるとランダム探索に近づいてしまう（解が収束しにくくなる）。

GAの問題点

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

初期収束

初期収束とは、最初の方の世代で「偶然」他の個体より適応度が圧倒的に高い個体が生まれたとき、その個体の遺伝子が集団中に爆発的に増えて探索がかなり早い段階で収束してしまう現象である。ルーレット選択の設定が甘い場合や、突然変異の効果が上手く表れないときに起こりやすい。
対策としては、ルーレット選択を使う場合の適切な設定や適用する問題に合わせて効果的になるように突然変異の操作を変更したり、突然変異率を増やしたり、または集団の数を増やすなどの設定を行うことで防ぐことができる。しかしながら明確な解決法というものはなく、各パラメータを何度も繰り返し設定しなおすしかない。

GA の理論

遺伝的アルゴリズムは他のメタヒューリスティックスに比べて、主要な探索手段である交叉が局所探索ではないことに大きな特徴がある。この性質のため、GA は提唱されて以来有効性に関して多くの疑問が投げかけられた。しかし、GAの有効性をアルゴリズムを解析して検証するのは難しいため、初期のGAに関する研究では有効性を実験的に検証していた。
1980年代後半から、以上の反省を踏まえて GA の理論的な考察が盛んに行われるようになった。ここではその基本的な部分をいくつか紹介する。

スキーマ理論

スキーマ理論とは、遺伝子型の部分集合（スキーマ）の有無が適応度に大きな影響を与えることを前提とした解析理論である。現在の 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 である。

GA の拡張

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

Messy GA

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

分布推定アルゴリズム

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

遺伝的プログラミング

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