„Roulette-wheel selection via stochastic acceptance”, Physica A 391, 2193 (2012)  (arxiv preprint)


Outline of  implementation:

  1) select (uniformly) one of the n elements, say k-th
  2) accept the selection with probability weight(k)/max, where max is the maximum weight
  3) if not accepted, select anew (step 1)

f77 code:

c----------------------------- roulette-wheel selection --------------------

c code selects one of n elements with probability proportional to weight(k)
        notaccepted=.TRUE.
        do while (notaccepted)
            call rndgnrt(r) ! generates a random number r (0<r<1)
            k=int(r*n)+1 ! k - randomly drawn integer number (k=1, 2,..., n)
            call rndgnrt(r)
            if (r.LT.weight(k)/MAX) notaccepted=.FALSE. ! MAX - maximum of weights
       end do
       write(6,*) 'selected number=', k

Comment: Typically,  weight(k) are evolving and one should keep track of the max. However, when weight(k) are known to be bounded, e.g., by definition one has  0<weight(k)<BOUND, then BOUND can be used instead of  MAX. It reduces efficiency but simplifies the algorithm.