2

C#で遺伝的アルゴリズムを使用して巡回セールスマン問題を解決しようとしています。しかし、私のアプリでは、最高の値がゆっくりと変化します。クラシック、貪欲、pmx などのさまざまな Crossing-Over メソッドを試しましたが、欲しいものが得られませんでした。遺伝的アルゴリズムで局所最小値への近似が遅くなる最も効果的な理由は何ですか? クロスオーバー法じゃないですか。

私の CO の方法は正しいと思いますね。私のコード:

        Tour ClassicCrossingOver(Tour mother, Tour father)
        {
            int pos = N / 2;
            City[] gens = new City[N];

            for (int i = 0; i < pos; i++)
            {
                gens[i] = mother.Cities[i];
            }
            List<int> nonPos = new List<int>(); //Handles duplicate city positions
            for (int i = pos; i < gens.Length; i++) 
            {
                if (gens.Contains(father.Cities[i]))
                    nonPos.Add(i); 
                gens[i] = father.Cities[i];
            }
            List<City> noneGenes = new List<City>(); //Handles cities that doesnt exists in the child
            foreach (City gene in map.Cities)
            {
                if (gens.Contains(gene)) continue;
                noneGenes.Add(gene);
            }
            for (int i = 0; i < noneGenes.Count; i++) 
            {
                int j = rnd.Next(nonPos.Count - 1);
                gens[nonPos[j]] = noneGenes[i];
                nonPos.RemoveAt(j);
            }
            Tour tur = new Tour(map) { Cities = gens };
            return tur;
        }
4

2 に答える 2

1

ここでは、「ダブル ポイント オーダー」と呼ばれることが多いクロスオーバーが非常に役立ちます。このタイプのクロスオーバーは、1 つの親から子を作成します。2 つの親が選択され、染色体に沿った 2 つのランダム ポイントが選択されます。ポイント間の遺伝子は子供に渡されます。残りの遺伝子は同じ親から移されますが、2 番目の親に現れる順序で移されます。その結果、子には単一の親からのすべての値が含まれますが、両方の親からの順序付け、したがって特性が含まれます。

ここに役立つ TSP の例がいくつかあります。

http://johnnewcombe.net/blog/gaf-part-4/ http://johnnewcombe.net/blog/gaf-part-7/

于 2016-01-09T01:09:30.880 に答える
0

GA を使用した私の経験では、Ordered Crossover (OX1) は TSP を解決するのに最適なクロスオーバー演算子の 1 つです。

OX1: 一方の親のランダムに選択された部分が、もう一方の親の部分にマップされます。置き換えられた部分から、残りは残りの遺伝子で埋められます。既存の遺伝子は省略され、順序は保持されます。

他の演算子は、GA が最適な値に到達する速度に影響を与える可能性があります。私は通常、巡回セールスマン問題で以下の演算子を使用します。

  • クロスオーバー：注文クロスオーバー（OX1）
  • 変異：逆配列変異
  • セレクション：エリートセレクション

これは、 GeneticSharpを使用して TSP を解くためのサンプル コードで、数秒で適切な解が見つかりました。

var numberOfCities = 20;
var selection = new EliteSelection();
var crossover = new OrderedCrossover();
var mutation = new ReverseSequenceMutation();
var fitness = new TspFitness(numberOfCities, 0, 1000, 0, 1000);
var chromosome = new TspChromosme(numberOfCities);
var population = new Population (100, 200, chromosome);

var ga = new GeneticAlgorithm(population, fitness, selection, crossover, mutation);
ga.Termination = new GenerationNumberTermination(100);

Console.WriteLine("GA running...");
ga.Start();

Console.WriteLine("Best solution found has {0} fitness.", ga.BestChromosome.Fitness);

TspChromosome.cs で TspChromosome の実装を、TspFitness.csでTspFitnessを確認できます。

于 2016-01-02T12:23:12.937 に答える