遺伝的アルゴリズム-Wikipedia、無料百科事典

遺伝的アルゴリズム – 最適なソリューションを見つけるための代替ソリューションのスペースを検索する一種のヒューリスティック。

遺伝的アルゴリズムが動作する方法は、生物学的進化の現象に誤って似ていません。なぜなら、彼らの作成者ジョン・ヘンリー・ホランドが生物学から彼の作品に影響を与えたからです。現在、進化的アルゴリズムのグループに含まれています。

この問題は、個人の特定の人口がある環境を定義します。それぞれの個人には、遺伝子型を構成する特定の情報セットがあり、表現型を作成するための基礎となっています。表現型は、環境をモデル化する適応の機能を評価することを条件として、一連の機能です。言い換えれば、遺伝子型は問題に対する提案された解決策を説明し、適応関数はこのソリューションの良好なものを評価します。

遺伝子型は染色体で構成されており、表現型がエンコードされ、場合によっては遺伝的アルゴリズムの補助情報があります。染色体は遺伝子で構成されています。

それらを他の従来の最適化方法と区別する進化的アルゴリズムの共通の特徴は次のとおりです。

1. 解決策の形に適応した遺伝子演算子の使用、
2. ソリューションの母集団の処理、さまざまなポイントからのソリューションの空間の並行検索につながり、
3. 検索プロセスを指示するために、現在のソリューションの品質は十分です。
4. ランダム要素の意図的な導入。

ほとんどの場合、アルゴリズムは次のとおりです。

1. 特定の初期母集団が描かれています。
2. 人口が評価されます（ 選択 ）。最良の適応個人は、繁殖プロセスに参加します。
3. 選択された個人の遺伝子型は、進化的演算子の対象となります。
   1. 彼らは親の遺伝子型に参加することによって互いに関連付けられています（ 十字架刑 ）、、
   2. 突然変異が実行されます。つまり、マイナーなランダム変化の導入です。
4. 2番目の（後続の）世代が生まれます。人口内の固定数の個人を維持するために、（機能評価機能に従って）最良の個人を維持するために再現され、最も弱い除去されます。適切なソリューションが見つからない場合、アルゴリズムは2番目のステップに戻ります。それ以外の場合、私たちは人口から最高の個人を選択します – 彼の遺伝子型が結果です。

遺伝的アルゴリズムの操作には、決定するために必要ないくつかの問題が含まれています。

1. 結果の代表としてゲノムを決定する
2. 適応/調整機能の決定
3. 検索オペレーターの決定

コーディングは、アルゴリズム設計の非常に重要な段階です。提案されたソリューションに関する染色体情報のコーディング方法は、発見された結果の速度と品質に大きく影響します。このような現象の理由は、スペーススペースの検索方法に対するコーディングの影響です。悪いコーディングは、最適なソリューションが検索されない空間の断片を引き起こす可能性があります！

最も一般的に使用される染色体コーディング：

• 遺伝子ベクトルは、それぞれが単一またはマルチビット整数、または実数である可能性があります。
• 木質のデータ構造を使用します。

評価を受けている個人を選択するプロセスは、特定の基準に従って発生します。これらの基準はフォームに記録されます 評価機能 もしくはそうでないか 適応関数 。遺伝的アルゴリズムは通常、最小化（最大化）に努めています。基準として、それはしばしば受け入れられます 目的関数 考慮される最適化の問題。

評価機能 [ 編集 | コードを編集します ]

評価関数はです 品質の尺度 母集団の個人（表現型、ソリューション）。各個人について、それは解決された問題の特定のモデルに基づいて計算されます。たとえば、特定の特性を持つ電気回路を設計したいと仮定しましょう。評価関数は、最小数の要素で作られたこの特性に最も類似したソリューションに報いるでしょう。最良の適応された個人は、選択プロセスで好まれます。彼らは人口の「親」になります。

選択方法 [ 編集 | コードを編集します ]

