TSPEnryGA
by Enrico Mambrucchi
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
Child F1'
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
Child F1'
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
Parent P2
...Sequential Uniform Crossover...
Child C1
Child C2
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