進化的アルゴリズム:最適な再人口の内訳
https://stackoverflow.com/questions/131165
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
タイトルにすべてが含まれていますが、進化的アルゴリズムに興味がある人のために、以下にその概要を示します。
EA では、基本的な前提として、特定の数の生物 (実際には単なるパラメーターのセット) をランダムに生成し、それらを問題に対して実行し、上位のパフォーマーを生き残らせるということです。
次に、生存者の交雑種、生存者の突然変異、および一定数の新しいランダムな生物の組み合わせを再配置します。
それを数千回繰り返すと、効率的な生物が誕生します。
また、生物の複数の「島」を導入するようなことを行う人もいます。これは、時々交雑することを許可される別々の個体群です。
そこで、私の質問は次のとおりです。最適な再人口率はどれくらいですか?
私は上位 10% の成績を維持し、30% の交雑種と 30% の突然変異を再移植してきました。残りの 30% は新しい生物のためのものです。
私は複数の島の理論も試しましたが、それに関するあなたの結果にも興味があります。
これがまさに EA が解決できる種類の問題であるということは私にとっても間違いありません。それを試している人を知っていますか?
前もって感謝します！
解決
私は最初、有機システムがどのようなものであると考えているかをモデル化しようとしました。最終的にはこれではダメだと判断し、10％を維持、20％を突然変異、60％を交雑、10％をランダムというように、より積極的になった。
その後、上位 10% がすべてほぼ同じであることに気づきました。そこでランダムを 30% に増やしました。それは一部には役に立ちましたが、あまり役に立ちませんでした。
複数のアイランド、世代スキップ、および再シードを試してみたところ、より良い結果が得られましたが、それでも非常に満足のいくものではなく、上位 10% の変動がほとんどなく、結果を得るまでに非常に長い世代数が必要でした。ほとんどのコードは、私のフィットネス評価をハッキングする方法を学習しました。
優秀な人材を獲得するのは非常に簡単なので、多くの人材を残しておくことを心配する必要はありません。交雑種はプラスの特性とマイナスの特性を削減するのに役立つため、便利ですが、実際に入手したいのは、多くの優れたランダム交配です。突然変異と新しいランダムに焦点を当てて機能を導入し、交雑種とトップパフォーマーが最良のものを追跡し、ゆっくりと洗練させていきます。IE:最後の世代に基づくものは、より良い局所最大値を見つけるだけであり、ランダムはより良い大域最大値を見つけます。
私は、ショウジョウバエの飛行経路のランダム性に関する最近の記事など、自然現象を観察することであなたの質問に対する最適な答えが見つかると今でも信じています。
おそらく最良の答えは、それを実行して微調整することです。かなり大幅に微調整することを恐れないでください。母集団は堅牢です。保存して続行する方法を必ず実装してください。
他のヒント
私がこれまでに出会った GA と EA に関する最高のリソースは、John Koza の書籍でした。 遺伝的プログラミング. 。彼は、ゲノムのエンコード技術、ランダム突然変異、育種、適応度関数の調整などのトピックを詳しく取り上げています。
私個人としては、教育目的で少数のシミュレータを作成しただけです。私が発見したのは、これらのパーセンテージをどのように調整したかは、使用していたフィットネス関数の詳細、導入したランダムな突然変異の量、および突然変異と繁殖をどの程度「賢く」しようとしたかに関係しているということでした。 「賢い」ミューテーターとクロスオーバー ロジックを作成しようとすると、母集団の適応度スコアが速く向上します。また、突然変異の確率を保守的にしすぎていたこともわかりました。最初の実行は極大値に達し、そこから抜け出すのは難しい。
これらはどれも具体的な答えを与えてくれませんが、具体的な答えがあるとは思えません。GA はその性質上予測不可能であり、その種のパラメーターを調整するのはまだ少し技術が必要かもしれません。もちろん、これらのパラメーターを染色体として使用し、実行中のベース GA でより迅速な適合を生み出す設定を検索して、いつでもメタ GA を試すことができます。
どのような「メタ」を取得したいかによって異なります。
これは（文献や文献で）激しい議論が行われています。 メラニーらの書籍) 非常にドメイン固有のトピックと思われます。n 個のパラメータを持つ 1 つのタイプの 1 つの問題で機能するものは、別の問題、別のドメイン、または別のパラメータ セットでは機能することはほとんどありません。
したがって、TraumaPony が提案したように、解決している問題ごとに自分で調整するか、最適化するものを作成します。最善の方法は、すべての「ノブ操作」と微調整実験を追跡して、ソリューションの領域を計画し、その領域内で最適化する方法をすばやく把握できるようにすることです。また、山登りなどの別のテクニックも試して、打ち負かすベースラインを確立しましょう。
@カイル・バートン:クロスオーバー vs.突然変異率も 常に議論されている 各クラスの問題で GA と GP に引き渡されます。
上位 X% のパフォーマンスを定量化する方法があると仮定すると、ハードコードされたしきい値を使用する代わりに、パフォーマンスの分布を分析し、パフォーマンスの最初の大幅な低下の範囲内のどこかにカットオフを設定してから調整することをお勧めします。クロスブレッド、突然変異、新しい生物がギャップを埋めます。こうすることで、多くのバリエーションが成功し、非常に「生産的な」実行ができた場合、かなりの数の高いパフォーマンスを発揮する人が失われることはありません。また、「非生産的な」作業を行っている場合は、代わりに配置されるべきより新しい生物を優先して、既存の生物をさらに廃棄することができます。
私は、親染色体のいくつかの遺伝子に突然変異と交叉を設定することによって、集団の多様性を高めることにある程度成功しました。
これは、突然変異率がゼロに低下するまで機能します。これを行うための定期的な進化圧力が存在する可能性が高いため、これらの遺伝子の比率が最小限であることを確認するように努める必要があります。
実際には、私は複数染色体の遺伝子型を選択しました。一方の染色体は、もう一方の生殖機能のためにコード化されています。より小さい「再生産染色体」は、突然変異と交叉の合理的な固定率を持っていました。
これにより、典型的なプラトーと人口の集中が止まることがわかりました。
余談ですが、私は各子に対して交叉と突然変異の両方を行うことが多いです。
世代別の GA の場合、私はエリート主義を完全に避けるように努めますが、複数の島から人口が集まる場合は、各島のトップエリートを維持します。島々が一つになれば、エリート全員が一緒に繁殖することができます。
2 番目の GA を使用して 1 番目の GA の最適パラメータを決定することを示唆する回答がいくつかあるようですが、2 番目の最適パラメータを決定する方法については言及されていません。このアプローチを提案する人々の宗教的信念について疑問を抱かずにはいられません...
他の人が述べたように、最適な組み合わせは、特定の問題や、解決空間のサイズなど、その他の問題固有の要因によって異なります。
ある世代から次の世代への進化の内訳について議論する前に、各世代の規模を考慮することが重要です。一般に、私のアプローチは、かなり多様な個人からなるかなり大規模な母集団 (約 10 万人から 50 万人) から始めることですが、これはコザ氏がいくつかの著作で示唆していることです。最初からこの多様性を実現するには、ソリューション空間をバケットに分割し、少なくとも一定数の個人が各バケットに入るようにすることができます。（例えば。各個人のツリー表現がある場合は、深さ 2、3、...、max_ Depth の等しい量が作成されるようにしてください)
実際の質問に関する限り、それにアプローチする明確な方法はありませんが、問題に応じて、ランダム性を強調したり、強調しなかったりする必要があるかもしれません。それを強調したい場合は、より少ない個体をそのままにし、より多くの新しいランダムな個体を導入する必要があります。一般に、解空間に多くの極大値があり、より広範囲の検索を行いたい場合は、これを実行します。
故障した場合は、考慮すべきことがいくつかあります...1つは重複（近親交配の上位に多数の同一個体または新たに同一個体が存在すること）です。これを減らすには、世代間の母集団を徹底的に調査し、重複を新しいランダムな個体または交配した個体に置き換えることをお勧めします。
そうは言っても、私の現在のアプローチは、上位 1% を維持し、上位 20% を交配して新しい 20% にし、上位 40% を交配して次の 20% にし、上位 90% を交配して次の 20% を生成し、ランダムに生成することです。残り（39%）を生成します。重複がある場合は削除し、ランダムな新しい個体と置き換えます。
ランダムな個体の数が多いため、次の交配中に「突然変異」を追加する必要があるため、私は突然変異を使用しません。
あなたに何ができるか知っていますか...最適な分布を決定する遺伝的アルゴリズムを作成できます。
しかし、通常は上位 12% と 28% の交雑種を維持します。残りはそれぞれ 30% ずつです。
