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.
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.
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:
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.
Here’s how we can implement a simple weighted roulette wheel in Python.
from random import uniforminputs = [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 = 0count = 0for value in probabilities:choose = choose + valuecount +=1if choose >= randomNumber:print("\nThe Random Number is: ", str(randomNumber) + '\n')print("Number Selected: " + str(value) + ". It's color is: " + colors[probabilities.index(value)])breakroulette_wheel(inputs)
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.
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
CONTRIBUTOR
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.