///////////////////////////// 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 ------------------------------------------------------