遺伝的アルゴリズム

個体群のサイズは問題の性質によって異なりますが、通常は数百または数千の可能な解が含まれます。多くの場合、初期個体群はランダムに生成され、可能な解の全範囲（探索空間）を網羅します。場合によっては、最適な解が見つかる可能性が高い領域に解を「シード」したり、サンプリング確率の分布を調整して、より関心のある領域に集中させたりすることがあります。^{[ 6 ]}

各世代において、既存の個体群の一部が選択され、新たな世代へと繁殖します。個々の解は適応度に基づくプロセスによって選択され、適応度関数によって測定される適応度の高い解ほど選択される可能性が高くなります。特定の選択方法では、各解の適応度を評価し、最良の解を優先的に選択します。一方、他の方法では、前者のプロセスは非常に時間がかかる可能性があるため、個体群のランダムサンプルのみを評価します。

適合度関数は遺伝的表現上で定義され、表現された解の質を測定します。適合度関数は常に問題に依存します。たとえば、ナップサック問題では、一定の容量のナップサックに入れることができる物の合計価値を最大化したいと考えます。解の表現はビットの配列である可能性があり、各ビットは異なる物を表し、ビットの値（0または1）は物がナップサックに入っているかどうかを表します。物のサイズがナップサックの容量を超える場合があるため、すべての表現が有効とは限りません。表現が有効な場合、解の適合度はナップサック内のすべての物の値の合計であり、そうでない場合は0です。

問題によっては、適応度を表す式を定義することが困難、あるいは不可能な場合もあります。このような場合、シミュレーションを用いて表現型の適応度関数値を決定する（例えば、形状が表現型として符号化された車両の空気抵抗を決定するために計算流体力学を用いる）か、あるいは対話型の遺伝的アルゴリズムを用いることもあります。

次のステップは、選択された解から、遺伝的演算子である交叉（組換えとも呼ばれる）と突然変異を組み合わせることによって、第2世代の解の集団を生成することです。

新たに生成されるソリューションごとに、以前に選択されたプールから繁殖用の「親」ソリューションのペアが選択されます。上記の交叉と突然変異の方法を使用して「子」ソリューションを生成すると、通常は「親」の多くの特性を共有する新しいソリューションが作成されます。新しい子ごとに新しい親が選択され、適切なサイズのソリューションの新しい集団が生成されるまでプロセスが続きます。2 つの親の使用に基づく繁殖方法はより「生物学にヒントを得た」ものですが、いくつかの研究^{[ 7 ] [ 8 ]}は、 2 つ以上の「親」がより高品質の染色体を生成することを示唆しています。

これらのプロセスを経て、最終的に次世代の染色体集団は初期世代とは異なるものとなる。一般的に、この手順によって集団の平均適応度は向上する。なぜなら、第一世代から最も優れた個体のみが繁殖のために選ばれ、適応度の低い個体も少数ながら残されるからである。これらの適応度の低い個体は、親の遺伝子プール内の遺伝的多様性を確保し、ひいては次世代の子孫の遺伝的多様性を確保する。

交叉と突然変異のどちらが重要かについては意見が分かれている。Fogel（2006）には、突然変異に基づく探索の重要性を支持する多くの文献がある。

突然変異確率、交叉確率、個体群サイズなどのパラメータを調整して、対象となる問題の複雑さに適した設定を見つけることが重要です。突然変異率が低すぎると、遺伝的浮動（非エルゴード的性質を持つ）が発生する可能性があります。組換え率が高すぎると、遺伝的アルゴリズムが早期に収束してしまう可能性があります。突然変異率が高すぎると、エリート選択を用いない限り、優れた解が失われる可能性があります。適切な個体群サイズは、対象となる問題に対して十分な遺伝的多様性を確保しますが、必要以上に大きな値に設定すると、計算リソースの無駄遣いにつながる可能性があります。

上記の主要な演算子に加えて、計算を高速化またはより堅牢にするために他のヒューリスティックが使用される場合があります。種分化ヒューリスティックは、類似しすぎる候補解間の交叉にペナルティを課します。これにより、集団の多様性が促進され、最適ではない解への早期収束を防ぐのに役立ちます。^{[ 9 ] [ 10 ]}

この世代交代プロセスは、終了条件に達するまで繰り返されます。一般的な終了条件は次のとおりです。

