TSP

• Download source files - 200 Kb

Introduction

over all my search through the internet I have never find a simple code for solving traveling Sales man problem using Genetic Algorithm. I designed an Initial library for GA and I impemeted the Algorithm of GA in the main application. it is so easily to understand and to be maintained.

Each point drawn represents a city. Each point has X and Y coordinates which I store it so i can calculate the distance between such a point and its neighbors.

The application at the end draws the lines according to the path conducted and a statistical file showing Chromoses formation will be saved by pressing the log info tool bar button before pressing the run button

Description

Genetic Algorithms are Hurestic Search Algorithms they are basically inteneded to solve problems with out no Algorthim one can follow. Genetic algorithms immutate the human generations (Kindly refer to the powerpoint representation). Genetic Algorithms doesn't gurantee that this is the best solution but it gurantees that this is a good solution.

Travelling sales man problem is simple a sales man that needs to travel serveral cities to display his products now the question is which path should he follows inorder to save time ie Shortest Path is required. Now when number of cities increases no of fesiable solutions increases and here comes the role of Genetic Algorithm.

Step 1

• Inorder to understand the Algorithm you must first read the presentation file.
• Inorder to use GALib there are four delegates needs to be implemented in your application

1. Initializer
2. Mutation method (Mutate)
3. CrossOver (CrossOver)
4. Fitness (Fitness)

GALib.Initializer newItializer = new GALib.Initializer(this.Initializer);
GALib.Mutate mutater = new GALib.Mutate(this. ChromoseCompraror); 
GALib.Fitness fitmethod = new GALib.Fitness(this.Fitness); 
GALib.CrossOver CrossMethod = new GALib.CrossOver(this.CrossOver); 
GALib.GA GAAlgo = new GA(newItializer,fitmethod,mutater,CrossMethod);

1-Initilization (GAChromosome Chromo /*Input Chromosome to be initialized*/)

private void Initializer(GAChromosome chromose){...}

Now when Calling GA.Initialize Method() I am actually calling a the Initializer Delegate (I am calling developer code the way he is going to initialize the chromosome)

In my code I intialized the chromose randamly by the indexes of the cities such that for example a chromosome of value 1-2-5-6-7 etc this chromosome is suggesting a path starting from city 1 then 2 then moving to city 5 and so on

2- Fintness (GAChromosome Chromo /*Input Chromosome to calc its fitness*/)

private void Fitness(GAChromosome chromosome){....}

I am also calling Fitness delegate to calculate the Chromose fitness. Fitness method is called internally from the GA class developer has to submit the implementation

Chromosome value of 1-2-5-6-7

In my application since as long as the total path distance decrease the better (less trip) then my chromosome fitness is simply calculated by getting the sum of distances etc D1 = distance from City 1 to City 2 D2 = Distance from City2 to City 5 untill we get the total sum

Since we need to minimze the distance to increase chromosome fitness i calculated fitnedd as 100/Total Sum Of Distance therefore the less distance the more fitness

3- CrossOver (GAChromosome mum, GAChromosome Dad, ref GAChromosome child1, ref GAChromosome child2)

private void CrossOver ( GAChromosome Dad, GAChromosome Mum, 
                         ref GAChromosome child1, ref GAChromosome child2)
{
   GreedyCrossOver(Dad, Mum, ref child1);
   GreedyCrossOver(Mum, Dad, ref child2);
}

I used the greedy Cross over technique which works like that

• Pick a random gene at Parent1
• Locate that gene at Parent2
• Start formatting the new Child Gene by inserting the value of the random gene as first Gene in the new formatted child
• From the first parent move into left direction read the gene value is it in the new child genes if yes add it to the left side if the gene else stop
• From the second parent move into right direction read the gene value is it in the new child genes if yes add it to the right side if the gene else stop

• if you stopped reading from Parent 1 and 2 and the Chromosome length is still missing then fill the rest of genes in randomly order with all genes not included yet in this chromosome

ex Parent 1 = D H B A C F G B Parent 2 = B C D G H F E A

Now Child Gene is composed of C as initial gene

From Parent 1 move left. we are reading Gene value of A. Is A one of the new child Genes? if Ans== No then New Child Genes are AC

From Parent 2 move right we are reading Gene value of D. Is D one of the new child Genes? if Ans== No then New Child Genes are ACD

In our Problem Gene is the city index and Chromosome is simply a formated path to follow represented from the cities indexes

4- Mutation

private void Mutator(GAChromosome chromose){....}

I used the neighborhoad matrix to apply mutation. Simply the neighborhood matrix works by placing two dimensional array of cities with distances between each city to other ex Cell[1,4] value will be distance between city 1 and city 4 same as Cell [4,1] will hold the same value (review the presentation)

now by picking a gene randamly G1 (City) we try to find shortest Gene G2(city) near to it when we find it we mark the whole column that not to be used again so i don't get at the end repeated chromosomes

Repeat this for G2 to Get G3 and so over until we finish all the Genes

I developed this project for My Masters course AI (Arab Academy - Cairo - Egypt)

PS I am not a GA Specialist