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
- 5Citations
- 14Captures
Metric Options: Counts1 Year3 YearSelecting the 1-year or 3-year option will change the metrics count to percentiles, illustrating how an article or review compares to other articles or reviews within the selected time period in the same journal. Selecting the 1-year option compares the metrics against other articles/reviews that were also published in the same calendar year. Selecting the 3-year option compares the metrics against other articles/reviews that were also published in the same calendar year plus the two years prior.
Example: if you select the 1-year option for an article published in 2019 and a metric category shows 90%, that means that the article or review is performing better than 90% of the other articles/reviews published in that journal in 2019. If you select the 3-year option for the same article published in 2019 and the metric category shows 90%, that means that the article or review is performing better than 90% of the other articles/reviews published in that journal in 2019, 2018 and 2017.
Citation Benchmarking is provided by Scopus and SciVal and is different from the metrics context provided by PlumX Metrics.
Example: if you select the 1-year option for an article published in 2019 and a metric category shows 90%, that means that the article or review is performing better than 90% of the other articles/reviews published in that journal in 2019. If you select the 3-year option for the same article published in 2019 and the metric category shows 90%, that means that the article or review is performing better than 90% of the other articles/reviews published in that journal in 2019, 2018 and 2017.
Citation Benchmarking is provided by Scopus and SciVal and is different from the metrics context provided by PlumX Metrics.
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.
Bibliographic Details
American Mathematical Society (AMS)
Provide Feedback
Have ideas for a new metric? Would you like to see something else here?Let us know