15,851,335 members
See more:
24hrs ago I asked a similar question (here) but with regards to a straight line,thanks to ppolymorphe for pointing it out, turns out I hadn't considered the return to starting point.

After fixing that and testing it out and I was happy with the solution,So I took the program to the next phase and used a scattered point instead of a straight line.

Problem:
It gave this :
For Scattered 10 Cities, it usually gives the output solution of the cost around 1319, which is pretty good, but occasionally gives an output of the cost around 1400 and sometimes even 1500.
10 Cities Optimum Solution

Whereas, for 20 Cities, it usually gives the bad solution of the cost around 2500-3000, and very rarely gives a good solution of the cost around 1700-1800.
20 Cities Optimum Solution

How do I improve on the output? I would like it to output more optimal solution.

I have also notice that due to numerous for loops, if I increase my population size, the program takes longer to execute. I will appreciate any suggestions on improving the code to decrease the execution time.
--------------------------------------------------------------------------------

I have made a minor change to the original project(link above) just so that I have a easier access to modifying the mutationRate,crossoverRate, and number of Cities.

City
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);
}
}```

Constant
C#
```public class Constant
{
public static List<City> CITIES = new List<City>()
#region
{
/*Straight Line*/
//new City(150, 190),//0
//new City(150, 73),
//new City(150, 388),
//new City(150, 65),
//new City(150, 330),
//new City(150, 5),
//new City(150, 57),
//new City(150, 380),
//new City(150, 147),
//new City(150, 251),  //9
//new City(150, 159),
//new City(150, 227),
//new City(150, 117),
//new City(150, 248),
//new City(150, 150)//,//14
//new City(150, 15),
//new City(150, 94),
//new City(150, 385),
//new City(150, 145),
//new City(150, 259)//19
//new City(150, 195),
//new City(150, 75),
//new City(150, 71),
//new City(150, 91),
//new City(150, 35),
//new City(150, 4),
//new City(150, 88),
//new City(150, 397),
//new City(150, 370),
//new City(150, 358),
//new City(150, 47),
//new City(150, 118),
//new City(150, 143),
// new City(150, 201),
// new City(150, 314),
// new City(150, 269),
// new City(150, 182),
//new City(150, 79),
// new City(150, 353),
// new City(150, 10)

/*Scattered*/
new City(6, 190),//0
new City(29, 73),
new City(47, 388),
new City(52, 65),
new City(75, 330),
new City(77, 5),
new City(93, 94),
new City(132, 380),
new City(389, 147),
new City(121, 251),//9
new City(230, 159),
new City(73, 227),
new City(317, 117),
new City(52, 248),
new City(265, 330),
new City(77, 5),
new City(393, 94),
new City(407, 380),
new City(401, 147),
new City(322, 251),//19
//new City(193, 190),
//new City(259, 73),
//new City(47, 71),
//new City(52, 94),
//new City(75, 35),
//new City(77, 4),
//new City(317, 94),
//new City(132, 397),
//new City(389, 380),
//new City(121, 388),
//new City(6, 47),
//new City(29, 118),
//new City(47, 143),
//new City(52, 201),
//new City(75, 314),
//new City(77, 269),
//new City(93, 182),
//new City(132, 73),
//new City(389, 353),
//new City(121, 10)
};
#endregion

public static double MUTATION = 0.50;
public static int POPULATION = 400;
public static int SAMECOUNT = 120;
public static double CROSSOVER = 0.6;
public static int TOURNAMENTSIZE = 40;
}```

Chromosomes
C#
```public class Chromosomes
{
public static int DefaultGeneLength = Constant.CITIES.Count();
private int[] Genes = new int[DefaultGeneLength];

public Chromosomes()
{
Genes = Enumerable.Repeat(-1, DefaultGeneLength).ToArray();
}

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);
}
if(Genes.Distinct().Count()<10)
{ }
}
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(cities[i].Y + ">>");
}
sbuilder.Append("Total Cost:" + GetFitness());
return sbuilder.ToString();
}
}```

FitnessCalc
C#
```public class FitnessCalc
{
static public City[] cities;

public static void Initialize(City[] arrCities)
{
cities = new City[arrCities.Count()];
for (int i = 0; i < arrCities.Count(); i++)
{
cities[i] = arrCities[i];
}
}

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;
}
cost += cities[chromosomes.GetGene(chromosomes.GetGenes().Length - 1)].GetDistance(cities[chromosomes.GetGene(0)]);
return cost;
}
}```

GA_TSPVER2:Genetic Algorithm Logic
C#
```public class GA_TSPVer2
{
private static double uniformRate;
private static double mutationRate;
private static int tournamentSize;
private static bool elitism = true;

//Evolve a population
public static Population Evolve(Population pop,double mutation,double crossover,int tournament)
{
mutationRate = mutation;
uniformRate = crossover;
tournamentSize = tournament;
//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)
{
//Create random gene
//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);

//Selection
Population selection = new Population(tournamentSize/2, false);
var temp = pop.individuals.OrderBy(x => x.GetFitness()).Take(tournamentSize/2);
//int counter = 0;
//foreach(Chromosomes c in temp)
//{
//    selection.SaveIndividual(counter++,c);
//}
//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 * selection.Size());
//tournament.SaveIndividual(i, selection.GetIndividual(randomId));
tournament.SaveIndividual(i, temp.ElementAt(randomId));
}
//Get the fittest
Chromosomes fittest = tournament.GetFittest();
return fittest;
}

}```

Population
C#
```public class Population
{
public 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();
}
}```

Main Class
C#
```public class MyMain
{
public static void Main()
{
TSPVer2.FitnessCalc.Initialize(Constant.CITIES.ToArray());
TSPVer2.Population myPop = new TSPVer2.Population(Constant.POPULATION, true);
Console.WriteLine(myPop.GetFittest().GetFitness());
int generationCount2 = 0;
int sameCount2 = 0;
int thisCost2 = 0;
int oldCost2 = 0;
Console.WriteLine("");
while (sameCount2 < Constant.SAMECOUNT)
{

generationCount2++;
myPop = TSPVer2.GA_TSPVer2.Evolve(myPop, Constant.MUTATION,Constant.CROSSOVER,Constant.TOURNAMENTSIZE);
thisCost2 = myPop.GetFittest().GetFitness();
if ((int)thisCost2 == (int)oldCost2)
{
Console.SetCursorPosition(0, Console.CursorTop - 1);
ClearCurrentConsoleLine();
sameCount2++;
Console.WriteLine("Same:" + sameCount2 + " Cost" + thisCost2);
}
else
{
Console.SetCursorPosition(0, Console.CursorTop - 1);
ClearCurrentConsoleLine();
sameCount2 = 0;
oldCost2 = thisCost2;
Console.WriteLine("Old Cost:" + oldCost2 + ", New Cost:" + thisCost2);
}
}
Console.WriteLine("Gen:" + generationCount2);
Console.WriteLine(myPop.GetFittest().Show(TSPVer2.FitnessCalc.cities));

}
public static void ClearCurrentConsoleLine()
{
int currentLineCursor = Console.CursorTop;
Console.SetCursorPosition(0, Console.CursorTop);
Console.Write(new string(' ', Console.WindowWidth));
Console.SetCursorPosition(0, currentLineCursor);
}
}```

What I have tried:

I have tried changing the mutationRate, crossOverRate, populationsize
Posted
Updated 5-May-16 22:46pm

## Solution 1

Quote:
if I increase my population size, the program takes longer to execute.
Normal, this is the reason why it is called NP-Hard problem.
Keep in mind that this is a combinational problem.
The more you add cities, the longer it takes to solve the problem and it is not linear.

A genetic algorithm is doing random changes, as you approach optimal solution, the number of efficient changes reduce and thus are less likely to be found.
You can consider that genetic algorithm is not efficient because of its random nature.
Travelling salesman problem - Wikipedia, the free encyclopedia[^]
Quote:
I will appreciate any suggestions on improving the code to decrease the execution time.
Unless you make a theoretical breakthrough, I fear there is not much to advice that is not already in the link.

The only advice is to let program do more rounds to get better solutions. Secondary problem, you will never know that you are on the optimal solution.

[UpDate]
Quote:
So genetic algorithm with random changes alone wouldn't give optimal solution
It will with time, faster with luck.
Quote:
Not much !
Any algorithm that explore all possibilities will take ages but ensure optimal solution.
Any algorithm that skip some possibilities will be faster but may miss the optimal solution.
The problem is still open in science, as of today, a good algorithm is one that will give a fairly good solution in reduced time.

v3