7
$\begingroup$

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

    the grammar

-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

$\endgroup$
  • 1
    $\begingroup$ Your title asks about how to know if you are in local optimum - there are no more changes after some number of iterations, but the body asks what to do - add some global optimum technique. Did I understood correctly? $\endgroup$ – Evil Mar 23 '16 at 17:14
  • $\begingroup$ @EvilJS Yes, that is correct, my algorithm keeps running but there is no relevant changes. $\endgroup$ – Kaostias Mar 23 '16 at 22:54
  • $\begingroup$ So you track the number of iterations without change, and when this is bigger than given threshold, you stop computation, in your case instead of stop you could increase mutation rate and try again. If you try only the solution to increase mutation rate - give it some number of iterations and set it to default value. $\endgroup$ – Evil Mar 23 '16 at 23:06
  • $\begingroup$ I have the impression that you are mixing up the order of the operations. $\endgroup$ – Auberon Mar 24 '16 at 20:44
  • $\begingroup$ A random genome in every batch $\endgroup$ – t123 Sep 19 '17 at 19:49
9
$\begingroup$

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, ...

$\endgroup$
  • $\begingroup$ Well, the term "local optimum was used in articles and books, e.g. here long time ago. The term is a bit overloaded but it is used, and meaningful. $\endgroup$ – Evil Mar 23 '16 at 18:24
  • $\begingroup$ I'm going to try the dummy solutions surviving a little more (i did destroy it inmediately when confronted a better one in the random tournament) Which would be a good passing ratio for the bad solution ? $\endgroup$ – Kaostias Mar 23 '16 at 22:56
  • $\begingroup$ @Kaostias Can you edit your answer and describe you genetic operations briefly (selection, recombination, mutation, replacement, ...)? This way we might detect a possible cause of premature convergence. $\endgroup$ – Auberon Mar 24 '16 at 0:03
  • $\begingroup$ @Auberon done, sorry for the bad english, i have a great lack of synonims. $\endgroup$ – Kaostias Mar 24 '16 at 20:26
  • $\begingroup$ @Kaostias I've altered my answer to what I think will be most interesting for you. $\endgroup$ – Auberon Mar 24 '16 at 21:20
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.