##１．定義
遺伝的アルゴリズム（genetic algorithm、略称：GA）とは、1975年にミシガン大学のジョン・H・ホランド（John Henry Holland）によって提案された近似解を探索するメタヒューリスティックアルゴリズムである。計算機科学とオペレーションズリサーチで遺伝的アルゴリズムはより大きな進化的アルゴリズムのクラスクラス（Evolutionary algorithm、略称：EA）に属する自然選択のプロセスに触発されてメタヒューリスティック。4つの主要な進化的アルゴリズムの一つであり、その中でも遺伝的アルゴリズムは最も一般的に使用されている。ダーウィンの進化論に基づいて、生物突然変異や交叉や選択などを使って、遺伝的アルゴリズムは最適化および検索問題に対する高品質の解決策を生成するために使用される。
##２．アルゴリズムの流れ
- 4つの主要ステップがある：
- ソリューションを暗号化する
- 初期集団を生成する
- 遺伝的数学と適応評価を使う
- 選択によって新しい集団を生成する
##3. 主な要因
###1. 選択
選択は生物の自然淘汰をモデル化したもので、適応度にもとづいて個体を増やしたり削除したりする操作である。 選択のアルゴリズムには次のようなものがある。
####ルーレット選択
ルーレット選択は個体 i を選ぶ確率を pi と置いたとき、
Pi =Fi/𝝨fk (1≤k≤N)
とする選択方式である。上記の式の fi は個体 i の適応度を表す。この方式はホランドが最初に提案したときに使われた選択方式であり、最も有名な選択方式であるが適応度が負の数を取らないことが前提になっている。また適応度が高いことが前提になっているため最小値を求める問題では使の適応度の格差が激しい場合は適応度の高い個体の選ばれる確率が非常に高くなり、初期収束（後述）の原因にもなる。このため、実際には適応度をスケーリングした値を使用することが多い。
####ランキング選択
ランキング選択は各個体を適応度によってランク付けして、「1位なら確率 p1, 2位なら確率 p2, 3位なら…」というふうにランクごとにあらかじめ確率を決めておく方式である。
この方法は、ルーレット選択と違い選択確率が適応度の格差に影響されない。しかし、これは逆に適応度にあまり差がない個体間でも選択確率に大きな差が生じる可能性がある。また、個体にランク付けをするため次世代が揃うたびにソートを行う必要がある。
###2. 交叉
交叉（組み換え）は生物が交配によって子孫を残すことをモデル化したもので、個体の遺伝子の一部を入れ換える操作である。交叉はその性質上、最も重要な遺伝的操作と言うことができる。
###3. 突然変異
突然変異は生物に見られる遺伝子の突然変異をモデル化したもので、個体の遺伝子の一部を変化させる操作である。局所（的）最適解に陥ることを防ぐ効果がある。
突然変異の確率は0.1%～1%、高くても数%である。確率が低すぎると局所（的）最適解に陥りやすくなり、高すぎるとランダム探索に近づいてしまう（解が収束しにくくなる）。
