TSP遗传算法陷入散乱点的低效解 [英] Genetic algorithm for TSP getting stuck with inefficient solution with scattered points

问题描述

24小时前我问了一个类似的问题（这里）但关于直线，感谢 ppolymorphe 指出事实证明我没有考虑回到起点。



修好并测试后我很满意解决方案，所以我参加了这个程序进入下一阶段并使用散点而不是直线。



问题：

它给了这个：

对于分散的10个城市，它通常给出1319左右的成本输出解决方案，这是相当不错的，但偶尔会产生大约1400，有时甚至1500的成本。

10个城市的最佳解决方案

10个城市不良解决方案



然而，20个城市，它通常会给成本大约2500-3000的成本提供不好的解决方案，很少能在1700-1800左右提供成本的良好解决方案。

20个城市不良解决方案

20个城市的最佳解决方案



如何改善输出？我希望它能输出更优的解决方案。



我还注意到由于有很多for循环，如果我增加了人口规模，程序执行时间会更长。我将非常感谢有关改进代码以减少执行时间的任何建议。

--------------------------- -------------------------------------------------- ---



我对原始项目（上面的链接）进行了一些小改动，这样我就可以更方便地修改mutRate，crossoverRate和number城市。



城市

24hrs ago I asked a similar question (here) but with regards to a straight line,thanks to ppolymorphe for pointing it out, turns out I hadn't considered the return to starting point.

After fixing that and testing it out and I was happy with the solution,So I took the program to the next phase and used a scattered point instead of a straight line.

Problem:
It gave this :
For Scattered 10 Cities, it usually gives the output solution of the cost around 1319, which is pretty good, but occasionally gives an output of the cost around 1400 and sometimes even 1500.
10 Cities Optimum Solution
10 Cities Bad Solution

Whereas, for 20 Cities, it usually gives the bad solution of the cost around 2500-3000, and very rarely gives a good solution of the cost around 1700-1800.
20 Cities Bad Solution
20 Cities Optimum Solution

How do I improve on the output? I would like it to output more optimal solution.

I have also notice that due to numerous for loops, if I increase my population size, the program takes longer to execute. I will appreciate any suggestions on improving the code to decrease the execution time.
--------------------------------------------------------------------------------

I have made a minor change to the original project(link above) just so that I have a easier access to modifying the mutationRate,crossoverRate, and number of Cities.

City

public class City
{
	public int X { get; set; }
	public int Y { get; set; }

	public City(int x, int y)
	{
		X = x; Y = y;
	}

	public int GetDistance(City otherCity)
	{
		int deltaX = X - otherCity.X;
		int deltaY = Y - otherCity.Y;
		return (int)Math.Sqrt(deltaX * deltaX + deltaY * deltaY);
	}
}

常数

Constant

