Roulette-wheel selection via stochastic acceptance
By Adam Lipowski, Dorota Lipowska. arXiv.org, 2011
769 citations recorded by the source corpus.
Roulette-wheel selection is a frequently used method in genetic and evolutionary algorithms or in modeling of complex networks. Existing routines select one of N individuals using search algorithms of O(N) or O(logN) complexity. We present a simple roulette-wheel selection algorithm, which typically has O(1) complexity and is based on stochastic acceptance instead of searching. We also discuss a hybrid version, which might be suitable for highly heterogeneous weight distributions, found, for example, in some models of complex networks. With minor modifications, the algorithm might also be used for sampling with fitness cut-off at a certain value or for sampling without replacement.
Subfields: Artificial Intelligence, Molecular Biology, Statistical and Nonlinear Physics
View Paper: https://www.semanticscholar.org/paper/82e1dcbf4b3bbedaf5702e4b9d9e927e09654dbd
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Molecular Biology
Citations in the corpus
- Connecting Large Language Models with Evolutionary Algorithms Yields Powerful Prompt Optimizers (2024, neutral): “Selection In GA, parent solutions are conventionally selected using the roulette wheel selection method, guided by their fitness values (Lipowski & Lipowska, 2012).”
- Fast Convolutional Neural Network Training Using Selective Data Sampling: Application to Hemorrhage Detection in Color Fundus Images (2016, background): “in is selected randomly while in is selected with probability [32]–[34]:”
- Choosing Mutation and Crossover Ratios for Genetic Algorithms - A Review with a New Dynamic Approach (2019, methodology): “Fitness values are used to choose Parents where the best chromosome stands a higher chance of selection [35,36].”