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

本文关键字：遗传算法 改变 TSP 最佳值 我们 方法 | 更新日期: 2023-09-27 18:28:50

我正在尝试使用C#中的遗传算法来解决旅行推销员问题。但在我的应用程序中，最佳价值观的变化如此缓慢。我尝试过不同的Crossing Over方法，如经典、贪婪和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;
        }

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

通常称为"双点有序"的交叉在这里非常有用。这种类型的交叉从单个父对象创建子对象。选择两个亲本，并沿着染色体选择两个随机点。这些点之间的基因被传给了孩子。剩下的基因是从同一个亲本转移来的，但顺序是它们出现在第二个亲本中。结果是，孩子包含来自单亲的所有值，但包括来自双亲的排序，因此也包括特征。

我这里有几个TSP的例子，这可能有助于

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

在我使用GA的经验中，有序交叉（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);

您可以在TspChrosome.cs和TspFitness.cs上看到TspChromome的实现。

相关文章：