public class Constant
{
	public static List<City> CITIES = new List<City>()
	#region
	{
		/*Straight Line*/
		//new City(150, 190),//0
		//new City(150, 73),
		//new City(150, 388),
		//new City(150, 65),
		//new City(150, 330),
		//new City(150, 5),
		//new City(150, 57),
		//new City(150, 380),
		//new City(150, 147),
		//new City(150, 251),  //9
		//new City(150, 159),
		//new City(150, 227),
		//new City(150, 117),
		//new City(150, 248),
		//new City(150, 150)//,//14
		//new City(150, 15),
		//new City(150, 94),
		//new City(150, 385),
		//new City(150, 145),
		//new City(150, 259)//19
		//new City(150, 195),
		//new City(150, 75),
		//new City(150, 71),
		//new City(150, 91),
		//new City(150, 35),
		//new City(150, 4),
		//new City(150, 88),
		//new City(150, 397),
		//new City(150, 370),
		//new City(150, 358),
		//new City(150, 47),
		//new City(150, 118),
		//new City(150, 143),
		// new City(150, 201),
		// new City(150, 314),
		// new City(150, 269),
		// new City(150, 182),
		//new City(150, 79),
		// new City(150, 353),
		// new City(150, 10)

		/*Scattered*/
		new City(6, 190),//0
		new City(29, 73),
		new City(47, 388),
		new City(52, 65),
		new City(75, 330),
		new City(77, 5),
		new City(93, 94),
		new City(132, 380),
		new City(389, 147),
		new City(121, 251),//9
		new City(230, 159),
		new City(73, 227),
		new City(317, 117),
		new City(52, 248),
		new City(265, 330),
		new City(77, 5),
		new City(393, 94),
		new City(407, 380),
		new City(401, 147),
		new City(322, 251),//19
		//new City(193, 190),
		//new City(259, 73),
		//new City(47, 71),
		//new City(52, 94),
		//new City(75, 35),
		//new City(77, 4),
		//new City(317, 94),
		//new City(132, 397),
		//new City(389, 380),
		//new City(121, 388),
		//new City(6, 47),
		//new City(29, 118),
		//new City(47, 143),
		//new City(52, 201),
		//new City(75, 314),
		//new City(77, 269),
		//new City(93, 182),
		//new City(132, 73),
		//new City(389, 353),
		//new City(121, 10)
	};
#endregion

	public static double MUTATION = 0.50;
	public static int POPULATION = 400;
	public static int SAMECOUNT = 120;
	public static double CROSSOVER = 0.6;
	public static int TOURNAMENTSIZE = 40;
}

染色体

Chromosomes

public class Chromosomes
{
	public static int DefaultGeneLength = Constant.CITIES.Count();
	private int[] Genes = new int[DefaultGeneLength];

	public Chromosomes()
	{
		Genes = Enumerable.Repeat(-1, DefaultGeneLength).ToArray();
	}

	public int[] GetGenes()
	{
		return Genes;
	}

	//Cache
	private int Fitness = 0;

	//Create a random individual
	public void GenerateRandom()
	{
		int timesZero = 0;
		for (int i = 0; i < Size(); i++)
		{
			bool repeat = false;
			do
			{
				int index = (int)(new Random(Guid.NewGuid().GetHashCode()).NextDouble() * (double)Size());
				if(Genes.Contains(index))
				{
					repeat = true;
					if(index == 0){
						if(timesZero ==0)
						{ 
						timesZero = 1;
						Genes[i] = index;
						repeat = false;
						}
					}
				}
				else{
					repeat = false;
					Genes[i] = index;
				}
			}while(repeat == true);
		}
		if(Genes.Distinct().Count()<10)
		{ }
	}
	public int GetGene(int index)
	{
		return Genes[index];
	}
	public void SetGene(int index, int value)
	{
		Genes[index] = value;
		Fitness = 0;
	}

	public int GetFitness()
	{
		if (Fitness == 0)
		{
			Fitness = FitnessCalc.GetFitness(this);
		}
		return Fitness;
	}
	public int Size()
	{
		return Genes.Length;
	}

	public string Show(City[] cities)
	{
		StringBuilder sbuilder = new StringBuilder();

		foreach (int i in Genes)
		{
			sbuilder.Append(cities[i].X + "," + cities[i].Y + ">>");
			//sbuilder.Append(cities[i].Y + ">>");
		}
		sbuilder.Append("Total Cost:" + GetFitness());
		return sbuilder.ToString();
	}
}

FitnessCalc

FitnessCalc

public class FitnessCalc
{
	static public City[] cities;

	public static void Initialize(City[] arrCities)
	{
		cities = new City[arrCities.Count()];
		for (int i = 0; i < arrCities.Count(); i++)
		{
			cities[i] = arrCities[i];
		}
	}

