I am working on Genetic Algorithyms to solve Travelling Salesman Problem. My chromosom representation is like 32415 as the order of the cities. I have tried 3 Crossing-Over methods.These are Classic, OX1 and Greedy. But any of them couldnt help me to solve TSP efficiently. The basic problem is that the algorithym always leaves an unfixed crossed path. This means it doesnt works good.
To be clearly understanded, please see this
image. The circled paths can be fixed to get a better solution as you see.But GA doesn't do that. How can I fix this problem?
I am using tournament with group of 5 to select parents, generally %3 mutation odds and 10000 fixed population size.
My code for Crossing Over, Mutation and GA Procedure:
Tour OrderingCrossingOver(Tour mother, Tour father)
{
int numberOfGens = rnd.Next(1, N - 2);
int pos = rnd.Next(0, N - numberOfGens);
City[] gens = new City[N];
List<City> noneGens = new List<City>(father.Cities);
List<int> nonePos = new List<int>();
for (int i = 0; i < N; i++)
{
if (i < pos || i >= pos + numberOfGens)
{
nonePos.Add(i);
continue;
}
gens[i] = mother.Cities[i];
noneGens.Remove(gens[i]);
}
for (int i = 0; i < noneGens.Count; i++)
{
gens[nonePos[i]] = noneGens[i];
}
noneGens.Clear();
nonePos.Clear();
return new Tour(map) { Cities = gens };
}
void Mutation(Tour tour)
{
int i = rnd.Next(N - 1);
int j = rnd.Next(N - 1);
City temp = tour.Cities[i];
tour.Cities[i] = tour.Cities[j];
tour.Cities[j] = temp;
mut++;
}
public void StartAsync()
{
Task.Run(() =>
{
isRunning = true;
CreatePopulation();
int st = 0;
while (currentProducedPopSize < maxPopNumber && !stopped)
{
int[] nums = selectParents();
Tour parent1 = population[nums[0]];
Tour parent2 = population[nums[1]];
#region First Child
Tour child = OrderingCrossingOver(parent1, parent2);
Tour old = new Tour(map) { Cities = child.Cities };
if (mutPosibility >= rnd.Next(1, 100))
Mutation(child);
population[nums[nums.Length - 1]] = child;
if (this.Best.Value > child.Value)
this.Best = child;
#endregion
#region Second Child
child = OrderingCrossingOver(parent2, parent1);
if (mutPosibility >= rnd.Next(1, 100))
Mutation(child);
population[nums[nums.Length - 2]] = child;
if (this.Best.Value > child.Value)
this.Best = child;
#endregion
currentProducedPopSize += 2;
st++;
this.Progress = double.Parse((currentProducedPopSize * 1.0 / maxPopNumber * 100).ToString("00.00"));
}
isRunning = false;
stopped = false;
this.Best = population[population.Length - 1];
if (GACompleted != null)
GACompleted(this, EventArgs.Empty);
});
}