Parameters when using Genetic Algorithm to solve TSP

Question

I just starting get a feel for genetic algorithm, and I am using it to solve traveling salesman problem. However, I am confused on what parameters I should use. Let me explain what I mean by parameters.

Parameters:

Population size

Number of Children Produced

Number of Mutations

I am sure that the above parameters depend on the number of cities that I have in my problem, and the exact form of my crossover and mutations specifications. But what is the relationship?

Is there any kind or rule of thumb on what parameters should be? Any kind of hints or suggestions would be great.

Here is what I did in detail for 5 city problem:

1) I generated 20 random paths, population = 20

2) Selected 14 best paths (threw away 6 worst ones)

3) Created 2 mutants from two paths randomly chosen from 14 best paths

Number of mutations = 2

(for mutation, I just swapped the order of two cities at random Ex: 0,1,2,3,4,0 could become 0,1,3,2,4,0

4) I created 4 children from 8 best paths.

Number of children = 4

(For crossover, I kept subpaths that were in common, and the rest was generated randomely) Ex: Parent 1: 0,1,2,3,4,0 , Parent 2: 0,2,1,3,4,0

3,4 are in common so the child path would travel from 3,4, the rest is random. Child path could be: 0,3,4,1,2,0 or 0,2,3,4,1,0

5) Now that I have 2 mutants and 4 children, I add them to my 14 best paths and I have a population of 20 paths.

6) do steps 2),3),4),5), and so on.

I set my parameters purely arbitrarily? Are they OK? What should I have used? What parameters should I use for a problem with 15 cities? 48 cities? 500 cities?

Thank You in Advance.

Answer 1

Your question is extremelly interesting and hard and I am sorry to say that there is no exact answer to it. I wrote a book on genetic algorithms and throughout its almost 500 pages I repeatedly insisted that the parameters are dependent on your problem.

Concerning your specific example, let us analyze your parameters. You have a population of 20 and each generation you will generate 6 different children. Assuming you have 50 generations, you will have analyzed 314 solutions (the 20 original individuals plus 49*6). Given that you have 5 cities, you have 5!=120 possible solutions, so your usage of GA is more time consuming than exhaustive search.

I know that this is a token problem and that you are concerned with the bigger problems (15, 48 and 500, to use your examples). Nevertheless, the rule of thumb is to have a small fraction of the search space covered (in the 48 and 500 case, this is automatic), so as to use the good characteristics of the GA to guide the search and you will probably get a good result. I suggest considering up to 0,001% of the search space as a total number of individuals generated throughout the whole execution (it might still be too much in the case of huge problems as the 500 cities one).

In terms of the operators used, there is a lot to say (in my book, it is more than 50 pages). Hence, I will refer you to a nice review written by Larrañaga et al. Even though it is a little old, it will provide guidance for you to explore your problem better. If you want a quicker reference, consider this Wikipedia article.

I am sorry for the advertising, but it is not intended to sell books (after all, my book is in portuguese and spanish only, so I don't think most members of this list will buy it). I just wanted to point out that there is a lot of literature on the subject. If you need an interesting read (and you don't speak portuguese), I suggest Michaewicz's book and the points it makes will certainly help you go deeper into your problem.