遺伝的アルゴリズム
CHC は1990年、Eshelman によって提案された GA の拡張手法である。この名前は
2世代エリート選択(Cross generational elitist selection)
異種間交叉(Heterogeneous recombination)
大変動突然変異(Cataclysmic mutation)
のそれぞれの頭文字をとったものであり、それぞれ選択、交叉、突然変異を詳細に再検討してより効率的なアルゴリズムにしたものである。
遺伝的アルゴリズムは他のメタヒューリスティックスに比べて、主要な探索手段である交叉が局所探索ではないことに大きな特徴がある。この性質のため、GA は提唱されて以来有効性に関して多くの疑問が投げかけられた。しかし、GAの有効性をアルゴリズムを解析して検証するのは難しいため、初期のGAに関する研究では有効性を実験的に検証していた。
1980年代後半から、以上の反省を踏まえて GA の理論的な考察が盛んに行われるようになった。ここではその基本的な部分をいくつか紹介する。
ルーレット選択は個体 i を選ぶ確率を pi と置いたとき、
p i = f i ∑ k = 1 N f k {\displaystyle p_{i}={\frac {f_{i}}{\sum _{k=1}^{N}f_{k}}}}
とする選択方式である。上記の式の fi は個体 i の適応度を表す。この方式はホランドが最初に提案したときに使われた選択方式であり、最も有名な選択方式であるが適応度が負の数を取らないことが前提になっている。また適応度が高いことが前提になっているため最小値を求める問題では使いづらい。さらに、もし個体間の適応度の格差が激しい場合は適応度の高い個体の選ばれる確率が非常に高くなり、初期収束(後述)の原因にもなる。このため、実際には適応度をスケーリングした値を使用することが多い。