selection - 遺伝的アルゴリズムにおけるトーナメント選択の複数の反復

Question

やあみんな、トーナメント選択の複数の反復がどのように機能するかについて少し混乱しています。

あなたがランダムなペア（またはk人のメンバー）を選択し、勝者を交配プールに入れ始めたことを知っています。交配プールがいっぱいになるまでこれを続けます。

しかし、その後どうなるかわかりません。

交配プールでランダムに交配を開始しますか？そして、新世代からランダムなペアを選択して、選択プロセスを再開しますか？

ありがとう。

Answer 1

私はこれらの一般的なアルゴリズムをかなりたくさん書いてきたので、同じコードを何度も書くことを避けるフレームワークを作成しました。

交配プールについては、探している個体の種類、探しているソリューションによって異なります。個体を組み合わせる方法があれば、より良い個体を生み出す可能性が高くなります。

ランダムな交配を使用することもできますが、これは「より悪い」解決策を提供します。より良い個体が生まれるかどうかわからないため、より悪い. それでも良い解決策であり、これらのアルゴリズムを書き始めたときは常にランダムな交配を使用していましたが、古い2つの個体から新しい個体を得た直後に、3つのパフォーマンスを比較し、悪い方を破棄して、時には2人の親（そして1秒の子供を捨てる）、または1人の親と1人の子供になってしまう.

しかし、より効率的にするために、かつ個体を組み合わせてより良い解を生成する方法を知っている場合 (これは非常に難しい場合があります)、親和性関数を使用できます。これは 2 つの個体を取り、それらの間の親和性を返します。トリッキーな部分は、親和性を決定することです。問題によっては、大きく異なる場合があります。たとえば、巡回セールスマンの問題を考えると、類似度の低い個体を交配すると、最良の解が得られます。したがって、私のアフィニティ関数は 1 - 類似度を返しました。

このようにして、反復回数を 80% 削減し、非常に優れたソリューションを得ることができました。

ただし、プールが大きいほど、アフィニティ関数の実行に時間がかかることに注意してください。アフィニティ関数は O(n²) または O(n³) になる可能性があり、その場合、アルゴリズムのボトルネックになる可能性があります。この場合、ランダム交配を使用する方が良い場合があります。

結論として、ランダムな交配は良いものです - 結局、実生活ではこのように機能すると言えますが、2 個体間の親和性を計算する方法を知っていれば、それを使用して反復回数を減らすことができます。良い解決策を得る必要があります。アフィニティの計算は非常に複雑になる可能性があることに注意してください (特定のプールに最適なアフィニティを計算するのは NP-Complete だと思います)。

Answer 2

これは良いアドバイスではありませんが...

ただし、その後どうなるかはわかりません。

好きなことをしてください。それらすべてを突然変異させることもできます...または、トーナメントで選んだ各ペアを交配させることもできます. 最適な方を使用してください。クリエイティブに。

このフォーラムの他の誰かが指摘したように: GA に関する汚い小さな秘密は、それが科学よりも芸術であるということです。

また、真に優れたアドバイスを得るには、解決したい問題をより適切に説明する必要があります。

Answer 3

伝統的に、トーナメントの勝者が見つかった後、彼らは次世代を形成します。突然変異、選択などのすべてのプロセスは、この後もサイクルで続きます。