• 最小基準を満たす解が見つかる
• 固定世代数に達した
• 割り当てられた予算（計算時間／金額）に達しました
• 最高ランクのソリューションの適合度は、それ以上反復してもより良い結果が得られないほど、プラトーに達しつつあるか、既に達している。
• 手動検査
• 上記の組み合わせ

進化アルゴリズムは、進化コンピューティングのサブ分野である。

• 進化戦略（ES、Rechenberg、1994を参照）は、突然変異と中間または離散的な組換えによって個体を進化させます。ESアルゴリズムは、特に実数値領域の問題を解決するように設計されています。^{[ 60 ]}自己適応を使用して、探索の制御パラメータを調整します。自己適応の非ランダム化により、現代の共分散行列適応進化戦略（CMA-ES）が生まれました。
• 進化プログラミング（EP）は、主に突然変異と選択、そして任意の表現を用いた解の集団を扱う。自己適応を用いてパラメータを調整し、複数の親からの情報を組み合わせるなど、他の変異操作も含むことができる。
• 分布推定アルゴリズム（EDA）は、従来の複製演算子をモデル誘導演算子に置き換えます。このようなモデルは、機械学習技術を用いて集団から学習され、確率的グラフィカルモデルとして表現され、そこから新しい解をサンプリングしたり^{[ 61 ] [ 62 ]}、誘導交叉によって生成したりできます^{[ 63 ] 。}
• 遺伝的プログラミング(GP) は、ジョン・コザによって普及した関連技術であり、関数パラメータではなくコンピュータ プログラムが最適化されます。遺伝的プログラミングでは、適応のためのコンピュータ プログラムを表現するために、遺伝的アルゴリズムで一般的なリスト構造の代わりに、ツリーベースの内部データ構造がよく使用されます。遺伝的プログラミングには、デカルト遺伝的プログラミング、遺伝子発現プログラミング、^{[ 64 ]}文法進化、線形遺伝的プログラミング、多重発現プログラミングなど、多くのバリエーションがあります。
• グループ化遺伝的アルゴリズム(GGA) は、古典的な GA のように個々のアイテムではなく、アイテムのグループまたはサブセットに焦点を当てた GA の進化形です。^{[ 65 ]}エマニュエル・ファルケナウアーが提案したこの GA 進化形の背後にある考え方は、アイテムのセットを最適な方法で互いに素なアイテムのグループに分割する必要があるクラスタリングやパーティショニング問題などの複雑な問題を解決するには、アイテムのグループの特性を遺伝子と同等にすることでより良く達成できるというものです。このような問題には、ビン パッキング、ライン バランシング、距離尺度に関するクラスタリング、等山などがあり、古典的な GA ではうまく機能しませんでした。遺伝子をグループと同等にするということは、一般的に可変長の染色体と、アイテムのグループ全体を操作する特別な遺伝的演算子を意味します。特にビン パッキングに関しては、マルテロとトスの優位性基準とハイブリッド化した GGA が、おそらく今日までで最高の技術です。
• 対話型進化アルゴリズムとは、人間の評価を用いる進化アルゴリズムのことである。これらは通常、計算による適合度関数を設計するのが難しい分野、例えば、ユーザーの美的嗜好に合わせて画像、音楽、芸術的なデザインや形態を進化させる場合などに適用される。

群知能は進化計算の一分野である。

• アリコロニー最適化（ACO）は、フェロモンモデルを備えた多数のアリ（またはエージェント）を使用して、解空間を探索し、局所的に生産性の高い領域を見つけ出します。
• 分布推定アルゴリズムと考えられているが、^{[ 66 ]}粒子群最適化(PSO) は、集団ベースのアプローチも使用する多パラメータ最適化の計算手法である。候補解 (粒子) の集団 (群れ) が探索空間内を移動し、粒子の移動は、粒子自身の既知の最良位置と群れのグローバルな既知の最良位置の両方の影響を受ける。遺伝的アルゴリズムと同様に、PSO 手法は集団メンバー間の情報共有に依存する。いくつかの問題では、特に連続変数を持つ制約のない問題では、PSO は GA よりも計算効率が高いことが多い。^{[ 67 ]}

進化計算は、メタヒューリスティック手法のサブ分野である。

