Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

python

What is roulette wheel selection?

Fahad Tahir

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Overview

Roulette wheel selection, commonly known as the fitness-proportion selection, is a way to randomly select from a given list of weighted inputs.

This is done similarly to having a roulette wheel with all the desired inputs and only selecting an input based on the spin result.

How roulette wheel selection works

When spinning a standard roulette wheel, each result has the same chance of occurring. In roulette wheel selection, however, each result is weighted such that some are more likely to occur than others.

Balls are selected using a ticker, which spins before randomly stopping somewhere on the wheel.

For example, let’s model picking a random colored ball from a bag with a weighted roulette wheel. For our example, we use:

  • Five red balls
  • Three blue balls
  • Two orange balls
  • One green ball
  • Six yellow balls
A weighted roulette wheel

We're always more likely to get the color red by spinning this roulette wheel. That is, any random ball we pick is more likely to be red. However, that doesn't mean we can't pick a color like green; it just has less probability of being selected.

Roulette wheel selection implementation

Here’s how we can implement a simple weighted roulette wheel in Python.

from random import uniform
inputs = [5, 3, 2, 1, 6]
colors = ['Red', 'Blue', 'Orange', 'Green', 'Yellow']
def roulette_wheel(inputs):
total_count = sum(inputs)
probabilities = [round((float)(value)/total_count,2) for value in inputs]
randomNumber = round(uniform(0, 1),3)
cumulativeprobability = [probabilities[0]]
for value in probabilities[1:]:
cumulativeprobability.append(round(value + cumulativeprobability[-1],2))
print("The probabilities of each color: ", probabilities)
print("\nThe cumulative probabilities are: ", cumulativeprobability)
choose = 0
count = 0
for value in probabilities:
choose = choose + value
count +=1
if choose >= randomNumber:
print("\nThe Random Number is: ", str(randomNumber) + '\n')
print("Number Selected: " + str(value) + ". It's color is: " + colors[probabilities.index(value)])
break
roulette_wheel(inputs)

Explanation

  • Line 1: We’re just importing one useful function from the random module. We’ll use this later.

  • Line 2–3: We’ll initialize two lists. One list has every color; the other has its number of occurrences or frequency.

  • Line 4: We define and name our function, passing in inputs.

  • Line 5: Create a variable called total_count. Inside this variable, we store the sum of all our inputs.

  • Line 6: We’ll find the probability of drawing any single color of the ball. We iterate through our input, then divide each entry by the total number of entries in our input. Finally, we append our result to a new list called probabilities. We round our answer to two decimal places with the in-built round function.

  • Line 8: We’ll initialize a variable called randomNumber. In it, we are storing a random value between 0 and our max weight. This is done through the uniform method in our imported random module. This way, we can simulate a spin of the wheel. Here, think of the value of randomNumber as a random area we chose on a roulette wheel.

  • Line 10–12: We’ll create a new list called cumulativeprobability. We store the first value of our probability list here. Then, we iterate through probability, adding each iteration to the most recent value added to cumulativeprobability and append it at the end.

  • Line 16–17: We’ll initialize two variables, choose and count. Choose will be used to obtain our result, while count will get us the color of our result.

  • Line 18–23: We iterate through probabilities, adding its values to our chosen variable. If the value of choose is greater than or equal to our randomNumber, we print out this value. This is our selection. Printing out the corresponding value in our color list using count gives us the right color.

  • Line 24: We’ll exit the loop since we already have our answer.

The benefits of roulette wheel selection

Roulette wheel selection is beneficial in situations where we want controlled randomness. Anything can happen, but not everything is equally likely to happen.

In practical applications, this is often used when selecting genes for genetic algorithms. Here, we need to select a random gene to use later, but not all genes are equally likely to be selected. To simulate this, we use roulette wheel selection.

RELATED TAGS

python

CONTRIBUTOR

Fahad Tahir
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring