TSP遗传算法陷入低效解决方案 [英] Genetic algorithm for TSP getting stuck with inefficient solution
问题描述
旅行推销员是一个典型的优化问题，即排列/组合问题，为销售人员准确访问所有城市一次找到最佳最短路径。
每个城市有X和Y坐标
遗传算法中的基因将是城市指数，染色体将是一个或多个基因，因此它将包含要访问的城市的顺序。
该计划将有一系列城市（在FitnessCalc类）。 Population类拥有一系列染色体（这是一个可以访问的城市的数组）。
GA_TSPVer2类具有变异和交叉方法的方法随机随机播放这些基因是为了改善下一代人口。
城市等级
Traveling salesman is a classic optimization problem which is Permutation/Combination problem to find an optimal shortest path for a salesman to visit all the cities exactly once.
Each City has an X and Y coordinates
The Genes in Genetic Algorithm would be the city index, and the Chromosomes would be an array or genes, hence it would contain the order of city to visit.
The program would have an array of cities (in FitnessCalc Class). The Population class holds an array of Chromosomes(which is an array of order of city to visit).
The GA_TSPVer2 class has methods to mutate and crossover methods to randomly shuffle the genes in order to improve the next generation of population.
City Class
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);
}
}
染色体：包含要访问的城市顺序的基因
Chromosomes: Contains Genes which are the order of the cities to visit
public class Chromosomes
{
public static int DefaultGeneLength = 10;
private int[] Genes = new int[DefaultGeneLength];
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);
}
}
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("Total Cost:" + GetFitness());
return sbuilder.ToString();
}
}
健身计算器：按基因顺序行走的总距离
Fitness Calculator: Which is the total distance traveled in the the order of genes
public class FitnessCalc
{
static public City[] cities;
public static void Initialize()
{
cities = new City[Chromosomes.DefaultGeneLength];
//Simple: Straight Line
cities[0] = new City(150, 190);
cities[1] = new City(150, 73);
cities[2] = new City(150, 388);
cities[3] = new City(150, 65);
cities[4] = new City(150, 330);
cities[5] = new City(150, 5);
cities[6] = new City(150, 57);
cities[7] = new City(150, 380);
cities[8] = new City(150, 147);
cities[9] = new City(150, 251);
//Complex: Dispersed points
//cities[0] = new City(6, 190);
//cities[1] = new City(29, 73);
//cities[2] = new City(47, 388);
//cities[3] = new City(52, 65);
//cities[4] = new City(75, 330);
//cities[5] = new City(77, 5);
//cities[6] = new City(93, 94);
//cities[7] = new City(132, 380);
//cities[8] = new City(389, 147);
//cities[9] = new City(121, 251);
}
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;
}
return cost;
}
}
人口：保留染色体数量
Population: Holds the Population of chromosomes
public class Population
{
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();
}
}
遗传算法逻辑
我的遗传算法涉及：
1.通过从染色体1获得基因进行交叉染色体2
2.通过改变染色体中基因的顺序进行突变。
我有两种类型的交叉方法，
第一种方法 - 它遍历每个基因并从Chromosome1复制一个基因，否则染色体2.
第二种方法（评论） - 随机选择一个指数并从染色体1中复制该指数的所有基因，并从染色体2中复制该指数的所有基因。
Genetic Algorithm Logic
My genetic algorithm involves:
1. crossover by getting a gene from Chromosome1 else Chromosome2
2. mutation by shuffling the order of a gene in a Chromosome.
I have two types crossover method,
first method - it loops over each gene and copy a gene either from Chromosome1 else Chromosome2.
second method(commented) - randomly selects an index and copies all genes left of that index from Chromosome1 and copies all genes right of that index from Chromosome2.
public class GA_TSPVer2
{
private static double uniformRate = 0.5;
private static double mutationRate = 0.05;
private static int tournamentSize = 5;
private static bool elitism = true;
//Evolve a population
public static Population Evolve(Population pop)
{
//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)
{
//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);
//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 * pop.Size());
tournament.SaveIndividual(i, pop.GetIndividual(randomId));
}
//Get the fittest
Chromosomes fittest = tournament.GetFittest();
return fittest;
}
}
主类
Main Class
public class Consoles
{
public static void Main()
{
TSPVer2.FitnessCalc.Initialize();
TSPVer2.Population myPop = new TSPVer2.Population(10, true);
int generationCount = 0;
int sameCount = 0;
int thisCost = 0;
int oldCost = 0;
while (sameCount < 200)
{
generationCount++;
myPop = TSPVer2.GA_TSPVer2.Evolve(myPop);
thisCost = myPop.GetFittest().GetFitness();
if ((int)thisCost == (int)oldCost)
{
sameCount++;
}
else
{
sameCount = 0;
oldCost = thisCost;
}
}
Console.WriteLine("Gen:"+generationCount);
Console.WriteLine(myPop.GetFittest().Show(TSPVer2.FitnessCalc.cities));
Console.Read();
}
}
**输出：**
150,251> > 150388>> 150380>> 150330>> 150190>> 150147>> 150,73>> 150,65>> 150,57>> 150,5>> ;总费用：520
因为它是一条直线，意味着最短的路径总是一个有序的点。
问题：
我面临的问题是程序确实尝试了它想做的事情，即尝试找到最短的路径并保存然而，我认为我应用的交叉和/或变异技术效率低下/无法更好地找到最短路径，也许是算法或者我需要添加另一个逻辑。
我确实认识到遗传算法提供的最佳解决方案不一定是最好的解决方案，但在我的情况下它也没有提供最佳解决方案，它得到了坚持一些经过几代人的演变后，解决方案无法找到更好的解决方案。
我的尝试：
我试过调整变异和交叉率和人口但是没有用
我还使用了两种不同的交叉技术
**Output:**
150,251>>150,388>>150,380>>150,330>>150,190>>150,147>>150,73>>150,65>>150,57>>150,5>>Total Cost:520
Since its a straight line, meaning the shortest path is always an ordered points.
Problem:
The problem I am facing is that the programs does try to what it is suppose to do, i.e., try to find the shortest path and saves the shortest path it found for the next generation population, however, I suppose the crossover and/or the mutation technique that I have applied is inefficient/incapable of doing a better job of finding the shortest path, perhaps its the algorithm or maybe I need to add another logic.
I do realize that Genetic algorithm gives an optimal solution not necessarily the best solution, but in my case its not giving an optimal solution either, it gets stuck on some solution and is unable to find a better solution, after evolving over a few generations.
What I have tried:
I have tried adjusting the mutation and crossover rate and population but didn't work
I have also used two different crossover technique
推荐答案
**输出：**
150,251>> ; 150388>> 150380>> 150330>> 150190>> 150147>> 150,73>> 150,65>> 150,57>> 150,5>>总费用：520
**Output:**
150,251>>150,388>>150,380>>150,330>>150,190>>150,147>>150,73>>150,65>>150,57>>150,5>>Total Cost:520
第一个问题，费用是766而不是520。如上所述。
First problem, the cost is 766 and not 520 as stated.
由于它是一条直线，意味着最短路径始终是有序点。
Since its a straight line, meaning the shortest path is always an ordered points.
第二个问题，它是一个循环。再想一想TSP。
我知道这是愚蠢的，但是你的程序停止优化其解决方案的主要原因是它已经达到了最佳解决方案。 （很难保持严肃：-O）
[更新]
你需要改进的是你对TSP的理解，它不是一条海峡线，它是一个环路！
海峡线的最佳成本是383，但你需要回到起点，所以总成本是766.它是您的解决方案的最佳实际成本！
Second problem, it is a loop. Think again about TSP.
I know it is stupid, but the main reason why your program stop optimizing its solution is that it already reached the optimum solution. (difficult to stay serious :-O )
[Update]
What you need to improve is your understanding of TSP, it is not a strait line, it is a loop!
the optimum cost of a strait line is 383, but you need to return to starting point, so total cost is 766. It is the actual cost of your solution which is optimum !
这篇关于TSP遗传算法陷入低效解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