	internal static int GetFitness(Chromosomes chromosomes)
	{
		int count = chromosomes.GetGenes().Where(i => i == 0).Count();
		if (count > 1)
			return 99999;
		int cost = 0;
		for (int i = 0; i < chromosomes.Size() - 1; i++)
		{
			int dist = cities[chromosomes.GetGene(i)].GetDistance(cities[chromosomes.GetGene(i + 1)]);
			cost += dist;
		}
		//add cost to return to starting point - to make a loop
		cost += cities[chromosomes.GetGene(chromosomes.GetGenes().Length - 1)].GetDistance(cities[chromosomes.GetGene(0)]);
		return cost;
	}
}

GA_TSPVER2：遗传算法逻辑

GA_TSPVER2:Genetic Algorithm Logic

public class GA_TSPVer2
{
	private static double uniformRate;
	private static double mutationRate;
	private static int tournamentSize;
	private static bool elitism = true;

	//Evolve a population
	public static Population Evolve(Population pop,double mutation,double crossover,int tournament)
	{
		mutationRate = mutation;
		uniformRate = crossover;
		tournamentSize = tournament;
		//Creating New Population
		Population newPopulation = new Population(pop.Size(), false);
		//Keep out best individual
		if (elitism)
		{
			newPopulation.SaveIndividual(0, pop.GetFittest());
		}

		//Crossover population
		int elitismOffset;
		if (elitism)
		{
			elitismOffset = 1;
		}
		else
		{
			elitismOffset = 0;
		}

		//Loop over the population size and create new individuals with crossover
		for (int i = elitismOffset; i < pop.Size(); i++)
		{
			Chromosomes indiv1 = TournamentSelection(pop);
			Chromosomes indiv2 = TournamentSelection(pop);
			Chromosomes newIndiv = Crossover(indiv1, indiv2);    
			newPopulation.SaveIndividual(i, newIndiv);
		}
		
		//Mutate Population
		for (int i = elitismOffset; i < newPopulation.Size(); i++)
		{
			Mutate(newPopulation.GetIndividual(i));
		}
		return newPopulation;
	}

	//CrossOver Individuals
	private static Chromosomes Crossover(Chromosomes indiv1, Chromosomes indiv2)
	{
		Chromosomes newSol = new Chromosomes();
		//for (int i = 0; i < newSol.GetGenes().Length; i++)
		//{
		//    newSol.SetGene(i, -1);
		//}
		//Loop through genes : CrossOver Type 1
		for (int j = 0; j < newSol.Size(); j++)
		{
			double toss = (new Random(Guid.NewGuid().GetHashCode()).NextDouble());
			if (toss > uniformRate)
			{
				//Crossover with Chromo 2
				int Gene = 0;
				int geneLeft = indiv2.GetGenes().Length - j;
				int counter = j;
				do{
					if(geneLeft == 0)
					{
						Gene = indiv2.GetGenes().Except(newSol.GetGenes()).First();
					}
					else { 
						Gene = indiv2.GetGenes().ElementAt(counter++);
						geneLeft--;
					}
					bool b = newSol.GetGenes().Contains(Gene);
				}while(newSol.GetGenes().Contains(Gene));
				newSol.SetGene(j, Gene);
			}
			else
			{
				//Crossover with Chrome 1
				int Gene = 0;
				int geneLeft = indiv1.GetGenes().Length - j;
				int counter = j;
				do
				{
					if (geneLeft == 0)
					{
						Gene = indiv1.GetGenes().Except(newSol.GetGenes()).First();
					}
					else
					{
						Gene = indiv1.GetGenes().ElementAt(counter++);
						geneLeft--;
					}
					bool b = newSol.GetGenes().Contains(Gene);
				} while (newSol.GetGenes().Contains(Gene));
				newSol.SetGene(j, Gene);
			}
		}

		//Cut-Paste Section Crossover Type 2
		//int toss = (int)(new Random(Guid.NewGuid().GetHashCode()).NextDouble());
		//if (toss > uniformRate)
		//{
		//    int d = (int)(new Random(Guid.NewGuid().GetHashCode()).NextDouble() * indiv1.Size());
		//    for (int i = 0; i < d; i++)
		//    {
		//        newSol.SetGene(i, indiv1.GetGene(i));
		//    }
		//    int[] leftovers = indiv2.GetGenes().Except(newSol.GetGenes()).ToArray();

		//    int counter = 0;
		//    for (int i = d; i < indiv2.Size(); i++)
		//    {
		//        newSol.SetGene(i, leftovers[counter++]);
		//    }
		//}
		//else
		//{
		//    newSol = indiv1;
		//}
		return newSol;
	}

