遺伝的アルゴリズムは、自然におけるダーウィンの進化論に触発された適応ヒューリスティック検索アルゴリズムです。 。」機械学習における最適化問題を解決するために使用されます。これは、解決に長い時間がかかる複雑な問題の解決に役立つため、重要なアルゴリズムの 1 つです。
ミニツールバーエクセル
遺伝的アルゴリズムは、さまざまな現実世界のアプリケーションで広く使用されています。 電子回路の設計、暗号解読、画像処理、人工的な創造性。
このトピックでは、遺伝的アルゴリズムで使用される基本的な用語、仕組み、遺伝的アルゴリズムの利点と制限など、遺伝的アルゴリズムについて詳しく説明します。
遺伝的アルゴリズムとは何ですか?
遺伝的アルゴリズムを理解する前に、このアルゴリズムをよりよく理解するために、まず基本的な用語を理解しましょう。
集団内に存在するすべての個体の適応度を計算した後、選択プロセスを使用して、集団内のどの個体が繁殖し、次の世代を形成する種子を生み出すかを決定します。
利用可能な選択スタイルの種類
したがって、最適化問題を解決するためのヒューリスティック検索アルゴリズムとして遺伝的アルゴリズムを定義できるようになりました。これは、コンピューティングで使用される進化的アルゴリズムのサブセットです。遺伝的アルゴリズムは、遺伝的選択と自然選択の概念を使用して最適化問題を解決します。
遺伝的アルゴリズムはどのように機能するのか?
遺伝的アルゴリズムは進化の世代サイクルに基づいて機能し、高品質のソリューションを生成します。これらのアルゴリズムは、母集団を強化または置換するさまざまな操作を使用して、改善された適合解を提供します。
基本的に、複雑な最適化問題を解決するには、次の 5 つのフェーズが含まれます。
1. 初期化
遺伝的アルゴリズムのプロセスは、母集団と呼ばれる個人のセットを生成することから始まります。ここでは、各個人が与えられた問題に対する解決策を示します。個人は、遺伝子と呼ばれる一連のパラメーターを含む、またはそれによって特徴付けられます。遺伝子を組み合わせて文字列にし、染色体を生成することで問題を解決します。初期化のための最も一般的な手法の 1 つは、ランダムなバイナリ文字列の使用です。
2. フィットネスの課題
フィットネス関数は、個人がどの程度健康であるかを判断するために使用されますか?それは、個人が他の個人と競争する能力を意味します。すべての反復で、個人は適応度関数に基づいて評価されます。フィットネス機能は、各個人にフィットネス スコアを提供します。このスコアは、再生用に選択される確率をさらに決定します。適応度スコアが高いほど、生殖のために選ばれる可能性が高くなります。
3. 選択
選択段階には、子孫を繁殖させるための個体の選択が含まれます。選択されたすべての個体は、繁殖力を高めるために 2 つのペアで配置されます。そして、これらの個体は自分の遺伝子を次世代に伝えます。
使用可能な選択方法には次の 3 種類があります。
- ルーレットホイールの選択
- トーナメントセレクション
- ランクベースの選択
4. 複製
選択プロセスの後、再生ステップで子の作成が行われます。このステップでは、遺伝的アルゴリズムは親集団に適用される 2 つの変動演算子を使用します。再生フェーズに関与する 2 つの演算子を以下に示します。
- ワンポイントクロスオーバー
- 2点クロスオーバー
- カラーリングのクロスオーバー
- 継承可能なアルゴリズムのクロスオーバー
交叉点に達するまで、両親の遺伝子が相互に交換されます。これらの新しく生成された子孫が集団に追加されます。このプロセスはクロスオーバーとも呼ばれます。利用可能なクロスオーバー スタイルの種類:
突然変異オペレーターは、集団の多様性を維持するために子孫 (新しい子供) にランダムな遺伝子を挿入します。これは、染色体の一部のビットを反転することで実行できます。
突然変異は、早期収束の問題の解決に役立ち、多様化を強化します。以下の画像は、突然変異のプロセスを示しています。
利用可能な突然変異スタイルの種類、
ディクストラ
5. 終了
再生フェーズの後、停止基準が終了の基準として適用されます。アルゴリズムは、閾値適合解に達すると終了します。最終的なソリューションが母集団内の最適なソリューションとして特定されます。
単純な遺伝的アルゴリズムの一般的なワークフロー
遺伝的アルゴリズムの利点
- 遺伝的アルゴリズムの並列機能は最高です。
- 離散関数、多目的問題、連続関数などのさまざまな問題の最適化に役立ちます。
- 時間の経過とともに改善される問題の解決策を提供します。
- 遺伝的アルゴリズムには派生情報は必要ありません。
遺伝的アルゴリズムの限界
- 遺伝的アルゴリズムは、単純な問題を解決するための効率的なアルゴリズムではありません。
- 問題に対する最終的な解決策の品質を保証するものではありません。
- 適応度値を繰り返し計算すると、計算上の問題が発生する可能性があります。
遺伝的アルゴリズムと従来のアルゴリズムの違い
- サーチ スペースは、問題に対する考えられるすべての解決策のセットです。従来のアルゴリズムでは、1 セットの解のみが維持されますが、遺伝的アルゴリズムでは、探索空間内の複数の解のセットを使用できます。
- 従来のアルゴリズムでは検索を実行するためにより多くの情報が必要ですが、遺伝的アルゴリズムでは個人の適応度を計算するために目的関数が 1 つだけ必要です。
- 従来のアルゴリズムは並行して動作できませんが、遺伝的アルゴリズムは並行して動作できます（個体の適応度の計算は独立しています）。
- 遺伝的アルゴリズムの大きな違いの 1 つは、継承可能なアルゴリズムがシーカーの結果に直接作用するのではなく、染色体として関連付けられることが多いその表現 (またはレンダリング) に作用することです。
- 従来のアルゴリズムと遺伝的アルゴリズムの大きな違いの 1 つは、候補解に直接作用しないことです。
- 従来のアルゴリズムは最終的に 1 つの結果しか生成できませんが、遺伝的アルゴリズムは異なる世代から複数の最適な結果を生成できます。
- 従来のアルゴリズムは最適な結果を生成する可能性が高くありませんが、遺伝的アルゴリズムは最適な全体的な結果を生成することを保証しませんが、クロスオーバーやミューテーションなどの遺伝的演算子を使用するため、問題に対して最適な結果が得られる可能性も高くなります。
- 従来のアルゴリズムは本質的に決定論的ですが、遺伝的アルゴリズムは本質的に確率的かつ確率的です。