遺伝的アルゴリズムの紹介

遺伝的アルゴリズムは、「適者の生存」、染色体交差、突然変異などの自然な進化プロセスをシミュレートすることにより、問題の最良の解決策を求めるプログラムです。この記事では、遺伝的アルゴリズムの執筆方法を簡単に紹介し、独自のアルゴリズムを作成する際に考慮する必要があるいくつかの重要な要因について説明し、遺伝的アルゴリズムの実用的なアプリケーションの例をいくつか提供します。

キーポイント

• 遺伝的アルゴリズムは、「適者の生存」などの進化プロセスをシミュレートし、選択、クロスオーバー、突然変異などのメカニズムを使用して、複雑な問題に対する最適な解を見つけます。
• 遺伝的アルゴリズムでは、潜在的なソリューションは染色体として表され、その適用性は、繁殖のために選択される確率を決定するフィットネス関数によって評価されます。
• クロスオーバープロセスは、一対の親ソリューションの機能を組み合わせて新しい子孫を作成しますが、バリエーションは子孫にランダムな変化をもたらし、遺伝的多様性を維持し、新しいソリューションを発見する可能性があります。
• 遺伝的アルゴリズムは、大規模で複雑なソリューションスペースを効果的に探索できるため、従来の検索および最適化方法で解決が困難な問題に非常に効果的です。
• 遺伝的アルゴリズムの実用的なアプリケーションは、パフォーマンス特性を強化したアンテナの設計から、実際の問題を解決する際の汎用性と力を示すWebデザインの最適化にまで及びます。

不明な情報の亀裂

時間は2369年で、人間は星の海に広がっています。あなたは、忙しい深い星の基地に駐留している若くて知的な医師であり、星間旅行者、商人、時折の無法者と賑わっています。あなたが到着して間もなく、基地の店主があなたに興味を持ちました。彼は自分が単なる仕立て屋であると主張しているが、噂によると、彼は特に邪悪な体制のために働いている秘密のエージェントだと言っている。

あなたは毎週一緒に昼食を取り始め、政治から詩までのトピックについて話し合います。数ヶ月後でも、彼がロマンチックな感情を表現しているのか、それとも秘密を奪っているのかはまだわかりません（確かに秘密はありません）。多分両方。

あなたは医療小屋のオフィスに戻りましたが、彼が今言ったことについてまだ考えていました。突然、以前に近くのコンピューターで実行した遺伝子シーケンスシミュレーション実験により、アイデアが得られました。あなたはパスワード復号化の専門家ではありませんが、遺伝学の専門知識を使用して彼の情報を解読できるかもしれません！

いくつかの理論

最初に述べたように、遺伝的アルゴリズムは、進化を駆動してソリューションを検索する操作を使用するプログラムです。多くの反復後、アルゴリズムは、可能な一連のソリューションから最高の候補（推測）を選択し、それらを再結合し、どの組み合わせがソリューションに近づくかをチェックします。貧しい候補者は廃棄されます。

上記のシーンでは、秘密のメッセージのキャラクターはA-Z、スペース、または基本的な句読点です。これが次の32文字「アルファベット」を与えるとします：abcdefghijklmnopqrstuvwxyz - 。、！？それらは正しいです。それぞれの可能性を確認するには時間がかかりすぎます。代わりに、遺伝的アルゴリズムは12文字をランダムに選択し、テーラー/スパイに彼の情報の結果がどれだけ近いかを評価するように依頼します。これは、スコアが将来の候補者を微調整できるため、ブルートフォース検索よりも効果的です。フィードバックにより、各推測のフィットネスを測定し、できれば行き止まりで時間を無駄にしないようにすることができます。 3つの推測を行ったとします：homlk？wsrzdj、bgk ka！qtpxc、xelpocv.xlf！。最初の候補者は248.2、2番目は632.5、3番目は219.5でした。スコアの計算方法は状況によって異なりますが、これについては後で説明しますが、候補者とターゲット情報の偏差に基づいていると仮定しましょう。完全なスコアは0です（つまり、偏差なし、候補とターゲットは同じ）、より高いスコアは偏差が大きくなることを意味します。 248.2と219.5のスコアを持つ推測は、635.5のスコアを持つ推測よりも秘密情報の内容に近い。 将来の推測は、最高の試みの組み合わせによって行われます。候補者を結合するには多くの方法がありますが、今では単純なクロスオーバーアプローチを検討しています。新しい推測の各キャラクターは、最初または2番目の親候補から50〜50の確率をコピーしています。 homlk？wsrzdjとxelpocv.xlf！の2つの推測を取ると、子孫の最初の文字はHの確率が50％、xの50％の確率があり、2番目の文字はoまたはeです。すぐ。子孫はこんにちは？W.rld！

