2

遺伝的アルゴリズムと GA 全体についていくつか質問があります。

曲線にポイントを指定すると、この曲線を生成した関数を見つけようとする GA を作成しました。

例は次のとおりです。 ポイント

{{-2, 4},{-1, 1},{0, 0},{1, 1},{2, 4}}

関数

x^2

関数をまったく生成しないポイントを与える場合もあれば、関数を生成する場合もあります。初期ツリーの深さに依存することさえあります。

いくつかの質問：

  • ポイントを評価して満足のいく関数を生成しようとする際に、ツリーの深さが重要なのはなぜですか?
  • 時期尚早の収束が発生し、サイクルの場合に GA が発生しないのはなぜですか?
  • 早期収束を防ぐにはどうすればよいですか?
  • アニーリングはどうですか？どのように使用できますか？

私のコードを簡単に見て、何か明らかに問題があるか教えていただけますか? (これはテスト コードです。コードをクリーンアップする必要があります。)

https://github.com/kevkid/GeneticAlgorithmTest

ソース：http://www.gp-field-guide.org.uk/

編集：トーマスの提案がうまくいったように見えます。非常に高速な結果が得られ、早期収束が少なくなります。遺伝子プールを増やすとより良い結果が得られるように感じますが、実際に世代ごとに改善されているのか、それともランダムであるという事実が正しい解決策を見つけることを可能にしているのかは正確にはわかりません.

編集 2: トーマスの提案に従って、適切に機能させることができました。生存者の取得と遺伝子プールの拡大に問題があったようです。また、他の誰かが見たい場合は、最近 GA テストに定数を追加しました。

4

2 に答える 2

1

あなたのコードを掘り下げる時間はありませんが、GAで覚えていることから答えようとします：

関数をまったく生成しないポイントを与える場合もあれば、関数を生成する場合もあります。初期ツリーの深さに依存することさえあります。

ここで何が問題なのかわかりませんが、結果が必要な場合は、指定されたポイントまでの距離が最小になる関数を選択してみてください (必要に応じて、合計、平均、ポイント数など)。

ポイントを評価して満足のいく関数を生成しようとする際に、ツリーの深さが重要なのはなぜですか?

木の深さの意味はわかりませんが、次の 2 つのことに影響する可能性があります。

  • 精度: つまり、深度が高いほど、解の精度が高くなるか、変異の可能性が高くなります。
  • パフォーマンス: どのツリーを意味するかによって、深さが深いほどパフォーマンスが向上する (関数についてより多くの知識に基づいた推測が可能になる) か、パフォーマンスが低下する (より多くのソリューションを生成して比較する必要がある) 可能性があります。

時期尚早の収束が発生し、サイクルの場合に GA が発生しないのはなぜですか?

これは、変異が少なすぎることが原因である可能性があります。すべてが局所的な最適値に収束する一連の解がある場合、わずかな突然変異だけでは、結果として得られる解がその局所的な最適値から十分に離れていない可能性があります。

早期収束を防ぐにはどうすればよいですか?

たとえば、ソリューションが収束し始めたときなど、より大きな突然変異を許可できます。または、まったく新しいソリューションをミックスに投入することもできます (「移民」と考えてください)。

アニーリングはどうですか？どのように使用できますか？

アニーリングは、ソリューションが特定のポイント/最適値に収束し始めると、ソリューションを徐々に改善するために使用できます。つまり、「ランダムな」突然変異よりも制御された方法でソリューションを改善します。

また、それらがどのように分布しているかに応じて、局所最適から抜け出すために使用することもできます。例として、ソリューションが収束し始めるまで GA を使用してから、アニーリングおよび/またはより大きな突然変異および/または完全に新しいソリューションを使用することができます (異なるアプローチでいくつかのソリューション セットを生成し、最後にそれらを比較することができます)。新しい人口と収束が壊れている場合は、GA で新しい反復を開始します。解がまだ同じ最適値に収束する場合は、それ以上の改善は期待できないため、停止することができます。

それに加えて、ヒューリスティック アルゴリズムは依然として局所的な最適値に到達する可能性がありますが、パフォーマンスと精度というトレードオフがあります。

于 2015-06-17T13:10:11.367 に答える