哪种交叉方法最能让我们快速改变 GA 中 TSP 的最佳值？

Question

我正在尝试使用 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;
        }

Answer 1

根据我使用 GA 的经验，有序交叉 (OX1) 是解决 TSP 的最佳交叉算子之一。

OX1: A randomly selected portion of one parent is mapped to a portion of the other parent. From the replaced portion on, the rest is filled up by the remaining genes, where already present genes are omitted and the order is preserved.

其他操作符会影响 GA 达到最佳值的速度。我通常在旅行商问题中使用下面的运算符：

交叉：有序交叉 (OX1)
突变：逆序突变
选择：精英选择

这是解决 TSP 的示例代码，使用 GeneticSharp，在几秒钟内找到了一个很好的解决方案：

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 and TspFitness at TspFitness.cs 查看 TspChromosome 实现。

Answer 2

通常称为 'Double Point Ordered' 的交叉在这里非常有用。这种类型的交叉从单个 parent 创建 child。选择了两个parent，并选择了染色体上的两个随机点。点之间的基因传递给child。其余基因从同一个 parent 中转移，但按照它们在第二个 parent 中出现的顺序。结果是 child 包含来自单个 parent 的所有值，但包括来自两个 parent 的排序和特征。

我这里有几个 TSP 示例，可能会有所帮助

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

哪种交叉方法最能让我们快速改变 GA 中 TSP 的最佳值？

Which crossing over method is best to give us quick changes in best values for TSP in GA?

c#

hamiltonian-cycle

genetic-algorithm

np