PlumX Metrics
Embed PlumX Metrics

The quasispecies regime for the simple genetic algorithm with ranking selection

Transactions of the American Mathematical Society, ISSN: 0002-9947, Vol: 369, Issue: 9, Page: 6017-6071
2017
  • 5
    Citations
  • 0
    Usage
  • 14
    Captures
  • 0
    Mentions
  • 0
    Social Media
Metric Options:   Counts1 Year3 Year

Metrics Details

  • Citations
    5
    • Citation Indexes
      5
  • Captures
    14

Article Description

We study the simple genetic algorithm with a ranking selection mechanism (linear ranking or tournament). We denote by ℓ the length of the chromosomes, by m the population size, by p the crossover probability and by p the mutation probability. We introduce a parameter σ, called the strength of the ranking selection, which measures the selection intensity of the fittest chromosome. We show that the dynamics of the genetic algorithm depends in a critical way on the parameter π = σ(1−p)(1−p). If π < 1, then the genetic algorithm operates in a disordered regime: an advantageous mutant disappears with probability larger than 1 − 1/m, where β is a positive exponent. If π > 1, then the genetic algorithm operates in a quasispecies regime: an advantageous mutant invades a positive fraction of the population with probability larger than a constant p (which does not depend on m). We estimate next the probability of the occurrence of a catastrophe (the whole population falls below a fitness level which was previously reached by a positive fraction of the population). The asymptotic results suggest the following rules: • π=σ(1−p)(1−p) should be slightly larger than 1; • p should be of order 1/ℓ; • m should be larger than ℓlnℓ; • the running time should be at most of exponential order in m. The first condition requires that ℓp + p < ln σ. These conclusions must be taken with great care: they come from an asymptotic regime, and it is a formidable task to understand the relevance of this regime for a real-world problem. At least, we hope that these conclusions provide interesting guidelines for the practical implementation of the simple genetic algorithm.

Provide Feedback

Have ideas for a new metric? Would you like to see something else here?Let us know