Click here to Skip to main content
15,846,342 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
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
C#
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
C#
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
C#
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
C#
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();
	}
}

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.



C#
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
C#
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();
	}
}


**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
Posted
Updated 13-May-16 13:36pm
v4
Comments
Sergey Alexandrovich Kryukov 5-May-16 2:02am    
Genetic methods are not supposed to be efficient for each and every problem. And its easy to build a problem where they are totally inefficient compared to other ones... :-)

Instead of jumping from City directly to genes and your algorithm description, it would be good to describe the problem.

—SA
j4rey89 5-May-16 2:38am    
Sorry for not adding a description, I have edited my question and have described the problem I am facing....thanks
Sergey Alexandrovich Kryukov 5-May-16 3:29am    
No need to apologize, but... you again skipped the goal. What problem should be solved? You again jumped from Cities to chromosomes. Can you totally separate the problem and the method?
—SA
j4rey89 5-May-16 6:09am    
now? ( ´△`)
Patrice T 6-May-16 0:54am    
I guess you will love my solution. :-)

1 solution

Quote:
**Output:**
150,251>>150,388>>150,380>>150,330>>150,190>>150,147>>150,73>>150,65>>150,57>>150,5>>Total Cost:520
First problem, the cost is 766 and not 520 as stated.
Quote:
Since its a straight line, meaning the shortest path is always an ordered points.
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 !
 
Share this answer
 
v2
Comments
j4rey89 5-May-16 7:02am    
How do I improve on it? I would like it to get as close as possible to the best solution(which is about 380-420). I would really appreciate it if you could suggest me any additional logic which I could add to the solution or perhaps any modification on the current solution.
j4rey89 6-May-16 1:55am    
Ah.....Okay, I get it now, the loop, I wasn't calculating the return to the starting point....
Patrice T 6-May-16 2:20am    
You got it.
j4rey89 6-May-16 3:17am    
yeah....so i thought I took it to the next phase by feeding it 10 scattered points.It usually gives me a decent solution of around 1300, however sometimes gives an output of around 1400-1500. But when I fed it 20 Cities, 9 out of 10 times it gave a horrible output of 3000, and occasionally an optimum output of around 1800.

I'd figure it would be right to ask this here, so I posted another question regarding it here (http://www.codeproject.com/Questions/1098223/Genetic-algorithm-for-TSP-getting-stuck-with-ineff). Looking forward to your input there. Many thanks.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900