クロスオーバーで新しい候補者を生成する

ただし、親候補の値のみを使用する場合、複数の反復に問題があるかもしれません：多様性の欠如。 1つの候補者がすべてのAで構成され、もう1つの候補がすべてのBで構成されている場合、クロスオーバーによって生成された子孫はAとBでのみ構成されます。ソリューションにCが含まれている場合、私たちは残念です。

このリスクを軽減し、多様性を維持しながら、ソリューションの範囲を狭めながら、わずかな変化を導入することができます。 50-50セグメンテーションを直接行うのではなく、アルファベットのあらゆる値を置き換える確率がわずかになります。この突然変異を通じて、子孫はHello Worldになるかもしれません！

突然変異は物事を新鮮に保ちます！

期待によると、遺伝的アルゴリズムは多数の遺伝科学語彙を借ります。それで、さらに議論する前に、いくつかの条件を改良しましょう：

• 対立遺伝子：遺伝的アルファベットのメンバー。対立遺伝子の定義はアルゴリズムに依存します。たとえば、0と1は、バイナリデータの処理に使用される遺伝的アルゴリズムの対立遺伝子であり、コードを処理するために使用されるアルゴリズムは機能ポインターなどを使用できます。私たちの秘密情報シナリオでは、対立遺伝子はアルファベットの文字、スペース、さまざまな句読点です。
• 染色体：候補ソリューション。私たちのシナリオでは、homlk？wsrzdj、xelpocv.xlf！
• 遺伝子：染色体の特定の場所にある対立遺伝子。染色体homlk？wsrzdjの場合、最初の遺伝子はh、2番目の遺伝子はO、3番目の遺伝子はmなどです。
• 集団：問題の解決策として提案された1つ以上の候補染色体のコレクション。
• 世代：アルゴリズムの特定の反復中の人口。ある世代の候補者は、次世代の集団を生成するために遺伝子を提供します。
• フィットネス：候補者が望ましいソリューションにどれだけ近いかの尺度。適応型染色体は、遺伝子を将来の候補に渡す可能性が高くなりますが、適応性の低い染色体は廃棄される可能性が高くなります。
• 選択：複製の候補を選択するプロセス（新しい候補染色体の作成に使用）し、他の候補者を破棄します。弱い候補を選択するための耐性が異なるさまざまな選択戦略があります。
• 複製：1つ以上の候補者の遺伝子を組み合わせて新しい候補者を生産するプロセス。ドナー染色体は父親と呼ばれ、生成された染色体は子孫と呼ばれます。
• 突然変異：多くの世代の遺伝的多様性の喪失を防ぐために、子孫に異常な遺伝子をランダムに導入しました。

いくつかのコードを見せてください！

高度な概要と用語リストを考えると、今すぐコードを見たいと思うかもしれません。それでは、秘密の情報問題を解決するJavaScriptコードを見てみましょう。読書プロセス中に、どの方法が「voilerplateコード」と見なされる可能性があるか、どの方法が解決しようとしている問題により密接に関連しているかを考えるように勧めます。

// ... (Candidate class and GeneticAlgorithm class code as provided in the original text) ...

最初に候補データオブジェクトを定義します。これは、染色体とフィットネススコアをペアリングするだけです。便利なため、静的なソート方法も添付されています。

次に、遺伝的アルゴリズム自体を実装する遺伝子測量クラスがあります。

コンストラクターは、シミュレーションに必要なさまざまなパラメーターを解くオブジェクトを使用します。これは、シミュレーションが実行される制約を定義する遺伝的アルファベット、ターゲットメッセージ、およびその他のパラメーターを指定する方法を提供します。上記の例では、世代ごとに100人の候補者が100人の人口を期待しています。これから、繁殖のために選択されるのは40個の染色体のみです。突然変異を導入する可能性は3％あり、それが発生した場合、2つの遺伝子に変化します。最大値は、100万世代後に解決策に収束しない場合、とにかくスクリプトを終了します。

