導入
進化的アルゴリズム、または進化的アルゴリズムは、さまざまな問題を解決するために進化論に触発された一連のアルゴリズムです。したがって、彼らは最良の結果を見つけることを目的として、特定の問題に対する一連の解決策を開発します。これらはランダムなプロセスを繰り返し使用するため、確率的アルゴリズムです。
これらの手法の大部分は最適化問題を解決するために使用され、それらはメタヒューリスティックですが、一般的なフレームワークは必ずしも厳密な意味での最適化アルゴリズム専用ではありません。これらは、計算知能(英語ではComputational Intelligence ) の手法にも分類されます。
パラダイム
これらのアルゴリズムは、解の母集団を操作します。
進化的アルゴリズムは生物の進化に触発されており、これにより環境により適応した生物が生み出される傾向があると考えられています。
進化論によれば、これを行うためにいくつかのメカニズムが働いています。概略的には:
- 生物の特徴は主に遺伝子にコード化されており、
- 生物の各集団はすべて異なる個体で構成されており、
- 個人間の違いにより、多かれ少なかれ環境に適応できるようになります。
- 生物はその特徴の一部を子孫に伝えます。
- 最も適応した個体はより「効率的に」繁殖するため、その特徴は集団全体にさらに広がる傾向があります。
主な家族
歴史的には、1960 年代半ばから 1970 年代にかけて、3 つの大きなアルゴリズム ファミリが個別に開発されました。最初の手法は、連続最適化問題を解決するために 1965 年に I. Rechenberg によって提案された進化戦略でした。翌年、フォーゲル、オーエンズ、ウォルシュは、有限状態オートマトンを設計するための 人工知能手法として進化的プログラミングを考案しました。最後に、1975 年に、JH Holland は、組み合わせ最適化のための最初の遺伝的アルゴリズムを提案しました。 1989 年に DE Goldberg が遺伝的アルゴリズムに関する本を出版したことにより、遺伝的アルゴリズムが特に人気になりました。
その後、これらの異なるアプローチは大幅に進化し、相互に緊密になり、最終的には進化的アルゴリズムという総称の下にグループ化されました。今日、このテーマに関する文献は非常に豊富で、これらのアルゴリズムは非常に多作な研究分野とみなされています。
進化戦略
基本バージョンでは、このアルゴリズムは、突然変異演算子と選択演算子を使用して、実変数のベクトルのセットを繰り返し操作します。選択は、目的関数の値スケールに従って、最適な個人の決定論的な選択によって実行されます。突然変異ステップは古典的に、正規分布から抽出されたランダムな値を追加することによって実行されます。これらのアルゴリズムの特徴は、正規分布の分散共分散行列の自己適応です。
進化戦略の代表的なアルゴリズムは差分進化である。このクラスの方法では、部分集団間の重み付けされた差を使用して、差次的突然変異演算子にバイアスをかけます。
進化的プログラミング
歴史的に、これらのアルゴリズムは有限状態オートマトンから問題を学習するように設計されており、突然変異演算子と置換演算子のみを使用していました。ただし、今日では表現に限定されなくなりましたが、依然としてクロスオーバー演算子は使用されていません。これらは、確率的置換演算子を優先するという点で進化戦略とは異なります。
遺伝的アルゴリズム
遺伝的アルゴリズムは、最も人気のある進化的アルゴリズムです。彼らは遺伝子型と表現型を明確に区別しており、遺伝子型は一般にバイナリ方式でコード化されています。遺伝子型コーディングの選択 (それが表現型にどのように関連するか) は、遺伝的アルゴリズムにとって重要です。従来は、比例選択演算子、世代置換を使用しており、クロスオーバー演算子が主な演算子です。
他の表現や演算子を使用する進化的アルゴリズムは、多くの場合、遺伝的アルゴリズムと呼ばれますが、学者はこの誤った呼び方を避けています。
遺伝的プログラミング
これらのアルゴリズムは、歴史的に統計学習とモデリングに適用されてきたため、論理式のツリー表現を使用します。これを行うために、遺伝的アルゴリズムと同じ基本アルゴリズムが使用されます。ただし、遺伝的プログラミングは、特にプログラムの自動構築に関係します。
分布推定アルゴリズム
「古典的な」進化アルゴリズムとは異なり、これらの手法の核心は、サンプルの各点に関連付けられた確率分布の推定を通じて、最適化問題のさまざまな変数間の関係を推定することで構成されます。したがって、交差演算子や突然変異演算子は使用せず、サンプルは前の反復で推定された分布パラメーターから直接構築されます。