遺伝的アルゴリズム

交叉と突然変異で次の世代を作る進化計算。 Genetic Algorithm、GA。 Holland が 1975 年の著書で定式化し、進化計算の出発点になった。

手順#

1. 初期集団を無作為に作る
2. 選択 — 適応度に応じて親を選ぶ（ルーレット選択、トーナメント選択など）
3. 交叉 (crossover) — 2 つの親の一部を入れ替えて子を作る
4. 突然変異 (mutation) — 子の一部を確率的に変える
5. 2〜4 を繰り返す

交叉が本体#

GA の特徴は交叉にある。「良い部分解どうしを組み合わせれば、より良い解になる」 という期待に賭けている。Holland はこれをスキーマ定理として論じたが、 その説明力については後年かなり批判があり、GA が有効な理由の説明としては 現在は decisive とは見なされていない。

どこで使うか#

• 表現が離散・組合せのとき。ビット列や順列をそのまま個体にできる
• 巡回セールスマン問題のように 順序が意味を持つ問題（順序専用の交叉が設計されている）

逆に連続変数の問題では、分布そのものを適応させる CMA-ES のほうが一般に強い。 ビット列に無理に符号化すると、近い値が遠いビット列になる（ハミング崖）問題も起きる。

参考文献#

• John H. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, 1975 / MIT Press, 1992. https://doi.org/10.7551/mitpress/1090.001.0001
• David E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, 1989. https://dl.acm.org/doi/book/10.5555/534133
• Agoston E. Eiben, James E. Smith. Introduction to Evolutionary Computing, 2nd ed. Springer, 2015. https://doi.org/10.1007/978-3-662-44874-8