問題タブ [evolutionary-algorithm]

モンテカルロ法と進化的アルゴリズムの関係は? 一見すると、それらは複雑な問題を解決するために使用される、無関係なシミュレーション方法のように見えます。それぞれどの種類の問題に最適ですか? 彼らは同じ一連の問題を解決できますか? 2つの関係は何ですか（もしあれば）？

誰かが分化進化法を説明してもらえますか? ウィキペディアの定義は非常に専門的です。

簡単な例が続く簡単な説明をいただければ幸いです:)

決定問題は、単純な正しい/間違ったフィットネス メジャーを最適化/進化させることができないため、進化的アルゴリズムでの使用には適していません。では、決定問題を最適化問題に変換するための方法/テクニックは何ですか?

たとえば、私は現在、個人のフィットネスが生成される出力に大きく依存する問題に取り組んでいます。遺伝子の順序に応じて、個人は出力を生成しないか、完全な出力を生成するか、つまり「中間」を生成しません (したがって、登る丘はありません)。個体の遺伝子配列のわずかな変化が、個体の適応度に劇的な影響を与える可能性があるため、進化的アルゴリズムを使用すると、本質的にランダム検索になります。

あなたが知っているなら、いくつかの文献の参考文献はいいでしょう。

Roger Alsing は、C# を使用してモナリザを再現するための進化的アルゴリズムを作成しました。彼のアルゴリズムは単純です。

1. サイズ 2 のランダムな母集団を生成します。
2. 最も適合しない個人を最も適合するクローンに置き換えます。
3. 個人の 1 人を変異させる。
4. 手順 2 に進みます

Watchmakerと呼ばれる Java Evolutionary Algorithm フレームワークがあります。著者は、本物の遺伝的アルゴリズムを使用してモナリザの問題を再実装しました: http://watchmaker.uncommons.org/examples/monalisa.php

最初はうまくいきましたが、30 分以内に Watchmaker の実装は不十分な概算で停滞し、Roger の実装はほぼ完了に見えます。設定をいじってみましたが、あまり役に立ちませんでした。Watchmaker の実装が Roger の実装よりもずっと遅いのはなぜですか? また、停滞しているのはなぜですか?

リンク:

• ロジャーのソースコード
• 時計職人のソースコード

コザがここで説明しているように、遺伝的プログラミングを使用して食物採餌行動が可能な進化中のアリを見ています。時間ステップごとに、各アリをループして、そのコンピューター プログラムを実行します (コロニー内のすべてのアリで同じプログラムが使用されます)。MOVE-ONE-STEP現在、TURN-LEFT、 、 などの単純な命令を定義していますが、引数を順番に実行するTURN-RIGHT関数もあります。PROGN私が抱えている問題は、PROGN命令を順番に実行できるため、アリは単一の時間ステップで複数のアクションを実行できることです。自然とは異なり、アリを並行して走らせることはできません。つまり、他のすべてのアリが自分の順番を待っている間に、1 つのアリがいくつかのアクションを実行して環境を操作する可能性があります。

これが通常の方法なのか、それとももっと良い方法があるのか​​ 疑問に思っています。コザはそれについて何も言及していないようです。つまり、シナリオを拡張して、単一の時間ステップで一度だけ発生するものに依存する可能性のある他のエージェント (敵など) を使用したいと考えています。

私は本のいくつかの紹介セクションと両方のトピックに関するいくつかの論文を読みました、そしてこれらの2つの方法はほとんどまったく同じであるように私には見えます。とはいえ、まだ実際に深く研究する時間がなかったので、間違っているかもしれません。

遺伝的アルゴリズムと進化戦略の違いは何ですか？それらの違いは何ですか？また、どこが似ていますか？

遺伝的アルゴリズムのクロスオーバー部分について読むとき、本や論文は通常、複製される2つの選択された候補のデータのビットを単純に交換する方法を指します。

実際の業界アプリケーションに実装された遺伝的アルゴリズムの実際のコードはまだ見ていませんが、単純なデータ型を操作するのに十分であるとは想像しがたいです。

私は常に、遺伝的アルゴリズムのさまざまな段階が、単一の整数の一部のビットを単に交換するのではなく、複雑な数学演算を含む複雑なオブジェクトに対して実行されることを想像していました。

ウィキペディアでさえ、クロスオーバーのためのこれらの種類の操作をリストしているだけです。

私は何か重要なものを見逃していますか、それともこれらの種類のクロスオーバーメソッドは本当に使用されている唯一のものですか？

私たちのプログラムでは、何年も前から遺伝的アルゴリズムを使用して、n 個の変数の問題を解決しており、それぞれが m 個の可能な値の固定セットを持っています。これは通常、変数が 1,000 個まで、可能性が 10 個の場合にうまく機能します。

現在、変数ごとに 2 つの可能性 (オン/オフ) しか存在しない新しいタスクがありますが、おそらく 10,000 以上の変数を持つシステムを解決する必要があります。既存の GA は機能しますが、ソリューションは非常にゆっくりとしか改善されません。

私が見つけたすべての EA は、連続または整数/浮動小数点数の問題用に設計されています。バイナリ問題に最も適しているのはどれですか?

遺伝的アルゴリズムを使用して解決しようとしている最適化の問題があります。基本的に、10 個のバインドされた実数値変数 (-1 <= x <= 1) のリストがあり、そのリストのいくつかの関数を最大化する必要があります。問題は、リスト内の最大 4 つの変数のみが != 0 (サブセット条件) になる可能性があることです。

数学的に言えば: ある関数 f の場合: [-1, 1]^10 -> R min f(X) st |{var in X with var != 0}| <= 4

f の背景: この関数は、Sum x*weight などのナップザック目的関数とは似ていません。

私がこれまでに試したこと：

ゲノム [-1, 1]^10 に対する基本的な遺伝的アルゴリズムであり、変数に 1 点交差といくつかのガウス変異があります。最初の 4 つの非ゼロ (0に十分近いゼロ) の値のみを使用して、フィットネス関数のサブセット条件をエンコードしようとしました。このアプローチはうまく機能せず、アルゴリズムは最初の 4 つの変数でスタックし、それを超える値を使用することはありません。このアプローチがうまく機能する 01-knapsack 問題のある種の GA を見ましたが、どうやらこれはバイナリ変数でのみ機能するようです。

次に何を試してみるのをお勧めしますか?

私は現在、遺伝的アルゴリズムに関する論文を書いています。アルゴリズムをいつ停止する必要があるかを決定する終了条件について、小さなサブセクションを作成したいと思います。

こんな素敵なサイトを見つけました：

http://www.nd.com/genetic/termination.html

これには、遺伝的アルゴリズムの終了条件を決定するいくつかの優れた方法がリストされています。しかし、私の論文を担当している教授は、ランダムなインターネット サイトを情報源として受け入れることに非常に消極的です。

これらの終了条件に関するより多くの情報を含み、さまざまな方法の長所または短所を詳しく説明している本をいくつかお勧めできますか (電子書籍の形で手に入れることができれば非常に良いでしょう)。