13

遺伝的アルゴリズムで巡回セールスマン問題（TSP）を解決しようとしています。私のゲノムは、グラフ内の頂点の順列です（セールスマンのパス）。

ゲノムに対してクロスオーバー操作をどのように実行する必要がありますか？

問題の実装はC＃のどこにありますか？

4

7 に答える 7

12

GokturkUcolukによる「特別なクロスオーバーと突然変異を回避するTSPの遺伝的アルゴリズムソリューション」を確認する必要があります。順列の特別なクロスオーバー演算子の概要を示し、標準のクロスオーバーでうまく機能する順列の巧妙な表現を提案します（つまり、2つの順列をクロスオーバーすると常に2つの順列が生成されます）。

重要な洞察は、順列をその反転シーケンスとして表すことです。つまり、各要素について、順列の左側よりも大きい要素の数iを格納します。直接表現とは異なり、の唯一の制約はローカルです。つまり、を大きくすることはできません。これは、2つの有効な反転シーケンスを単純にクロスオーバーすると、常に2つの有効な反転シーケンスが生成されることを意味します。繰り返し要素を特別に処理する必要はありません。a[i]iia[i]a[i]N - i

于 2009-10-09T20:30:40.377 に答える
8

標準的な GA クロスオーバー手法 ( MusiGenesis で概説されている) を使用するよりも、巡回セールスマン問題に順序付きクロスオーバーを使用する方が適切です。

通常のアプローチは、TSP ではうまく機能しません。フィットネス関数は、進化したルート内のさまざまな都市の絶対位置ではなく、相対位置に非常に敏感だからです。たとえば、すべてのヨーロッパの首都を訪れた場合、ブラチスラバ 1 番目、2 番目、または 9 番目のいずれを訪れるかによって、最短ルートは実際には異なります。さらに重要なことは、ヘルシンキ、アテネ、およびその間にある他の 6 つの首都を訪れるよりも、ウィーンを訪れる直前または直後に訪れることです。

もちろん、mjv も指摘しているように、従来のクロスオーバーもルートに重複をもたらします。1 つの親がパリを 2 位に、別の親がパリを 14 位に持つ場合、クロスオーバーにより、パリを 2 回訪問する 1 つの進化したルート (そして別の都市を逃す) と、パリをまったく訪れない別の進化したルートが生じる可能性があります。順序交差遺伝演算子は、この問題に悩まされることはありません。要素を保持し、順序を変更します。

于 2009-10-09T19:57:09.637 に答える
4

これは、探しているものに対するC# プログラムのアプローチです。

cross-overを実装することの関心 (またはその欠如) に関しては、実装が使用する特定の選択ロジック (および/または評価関数自体、たとえば改善速度の評価が含まれている場合) にすべて依存します。 . 多くの場合、クロスオーバー操作は、グラフの領域では効果的/最適であるが、他の領域では何らかの形で「立ち往生」しているいくつかのソリューションを「チョッピング ブロックから救い出す」でしょう。これは、アルゴリズム全体が十分に遅く、ソリューション空間のかなりの割合をカバーしている場合、同じソリューションが新たに発見されていない可能性があると言っているわけではありませんが、クロスオーバーによってこれらの発見が増加する可能性があります (および/または別の極小値 ;-) )

直接関係はありませんが、 GAを調べている人にとって注目に値する興味深いのは、実際の DNA 分子を [C プログラムに -冗談です]関連するグラフの問題、ハミルトニアングラフの問題を解決します。

編集：質問を読み直すと、なぜあなたがそれを尋ねたのか、より正確には「いいえ、クロスオーバーはしたくない」という返信が必要なのかがわかりました;-)
あなたのゲノムはグラフ自体に直接結びついています(何も悪いことはありません)先験的に)、しかしこれは、ほとんどのクロスオーバー offsrping が実行可能ではないという障害をもたらします。これは、ノードが重複している (同じ都市を 2 回以上訪問している) 可能性があり、ノードが欠落している (いくつかの都市を訪問していない) 可能性があるためです。 ..さらに、実行可能なクロスオーバーは同様のグラフに影響を与えるため、突然変異が発見したものと比較して、検索を徐々に拡張するだけかもしれません...
うーん...そして、この特定の実装ではクロスオーバーかもしれませんアルゴリズムはあまり役に立ちません(実際、クロスオーバー子孫の作成、テスト、および多くの場合破棄するために CPU の多くを使用します。CPU は、より多くの反復を提供することでより適切に使用され、冷却速度が遅くなります...)。そうでもなければ！クロスオーバー操作を実行する賢い方法を見つけます ;-)