アルゴリズムを実行するときに提供される年齢の人口、選択サイズ、最大数が非常に少ないことに言及する価値があります。より複雑な問題には、より大きな検索スペースが必要になる場合があり、これにより、アルゴリズムのメモリ使用量と実行にかかる時間が増加する場合があります。ただし、小さなバリアントパラメーターを使用することを強くお勧めします。彼らが大きくなりすぎると、フィットネスに基づいて繁殖候補者の利点が失われ、シミュレーションがランダムに検索され始めます。

randomint（）、init（）、run（）などのメソッドは、ボイラープレートと見なされる場合があります。しかし、ボイラープレートがあるからといって、シミュレーションに実際的な影響を与えないという意味ではありません。たとえば、遺伝的アルゴリズムはランダム性を大きく使用します。組み込みのMath.random（）関数は当社の目的に適していますが、他の問題については、より正確なランダムジェネレーターが必要です。 crypto.getRandomValues（）は、より強力な暗号化ランダム値を提供します。

パフォーマンスも考慮されます。この記事では明確で理解しやすいように努めていますが、操作が繰り返されることを忘れないでください。ループ内のコードをマイクロ最適化し、より効率的なメモリデータ構造を使用し、コードを機能/メソッドに分離する代わりに、実装言語に関係なく、コードをインライン化する必要がある場合があります。

calcfitness（）、select（）、reprod（）、さらにはstop（）メソッドの実装は、解決しようとしている問題に固有のものです。

calcfitness（）特定の予想された基準に基づいて染色体のフィットネスを測定する値を返します。私たちの場合、それは秘密のメッセージとどれだけうまく一致しますか。フィットネスの計算は、ほとんどの場合、状況固有です。たとえば、2つの値間のハミング距離またはレビンシュタイン距離を計算し、複数の測定値を組み合わせることさえできます。最終的に、Fitness関数は、Booleanの「Fit」/「Not Fit」だけでなく、手元の問題に基づいて有用な測定値を返すことが重要です。

select（）メソッドは、エリート選択戦略を示しています。繁殖に最適な候補者のみが選択されています。前述したように、人口の個々の候補者のセットから最も適切な候補者を選択するトーナメントの選択や、候補者のプレッシャーの選択にますます大規模で大規模な候補者を課すボルツマン選択など、他の戦略があります。これらの異なる方法の目的は、染色体がすぐに明らかにならない場合でも、後で有益であることが証明される可能性のある遺伝子を提供する機会を確保することです。これらおよびその他の選択戦略の詳細な説明、および実装の例は、オンラインで簡単に見つけることができます。

さまざまな選択戦略を説明する

遺伝子を組み合わせる多くの方法があります。私たちのコードは、均一なクロスオーバーを使用して子孫を作成します。そこでは、各遺伝子が親から選択する可能性が同じです。他の戦略は、別の親の遺伝子ではなく、ある親の遺伝子に向かう傾向があります。もう1つの一般的な戦略はKポイントクロッシングで、染色体が

kポイントで分割され、結合して子孫を生成する1フラグメントになります。交差点は固定またはランダムに選択できます。

k-point交差戦略の説明 2つの親染色体に限定されない。ランダムポリゴンを描画して画像を進化させるアルゴリズムを検討してください。この場合、染色体は画像データとして実装されています。各世代で、最も適切な画像が親として母集団から選択され、すべての子供候補者は、自分のポリゴンを親コピーに描くことによって生成されます。親染色体/画像は、親のユニークなバリエーション/図面です。

遺伝的アルゴリズムの実用的な応用

遺伝的アルゴリズムは、エンターテイメントと収益性の両方に使用できます。おそらく、遺伝的アルゴリズムの実用的な応用の最も一般的な2つの例は、BoxCar 2DとNASAによって進化したXバンドアンテナです。

BoxCar 2Dは、遺伝的アルゴリズムを使用して、シミュレートされた地形を通過できる最高の「車」を進化させるシミュレーションです。車は8つのランダムベクターで構成され、車輪をランダムポイントに接続します。プロジェクトのWebサイトは、BoxCar2D.comで見つけることができます。これは、Aboutページにアルゴリズムを簡単に紹介し、最高のデザインのいくつかを示すランキングリストを提供します。残念ながら、このサイトはフラッシュを使用しており、多くの人にアクセスできないようになりました。この場合、興味がある場合はYouTubeでさまざまな画面録音を見つけることができます。また、rednuht.org/genetic_cars_2にあるHTML5テクノロジーを使用して、Rafael Matsunagaによって書かれた同様の（優れた）シミュレーションをチェックアウトすることもできます。

