2

我正在尝试使用 C# 中的遗传算法解决旅行推销员问题。但在我的应用程序中，最佳值变化如此缓慢。我尝试过不同的交叉方法，例如经典、贪婪和 pmx，但我从来没有得到我想要的。在遗传算法中导致缓慢逼近局部最小值的最有效原因是什么？不是交叉方法吗？

我认为我的 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

通常称为“双点排序”的交叉在这里非常有用。这种类型的交叉从单亲创建一个孩子。选择两个父母并选择染色体上的两个随机点。点之间的基因被传递给孩子。其余基因从同一亲本转移，但按照它们出现在第二亲本中的顺序。结果是子代包含来自单亲的所有值，但包含来自双亲的排序，因此也包含特征。

我在这里有几个 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 的最佳交叉算子之一。

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 回答