user11406
user11406

Reputation: 1258

Adaptive mutation/crossover rates for genetic algorithms

I've been looking into ways I can implement an adaptive mutation rate for a genetic algorithm I'm working on. I've seen an algorithm which uses the current individuals fitness and the average population fitness to calculate a mutation rate, however I'm not sure it's very effective.

In the algorithm I've seen you do the following:

mutationRate = (bestFitness - individualFitness) / (bestFitness - averageFitness) * 0.5

Would this be a good approach or are there better?

Upvotes: 4

Views: 1705

Answers (2)

manlio
manlio

Reputation: 18972

I don't think there is a "best way": mutation algorithm and mutation rate are quite problem/algorithm specific.

Unfortunately, according to many practical experiments, even self-adaptive mutation may easily get trapped into local optima.

With the adaptive mutation approach you're using, an individual with high fitness correspond to a smaller mutation probability and individuals with low fitness corresponds to a high mutation probability.

This method can effectively protect the excellent individuals, but it is easy to fall into local convergence.

A different (and not necessarily better) approach is to increase mutation rate if the genetic diversity is gradually lost (in order to maintain a population distributed in the search space).

Otherwise, the value is reduced when an increase in the population diversity is observed.

These changes in the value of the mutation rate are also an additional source for a good balance between exploration and exploitation (see 1).

References

  1. A New Strategy for Adapting the Mutation Probability in Genetic Algorithms - Natalia Stark, Gabriela Minetti, Carolina Salto
  2. Adaptive mutation rate control schemes in genetic algorithms - Dirk Thierens

Upvotes: 4

trailmax
trailmax

Reputation: 35126

There is no silver bullet in GA. There are multiple ways you can implement mutation and other factors, but all depend on your domain you work with, amount of constraints, fitness function and all the rest.

The best you can do is to find out yourself - play with different approaches and see if you get better results. Also, perhaps https://cstheory.stackexchange.com/ would be a better place to ask such questions.

Upvotes: 1

Related Questions