How to avoid getting stuck on local optimum, for genetic algorithms

Question

I'm programming a genetic algorithm using grammatical evolution. My problem is that I reach local optimal values (premature convergence) and when that happens, I don't know what to do. I'm thinking about increasing the mutation ratio (5% is it's default value), but I don't know how to decide when it is necessary.

The data I have on every generation is a bidimensional array whose first column is its fitness

adn[i][0] ← fitness 
row → is the values of the Grammar
column ↓ Each indiviual result

If you need clarification, please ask and I'll be pleased of modifying. Note that this is not my mother language and sorry for the mistakes and for the inconvenience.

Answering a request, my operations are the following, and exactly in this order:

• I generate a random Population (A matrix with random numbers)
• I generate a matrix that contains the desired result. For doing this, i have implemented a couple functions that have aditionally a +-5% of variation, for example: fun(x)= (2*cos(x) + sen(x) - 2X) * (0,95+(a number oscillating between 0 and 0,1), the x contains every f(x) with sequentially from 0 to N (Being N the size of row), the y contains exactly the same (more results)
• Starts algorithm (generations beginning to change

The actions that make every generation are:

• Mutation: A random number of every cromosome can mutate on any gene → adn[i][random] = random number (with a 5% of probability of this happening)
• Crossover: I cross every adn with other adn (80% is the chance of mutation for every pair), for the pairing I pick a random number and face adn[i] and adn[(i+j) mod NumADNs]

• Translate. I get a matrix that contains the values f(0 to N) making in one step transcription and translate aplying the grammar on the image

  

-fitness: I compare the values obtained with the expected ones and update the fitness.

-Elitism: After that, i choose the best 4 adn's and get it to the top, they will be selected

-Selection: Any non elitist adn will face a totally random adn, and if its fitness is lower (Lower is better) will prevail, being a possibilities of the worse one surviving

Answer 1

It looks like you're dealing with premature convergence.

In other words, your population fills itself with individuals that represent the suboptimal solution and/or individuals that are (too) close to said solution.

The basic framework of a genetic algorithm is as follows:

P <- Population of size N with N random individuals.
evaluate fitness of all individuals in P
while (stopping criteria not met) {
    C <- empty Child set of size M
    while (size of C is not M) {
        parent1 <- select an individual from P
        parent2 <- select an individual from P

        child1, child2 <- combine parent1 and parent2 somehow.
        child1, child2 <- mutate children by chance
        evaluate fitness of child1, child2
        C <- C + child1 + child2
    }
    P <- combine P and C. (P remains size N)
}
return individual with best fitness

Note that the (e.g.) the size of the population/children doesn't have to be constant per se. Or you might combine a variable number of parents into a variable amount of children (e.g. a crossover between 5 parents resulting in 7 children). But I would keep it simple, at first.

As you can see, the main operators in a genetic algorithm are, in order

• Selection: Select individuals from the population that will be combined. Examples: tournament selection, proportionate selection, truncation selection, ...
• Crossover: Combine selected individuals (parents) to new indidivuals (children). Examples: one-point crossover, n-point crossover, uniform crossover, cut and splice, ...
• Mutation: By chance, (don't) mutate an individual by changing the individual slightly.
• Recombination: Somehow insert the children into the set of parents. Examples: Add all children to the population, sort the thing by fitness and remove the worst individuals so your population is size N again; Sort your population and drop the worst M individuals and add all children; often the same techniques that are presented in the selection phase are used.

In your description, you're confusing multiple steps as if it were one (e.g. you skip the selection step but you incoorperate it in the crossover step). You also describe techniques as if it were a step of the algorithm (e.g. Elitism is a technique used in the recombination step to ensure that at least the best individuals don't die).

An example where premature convergence might/will occur is when you only select the best individuals as parents and only allow the best individuals survive (in the recombination step).

Some possible methods to resolve this:

• Increase mutation rate. However, a mutation is usually a very random process. You would need 'pure' luck to escape the suboptimal solution.
• Redesign your genetic operations. e.g. allow bad fitness individuals/offspring to survive the generation more frequently. It could be that you're currently selecting too much good individuals to survive. Don't let too much bad individuals survive though, or your algorithm will never converge to something good.
• (...)

The goal is to tweek your genetic operations in such a way that in each next generation, the average fitness of your population has (preferably) increased while maintaining a big enough fitness variation. This is not easy.

There are several other methods to avoid premature convergence if the above doesn't help you out. I strongly recommend experimenting with altering your genetic operations first before doing this, however. Search terms: preselection, crowding, fitness sharing, incest prevention, ...

Answer 2

If you increase mutation rate you can bounce from local optimum, search more possibilities but there is tradeoff - with higher mutation rate convergence rate will change, and with too high rate it will stop converging.
When results stop changin for some number of iterations - this is when you stop, so it is also the moment to start the new search.
I would propose to mix GA with SA to find global optimum.
Working hacky solution is to remember local optima and restart (mutate or reinitialize), but after it discarded attractor - drop mutation rate.