Description for Genetic algorithm for Travelling salesman problem
Unzip each_with_each_2.zip to one new clear folder. Then open in matlab tsp_ga.m It will be opened
in matlab editor. Push F5. You will be asked to change folder, choose "change folder". Then after few
seconds figure must appear.
in gui_version subfolder there are gui version. Run tsp_ga_gui.m
Gui version is just same code as tsp_ga.m but add GUI, you can change here probabilities and randomize
nodes even during generations.
We have a set of cities (points) in 2d plane. Each city has road to each city. We need to find loop-path
that will be in each city only one time and path length is minimal.
The genetic algorithm is sequence of following operations that repeated in generations loop:
1) find length of paths
2) find probabilities
3) prepare to crossover according probabilities
4) crossover, parents replaced with children.
5) mutations
So we have a lot of paths with different lengths. A path can have crossover with another path and
mutate. After crossover it will be replaced by its children. All paths recorded in matrix G :
here we have population with 6 paths (population size ps=6), and it is for 4 cities. Each row of matrix G is
describe one path, for example path No.3 is:
2
1
4
3
3
1
1
2
3
4
2
2
3
3
2
2
1
3
4
4
1
1
4
4
path No. 1
path No. 2
path No. 3
path No. 4
path No. 5
path No. 6
