3

遺伝的アルゴリズム (または進化的計算) は、これらの点を直接ではなく、解空間 Ω 内の点のエンコードで機能することがわかっています。文献では、GA には欠点があることがよくわかります。(1) 多くの染色体が Ω の類似点にコード化されているか、類似した染色体が非常に異なる点を持っているため、効率が非常に低い。それは本当に欠点だと思いますか？これらの種類のアルゴリズムは、各反復で突然変異演算子を使用して候補ソリューションを多様化するためです。多様化をさらに進めるには、単純にクロスオーバーの確率を上げます。そして、(染色体の) 初期集団がランダムに生成されることを忘れてはなりません (もう 1 つの多様化)。問題は、(1) が GA の欠点であると思われる場合、詳細を教えていただけますか? ありがとうございました。

4

2 に答える 2

6

突然変異とランダムな初期化は、遺伝的アルゴリズムの主要な問題である遺伝的ドリフトとして知られている問題に対処するには十分ではありません。遺伝的ドリフトとは、GA がその遺伝的多様性のほとんどを急速に失う可能性があり、検索がクロスオーバーにとって有益ではない方法で進行することを意味します。これは、ランダムな初期集団がすぐに収束するためです。突然変異は別のことで、それが高ければ多様化しますが、同時に収束を妨げ、解はより高い確率で最適解まで一定の距離にとどまります。検索中に突然変異確率 (交差確率ではない) を適応させる必要があります。同様に、GA に似た Evolution Strategy は、検索中に突然変異の強さを適応させます。

クロスオーバー後に別の選択ステップを導入する OffspringSelection GA (OSGA) と呼ばれる GA のバリアントを開発しました。親のフィットネスを超える (より良い、より悪い、または線形補間された値) 子のみが受け入れられます。このようにして、ランダムな親選択を使用して、子孫の質にバイアスをかけることさえできます. これにより、遺伝的浮動が遅くなることが示されています。このアルゴリズムは、フレームワークHeuristicLabに実装されています。GUI を備えているため、ダウンロードしていくつかの問題で試すことができます。

遺伝的浮動に対抗する他の技術は、ニッチングとクラウディングであり、多様性が選択に流れ込み、別の、おそらく異なるバイアスを導入します.

編集：同じ品質の複数のソリューションを持つ状況は、検索空間に中立的な領域を作成するため、もちろん問題を引き起こす可能性があることを付け加えたい. しかし、あなたは本当にそれを意味していなかったと思います。主な問題は遺伝的浮動です。（重要な）遺伝情報の喪失。

于 2012-02-08T09:43:01.880 に答える
0

補足として、あなた（OP）は次のように述べています。

遺伝的アルゴリズム (または進化的計算) は、これらの点を直接ではなく、解空間 Ω 内の点のエンコードで機能することがわかっています。

これは常に正しいとは限りません。個体は遺伝子型としてコード化され、文字列 (遺伝的アルゴリズム) や実数のベクトル (進化戦略) など、任意の形状を持つことができます。各遺伝子型は、個体を評価するとき、つまりその適合度を計算するときに表現型に変換されます。場合によっては、表現型が遺伝子型と同一であり、直接コーディングと呼ばれます。それ以外の場合、コーディングは間接的と呼ばれます。(ここでより多くの定義を見つけることができます(セクション 2.2.1) )

直接エンコードの例: http://en.wikipedia.org/wiki/Neuroevolution#Direct_and_Indirect_Encoding_of_Networks

間接エンコーディングの例:
長さ、高さ、幅によって定義される直方体のサイズを最適化するとします。例を単純化するために、これら 3 つの量が 0 から 15 までの整数であると仮定します。その後、それぞれを 4 ビットの 2 進数で表すことができます。考えられる解決策の例として、遺伝子型 0001 0111 01010 が考えられます。対応する表現型は、長さ 1、高さ 7、幅 10 の平行六面体です。


多様性に関する元の質問に戻ると、DonAndre が読むことができると言ったことに加えて、AE Eiben と JE Smith によって書かれた優れた本、Introduction to Evolutionary Computingの第 9 章「 Multi-Modal Problems and Spatial Distribution 」を読むことができます。進化的ロボティクスにおける行動の多様性の促進: 経験的研究など、その問題に関する研究論文も同様です。つまり、多様性は GA の欠点ではなく、「単なる」問題です。

于 2012-02-08T12:54:30.097 に答える