Travelling Salesman - Genetic Algorithm

[nedo]

Introduction

I recently published the article An alternative introduction to Genetic and Evolutionary Algorithms, in which I presented an Evolutionary Algorithm that's capable of finding some math formulas.

The important traits there were the creation of populations, the selection of the best results when we don't have a satisfatory result and the reproduction with mutation. Those are all traits used by the Genetic Algorithms, yet my sample was not a Genetic Algorithm because it didn't used chromosomes and genes.

Well, this time I will present a real genetic algorithm which the purpose of solving the Travelling Salesman Problem (often presented simply as TSP).

Genes and chromosomes

Maybe the most important trait to have a Genetic Algorithm is the analogy to biology that requires the use of chromosomes and, consequently, the use of genes.

Many documents say that the chromosomes are usually represented as strings and the parts of that string are the genes. The samples in those documents actually use the string data type, so each character in the string is interpreted as a gene.

In the Travelling Salesman sample I am not using the string data type. Each gene is a Location that must be visited and the chromosomes are arrays of those Locations, effectively telling the travel plan (first we go there, then there...). The size of those chromosomes is the number of locations that must be visited and, to have a valid chromosome, all the locations must be visited exactly once.

It is important to note that the use of arrays doesn't violate the idea of "strings", as that's not a data-type name, it is simply an indication that we need a sequence of genes, and arrays do that job very well.

The basic algorithm

After having a list of locations that must be visited, an initial population of chromosomes (the travel plans) needs to be generated. To do that, it is enough to randomly order those places (yet other algorithms could be used here).

After creating that initial population, the code enters a loop in which it:

Selects the best chromosomes (the travel plans);

Presents the best solution up to that moment;

Reproduces them and continues the loop with the next generation.

The things that are specific to the problem are:

How does it decide what are the best chromosomes?

How does it decide when to stop?

During the reproduction, will it use crossovers, mutations or what exactly to evolve?

My answers to make the sample are:

It simply calculates the total distance travelled considering the order of the visited locations. The start location, which is the end location too and is always located in the top-left, is not encoded in the chromosomes to avoid wasting time with chromosomes that start at the wrong place, yet it is used to calculate the distance travelled;

It doesn't decide when to stop. The algorithm continues to run forever. It is the user of the application that may consider that a good solution was found (or is simply tired of waiting) and will close the application or try with new destinations;

Doing crossovers and random mutations will definetely create chromosomes that visit the same location twice. It may eventually evolve to the good solution but it will lose many time which those wrong solutions. This problem is a large one, so I will explain it in more detail.

Restul aici.