How to use Genetic Algorithm for Traveling Salesman Problem

The Travelling Salesman Problem (TSP) problem is programmed by using C#.NET.

Please feel free to re-use the source codes.

A genetic algorithm is a adaptive stochastic optimization algorithms involving search and optimization. The evolutionary algorithm applies the principles of evolution found in nature to the problem of finding an optimal solution to a Solver problem.

The traveling salesman problem (TSP) is a problem in discrete or combinatorial optimisation. It is a prominent illustration of a class of problems in computational complexity theory which are hard to solve.

An equivalent formulation in terms of graph theory is: Given a complete weighted graph (where the vertices would represent the cities, the edges would represent the roads, and the weights would be the cost or distance of that road), find a Hamiltonian cycle with the least weight.

It can be shown that the requirement of returning to the starting city does not change the computational complexity of the problem.

A related problem is the bottleneck traveling salesman problem: Find a Hamiltonian cycle in a weighted graph with the minimal length of the longest edge.

---------------------------- Below are the source codes ----------------------------------

///////////////////////////// Travelling Salesman Problem (TSP) ///////////////////////////////

// TSP is a famous math problem: Given a number of cities and the costs of traveling

// from any city to any other city, what is the cheapest round-trip route that visits

// each city exactly once and then returns to the starting city?

///////////////////////////////////////////////////////////////////////////////////////////////

///---------------------- Begin CHROMOSOME.CS ----------------------------------------

using System;

using System.Threading;

namespace simga

