Reader Level:
ARTICLE

How to use Genetic Algorithm for Traveling Salesman Problem

Posted by Yuan Wang Articles | .NET Remoting December 20, 2006
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? We use the Genetic Algorithm to solve the TSP problem as a C# programing example .
  • 0
  • 0
  • 62071

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;

                                      do

                                      {

                                                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:

Article Extensions
Contents added by Javier Pardo Gomez on May 08, 2013
Contents added by qebir shemshi on Apr 25, 2013
Contents added by qebir shemshi on Feb 23, 2013
COMMENT USING

Trending up