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:

1. Calculate the total fitness of the population.
2. Calculate the relative fitness for each individual by dividing their fitness by the total fitness.
3. Calculate the cumulative probability for each individual by summing up the relative fitnesses.
4. Generate a random number between 0 and 1.
5. 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.

Example

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

1. Calculate the total fitness:

Total Fitness = 12 + 8 + 6 + 4 = 30

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

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

1. Generate a random number between 0 and 1:

Random number = 0.52

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

Implementation

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.