  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.