多くの選択方法があります。たとえば、So -Calledを提示できます ルーレットメソッド 。私たちは実質的にホイールを構築し、その切り抜きは個人に対応しています。個人の方が優れているほど、ホイールクリッピングが大きくなります。カリッピングのサイズは、評価の高い値が高い適応を意味する場合、評価関数の値に依存する場合があります。この取り決めでは、親としてより良い個人が選択される可能性が大きくなります。残念ながら、このようなアルゴリズムを使用した進化は、各ステップで遅くなります。個人が似ている場合、誰もが平等なクリッピングを受けます フォーチュンホイール 選択的圧力降下。アルゴリズムは、良好な個人と弱い個人によってあまり区別されません。

この不利な点はありません ランキング方法 。個人ごとに計算します 評価機能 そして、私たちはそれらをベストワーストの連続で設定します。リストの最初の人は再現する権利を得て、残りは人口から削除されます。この方法の欠点は、キュー内の連続した個人の違いに対する無感覚です。隣接するソリューションには評価関数の値が異なることが判明するかもしれませんが、ほぼ同じ量の子孫が得られます。

方法もあります マルチ基準選択 。いくつかの異なる評価関数を作成します（個人の選択された機能を個別に評価します）。たとえば、個人は1つではなく、いくつかのランクで最高のバッドで配置でき、選択プロセスはより複雑です。

ご覧のように、 選択 それは、適応が高い個人に繁殖の可能性を高めるため、その後の世代はより良く適応しています。ただし、人口遺伝子型のさまざまなものは減少します – 人口は、同じ個人のわずかに異なる（または同一の）品種によって時間とともに独占されています。これは、次の最良の解決策の一定の制限に対する収束によって明らかにされています。収束が時期尚早であり、進化が遅くなり、得られたソリューションは局所的な極端なものを示しています。それらは、予想されるグローバルソリューション、つまり、検索されたスペース全体で最高のソリューションからはほど遠い場合があります。この問題の部分的な解決策は、個々の遺伝子型のランダムな突然変異です。

各サイクル（各世代）では、進化オペレーターを使用して「処理」されています。この段階の目的は、前の段階に基づいて新しい世代を生成することです。これは、想定される環境により適している可能性があります。

交差オペレーター さまざまな人口の個人のさまざまな組み合わせ機能を組み合わせるように設計されていますが、 突然変異演算子 これらの個人の多様性を高めるように設計されています。
遺伝的アルゴリズムのクラスへのあらゆるアルゴリズムの帰属は、主に使用によって決定されます 交差オペレーター 個人のすべての集団と協力して（誤って選択された個人ではなく、事故で遺伝子型に参加するという考え）。同様に重要です 突然変異演算子 。交差点が方法として扱われている場合 搾取 解決策スペース、この突然変異は彼女への方法です 探索 。ただし、一部の問題では、その使用は重要ではないことがあります。

十字架刑 [ 編集 | コードを編集します ]

交差には、一部の（ランダムに選択された）遺伝子型の組み合わせが含まれます。協会は、2人の親の個人の子孫に一連の機能を作ることです。これは、その機能の組み合わせです（最高の機能が起こる可能性があります）。

交差方式は、染色体のコーディングと問題の詳細に依存します。ただし、いくつかの標準的な交差方法を示すことができます。

• 2つの染色体を切断し、一方の親の左部分をもう一方の親の右側の部分（バイナリおよび総磨きのコーディングを備えた染色体の場合）を接着することにより、新しい染色体を作成します。
• 論理操作の使用（バイナリコーディング）、
• 平均遺伝子値の計算（実数のコーディング）。

突然変異 [ 編集 | コードを編集します ]

この変異は、遺伝子型にランダムな変化をもたらします。そのタスクは、母集団に多様性を導入すること、つまり（少なくとも部分的に）アルゴリズムの早期収束を防ぐことです。突然変異は特定の確率で発生します – 通常は順序で 初め％ 。強すぎる突然変異は、意図したものとは逆の効果をもたらすため、それは低いです。良いソリューションを微妙に区別するのではなく、それらを破壊します。したがって、進化の過程で、特に長い染色体の場合、突然変異は二次的に重要です。

バイナリコード化された染色体の場合、2つの遺伝子が通常描画され、それらは場所に交換されるか、たとえば特定の描画された遺伝子を否定します。

整数が整数でコード化された遺伝子型の場合、順列が使用されます。

実数でコード化された遺伝子型の場合、特定の分布によるランダムな変化は、ほとんどの場合正常なランダム遺伝子に導入されます。

遺伝的アルゴリズムの使用 [ 編集 | コードを編集します ]

問題の解決、例えば [ 編集 | コードを編集します ]

遺伝的アルゴリズムは、問題が明確に定義または学習されていない場合に使用されますが、ソリューションの品質を評価する方法がわかっています。例は、たとえば、すべての都市をつなぐ最短経路を見つける必要があるセールスマンの問題であり、すべての都市を一度だけ通過できるようにすることです。提案されたルートの品質評価は迅速ですが、最適なルートを見つけることは、困難な問題などのクラスに適格です。進化的アプローチを使用する場合、優れたソリューションを非常に迅速に見つけることができますが、もちろん、クラスの問題の形式的に説明されている難易度から生じる最適なソリューションを取得することしかできません。遺伝的アルゴリズムは、分析的に計算できない極端な関数の近似を見つけるのにも優れています。

遺伝設計 [ 編集 | コードを編集します ]

遺伝的アルゴリズムは、ニューラルネットワークの母集団を管理するためにも使用されます。機械または電気回路の設計は、遺伝的アルゴリズムを示すのに最適な分野です。エンジニアは、新しいアイデアを作成する際に可能な限り最良のソリューションを見つけることではありません。必要なのは、国境条件とプロジェクトの最適化のおおよその会議だけです。遺伝的アルゴリズムは、人間とは異なり、概略的には機能しません。このプログラムは以前のプロジェクトを知らないため、いくつかの独創性を示すことがあります。さらに、人間は多くの場合、問題の誤った絵を描く非常に近似モデルに依存しています。遺伝的アルゴリズムは、複雑なモデル /問題を分析し、人が思い付かない解決策を見つけることができます。

電気回路の設計 [ 編集 | コードを編集します ]

遺伝的アルゴリズムは、電気回路の設計に使用できます。各個人の評価は、計算が簡単な要素と電気特性の数に基づいています。主な違いは、ゲノムに基づく個人の構造アルゴリズムにあります。彼は、それに基づいて電気回路を構築するプログラムの指示の形を持っています。まず、出口への簡単な接続があります。次に、プログラムは接続と要素を追加および削除します。このように組み込まれていると、回路は単純な物理的依存関係に基づいて評価されます。同様の遺伝的アルゴリズムがラダーフィルターによって構築されました。アンテナを設計するときに、類似のアプローチを使用できます。違いは、仮想ビルダーが3次元空間で移動し、波を反映する金属要素を設定することです。

新しいアイデアの1つは、FPGA（フィールドプログラム可能なゲートアレイ）システムと組み合わせて遺伝的アルゴリズムを使用することです。それらには、それらに含まれる電気回路の構造を変更するようにすばやくプログラムできるチップの形があります。遺伝的アルゴリズムは通常、シミュレートされた世代の挙動を調べます。 FPGAシステムのおかげで、実際の電気回路を進化させることができます。それらはチップに入力され、その後、それらの電気特性は実際のテスト回路によって測定されます。このようにして、進化は実際の電気システムのすべての物理的特性を使用できます。

