Parameters setting in genetic programming to avoid locally optimum

Question

I'm fresh on genetic algorithm. Now, I wrote an python program based on genetic algorithm. The programming contain:

1. Set the population and individuals(For my case, each individual is a list with 8-elements)
2. Define the evaluation function to asses each individual's fitness(For my case, Larger is good.)
3. Define the grade function to calculate each generation's average fitness.
4. Each generation will sort by grade and leave higher ranked ones as parents.
5. parents will undergo the mutation and crossover.(For example, if the population = 100, only 20 parents was left dut to its higher grade. The rest 80 individuals as children are generated by randomly choosing father, mother for crossover. Then, the 100 individuals as next generation will go through another evolution)
6. After some generation, the ideal results should represent the highest grade.

My target was to get an 8-elements list with the highest fitness among the solution domain.

But in pratice, my program always got stuck into locally optimum. The result has many list containing he same number. By setting parameters correctly, it should solve my problem. But I want to modify them on target, not in eyeless.
The parameters I could change comprised by these:

1. len(population): the whole scale of individuals. For now, I set the len(population) = 10.
2. evolution time: It means the number of generations I will created by using subroutine like next_generation = evolve(population)
3. retain_fraction: After ranking by grade, the "outstanding" individuals' number would be determined by retain_fraction. For example, r_f = 0.2, len(pop)=10=> only 2 individual would be left.
4. mutation_frequency: By modify this arguement, an random point of individual would be changed into an random value in range(min(individual),max(individual)).

I tried to adjust them to get an better solution. But the result which represent the grade(average fitness of the generation) shows like this:

118.833333333
126.833333333
165.0
201.0
201.0
201.0
201.0
201.0
201.0
201.0
201.0

Answer 1

Metaheuristic algorithms such as Genetic Algorithm do not guarantee to find the global optimum. However, they do tend to produce suboptimal, yet good solutions and sometimes hit the global optimum. So you should not expect that GA succeeds in finding the global optimum every time you run it on each problem instance. Also, you do not need to have every individual become the global optimum, only one of them. So, instead of grade that is the average fitness, use the maximum.

Another thing you should change in your design in how you select individuals for crossover. Now, you choose the r_f*len(pop) best individuals, but if you do that, the best individual will always stay in the population. If that individual represents a local optimum, it is highly probable that its offspring will prevail in the population. Instead, you could select r_f*len(pop) individuals by roulette wheel. To make sure that GA remembers the best-so-far individual, store it in a special variable and update when necessary. :)

You are right when you say that the parameters influence performance. In the ideal case, your settings will lead to GA always finding the global optimum, however, it is not realistic due to the nature of metaheuristics. What you should aim for is minimizing fitness difference between global optimum to the best-so-far found optimum. This is usually done by experimenting with different values of parameters and selecting the combination that yields the best response over a set of problem instances. Recently, the Design of Experiments (DoE) approach has become popular in the field of metaheuristic research. You can try that.

$N \in [50,150], e \approx 0.8, \mu = 1/n$ are the commonly used settings, where $N$ is the number of individuals in population, $e$ corresponds to your r_f, $\mu$ is the probability to mutate a gene in individual, and $n$ is the number of genes in an individual, which corresponds to the number of problem dimensions.

However, there are several other things to take care of. Metaheuristic algorithms work better when they are used together with a problem-specific heuristic. For example, FlipGA is a tool for solving Boolean Satisfiability Problem (SAT). It consists of Genetic Algorithm where each individual is transformed with the Flip heuristic before crossover. That combination represents a very powerful SAT solver. I experimented with it and if Flip is taken away, pure GA is not able to find the global solution for problem instances where FlipGA succeeds in a matter of seconds. So, if you want to make your implementation of GA better, combine it with a problem-specific solving technique. Note that $N=10$ in the FlipGA paper.

Also, there are different types of crossover and mutation. Which do you use? Did you program 1-cut or 2-cut crossover? The latter performs better, at least from my experience. How did you implement mutation? If $a$ and $b$ are the minimal and maximal values of a gene, do you generate a random value from $[a,b]$ to replace the gene $x_i$ ($i=1,2,\ldots,n$) which has been selected for mutation, or you draw a relatively small random value $\Delta$ and add/subtract it to $x_i$?

Therefore, it is not just parameter values that play part in performance, it is the design of the algorithm. Moreover, different problems respond different to the same parameter settings and design choices.

In brief:

1. take different crossover and mutation stategies into consideration as well;
2. you can use the DoE techniques, as suggested in this thesis: Design of Experiments for the Tuning of Optimisation Algorithms, Enda Ridge (I need at least 10 reputation to post more than 2 links, otherwise, I would have included it here). It could take time, but your settings would have statistical justification;
3. you can specify several combination of parameters and strategies, run them over a set of problem instances, and go with the one that gives the best response.
4. do not expect GA to behave as exact methods which guarantee to find the global optimum. :)