• ミームアルゴリズム（MA）は、ハイブリッド遺伝的アルゴリズムなどとも呼ばれ、解が局所的な改善段階も経る集団ベースの手法です。ミームアルゴリズムの発想は、遺伝子とは異なり自己適応能力を持つミームに由来しています。いくつかの問題領域では、従来の進化アルゴリズムよりも効率的であることが示されています。
• 細菌学的アルゴリズム（BA）は、進化生態学、特に細菌の適応に触発されたものです。進化生態学は、生物が環境の中でどのように適応するかを解明することを目的として、生物をその環境との関連で研究する学問です。その基本概念は、異質な環境では、環境全体に適合する個体は存在しないということです。したがって、集団レベルで推論する必要があります。BAは、複雑な位置特定問題（携帯電話のアンテナ、都市計画など）やデータマイニングにもうまく適用できると考えられています。^{[ 68 ]}
• 文化アルゴリズム（CA）は、遺伝的アルゴリズムとほぼ同じ集団構成要素に加え、信念空間と呼ばれる知識構成要素から構成される。
• 超生物の移動に触発された差異進化（DE）。^{[ 69 ]}
• ガウス適応（正規または自然適応、GA との混同を避けるために NA と略記）は、信号処理システムの製造歩留まりを最大化することを目的としています。通常のパラメトリック最適化にも使用できます。これは、すべての許容領域とすべてのガウス分布に有効な特定の定理に基づいています。NA の効率は、情報理論と特定の効率定理に基づいています。その効率は、情報を取得するために必要な作業で割った情報として定義されます。^{[ 70 ]} NA は個体の適応度ではなく平均適応度を最大化するため、地形は滑らかになり、ピーク間の谷が消える可能性があります。したがって、適応度地形の局所的なピークを回避するという一定の「野心」があります。NA は、モーメント行列の適応によって鋭い頂上を登ることにも優れています。これは、NA が平均適応度を一定に保ちながらガウスの無秩序（平均情報）を最大化できるためです。

メタヒューリスティック手法は、概して確率的最適化手法に分類される。

• シミュレーテッドアニーリング（SA）は、個々の解に対してランダムな突然変異をテストすることで探索空間を探索する、関連するグローバル最適化手法です。適応度を高める突然変異は常に受け入れられます。適応度を低下させる突然変異は、適応度の差と低下する温度パラメータに基づいて確率的に受け入れられます。SAの用語では、最大適応度ではなく最小エネルギーを追求すると言えます。SAは、比較的高い突然変異率から開始し、所定のスケジュールに従って時間とともに低下させることで、標準的なGAアルゴリズム内でも使用できます。
• タブーサーチ（TS）は、個々の解の変異をテストすることで解空間を探索するという点で、シミュレーテッドアニーリングと類似しています。シミュレーテッドアニーリングは変異した解を1つだけ生成するのに対し、タブーサーチは多数の変異した解を生成し、生成された解の中でエネルギーが最も低い解へと移動します。循環を防ぎ、解空間をより広く探索するために、部分解または完全な解のタブーリストが維持されます。タブーリストの要素を含む解へ移動することは禁止されており、解が解空間を探索するにつれてタブーリストは更新されます。
• 極値最適化（EO）は、候補解の集団を扱う遺伝的アルゴリズム（GA）とは異なり、単一の解を進化させ、最も劣るコンポーネントに局所的な修正を加えます。そのためには、個々の解のコンポーネントに品質尺度（「適合度」）を割り当てることができる適切な表現を選択する必要があります。このアルゴリズムの背後にある原理は、低品質のコンポーネントを選択的に除去し、ランダムに選択されたコンポーネントに置き換えることによって、創発的に改善していくというものです。これは、より良い解を作ろうとして優れた解を選択するGAとは明らかに相容れません。

• 交差エントロピー（CE）法は、パラメータ化された確率分布を用いて候補解を生成する。パラメータは交差エントロピー最小化によって更新され、次の反復処理でより良いサンプルが生成される。
• リアクティブサーチ最適化（RSO）は、複雑な最適化問題を解決するための探索ヒューリスティクスに、サブシンボリック機械学習技術を統合することを提唱しています。リアクティブという言葉は、重要なパラメータを自己調整するための内部オンラインフィードバックループを通じて、探索中のイベントに迅速に対応できることを示唆しています。リアクティブサーチで注目されている手法には、機械学習と統計学、特に強化学習、アクティブラーニングまたはクエリ学習、ニューラルネットワーク、メタヒューリスティクスなどがあります。