Main Content

このページは機械翻訳を使用して翻訳されました。元の英語を参照するには、ここをクリックします。

遺伝的アルゴリズムとは何ですか?

遺伝的アルゴリズムは、生物学的進化を促進するプロセスである自然選択に基づいて、制約付きおよび制約なしの最適化問題の両方を解決する方法です。遺伝的アルゴリズムは、個々のソリューションの集団を繰り返し変更します。各ステップで、遺伝的アルゴリズムは現在の集団から親となる個体を選択し、それを使って次の世代の子供を生み出します。世代を重ねるごとに、個体群は最適な解決策に向かって「進化」していきます。遺伝的アルゴリズムを適用すると、目的関数が不連続、微分不可能、確率的、または高度に非線形である問題など、標準的な最適化アルゴリズムに適さないさまざまな最適化問題を解決できます。遺伝的アルゴリズムは、一部のコンポーネントが整数値に制限されている 混合整数計画法 の問題に対処できます。

このフローチャートは、主要なアルゴリズムの手順の概要を示しています。詳細については、遺伝的アルゴリズムの仕組み を参照してください。

Flow chart: create initial population, score and scale population, retain elite, select parents, produce crossover and mutation children, return to score and scale

遺伝的アルゴリズムは、各ステップで 3 つの主なタイプのルールを使用して、現在の集団から次の世代を作成します。

  • 選択ルールは、次の世代の集団に貢献する と呼ばれる個体を選択します。選択は一般的に確率的であり、個人のスコアに依存する場合があります。

  • 交差ルールは、2 つの親を組み合わせて次の世代の子を形成します。

  • 突然変異ルールは、個々の親にランダムな変更を適用して子を形成します。

An elite child is identical to its parent. A crossover child gets some of each parent. A mutation child comes from one parent, and includes a change.

遺伝的アルゴリズムは、次の表にまとめられているように、主に 2 つの点で従来の微分ベースの最適化アルゴリズムと異なります。

古典的アルゴリズム遺伝的アルゴリズム

各反復で 1 つのポイントを生成します。点のシーケンスは最適な解に近づきます。

各反復でポイントの集団を生成します。集団内の最良の点は、最適な解決策に近づきます。

決定論的な計算によってシーケンス内の次のポイントを選択します。

乱数ジェネレータを使用した計算によって次の集団を選択します。

通常、ローカル ソリューションにすぐに収束します。

通常、収束するには多くの関数評価が必要です。局所的または全体的な最小値に収束する場合と収束しない場合があります。

関連するトピック