Roulette Wheel Selection
Note: this page has been created with the use of AI. Please take caution, and note that the content of this page does not necessarily reflect the opinion of Cratecode.
Roulette wheel selection is a popular technique in genetic algorithms to randomly choose parents for reproduction based on their fitness scores. It's like spinning a roulette wheel where each candidate in a population has a slice proportional to its fitness, and the wheel stops at a random position, selecting the parent within that slice. This method favors individuals with higher fitness scores, increasing the chances of better offspring.
How Roulette Wheel Selection Works
Imagine a roulette wheel with sectors assigned to each individual in the population based on their fitness scores. The probability of being chosen is proportional to the size of the individual's sector. Here's a step-by-step guide:
- Calculate the total fitness of the population.
- Calculate the relative fitness for each individual by dividing their fitness by the total fitness.
- Calculate the cumulative probability for each individual by summing up the relative fitnesses.
- Generate a random number between 0 and 1.
- Select the first individual whose cumulative probability is greater than or equal to the random number.
Let's go through an example to understand this better.
Suppose we have a population of four individuals with the following fitness scores:
Individual A: 12 Individual B: 8 Individual C: 6 Individual D: 4
- Calculate the total fitness:
Total Fitness = 12 + 8 + 6 + 4 = 30
- Calculate the relative fitness:
Individual A: 12 / 30 = 0.4 Individual B: 8 / 30 = 0.2667 Individual C: 6 / 30 = 0.2 Individual D: 4 / 30 = 0.1333
- Calculate the cumulative probability:
Individual A: 0.4 Individual B: 0.4 + 0.2667 = 0.6667 Individual C: 0.6667 + 0.2 = 0.8667 Individual D: 0.8667 + 0.1333 = 1
- Generate a random number between 0 and 1:
Random number = 0.52
- Select the parent:
In this case, the random number falls between the cumulative probabilities of Individual A (0.4) and Individual B (0.6667). So, Individual B is selected as a parent.
Repeat the process to select another parent, and then perform crossover and mutation to create offspring.
Here's a simple implementation of roulette wheel selection in Python:
import random def roulette_wheel_selection(population, fitness_scores): total_fitness = sum(fitness_scores) relative_fitness = [f / total_fitness for f in fitness_scores] cumulative_probability = [sum(relative_fitness[:i+1]) for i in range(len(relative_fitness))] rand = random.random() for i, cp in enumerate(cumulative_probability): if rand <= cp: return population[i]
Now you know how roulette wheel selection works and how to implement it in genetic algorithms. By using this technique, your algorithm will favor individuals with higher fitness scores, increasing the probability of producing better offspring and improving your solution over time.