要素でコンピューターの制御を左右する。4つの主要な進化的アルゴリズムの一つであり、その中でも最も一般的に使用されている。遺伝的アルゴリズムはデータ(解の候補)を遺伝子で表現した「個体」を複数用意し、適応度の高い個体を優先的に選択して交叉・突然変異などの操作を繰り返しながら解を探索する。適応度は適応度関数によって与えられる。この手法の利点は、評価関数の可微分性や単峰性などの知識がない場合であっても適用可能なことである。必要とされる条件は評価関数の全順序性と、探索空間が位相(トポロジー)を持っていることである。遺伝子の表現の仕方によっては組合せ最適化問題やNP困難な問題などのさまざまな問題に適用可能である。遺伝的アルゴリズムは一般に以下の流れで実装される。個の個体が入る集合を二つ用意する。個の個体をランダムに生成する。評価関数により、現世代の各個体の適応度をそれぞれ計算する。ある確率で次の3つの動作のどれかを行い、その結果を次世代に保存する。個体を二つ選択(選択方法は後述)して交叉(後述)を行う。個体を一つ選択して突然変異(後述)を行う。個体を一つ選択してそのままコピーする。個になるまで上記の動作を繰り返す。個になったら次世代の内容を全て現世代に移す。アルゴリズムでは一般的に次の遺伝的操作が用いられる。交叉する確率を交叉率、突然変異する確率を突然変異率という。一般には(交叉率)>>(突然変異率)とすることが望ましいとされる。選択は生物の自然淘汰をモデル化したもので、適応度にもとづいて個体を増やしたり削除したりする操作である。選択のアルゴリズムには次のようなものがある。_{k=1}^{N}f_{k}}}}とする選択方式である。この方式はホランドが最初に提案したときに使われた選択方式であり、最も有名な選択方式であるが適応度が負の数を取らないことが前提になっている。適応度が高いことが前提になっているため最小値を求める問題では使の適応度の格差が激しい場合は適応度の高い個体の選ばれる確率が非常に高くなり、初期収束(後述)の原因にもなる。このため、実際には適応度をスケーリングした値を使用することが多い。3位なら...」というふうにランクごとにあらかじめ確率を決めておく方式である。この方法は、ルーレット選択と違い選択確率が適応度の格差に影響されない。これは逆に適応度にあまり差がない個体間でも選択確率に大きな差が生じる可能性がある。個体にランク付けをするため次世代が揃うたびにソートを行う必要がある。トーナメント選択編集トーナメント選択はあらかじめ決めた数(トーナメントサイズという)だけ集団の中からランダムで個体を取り出し、その中で最も適応度の高い個体を選択する方式である。トーナメントサイズを変更する事で選択圧をコントロールできる特徴がある。トーナメントサイズを大きくする事で選択圧を高める事ができるが、初期収束による局所(的)最適解に陥りやすくなる。上記の選択とは別に適応度が高い個体(エリート)を一定個数、次世代に残すことがある(エリート選択)。これを利用することで、選択によって解が悪い方向に向かわない(適応度の最大値が下がらない)ことを保証できる。エリートの遺伝子が集団の中に広まりすぎて解の多様性が失われるという恐れもある。交叉(組み換え)は生物が交配によって子孫を残すことをモデル化したもので、個体の遺伝子の一部を入れ換える操作である。交叉はその性質上、最も重要な遺伝的操作と言うことができる。交叉のアルゴリズムには次のようなもの、その場所より後ろを入れ換える方式である。ホランドが最初に提案したときの交叉方法であるが、効率は低く現在ではあまり使われていない。ランダムで二つ選び、二つの交叉点に挟まれている部分を入れ換える方式。独立に1/2の確率で入れ換える交叉である。後述するヒッチハイキングの問題をおさえることが可能である。一般に二点交叉が得意とする問題を苦手とし、二点交叉と逆の性質を示すことが知られている。生物に見られる遺伝子の突然変異をモデル化したもので、個体の遺伝子の一部を変化させる操作である。局所(的)最適解に陥ることを防ぐ効果がある。遺伝子型がビット列の場合は、ある遺伝子座の0と1を入れ換える。数字の場合は乱数と置き換える。他にも遺伝子座の位置を変更するなどの方法がとられる。変異の確率は0.1%~1%、高くても数%である。確率が低すぎると局所(的)最適解に陥りやすくなり、高すぎるとランダム探索に近づいてしまう(解が収束しにくくなる)。さまざまな問題に適用できる手法であるが、問題と使う方式によっては上手く探索しない場合がある。最初の方の世代で「偶然」他の個体より適応度が圧倒的に高い個体が生まれたとき、その個体の遺伝子が集団中に爆発的に増えて探索がかなり早い段階で収束してしまう現象である。ルーレット選択の設定が甘い場合や、突然変異の効果が上手く表れないときに起こりやすい。対策としては、ルーレット選択を使う場合の適切な設定や適用する問題に合わせて効果的になるように突然変異の操作を変更したり、突然変異率を増やしたり、または集団の数を増やすなどの設定を行うことで防ぐことができる。明確な解決法というものはなく、各パラメータを何度も繰り返し設定しなおすしかない。最適解が~101~という問題があるとする。このとき~111~~000~という二つの個体が交叉して最適解を得る確率を求める。~010~で最適解が得られる。{2}{l(l-1)}}}と求められる。長くなるにつれ加速度的に確率が低くなる。長いとほとんどの確率で上記の二つの個体は最適解と一致しないビットを新しく生成した個体に受け継がせてしまうことになる。このように最適解と一致するビットの近くにいて最適解の生成を妨げる現象をヒッチハイキングといい、そのビットをヒッチハイカーという。このヒッチハイキングは一様交叉によって防ぐことができる。一様交叉は各要素が独立で交叉するので、上記の場合は~111~⇒~101~~000~⇒~010~か~111~⇒~010~~000~⇒~101~で最適解を得る。長さが長くなっても変化しない。遺伝的アルゴリズムは他のメタヒューリスティックスに比べて、主要な探索手段である交叉が局所探索ではないことに大きな特徴がある。提唱されて以来有効性に関して多くの疑問が投げかけられた。GAの有効性をアルゴリズムを解析して検証するのは難しいため、初期のGAに関する研究では有効性を実験的に検証していた。理論的な考察が盛んに行われるようになった。ここではその基本的な部分をいくつか紹介する。用いて解析を進めるのが一般的になっている。1箇所の遺伝子座の値を反転させるという実装の遺伝的アルゴリズムである。スキーマ理論編集スキーマ理論とは、遺伝子型の部分集合(スキーマ)の有無が適応度に大きな影響を与えることを前提とした解析理論である。理論の根幹を成している。(アスタリスク)はワイルドカードのことであり、この部分には0と1のどちらが入っても良いことを意味している。含む個体」と表現する。スキーマ理論特有の用語として定義長とオーダがある。定義長とはスキーマの一番左のアスタリスク以外の文字と一番右のアスタリスク以外の文字との距離のことである。