于 2009-10-09T14:25:37.857 に答える
3

クロスオーバーの目的は、新しいゲノムの組み合わせをまとめることで、進化の探索空間を拡大することです。

進化のプロセスに必要な唯一の実際の基準は、交差の産物が両方の親の部分を含み、有効なゲノムを表すことです。

アルゴリズムの有効性ルールを知っているのはあなただけなので、機能する交差法を指定できるのはあなただけです (ゲノム構造の検証ルールの詳細を共有したくない場合を除きます)。

于 2009-10-09T14:37:46.703 に答える
2

これは、TSP の GA におけるいわゆる「部分的にマッピングされたクロスオーバー」メソッドの私の正確な実装です。

これは、部分的にマッピングされたクロスオーバーを理論的に説明する論文であり、以下は私のコードです。

//construct a new individual with the genes of the parents
//method used is cross over mapping
//note that Individual datastrucuture contains an integer array called Genes which            //contains the route.
//
public Individual Breed(Individual father, Individual mother)
{
    int[] genes = new int[father.Genes.Length];
    int[] map = new int[father.Genes.Length + 1]; //create a map to map the indices
    int crossoverPoint1 = rand.Next(1, father.Genes.Length - 2); //select 2 crossoverpoints, without the first and last nodes, cuz they are always thje same
    int crossoverPoint2 = rand.Next(1, father.Genes.Length - 2);
    father.Genes.CopyTo(genes, 0); //give child all genes from the father
    for (int i = 0; i < genes.Length; i++) //create the map
    {
        map[genes[i]] = i;
    }
    //int[] genesToCopy = new int[Math.Abs(crossoverPoint1 - crossoverPoint2)]; //allocate space for the mother genes to copy
    if (crossoverPoint1 > crossoverPoint2) //if point 1 is bigger than point 2 swap them
    {
        int temp = crossoverPoint1;
        crossoverPoint1 = crossoverPoint2;
        crossoverPoint2 = temp;
    }
    //Console.WriteLine("copy mother genes into father genes from {0} to {1}", crossoverPoint1, crossoverPoint2);
    for (int i = crossoverPoint1; i <= crossoverPoint2; i++) //from index one to the 2nd
    {
        int value = mother.Genes[i];
        int t = genes[map[value]]; //swap the genes in the child
        genes[map[value]] = genes[i];
        genes[i] = t;
        t = map[genes[map[value]]]; //swap the indices in the map
        map[genes[map[value]]] = map[genes[i]];
        map[genes[i]] = t;
    }
    Individual child = new Individual(genes);
    return child;
}
于 2012-07-20T18:10:25.003 に答える
1

私が大学の最初のコースにいたとき、さまざまな GA 演算子が解の収束に与える影響についていくつかの計算 (約 30 ページかかりました) を行っていました。私が覚えているように、クロスオーバーは TSP の最良の解決策ではありません。より適切な解決策は、頂点のサブシーケンスの反転である突然変異です。

例：

前: BCDEF GH

後: FEDCB GH

于 2009-10-09T15:36:33.313 に答える
0

遺伝的アルゴリズムの「クロスオーバー」とは、2 つの「遺伝的配列」を任意に混合する方法を指します。それぞれが問題の特定の解決策を表します (配列が解決策にどのようにマッピングされるかはユーザー次第です)。たとえば、次の 2 つのシーケンスで構成される母集団があるとします。 

AAAAAAAAAA
BBBBBBBBBB

これら 2 つの「親」シーケンスを再結合する 1 つの方法は、クロスオーバー ポイント (たとえば、位置 3) をランダムに選択することです。これにより、次の 2 つの「子」シーケンスが生成されます。

AAABBBBBBB
BBBAAAAAAA

または、2 つのクロスオーバー ポイント (たとえば、3 と 8) をランダムに選択して、次の 2 つのシーケンスを作成することもできます。

AAABBBBBAA
BBBAAAAABB

楽しみと追加の可変性のために、時折の点突然変異の可能性を導入することもできます:

AAABBBABAA
BBBAAAAABB

遺伝的アルゴリズムでクロスオーバーを実装する方法に関して、厳格なルールはありません。生物学の世界で進化を制御する厳格なルールが実際には存在しないのと同じです。うまくいくものは何でもうまくいく。

于 2009-10-09T14:55:54.127 に答える