自動化で使用されるレギュレーターも、遺伝的アルゴリズムを使用することで改善できることが判明しました。最も人気のあるコントロールアルゴリズム、すなわちPIDは、接続された微分メンバーと積分メンバーの特定のセットとして想像できます。適切な遺伝的アルゴリズムは、このようなシステムを電気回路と同様に構築できます。この方法を使用して、John R. KozaはPIDの新しいバージョンを開発しました [初め] 。

さらに、ロボットを生成する遺伝的アルゴリズムに基づいて構築された実験システムが作成され、物理環境を提出し、この環境で最高の動きの観点から最適化します。このプロジェクトはGolemと呼ばれます。

残念ながら、進化が多くの時間をとることができるようにします。実際には、これは、数百世代にわたって数千のシステムの集団を研究する必要性を意味します。今日のコンピューターのコンピューティング能力は、合理的な時間にそのようなタスクを満たすには小さすぎます。このため、コンピュータークラスターが使用されます。それぞれに特定のシステムの集団があります。時々、それらのいくつかは別のコンピューターに移行して結果を改善します。ただし、コンピューターテクノロジーの開発により、数年後に遺伝的アルゴリズムがヒットできるようになります。 サッチの下 。

検索 [ 編集 | コードを編集します ]

遺伝的アルゴリズムは、大規模なソリューションを検索するための効果的なメカニズムを提供します。グループ化はこのカテゴリのタスクに属しているため、遺伝的アルゴリズムがグループ化に使用されていることは明らかです。遺伝的アルゴリズムは、初期化からより独立しており、最適な代わりにローカルソリューションを見つける意思が少なくありません。例は、古典的なアルゴリズムの代わりに遺伝的アルゴリズムが正常に使用されるグループ化の問題です。

• ジョン・R・コザ、A。キーン、マッテセウJ.ストリーナー： 進化によって発明を行うことについて 。 （ pol。 ）） 。
• 「科学の世界」。 No. 4（140）、2003年4月、pp。40-47。 （ pol。 ）） 。
• D. E.ゴールドバーグ： 遺伝的アルゴリズムとそのアプリケーション 。ワルシャワ：Wnt、1998。 （ pol。 ）） 。
• Z. Michalewicz： 遺伝的アルゴリズム +データ構造=進化プログラム 。ワルシャワ：Wnt、1996。 （ pol。 ）） 。
• J.アラブ： 進化的アルゴリズムに関する講義 。ワルシャワ：Wnt、2001。 （ pol。 ）） 。
• R.ポリ、W.B。ラングドン、N.F。マクフィー： 遺伝子プログラミングのフィールドガイド 。 2008年。 （ 。 ）） 。 （ 本について ））
• アランM.チューリング： コンピューティング機械とインテリジェンス 。
• “マインド”。 Tom 59、Nr 236、s。 433-460; X/1950。 （ 。 ）） 。 （ 利用可能なテキスト ））
• ジョン・R・コザ： 遺伝的プログラミング：自然選択によるコンピューターのプログラミングについて 。プレス付き、1992年。 （ 。 ）） 。
• ジョン・R・コザ、ジェームズ・P・ライス： 遺伝的プログラミング：映画 。プレス付き、1992年。 （ 。 ）） 。
• ランディ・L・ハウプト、スー・エレン・ハウプト： 実用的な遺伝的アルゴリズム 。ジョン・ワイリー＆サンズ、1998年。 （ 。 ）） 。
• ジョン・R・コザ、フォレストH.ベネティイ、デビッドアンドレ、マーティンA.キーン、スコットブレイブ： 遺伝的プログラミングIII：ダーウィンの発明と問題。解決 。モーガン・カウフマン、1999年。 （ 。 ）） 。
• ジョン・R・コザ、マーティン・A・キーン、マシュー・J・ストリーダー、ウィリアム・マイドロウェック、ジェセン・ユ、グイド・ランザ： 遺伝子プログラミングIII：ビデオテープ：ヒューマン競争力のあるマシンインテリジェンス 。 Kluwer Academic Publishers、2003。 （ 。 ）） 。