車はBoxCar 2Dで進化し、2006年にBoxCar 2Dランキングの写真

で進化し、NASAのSpace Technology 5ミッションは宇宙のさまざまな新しいテクノロジーをテストしました。これらのテクノロジーの1つは、遺伝的アルゴリズムを使用して設計された新しいタイプのアンテナです。新しいアンテナを設計することは、非常に高価で時間のかかるプロセスです。特別な専門知識が必要であり、需要の変更またはプロトタイプが予想どおりに実行されない場合、多くの場合、set折が発生します。進化したアンテナの作成時間は短く、より高いゲインと低電力消費があります。設計プロセスを議論する論文の全文は、オンラインで無料で利用できます（進化的アルゴリズムを使用した自動アンテナ設計）。遺伝的アルゴリズムは、より高いパフォーマンスのために既存のアンテナ設計を最適化するためにも使用されています。

そのカテゴリでは、自動化されたアンテナデザインペーパーからの写真は、Webデザインでさえ使用されています。 Elijah Menschによる高度なプロジェクト（インタラクティブな遺伝的アルゴリズムを適用してWebサイトの設計を最適化）は、それらを使用して、A/Bテストを使用してCSSルールを操作し、フィットネスを評価することにより、ニュース記事Carouselsを最適化します。

第一世代と第9世代に最適なレイアウトである写真は、最適化されたウェブサイトのデザインの論文

結論

これまでのところ、遺伝的アルゴリズムが何であるかを基本的に理解し、自分の研究で遭遇する可能性のあるリソースを解釈するために、語彙に十分に精通している必要があります。ただし、理論と用語を理解することは、作業の半分にすぎません。独自の遺伝的アルゴリズムを作成する場合は、特定の問題も理解する必要があります。開始する前に、自問するためのいくつかの重要な質問があります：

染色体としての問題をどのように表現できますか？私の有効な対立遺伝子は何ですか？
目標が何であるか知っていますか？つまり、私は何を探していますか？それは特定の値か、フィットネスが特定のしきい値を超えるソリューションですか？
候補者のフィットネスを定量化するにはどうすればよいですか？
候補者を組み合わせて変異させて、新しい候補ソリューションを生成するにはどうすればよいですか？

私はまた、プログラムが自然からインスピレーションを引き出す方法を理解するのを手伝ってくれることを願っています。フォーラムで自分の考えを自由に共有してください。

遺伝的アルゴリズムに関するよくある質問

• 遺伝的アルゴリズム（GA）とは何ですか？遺伝的アルゴリズムは、自然選択プロセスに触発されたヒューリスティックな検索と最適化手法です。シミュレーションの進化の原則を通じて、最適化と検索問題に対する近似ソリューションを見つけるために使用されます。
• 遺伝的アルゴリズムはどのように機能しますか？遺伝的アルゴリズムは、連続した世代にわたって候補ソリューションの集団を進化させることにより機能します。このプロセスには、選択、クロスオーバー（組換え）、突然変異、および人口の個人の評価が含まれ、ソリューションの品質を繰り返し改善することを目指しています。
• 遺伝的アルゴリズムはどのような問題に適していますか？遺伝的アルゴリズムは広く使用されており、スケジューリング、ルーティング、機械学習、機能の最適化を含むがこれらに限定されないさまざまな最適化と検索の問題に適用できます。
• 遺伝的アルゴリズムのパラメーターを選択する方法は？人口サイズ、変動性、クロスオーバーレートなどのパラメーターは、特定の問題とソリューション空間の特性に依存します。実験とチューニングは、特定の問題に最適なパラメーター値を見つけるための一般的なプラクティスです。
• 遺伝的アルゴリズムにおけるフィットネス機能の役割は何ですか？フィットネス関数は、個々のソリューションが特定の問題でどのように機能するかを定量化します。選択プロセスを導き、最適化の目標に積極的に貢献するソリューションを促進します。

以上が遺伝的アルゴリズムの紹介の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。