Roulette Wheel Selection Algorithm

Question

Can someone provide some pseudo code for the roulette selection function? How to implement this: I really don’t understand how to read this mathematical notation. I need a general algorithm.

Answer 1

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

Here is some Java code that implements the choice of the roulette wheel.

Suppose you have 10 items to choose from, and you select by creating a random number from 0 to 1. You divide the range from 0 to 1 up into ten disjoint segments, each of which is proportional to the fitness of one of ten items, For example, this can 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 from 0 to 1 is your rotation. If the random number is 0.46, then the selected element is paragraph 3. If it is 0.92, then this is paragraph 9.

Answer 2

Here is some 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 

Answer 3

There are two steps to this: first create an array with all the values ​​on the wheel. It can be a 2-dimensional array with color as well as a number, or you can add 100 to the red numbers.

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

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

Extract the value from this position in the array and you have a random roulette number.

Final note : do not forget to sow the random number generator or you will get the same sequence of draws every time you start the program.

Answer 4

First, create an array of the percentages you specify, say p[1..n] and suppose that the sum is the sum of all percentages.

Then we get a random number from 1 to the total, 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 

Answer 5

Here is a very quick way to do this using thread selection in Java. It selects the indices of the array using the values ​​in the form of weights. No cumulative weights needed due to 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 by using Kahan summation or reading doubles as iterable if the array was too large to initialize immediately.

Answer 6

I needed the same and created this independent class of roulette. You give it a series of weights (in the form of a double array), and it simply returns the index from that array according to a weighted random selection.

I created the class because you can get more speed by only making cumulative additions once through the constructor. This is C # code, but enjoy C as fast and easy!

 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 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. Perhaps this may be the suitability of each member or a value inversely proportional to the position of the member in the "top 50". For example: 1st place = 1.0 weighing, 2nd place = 0.5, 3rd place = 0.333, 4th place = 0.25 weighing, etc. Etc.

Answer 7

Well, for the American Roulette wheel you will need to generate a random integer from 1 to 38. There are 36 numbers, 0 and 00.

One of the great things to keep in mind is that there are a lot of different bets to make in American roulette. One bet can cover 1, 2, 3, 4, 5, 6, two different 12 or 18. You might want to create a list of lists in which each number has additional flags to simplify this, or do it all in programming.

If I implemented it in Python, I would just create a Tuple from 0, 00 and from 1 to 36 and use random.choice () for each rotation.

Answer 8

This assumes some Classifier class that only has a String condition, a String message, and double power. 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; } 

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 representing the pocket of the roulette wheel , and B is the index that identifies the chromosome in the population . The number of pockets is proportional to the proportion of suitability of each chromosome:

number of pockets = (proportional to fitness) · (scale factor)

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

We calculate the relative error between the suitability ratio of each chromosome and the probability of selection according to the selection scheme.

The getRouletteWheel method returns a selection scheme based on the 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; } 

Answer 10

I developed Java code similar to Java Dan Dyer (link to it earlier). However, my roulette wheel selects one element based on a probability (input) vector 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 probabilities are calculated and a value of zero probability is allowed. The code is self-contained and includes a 20-wheel test (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 the sample run for the sample 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 checks the roulette wheel with zero probability.

Answer 11

I am afraid that anyone who uses the built-in random number generator in all programming languages ​​should know that the generated number is not 100% random. Use with caution.

Answer 12

Random Number Generator Pseudocode

• add one to the serial counter
• get the current value of the serial counter
• add the counter value for the number of computers count or another value of a small timer interval
• optionally add add-on numbers, such as a number from an external device such as a plasma generator or some other type of random event.
• divide the result by a very large prime number 359334085968622831041960188598043661065388726959079837 for example.
• get some digits from the right edge of the decimal point of the result
• use these numbers as a random number

Use random numbers to create random numbers from 1 to 38 (or 37 European) for roulette.