13

私は順列で遺伝的アルゴリズムのクロスオーバーの問題を解決しようとしています。20 個の整数の順列が 2 つあるとします。それらを交配して2人の子供をもうけたいです。親は同じ整数を内部に持っていますが、順序は異なります。

例：

Parent1: 
 5 12 60 50 42 21 530 999 112 234 15 152 601 750 442 221 30 969 113 134
Parent2: 
 12 750 42 113 530 112 5 23415 60 152 601 999 442 221 50 30 969  134 21

そのようにしましょう-どうすればこれら2つの子供を得ることができますか?

4

4 に答える 4

5

あなたが探しているのは、注文されたクロスオーバーです。ここに巡回セールスマン問題の説明があります。

部分的にマップされたクロスオーバー（PMX）バリアントを実装するJavaコードを次に示します。

于 2013-01-20T01:42:54.173 に答える
4

クロスオーバーの選択は、整数の順序または絶対位置が適合性にとって重要かどうかによって異なります。HeuristicLab (C#)では、次のような文献に見られるいくつかの一般的なものを実装しました: OrderCrossover (2 つのバリアント)、OrderBasedCrossover、PartiallyMatchedCrossover、CyclicCrossover (2 つのバリアント)、EdgeRecombinationCrossover (ERX)、MaximalPreservativeCrossover、PositionBasedCrossover、および UniformLikeCrossover。それらの実装は、HeuristicLab.Encodings.PermutationEncoding プラグインの科学的なソースへの参照と共に見つけることができます。ERX は、TSP または TSP のような問題に対してのみ意味があります。CX は位置ベースであり、PMX は部分的に位置と順序に基づいていますが、より位置に向けられています。OX は注文ベースのみです。

私たちの実装では、0 から N-1 までの整数による連続番号順列を想定していることに注意してください。まず、それらをこの範囲にマップする必要があります。

于 2013-01-20T09:31:28.700 に答える
2

私の研究と遺伝的演算子の実装によると。多くのタイプのクロスオーバー演算子がオーダーコーディング用に存在します (つまり、TSPのように許可されていない遺伝子の繰り返し)。一般に、私は主に 2 つのファミリーがあると考えています。

ERXファミリー

近隣のリストは、各ノードの近隣を両方の親に格納するために使用されます。次に、リストのみを使用して子を生成します。ERXはより敬意を払い、対立遺伝子を伝達することが知られています。これは基本的に、遺伝子間のリンクが壊れる可能性が低いことを意味します.

ERX に似た演算子の例には、 Edge Recombination (ERX)、Edge-2、Edge-3、Edge-4、Generalized Partition Crossover (GPX) などがあります。

OXのようなクロスオーバー

2 つの交差点が選択されます。次に、ポイント間の遺伝子が 2 つの親の間で交換されます。繰り返しは許可されていないため、各クロスオーバーでは、繰り返しを回避/排除するための手法が提案されています。これらのクロスオーバー オペレーターは、ERX よりも破壊的です。

OX のような交叉の例:次数交叉 (OX)、最大保存交叉 (MPX)、および部分写像交叉 (PMX)。

最初のファミリー (ERX) は、単純な遺伝的アルゴリズムでより優れたパフォーマンスを発揮します。2 番目のファミリーは、ハイブリッド遺伝的アルゴリズムまたはミーム アルゴリズム (ローカル検索の使用) により適しています。本稿ではその詳細を解説した。

于 2016-03-20T00:16:27.100 に答える
1

巡回セールス担当者問題 (TSP) では、注文で都市のリストを訪問し、各都市を 1 回だけ訪問する必要があります。都市をゲノムに直接エンコードすると、単純なクロスオーバーまたは変異によって無効な旅程が生成されることがよくあります。

私はかつて、この問題を解決するための斬新なアプローチを思いつきました。解決策をゲノムに直接エンコードする代わりに、値の正規リストを並べ替える変換をエンコードしました。

ゲノム [1, 2, 4, 3, 2, 4, 1, 3] が与えられた場合、都市のリストを任意の順序 (アルファベット順など) で開始します。

  1. アトランタ
  2. ボストン
  3. シカゴ
  4. デンバー

次に、ゲノムから値の各ペアを取得し、それらの位置にある都市を交換します。したがって、上記のゲノムでは、1 と 2 を交換し、次に 4 と 3 を交換し、次に 2 と 4 を交換し、最後に 1 と 3 を交換します。最終的には次のようになります。

  1. デンバー
  2. シカゴ
  3. ボストン
  4. アトランタ

この手法を使用すると、任意のタイプのクロスオーバーまたはミューテーション操作を使用しても、常に有効なツアーを取得できます。ゲノムが十分に長い場合、ソリューション スペース全体を探索できます。

私はこれを TSP やその他の最適化問題に使用して、多くの成功を収めてきました。

于 2016-02-16T16:58:21.310 に答える