Roulette wheel selection algorithm [duplicate]

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.

Parachute

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

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

Answer 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.

Saccharin

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

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

@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. – Irtysh

Answer 2

def roulette_select(population, fitnesses, num):
    """ Roulette selection, implemented according to:
        <https://mcmap.net/q/341567/-roulette-selection-in-genetic-algorithms
        -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

Mantle

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

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? – Mantle

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? – Otho

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). – Mantle

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

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

Answer 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

Plagiarize

Answer 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.

Torsibility

Answer 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.

Tottering

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). – Backman

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 :) – Tottering

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. – Backman

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. – Tottering

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. – Backman

Answer 6

I wanted the same and so created this self-contained Roulette class. You give it a series of weights (in the form of a double array), and it will simply return an index from that array according to a weighted random pick.

I created a class because you can get a big speed up by only doing the cumulative additions once via the constructor. It's C# code, but enjoy the C like speed and simplicity!

class Roulette
{
    double[] c;
    double total;
    Random random;

    public Roulette(double[] n) {
        random = new Random();
        total = 0;
        c = new double[n.Length+1];
        c[0] = 0;
        // Create cumulative values for later:
        for (int i = 0; i < n.Length; i++) {
            c[i+1] = c[i] + n[i];
            total += n[i];
        }
    }

    public int spin() {
        double r = random.NextDouble() * total;     // Create a random number between 0 and 1 and times by the total we calculated earlier.
        //int j; for (j = 0; j < c.Length; j++) if (c[j] > r) break; return j-1; // Don't use this - it's slower than the binary search below.

        //// Binary search for efficiency. Objective is to find index of the number just above r:
        int a = 0;
        int b = c.Length - 1;
        while (b - a > 1) {
            int mid = (a + b) / 2;
            if (c[mid] > r) b = mid;
            else a = mid;
        }
        return a;
    }
}

The initial weights are up to you. Maybe it could be the fitness of each member, or a value inversely proportional to the member's position in the "top 50". E.g.: 1st place = 1.0 weighting, 2nd place = 0.5, 3rd place = 0.333, 4th place = 0.25 weighting etc. etc.

Backman

Answer 7

Well, for an American Roulette wheel, you're going to need to generate a random integer between 1 and 38. There are 36 numbers, a 0, and a 00.

One of the big things to consider, though, is that in American roulette, their are many different bets that can be made. A single bet can cover 1, 2, 3, 4, 5, 6, two different 12s, or 18. You may wish to create a list of lists where each number has additional flages to simplify that, or do it all in the programming.

If I were implementing it in Python, I would just create a Tuple of 0, 00, and 1 through 36 and use random.choice() for each spin.

Octamerous

Answer 8

This assumes some class "Classifier" which just has a String condition, String message, and double strength. Just follow the logic.

-- Paul

public static List<Classifier> rouletteSelection(int classifiers) {
    List<Classifier> classifierList = new LinkedList<Classifier>();
    double strengthSum = 0.0;
    double probabilitySum = 0.0;

    // add up the strengths of the map
    Set<String> keySet = ClassifierMap.CLASSIFIER_MAP.keySet();
    for (String key : keySet) {
        /* used for debug to make sure wheel is working.
        if (strengthSum == 0.0) {
        ClassifierMap.CLASSIFIER_MAP.get(key).setStrength(8000.0);
        }
         */
        Classifier classifier = ClassifierMap.CLASSIFIER_MAP.get(key);
        double strength = classifier.getStrength();
        strengthSum = strengthSum + strength;
    }
    System.out.println("strengthSum: " + strengthSum);

    // compute the total probability. this will be 1.00 or close to it.
    for (String key : keySet) {
        Classifier classifier = ClassifierMap.CLASSIFIER_MAP.get(key);
        double probability = (classifier.getStrength() / strengthSum);
        probabilitySum = probabilitySum + probability;
    }
    System.out.println("probabilitySum: " + probabilitySum);

    while (classifierList.size() < classifiers) {
        boolean winnerFound = false;
        double rouletteRandom = random.nextDouble();
        double rouletteSum = 0.0;

        for (String key : keySet) {
            Classifier classifier = ClassifierMap.CLASSIFIER_MAP.get(key);
            double probability = (classifier.getStrength() / strengthSum);
            rouletteSum = rouletteSum + probability;
            if (rouletteSum > rouletteRandom && (winnerFound == false)) {
                System.out.println("Winner found: " + probability);
                classifierList.add(classifier);
                winnerFound = true;
            }
        }
    }
    return classifierList;
}

Inositol

Answer 9

You can use a data structure like this:

Map<A, B> roulette_wheel_schema = new LinkedHashMap<A, B>()

where A is an integer that represents a pocket of the roulette wheel, and B is an index that identifies a chromosome in the population. The number of pockets is proportional to the fitness proportionate of each chromosome:

number of pockets = (fitness proportionate) · (scale factor)

Then we generate a random between 0 and the size of the selection schema and with this random number we get the index of the chromosome from the roulette.

We calculate the relative error between the fitness proportionate of each chromosome and the probability of being selected by the selection scheme.

The method getRouletteWheel returns the selection scheme based on previous data structure.

private Map<Integer, Integer> getRouletteWheel(
        ArrayList<Chromosome_fitnessProportionate> chromosomes,
        int precision) {

    /*
     * The number of pockets on the wheel
     * 
     * number of pockets in roulette_wheel_schema = probability ·
     * (10^precision)
     */
    Map<Integer, Integer> roulette_wheel_schema = new LinkedHashMap<Integer, Integer>();
    double fitness_proportionate = 0.0D;
    double pockets = 0.0D;
    int key_counter = -1;
    double scale_factor = Math
            .pow(new Double(10.0D), new Double(precision));
    for (int index_cromosome = 0; index_cromosome < chromosomes.size(); index_cromosome++){

        Chromosome_fitnessProportionate chromosome = chromosomes
                .get(index_cromosome);
        fitness_proportionate = chromosome.getFitness_proportionate();
        fitness_proportionate *= scale_factor;
        pockets = Math.rint(fitness_proportionate);
        System.out.println("... " + index_cromosome + " : " + pockets);

        for (int j = 0; j < pockets; j++) {
            roulette_wheel_schema.put(Integer.valueOf(++key_counter),
                    Integer.valueOf(index_cromosome));
        }
    }

    return roulette_wheel_schema;
}

Syst

Answer 10

I have worked out a Java code similar to that of Dan Dyer (referenced earlier). My roulette-wheel, however, selects a single element based on a probability vector (input) and returns the index of the selected element. Having said that, the following code is more appropriate if the selection size is unitary and if you do not assume how the probabilities are calculated and zero probability value is allowed. The code is self-contained and includes a test with 20 wheel spins (to run).

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 * Roulette-wheel Test version.
 * Features a probability vector input with possibly null probability values.
 * Appropriate for adaptive operator selection such as Probability Matching 
 * or Adaptive Pursuit, (Dynamic) Multi-armed Bandit.
 * @version October 2015.
 * @author Hakim Mitiche
 */
public class RouletteWheel {

/**
 * Selects an element probabilistically.  
 * @param wheelProbabilities elements probability vector.
 * @param rng random generator object
 * @return selected element index
 * @throws java.lang.Exception 
 */
public int select(List<Double> wheelProbabilities, Random rng) 
        throws Exception{

    double[] cumulativeProba = new double[wheelProbabilities.size()];
    cumulativeProba[0] = wheelProbabilities.get(0);
    for (int i = 1; i < wheelProbabilities.size(); i++)
    {
        double proba = wheelProbabilities.get(i);
        cumulativeProba[i] = cumulativeProba[i - 1] + proba;
    }
    int last = wheelProbabilities.size()-1;
     if (cumulativeProba[last] != 1.0)
     {
            throw new Exception("The probabilities does not sum up to one ("
                    + "sum="+cumulativeProba[last]);
     }
    double r = rng.nextDouble();
    int selected = Arrays.binarySearch(cumulativeProba, r);
     if (selected < 0)
        {
            /* Convert negative insertion point to array index.
            to find the correct cumulative proba range index.
            */
            selected = Math.abs(selected + 1);
        }
     /* skip indexes of elements with Zero probability, 
        go backward to matching index*/  
    int i = selected; 
    while (wheelProbabilities.get(i) == 0.0){
        System.out.print(i+" selected, correction");
        i--;
        if (i<0) i=last;
    }
    selected = i;
    return selected;
}



   public static void main(String[] args){

   RouletteWheel rw = new RouletteWheel();
   int rept = 20;
   List<Double> P = new ArrayList<>(4);
   P.add(0.2);
   P.add(0.1);
   P.add(0.6);
   P.add(0.1);
   Random rng = new Random();
   for (int i = 0 ; i < rept; i++){
       try {
           int s = rw.select(P, rng);
           System.out.println("Element selected "+s+ ", P(s)="+P.get(s));
       } catch (Exception ex) {
           Logger.getLogger(RouletteWheel.class.getName()).log(Level.SEVERE, null, ex);
       }
   }
   P.clear();
   P.add(0.2);
   P.add(0.0);
   P.add(0.5);
   P.add(0.0);
   P.add(0.1);
   P.add(0.2);
   //rng = new Random();
   for (int i = 0 ; i < rept; i++){
       try {
           int s = rw.select(P, rng);
           System.out.println("Element selected "+s+ ", P(s)="+P.get(s));
       } catch (Exception ex) {
           Logger.getLogger(RouletteWheel.class.getName()).log(Level.SEVERE, null, ex);
       }
   }
}

 /**
 * {@inheritDoc}
 * @return 
 */
 @Override
 public String toString()
 {
    return "Roulette Wheel Selection";
 }
}

Below an execution sample for a proba vector P=[0.2,0.1,0.6,0.1], WheelElements = [0,1,2,3]:

Element selected 3, P(s)=0.1

Element selected 2, P(s)=0.6

Element selected 3, P(s)=0.1

Element selected 2, P(s)=0.6

Element selected 1, P(s)=0.1

Element selected 2, P(s)=0.6

Element selected 3, P(s)=0.1

Element selected 2, P(s)=0.6

Element selected 2, P(s)=0.6

Element selected 2, P(s)=0.6

Element selected 2, P(s)=0.6

Element selected 2, P(s)=0.6

Element selected 3, P(s)=0.1

Element selected 2, P(s)=0.6

Element selected 2, P(s)=0.6

Element selected 2, P(s)=0.6

Element selected 0, P(s)=0.2

Element selected 2, P(s)=0.6

Element selected 2, P(s)=0.6

Element selected 2, P(s)=0.6

The code also tests a roulette wheel with zero probability.

Hanukkah

Answer 11

I am afraid that anybody using the in built random number generator in all programming languages must be aware that the number generated is not 100% random.So should be used with caution.

Mccorkle

Thank you for the precious information. – Hofer

Answer 12

Random Number Generator pseudo code

• add one to a sequential counter
• get the current value of the sequential counter
• add the counter value by the computer tick count or some other small interval timer value
• optionally add addition numbers, like a number from an external piece of hardware like a plasma generator or some other type of somewhat random phenomena
• divide the result by a very big prime number 359334085968622831041960188598043661065388726959079837 for example
• get some digits from the far right of the decimal point of the result
• use these digits as a random number

Use the random number digits to create random numbers between 1 and 38 (or 37 European) for roulette.

Creigh

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? – Demars