# Pick a random item with the help of an array of cumulative probabilities

I have to implement a genetic algorithm and therefore select the "fittest" of all possible members of a generation.

I have the following arrays of fitnesses, their weighed equivalents and a cumulative array.

Fitnesses: [0.2, 0.0, 0.2, 0.0, 0.0, 0.0]
Weighed Fitnesses: [0.5, 0.0, 0.5, 0.0, 0.0, 0.0]
Cumulative Fitnesses: [0.5, 0.5, 1.0, 1.0, 1.0, 1.0]


Now I have to choose five new members, with a higher probability of the chosen member being fitter than the others, i.e. the probability of being chosen proportional to the fitness.

How would I go about doing this by using a random number?

• Generate a random float x in the interval (0,1) and perform a binary search of the cumulative fitness array, finding the first entry that equals or exceeds x. Its index denotes the chosen fitness.
– whuber
Jan 30, 2011 at 18:02

Whuber answer is of course very good and simple, but if You are looking for something faster (binary search approach needs $O(logn)$ steps) then You can look at Walker's alias method, it is described well in Knuths Art of Computer Programming, unfortunatelly I can't tell You the exact page because I have only Polish version of this book. You can also read this article. These method allows to draw a random number from any finite discrete distribution in constant time.