3

GA についてもっと学びたいという欲求が再び燃え上がり、たくさん読んで何もしないのではなく、逆の方法で始めることにしました。問題を選んで、それを解決しようとします。

私は魔方陣問題を選びました。染色体をエンコードするために、私はPermutation Encodingを使用しており、 Mutation()およびNewChild(parent1, parent2, pivot) には次のメソッドを使用しています。

私の選択アルゴリズムは少し奇妙で、インターネットで見つかった例を基にしています。

スコアは、次のように、行/列/対角線の合計と魔法の定数の差の 2 乗に基づいて計算されます。

私が気付いたのは、収束が非常に速く、スコアが 1..7 (少ないほど良い) に達すると改善が止まるということです。

私はこれを次のように見ています：それは局所最適、潜在的な井戸に到達し、そのように呼ぶことができれば、突然変異が十分に異なっていないため、近くの丘を飛び越えませんか?
ここに画像の説明を入力

突然変異率を 5 ～ 80% に変更して、染色体集団に 10 ～ 20% のエリート グループを残し、集団サイズを 16 ～ 32 染色体から変更しようとしましたが、うまくいきませんでした。

私は何を間違っていますか？人口スコアをゼロに収束させるには、どのような改善を使用できますか?

必要に応じて、完全なソース コードを投稿することができます。

更新:サイズ 5 の立方体の収束率は次のようになります。交差率は 60%、突然変異率は 10% です。

ここに画像の説明を入力

4

2 に答える 2

3

これに対する明確な答えはありませんが、エリート主義を 5% 以下に減らし、人口規模を増やすことをお勧めします。あなたの getPermutation() 呼び出しが潜在的な候補者を選択するためにどのように機能しているかはよくわかりませんが、母集団のサイズを大きくすると、トーナメントのサイズも大きくなります (選択アルゴリズムの 8 ～ 16 行目)。局所的な最適化に行き詰まっている場合は、突然変異関数が十分にジャンプしていないか、そもそも母集団に十分な多様性がないことを意味します.

お役に立てば幸いです、頑張ってください！

于 2011-12-14T02:06:37.960 に答える
2

このような場合、私は部分母集団を使用して良い結果を得ました。基本的に、アルゴリズムを n 回実行し、各実行で最適な個体を選択します。これらを使用して、(通常の実行のようにランダムに初期化するのではなく) 初期集団を形成し、ga を再度実行します。この最後の実行の最初の個体は、通常、さまざまな点で次善であり、それらのすべてが多かれ少なかれ同じフィットネスを持っているため、それらが組み合わされると、極小値から互いに引き離される傾向があります。ここでも、すでに進化した個体を簡単に失わないように、エリート主義を使用することをお勧めします。

于 2012-01-05T10:59:02.493 に答える