Roulette wheel selection algorithm

Question

Can anyone provide some pseudo code for a roulette selection function? How would I implement this: I don't really understand how to read this math notation.I want General algorithm to this.

Solution 1

The other answers seem to be assuming that you are trying to implement a roulette game. I think that you are asking about roulette wheel selection in evolutionary algorithms.

Here is some Java code that implements roulette wheel selection.

Assume you have 10 items to choose from and you choose by generating a random number between 0 and 1. You divide the range 0 to 1 up into ten non-overlapping segments, each proportional to the fitness of one of the ten items. For example, this might look like this:

0 - 0.3 is item 1
0.3 - 0.4 is item 2
0.4 - 0.5 is item 3
0.5 - 0.57 is item 4
0.57 - 0.63 is item 5
0.63 - 0.68 is item 6
0.68 - 0.8 is item 7
0.8 - 0.85 is item 8
0.85 - 0.98 is item 9
0.98 - 1 is item 10

This is your roulette wheel. Your random number between 0 and 1 is your spin. If the random number is 0.46, then the chosen item is item 3. If it's 0.92, then it's item 9.

Solution 2

Here is a bit of python code:

def roulette_select(population, fitnesses, num):
    """ Roulette selection, implemented according to:
        <http://stackoverflow.com/questions/177271/roulette
        -selection-in-genetic-algorithms/177278#177278>
    """
    total_fitness = float(sum(fitnesses))
    rel_fitness = [f/total_fitness for f in fitnesses]
    # Generate probability intervals for each individual
    probs = [sum(rel_fitness[:i+1]) for i in range(len(rel_fitness))]
    # Draw new population
    new_population = []
    for n in xrange(num):
        r = rand()
        for (i, individual) in enumerate(population):
            if r <= probs[i]:
                new_population.append(individual)
                break
    return new_population

Solution 3

First, generate an array of the percentages you assigned, let's say p[1..n] and assume the total is the sum of all the percentages.

Then get a random number between 1 to total, let's say r

Now, the algorithm in lua:

local  c  =  0
for i = 1,n do
    c = c + p[i]
    if r <= c then
        return i
    end
end

Solution 4

There are 2 steps to this: First create an array with all the values on the wheel. This can be a 2 dimensional array with colour as well as number, or you can choose to add 100 to red numbers.

Then simply generate a random number between 0 or 1 (depending on whether your language starts numbering array indexes from 0 or 1) and the last element in your array.

Most languages have built-in random number functions. In VB and VBScript the function is RND(). In Javascript it is Math.random()

Fetch the value from that position in the array and you have your random roulette number.

Final note: don't forget to seed your random number generator or you will get the same sequence of draws every time you run the program.

Solution 5

Here is a really quick way to do it using stream selection in Java. It selects the indices of an array using the values as weights. No cumulative weights needed due to the mathematical properties.

static int selectRandomWeighted(double[] wts, Random rnd) {
    int selected = 0;
    double total = wts[0];

    for( int i = 1; i < wts.length; i++ ) {
        total += wts[i];            
        if( rnd.nextDouble() <= (wts[i] / total)) selected = i;
    }

    return selected;        
}

This could be further improved using Kahan summation or reading through the doubles as an iterable if the array was too big to initialize at once.

View more solutions

Comments

[Dan Dyer]

Edited tags. Somebody removed the "genetic" tag from the first revision of this question, making it a lot less clear what was being asked.

[Viktor Sehr]

unsigned int num = ::rand() % 37;

[Karl]

I think random numbers have been solved in every programming language ever, and this process no longer has to be done by hand. Why didn't you mention wiring up all the half-adders while youre at it?

[mkuse]

will this work, even if some of the fitness values are negative??

[noio]

No, it won't. But you have to wonder, since fitness corresponds to the probability of drawing that sample, there is no such thing as a negative probability of drawing a sample, so what kind of behavior would you expect?

[mkuse]

What I mean to say is, I have a fitness function which gives negative values. Suppose I am solving a problem in which the fitness is 'error', ie. difference of the target value to the value obtained by the GA. In this case the fitness function will generate negative values. How to I formulate this into a Routtle wheel?

[noio]

Like I said, you have to think about what you want to do with those negative values! The roulette wheel does not take fitness values as input, but (unnormalized) probabilities. You have to come up with a way to turn these possibly negative error values into probabilities. You are doing something weird if you can have negative error values, but maybe you can just negate them (error = -error), then what I usually do is fitness = 1/(1+error).

[Dan W]

That looks an interesting solution. I also gave an answer in the same hour as you, despite the question being years old (maybe you saw my post). Anyway, I love yours because it's so short, but I think mine may be more efficient due to the O(log2 n) efficiency instead of your O(n).

[Andrew Mao]

I think you bumped the question causing me to post my answer. Anyway, your initial cumulative sum still takes O(n). I think that is definitely a lower bound regardless :)

[Dan W]

Only the first time in the constructor. In a real world case, you'll be doing lots of 'roulette spins' (i.e. looking for many different parent pairs). That's where the O(log2 n) comes into play as only the spin() method is called afterwards.

[Andrew Mao]

That's true if you want to draw repeatedly from the same distribution. But I think that doesn't happen much in practice and from my experience; for example in genetic algorithms the fitness weights are always changing. Besides if you are going to draw a huge sample from such a distribution you don't need to really randomize at all as the fraction will converge to the normalized weights.

[Parrish Husband]

This is the fastest one I've encountered yet. Very nice.

[Phantômaxx]

Thank you for the precious information.

[fangmobile]

roulette wheel selection does not work with negative fitness values. Try tournament selection.

[Dan W]

Perhaps granted for GA like you say. For the case I needed it for though (simulating millions or billions of bets to test for risk/profit) my O(log2 n) answer code is an improvement. I'm sure there would be others cases too.

[Anik Islam Abhi]

you didn't replace the selected individual. Didn't it make a opening for the same item being selected again in the population ?

[Anik Islam Abhi]

No one talk about replacement of selected item so that selected item didn't get selected again . Any solution for this ?

[Sebastian Budka]

@AnikIslamAbhi as far as I'm concerned roulette wheel selection assumes that every item can be choosen more than one time. If you randomize N times (where N is population count) you would take exactly the same population after selection.