Roulette-wheel selection via stochastic acceptance
arXiv:1109.3627 · doi:10.1016/j.physa.2011.12.004
Abstract
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.
4 pages, Physica A, accepted
References in corpus (1)
Cited by in corpus (24)
- Deep autoregressive neural networks for high-dimensional inverse problems in groundwater contaminant source identification
- Go-Explore: a New Approach for Hard-Exploration Problems
- Parton showers beyond leading logarithmic accuracy
- Integration of adversarial autoencoders with residual dense convolutional networks for estimation of non-Gaussian hydraulic conductivities
- POBA-GA: Perturbation Optimized Black-Box Adversarial Attacks via Genetic Algorithm
- 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
- Collective predator evasion: Putting the criticality hypothesis to the test
- Coevolutionary search for optimal materials in the space of all possible compounds
- Multi-Objective Reinforced Evolution in Mobile Neural Architecture Search
- Competing Sudakov Veto Algorithms
- A generalized linear threshold model for an improved description of the spreading dynamics
- Managing Service-Heterogeneity using Osmotic Computing
- Statistical mechanics model of angiogenic tumor growth
- Phase transition and fast agreement in Naming Game with preference for multi-word agents
- Emergence of Social Structures via Preferential Selection
- Blockchain-assisted Demonstration Cloning for Multi-Agent Deep Reinforcement Learning
- Optimization of Coulomb Energies in Gigantic Configurational Spaces of Multi-Element Ionic Crystals
- Evolutionary Retrosynthetic Route Planning
- Critical behaviour of a tumor growth model - Directed Percolation with a mean-field flavour
- A Genetic Algorithm based Kernel-size Selection Approach for a Multi-column Convolutional Neural Network
- Inverse design of multilayer nanoparticles using artificial neural networks and genetic algorithm
- Generic criticality of community structure in random graphs
- Global optimization-based dimer method for finding saddle points
- Fast Stochastic Peer Selection in Proof-of-Stake Protocols