{

/// <summary>

/// Summary description for Chromosome.

/// </summary>

public class Chromosome

{

public Chromosome()

{

// TODO: Add constructor logic here

}

// The cost for the fitness of the chromosome

protected double cost;

Random randObj = new Random();

//City myCity = new City();

// The list of cities which are the genes of the chromosome

protected int [] cityList;

// The mutation rate at percentage.

protected double mutationPercent;

// crossover point.

protected int crossoverPoint;

public Chromosome( City [] cities)

{

bool [] taken = new bool[cities.Length];

cityList = new int[cities.Length];

cost = 0.0;

for ( int i=0; i<cityList.Length; i++ ) taken[i] = false;

for ( int i=0; i<cityList.Length-1; i++ )

{

int icandidate;

{

icandidate = (int) ( randObj.NextDouble() * (double) cityList.Length );

} while ( taken[icandidate] );

cityList[i] = icandidate;

taken[icandidate] = true;

if ( i == cityList.Length-2 )

{

icandidate = 0;

while ( taken[icandidate] ) icandidate++;

cityList[i+1] = icandidate;

}

calculateCost(cities);

crossoverPoint = 1;

}

// fitness calculation

//void calculateCost(myCity cities)

public void calculateCost(City [] cities)

{

cost=0;

for ( int i=0; i<cityList.Length-1; i++ )

{

double dist = cities[cityList[i]].proximity(cities[cityList[i+1]]);

cost += dist;

}

public double getCost()

{

return cost;

}

public int getCity(int i)

{

return cityList[i];

}

public void assignCities(int [] list)

{

for ( int i=0; i<cityList.Length; i++ )

{

cityList[i] = list[i];

}

public void assignCity(int index, int value)

{

cityList[index] = value;

}

public void assignCut(int cut)

{

crossoverPoint = cut;

}

public void assignMutation(double prob)

{

mutationPercent = prob;

}

public int mate(Chromosome father, Chromosome offspring1, Chromosome offspring2)

{

int crossoverPostion1 = (int) ((randObj.NextDouble())*(double)(cityList.Length-crossoverPoint));

int crossoverPostion2 = crossoverPostion1 + crossoverPoint;

int [] offset1 = new int[cityList.Length];

int [] offset2 = new int[cityList.Length];

bool [] taken1 = new bool[cityList.Length];

bool [] taken2 = new bool[cityList.Length];

for ( int i=0; i<cityList.Length; i++ )

{

taken1[i] = false;

taken2[i] = false;

}

for ( int i=0; i<cityList.Length; i++ )

{

if ( i<crossoverPostion1 || i>= crossoverPostion2 )

{

offset1[i] = -1;

offset2[i] = -1;

}

else

{

int imother = cityList[i];

int ifather = father.getCity(i);

offset1[i] = ifather;

offset2[i] = imother;

taken1[ifather] = true;

taken2[imother] = true;

}

for ( int i=0; i<crossoverPostion1; i++ )

{

if ( offset1[i] == -1 )

{

for ( int j=0;j<cityList.Length;j++ )

{

int imother = cityList[j];

if ( !taken1[imother] )

{

offset1[i] = imother;

taken1[imother] = true;

break;

}

if ( offset2[i] == -1 )

{

for ( int j=0;j<cityList.Length;j++ )

{

int ifather = father.getCity(j);

if ( !taken2[ifather] )

{

offset2[i] = ifather;

taken2[ifather] = true;

break;

}

for ( int i=cityList.Length-1; i>=crossoverPostion2; i-- )

{

if ( offset1[i] == -1 )

{

for ( int j=cityList.Length-1;j>=0;j-- )

{

int imother = cityList[j];

if ( !taken1[imother] )

{

offset1[i] = imother;

taken1[imother] = true;

break;

}

if ( offset2[i] == -1 )

{

for ( int j=cityList.Length-1;j>=0;j-- )

{

int ifather = father.getCity(j);

if ( !taken2[ifather] )

{

offset2[i] = ifather;

taken2[ifather] = true;

break;

}

offspring1.assignCities(offset1);

offspring2.assignCities(offset2);

int mutate = 0;

int swapPoint1 = 0;

int swapPoint2 = 0;

if ( randObj.NextDouble() < mutationPercent )

{

swapPoint1 = (int) (randObj.NextDouble()*(double)(cityList.Length));

swapPoint2 = (int) (randObj.NextDouble()*(double)cityList.Length);

int i = offset1[swapPoint1];

offset1[swapPoint1] = offset1[swapPoint2];

offset1[swapPoint2] = i;

mutate++;

}

if ( randObj.NextDouble() < mutationPercent )

{

swapPoint1 = (int) (randObj.NextDouble()*(double)(cityList.Length));

swapPoint2 = (int) (randObj.NextDouble()*(double)cityList.Length);

int i = offset2[swapPoint1];

offset2[swapPoint1] = offset2[swapPoint2];

offset2[swapPoint2] = i;

mutate++;

}

return mutate;

}

public void PrintCity(int i, City [] cities)

{

System.Console.WriteLine("City "+i.ToString()+": ("+cities[cityList[i]].getx().ToString()+", "

+ cities[cityList[i]].gety().ToString()+")");

}

// chromosomes -- an array of chromosomes which is sorted

// num -- the number of the chromosome list

public static void sortChromosomes(Chromosome [] chromosomes,int num)

{

bool swapped = true;

Chromosome dummy;

while ( swapped )

{

swapped = false;

for ( int i=0; i<num-1; i++ )

{

if ( chromosomes[i].getCost() > chromosomes[i+1].getCost() )

{

dummy = chromosomes[i];

chromosomes[i] = chromosomes[i+1];

chromosomes[i+1] = dummy;

swapped = true;

}

//// ---------------------------- end CHROMOSOME.CS -------------------------------

/// ---------------------------- begin GA_TSP.CS --------------------------------------

using System;

using System.Threading;

using System.IO;

namespace simga

{

/// <summary>

/// Summary description for Class1.

/// </summary>

class GA_TSP

{

protected int cityCount;

protected int populationSize;

protected double mutationPercent;

protected int matingPopulationSize;

protected int favoredPopulationSize;

protected int cutLength;

protected int generation;

protected Thread worker = null;

protected bool started = false;

protected City [] cities;

protected Chromosome [] chromosomes;

private string status = "";

public GA_TSP()

{

}

public void Initialization()

{

Random randObj = new Random();

try

{

cityCount = 40;

populationSize = 1000;

mutationPercent = 0.05;

}

catch(Exception e)

{

cityCount = 100;

}

matingPopulationSize = populationSize/2;

favoredPopulationSize = matingPopulationSize/2;

cutLength = cityCount/5;

// create a random list of cities

cities = new City[cityCount];

for ( int i=0;i<cityCount;i++ )

{

cities[i] = new City(

(int)(randObj.NextDouble()*30),(int)(randObj.NextDouble()*15));

}

// create the initial chromosomes

chromosomes = new Chromosome[populationSize];

for ( int i=0;i<populationSize;i++ )

{

chromosomes[i] = new Chromosome(cities);

chromosomes[i].assignCut(cutLength);

chromosomes[i].assignMutation(mutationPercent);

}

Chromosome.sortChromosomes(chromosomes,populationSize);

started = true;

generation = 0;

}

public void TSPCompute()

{

double thisCost = 500.0;

double oldCost = 0.0;

double dcost = 500.0;

int countSame = 0;

Random randObj = new Random();

while(countSame<120)

{

generation++;

int ioffset = matingPopulationSize;

int mutated = 0;

for ( int i=0;i<favoredPopulationSize;i++ )

{

Chromosome cmother = chromosomes[i];

int father = (int) ( randObj.NextDouble()*(double)matingPopulationSize);

Chromosome cfather = chromosomes[father];

mutated += cmother.mate(cfather,chromosomes[ioffset],chromosomes[ioffset+1]);

ioffset += 2;

}

for ( int i=0;i<matingPopulationSize;i++ )

{

chromosomes[i] = chromosomes[i+matingPopulationSize];

chromosomes[i].calculateCost(cities);

}

// Now sort the new population

Chromosome.sortChromosomes(chromosomes,matingPopulationSize);

double cost = chromosomes[0].getCost();

dcost = Math.Abs(cost-thisCost);

thisCost = cost;

double mutationRate = 100.0 * (double) mutated / (double) matingPopulationSize;

System.Console.WriteLine("Generation = "+generation.ToString()+" Cost = "+thisCost.ToString()+" Mutated Rate = "+mutationRate.ToString()+"%");

if ( (int)thisCost == (int)oldCost )

{

countSame++;

}

else

{

countSame = 0;

oldCost = thisCost;

//System.Console.WriteLine("oldCost = " + oldCost.ToString());

}

for(int i = 0; i < cities.Length; i++)

{

chromosomes[i].PrintCity(i, cities);

}

/// <summary>

/// The main entry point for the application.

/// </summary>

[STAThread]

static void Main(string[] args)

{

// TODO: Add code to start application here

GA_TSP tsp = new GA_TSP();

tsp.Initialization();

tsp.TSPCompute();

}

public class City

{

public City()

{

// TODO: Add constructor logic here

}

// The city's x coordinate.

private int xcoord;

// The city's y coordinate.

private int ycoord;

// x -- the city's x coordinate

// y -- the city's y coordinate

public City(int x, int y)

{

xcoord = x;

ycoord = y;

}

public int getx()

{

return xcoord;

}

public int gety()

{

return ycoord;

}

// Returns the distance from the city to another city.

public int proximity(City cother)

{

return proximity(cother.getx(),cother.gety());

}

// x -- the x coordinate

// y -- the y coordinate

// return The distance.

public int proximity(int x, int y)

{

int xdiff = xcoord - x;

int ydiff = ycoord - y;

return(int)Math.Sqrt( xdiff*xdiff + ydiff*ydiff );

}

////----------------------- end GA_TSP.CS ------------------------------------------------------

Below is the optimal solution for the GA algorithm. In order to re-use the source codes easily, we removed the GUI program in the example above. If you compile and run the program, the optimal solution will appear in the DOS window as follow.

If we show the optimal solution in graph (that is, we connect the cities in the order), the graph will look like below:

7 Comments

Join the conversation! Your thoughts help the community grow.

Mohau Little14y ago
How do i go about add cities, eg cities like New York, Philadelphia, Pittsburgh and Washington, and their distances. to the source code above. THANKS IN ADVANCE!
Muddy khan14y ago
Excellent article But how can this be implemented to Graph Coloring problem ?
ravi bagal15y ago
can we implement genetic algorithm for shortest path finder in cities using front end as c sharp. we hav to go through the tsp problem????
Mus Peke17y ago
Excellent a study
kshito17y ago
I there, Do you have an idea of how to solve timetabling using a GA; Im a newbie in GA's. Thanks in advance
Don17y ago
The connection between the 1st and last cities is not represented in the path or on the graph. A quick eye-ball of the graph seems to yield that this is not the shortest path if the return trip is considered and that there are alternate routes that would be better WHEN considering the return trip.
farayi musharavati19y ago
hi i was impressed by your interest in GA for the TSP. Do you by any chance have or know any GA for TSP in C++? i am working on a project and i need a starting point like the one that you presented in C# thanks