	//Mutate an individual
	private static void Mutate(Chromosomes indiv)
	{
		//Loop through genes
		for (int i = 0; i < indiv.Size(); i++)
		{
			double d = new Random(Guid.NewGuid().GetHashCode()).NextDouble();
			if (d <= mutationRate)
			{
				//Create random gene
				//switch gene
				int sindex = (int)(new Random(Guid.NewGuid().GetHashCode()).NextDouble() * indiv.Size());
				int sValue = indiv.GetGene(sindex);
				int eindex;
				do
				{
					eindex = (int)(new Random(Guid.NewGuid().GetHashCode()).NextDouble() * indiv.Size());
				} while (sindex == eindex);
				int eValue = indiv.GetGene(eindex);
				indiv.SetGene(sindex, eValue);
				indiv.SetGene(eindex, sValue);
			}

		}
	}

	//Select individuals for crossover
	private static Chromosomes TournamentSelection(Population pop)
	{
		//Create a tournament population
		Population tournament = new Population(tournamentSize, false);

		//Selection 
		Population selection = new Population(tournamentSize/2, false);
		var temp = pop.individuals.OrderBy(x => x.GetFitness()).Take(tournamentSize/2);
		//int counter = 0;
		//foreach(Chromosomes c in temp)
		//{
		//    selection.SaveIndividual(counter++,c);
		//}
		//For each place in the tournament get a random indivudual
		for (int i = 0; i < tournamentSize; i++)
		{
			double d = new Random(Guid.NewGuid().GetHashCode()).NextDouble();
			int randomId = (int)(d * selection.Size());
			//tournament.SaveIndividual(i, selection.GetIndividual(randomId));
			tournament.SaveIndividual(i, temp.ElementAt(randomId));
		}
		//Get the fittest
		Chromosomes fittest = tournament.GetFittest();
		return fittest;
	}

}

人口

Population

public class Population
{
	public Chromosomes[] individuals;

	//Create a population
	public Population(int populationSize, bool initialize)
	{
		individuals = new Chromosomes[populationSize];
		if (initialize)
		{
			//Loop and create individuals
			for (int i = 0; i < Size(); i++)
			{
				Chromosomes newIndividual = new Chromosomes();
				newIndividual.GenerateRandom();
				SaveIndividual(i, newIndividual);
			}
		}
	}

	public Chromosomes GetIndividual(int index)
	{
		return individuals[index];
	}

	public Chromosomes GetFittest()
	{
		return individuals.Aggregate((i1, i2) => i1.GetFitness() < i2.GetFitness() ? i1 : i2);
	}

	public int Size()
	{
		return individuals.Length;
	}

	public void SaveIndividual(int index, Chromosomes individual)
	{
		individuals[index] = individual;
		individual.GetFitness();
	}
}

主类

Main Class

