子供が特定の順序を持たなければならない場合、どうやって 2 人の親を越えることができるでしょうか?
たとえば、頂点/エッジの固定グラフで巡回セールスマン問題に遺伝的アルゴリズムを適用する場合、すべての頂点が他の頂点に移動できるわけではないという事実に対処する必要があります。すべての頂点が他のすべての頂点に移動する可能性がある TSP とは異なり、クロスオーバーを実行するときは、正当なパスを生成するポイントで実行する必要があるため、これによりクロスオーバーがはるかに困難になります。代わりの方法は、とにかくクロスオーバーして不正なパスを拒否することですが、そのリスクは計算コストが高く、正当なパスはほとんどまたはまったくありません。
順列クロスオーバーについて読んだことがありますが、これがどのように問題を解決するのか完全にはわかりません。誰かが私を正しい方向に向けたりアドバイスしたりできますか?
順序付けは、可能な限り、遺伝的プログラミングの制約であってはなりません。おそらく、ソリューションに別の形式を選択することを検討する必要があります。たとえば、TSP でコドン A->B を考えてみましょう。
「A から B へのエッジを取る」という意味の代わりに、「A から B への最短経路を取る」と考えることができます。このようにして、ソリューションは常に実行可能になります。前処理として最短経路行列を事前計算するだけです。
これは、クロスオーバー後に候補が実行可能なソリューションになることを保証するものではありません。ソリューションが引き続き実行可能であることを保証するために、クロスオーバーを調整する必要があります。たとえば、TSP の場合、次のシーケンスを検討してください。
1 : ABCD E FGH
2 : AD E GCBFH
ピボットをランダムに選択します (この例ではE )。これにより、次のシーケンスが完了します。
1 ' : ABCD E. . .
2 ' : AD E. . . . .
有効な解を得るには、すべての頂点を調べる必要があります。1' では、F、G、および H を訪問する必要があります。2' では、G、C、B、F、および H が 1 のように並べ替えられます。
1' : ABCD E GFH
2' : AD E BCFGH
お役に立てれば。