4
$\begingroup$

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?

$\endgroup$
1
  • 4
    $\begingroup$ 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. $\endgroup$
    – whuber
    Jan 30, 2011 at 18:02

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.