Source-linked AI summary
Roulette-wheel selection via stochastic acceptance
Adam Lipowski, Dorota Lipowska
TL;DR
Roulette-wheel selection commonly relies on O(N) or O(log N) search, motivating a faster implementation. The paper replaces searching with stochastic acceptance and shows that the resulting procedure preserves the roulette-wheel distribution while typically achieving O(1) complexity. It also discusses hybrid and modified versions for heterogeneous weights, fitness cut-offs, and sampling without replacement.
Problem
Existing roulette-wheel selection routines use linear or binary search, creating a need for faster implementations.
Method
The paper selects individuals uniformly and accepts them stochastically according to fitness, with hybrid and modified variants for special sampling settings.
Results
The stochastic-acceptance procedure has the same probability distribution as roulette-wheel selection and typically O(1) complexity.
Takeaways & Limitations
For genetic-algorithm population sizes from 10^2 to 10^4, the algorithm offers a significant CPU gain over linear- and binary-search routines.
Abstract
from arXiv · showhide
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(log(N)) 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.
I. INTRODUCTION
Roulette-wheel selection assigns survival and mating probability in proportion to fitness, but conventional implementations locate individuals through linear or binary search. The paper proposes a typically O(1) stochastic-acceptance alternative, while situating roulette-wheel selection among methods used in genetic algorithms and complex-network models.
- Selection probability is proportional to an individual’s fitness, so better-fitted individuals have greater survival and mating probability.
- Linear search locates a selected individual in O(N) operations, whereas binary search requires O(log N).
- Alternative selection methods include stochastic remainder, stochastic universal, and ranking-based approaches, whose relative advantages are difficult to determine.
- Roulette-wheel selection is also used in growing-network models, where attachment probability is proportional to an existing site’s degree.
- The proposed algorithm avoids searching by uniformly selecting an individual and using stochastic acceptance, typically achieving O(1) complexity.
II. DESCRIPTION AND PROPERTIES OF THE ALGORITHM
The algorithm repeatedly samples individuals uniformly and accepts each with probability proportional to fitness, preserving roulette-wheel probabilities without searching. Its typical O(1) complexity depends on the fitness distribution, while experiments compare it with linear and binary search.
- Algorithm procedure: The procedure selects an individual uniformly with probability 1/N and repeats after rejection until an attempt is accepted.Acceptance is based on the individual's fitness relative to the maximal fitness.
- Algorithm properties: The repeated-attempt procedure produces the same selection-probability distribution as roulette-wheel selection.The derivation sums the geometric series of failed attempts and recovers the roulette-wheel probability p_i.
- Algorithm properties: The algorithm's average number of attempts determines its computational complexity, which is typically O(1) when the relevant fitness ratio remains bounded.The stated condition includes bounded fitness and an average fitness that does not vanish as population size increases.
- Algorithm properties: Using an acceptance denominator A greater than the maximal fitness preserves the selection distribution but lowers efficiency through increased rejection.Choosing A = wmax is identified as optimal because smaller denominators can invalidate acceptance probabilities.
- Performance evaluation: In a uniformly distributed fitness experiment, stochastic acceptance matched roulette-wheel selection statistically and showed O(1) behavior against O(N) linear and O(log(N)) binary search.The comparison measured average execution time per selection as population size increased.
III. POSSIBLE EXTENSIONS AND CONCLUSIONS
The paper extends stochastic-acceptance roulette-wheel selection to heterogeneous weights, cutoff fitness, adaptive systems, and sampling without replacement. It concludes that the basic algorithm typically achieves O(1) complexity and significant CPU gains over linear or binary search for populations of 10^2 to 10^4.
- Extensions: Highly heterogeneous networks can reduce stochastic-acceptance efficiency because their degree-proportional weight distributions are broad and have very large maxima.The paper proposes a hybrid search-and-stochastic-acceptance algorithm when one or more weights greatly exceed the others.
- Extensions: The hybrid algorithm first selects an exceptionally heavy individual directly, then applies roulette-wheel selection to the remaining individuals.Removing the largest weight should make stochastic acceptance more efficient for the remaining N−1 weights.
- Extensions: The hybrid procedure preserves the intended selection probabilities for remaining individuals, and its generalization to several dominant weights is straightforward.The probability for an individual i > 1 is shown to equal the original fitness-proportional probability.
- Extensions: Sampling without replacement can be obtained by setting a selected individual’s fitness to 0, while retaining the old maximum may slightly reduce efficiency when it was selected.The old maximum can still calculate the acceptance probability wi/wmax after a new maximum is not found.
- Extensions: Replacing wmax with a constant A < wmax implements fitness cut-off at A and may increase population variability; the method can also be adapted to changing fitnesses.The paper cautions that selection-method performance depends on multiple factors and the optimization problem, with fuller comparisons left for future work.
- Conclusions: The algorithm typically has O(1) complexity and yields significant CPU gains over linear- or binary-search routines for populations from 10^2 to 10^4.The conclusion presents the method as simple and potentially modifiable for more sophisticated selection schemes.