TSPEnryGA

   by Enrico Mambrucchi    English  Italiano    SourceForge.net Logo Support This Project
Download TSPEnryGA

Travelling Salesman Problem




Introduction


You have some cities. Find the shortest path which starts from a city, pass through all other cities and then come back to the starting one.

If there were just a few cities, you could solve this problem with a normal algorithm. Whenever you have a lot of cities, instead, you'd need a non-linear algorithm to get fast results. Here comes genetic algorithm.

Genetic Algorithm


A genetic algorithm is a method able to solve research and optimization problems.
They're based upon biological evolutionary systems. A population of subjects evolves itself, generation after generation, following natural selection and "the best survive" law, just like Charles Darwin said in his famous book.
Just imitating this behavior genetic algorithms can evolve solutions to real problems.
In nature, all the subjects of a population compete each other for food, water, territory, mating, ...
Those subjects better in reproduction and in surviving will have a greater number of descendant and so their characteristic will be inherited by a lot of subjects, while less adapted subjects will have a few children and, with time, they will extinct.
This is the way species can evolve erasing useless or negative characteristics and gaining better ones.
Genetic algorithms works in the same way. They represent a population of subjects, too, where every subject represent a possible solution to the problem.
Every subject has a score (fitness) depending on how good is the solution it gives.
Just like in nature, better subjects in a genetic algorithm have more possibility to reproduce themselves to transmit their own characteristic (genes) to future generations.

Adopted Solution


To solve the traveling salesman problem we represent every city with a gene.
A subject, his chromosome, is made by a list of all the genes and their order is the solution to the problem showed by the subject.
The shorter is the path, the better will be his fitness and so its possibility to reproduce itself.

Parent Selection


Subjects with higher fitness have more possibility to be selected for mating.
The selection is random but is driven to the subjects with higher fitness.

Fitness


We use fitness ranking to calculate the fitness of a subject.
In our case, we calculate the path's length of every subject (fitness).
Starting then from the subject with the higher length we order them by giving the fitness ranking value, a progressive number starting from 1 to n (number of subjects).
The best subject will have n as fitness value, and the worse 1.

Elitism


We use this technique to save the characteristics of the best subject (in our case we save two subjects).
The best chromosome (the one with the highest fitness) is copied into the new generation (we copy two subjects).
Using fitness ranking is possible than the best and the worse subjects wouldn't be chosen for mating. That's why we use elitism to save the best solution found until now.

Mutation


To grant a more random population, we add the possibility (very low probability around 0,001) of a mutation into the children just born.

Extended exchange mutation

In this case, if there is a mutation, we exchange the position of two genes, one chosen from the first chromosome's half and one from the second one.

Child F1
A B C D E F G H I J

Child F1'
A B I D E F G H C J


Extended double exchange mutation

With this technique we exchange two consecutive couple of genes, one in the first chromosome's half and one in the second one.

Child F1
A B C D E F G H I J

Child F1'
A B I J E F G H C D


Crossover


This is the technique to apply to cross two chromosomes and to obtain two children.
There are a lot of methods to crossover two chromosomes.
In our software we'll try some of them to see which are the best to solve the specific problem.

Sequential Uniform Crossover

This technique is the mix of two different techniques and it's good since it doesn't mix genes position. In our case it's very important to find a good solution.
We split the chromosome in four random parts (3-point crossover). Two of this parts will be copied in the child A and the other two in the child B, keeping the position where they were into the parent.
From the second parent, finally, we keep unused genes (those not used in the first parent) and we put them into the children filling their holes (we still keep the order but obviously we loose the position, this time).

Parent P1
A B I J E F G H I J

Parent P2
E H D B A G C J F I


...Sequential Uniform Crossover...

Child C1
E B I J A F G H I J


Child C2
A B H D E F G C J I


Single Point Crossover

This technique is easier and consist in splitting parent in two. Then we exchange those parts to make two children. It's very simple but still grants a good result since keep near parent's genes.

Mating


Using those techniques just said we select parents from the population and we create a brand new population with the same numbers of subjects (parents may be chosen more than one time for mating).
When the new generation is complete we erase the old one (subject which weren't chosen for mating die and don't spread their genes).

Software


In this software you can change some parameters before and during the execution (crossover and mutation type, ...) so that you can see which is the faster method to obtain the best result.
The graphical interface let you see the best path found at the moment so that you can have an idea about the eveolution of the population.

Download TSPEnryGA