public class MyMain
{
	public static void Main()
	{
		TSPVer2.FitnessCalc.Initialize(Constant.CITIES.ToArray());
		TSPVer2.Population myPop = new TSPVer2.Population(Constant.POPULATION, true);
		Console.WriteLine(myPop.GetFittest().GetFitness());
		int generationCount2 = 0;
		int sameCount2 = 0;
		int thisCost2 = 0;
		int oldCost2 = 0;
		Console.WriteLine("");
		while (sameCount2 < Constant.SAMECOUNT)
		{

			generationCount2++;
			myPop = TSPVer2.GA_TSPVer2.Evolve(myPop, Constant.MUTATION,Constant.CROSSOVER,Constant.TOURNAMENTSIZE);
			thisCost2 = myPop.GetFittest().GetFitness();
			if ((int)thisCost2 == (int)oldCost2)
			{
				Console.SetCursorPosition(0, Console.CursorTop - 1);
				ClearCurrentConsoleLine();
				sameCount2++;
				Console.WriteLine("Same:" + sameCount2 + " Cost" + thisCost2);
			}
			else
			{
				Console.SetCursorPosition(0, Console.CursorTop - 1);
				ClearCurrentConsoleLine();
				sameCount2 = 0;
				oldCost2 = thisCost2;
				Console.WriteLine("Old Cost:" + oldCost2 + ", New Cost:" + thisCost2);
			}
		}
		Console.WriteLine("Gen:" + generationCount2);
		Console.WriteLine(myPop.GetFittest().Show(TSPVer2.FitnessCalc.cities));

		Console.Read();
	}
	 public static void ClearCurrentConsoleLine()
	{
		int currentLineCursor = Console.CursorTop;
		Console.SetCursorPosition(0, Console.CursorTop);
		Console.Write(new string(' ', Console.WindowWidth));
		Console.SetCursorPosition(0, currentLineCursor);
	}
}

我的尝试：



我试过更改mutationRate，crossOverRate，populationize

What I have tried:

I have tried changing the mutationRate, crossOverRate, populationsize

推荐答案

引用：

如果我增加我的人口规模，程序执行时间会更长。

if I increase my population size, the program takes longer to execute.

正常，这就是它被称为NP-Hard问题的原因。
请记住，这是一个组合问题。

您添加城市的次数越多，解决问题的时间就越长，而且不是线性的。



遗传算法正在进行随机变化，当您接近最优解时，有效变化的数量减少，因此不太可能被发现。

您可以认为遗传算法不是由于其随机特性而高效。

请参阅链接中的算法。

旅行推销员问题 - Wikip edia，免费的百科全书 [ ^ ]

Normal, this is the reason why it is called NP-Hard problem.
Keep in mind that this is a combinational problem.
The more you add cities, the longer it takes to solve the problem and it is not linear.

A genetic algorithm is doing random changes, as you approach optimal solution, the number of efficient changes reduce and thus are less likely to be found.
You can consider that genetic algorithm is not efficient because of its random nature.
See algorithms in link.
Travelling salesman problem - Wikipedia, the free encyclopedia[^]

Quote：

我将非常感谢有关改进代码以减少执行时间的任何建议。

I will appreciate any suggestions on improving the code to decrease the execution time.

除非你做了一个理论上的突破，我担心没有多少建议没有在链接中。



唯一的建议是让程序做更多轮次以获得更好的解决方案。次要问题，你永远不会知道你是最佳解决方案。



[UpDate]

Unless you make a theoretical breakthrough, I fear there is not much to advice that is not already in the link.

The only advice is to let program do more rounds to get better solutions. Secondary problem, you will never know that you are on the optimal solution.

[UpDate]

引用：

因此单独随机变化的遗传算法不会给出最优解

So genetic algorithm with random changes alone wouldn't give optimal solution

随着时间的推移，运气会更快。

It will with time, faster with luck.

引用：

你的建议是什么，

不多！

任何探索所有可能性的算法都需要很长时间但是要确保最佳解决方案。

任何跳过某些可能性的算法都会更快但可能会错过最佳解决方案。

问题在科学上仍然是开放的，截至今天，好的算法可以在缩短的时间内提供相当好的解决方案。

Not much !
Any algorithm that explore all possibilities will take ages but ensure optimal solution.
Any algorithm that skip some possibilities will be faster but may miss the optimal solution.
The problem is still open in science, as of today, a good algorithm is one that will give a fairly good solution in reduced time.

这篇关于TSP遗传算法陷入散乱点的低效解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！