Oppiskele Selection, Crossover, and Mutation

Selection Strategies

Selection is a crucial process in genetic algorithms, determines which individuals contribute to the next generation, balancing fitness and diversity. There are several widely used selection strategies:

Roulette Wheel Selection: Assigns a selection probability to each individual proportional to its fitness. Imagine a wheel where each slice's size corresponds to fitness; individuals with higher fitness have a greater chance of being selected;
Tournament Selection: Randomly selects a group (tournament) of individuals and chooses the best among them as a parent. This method is simple and effective, and the tournament size can control selection pressure;
Rank-Based Selection: Ranks individuals by fitness and assigns selection probabilities based on their rank rather than their absolute fitness. This helps avoid domination by a few high-fitness individuals, especially in problems with large fitness differences.


              1234567891011121314151617
            
import random

def tournament_selection(population, fitnesses, tournament_size=3):
    """
    Selects one individual from the population using tournament selection.
    """
    # Randomly pick tournament_size individuals
    selected_indices = random.sample(range(len(population)), tournament_size)
    # Find the one with the highest fitness
    best_index = max(selected_indices, key=lambda idx: fitnesses[idx])
    return population[best_index]

# Example usage
population = [[0,1,1,0], [1,0,0,1], [1,1,0,0], [0,0,1,1]]
fitnesses = [3, 2, 5, 4]
parent = tournament_selection(population, fitnesses, tournament_size=2)
print("Selected parent:", parent)

Crossover Operators

After selection, genetic algorithms use crossover to create new individuals by combining information from two parents. Crossover introduces variation and allows the algorithm to explore new combinations of traits within the population.

Common types of crossover:

Single-Point Crossover: A crossover point is chosen at random. The first part of one parent is combined with the remaining part of the other.
Two-Point Crossover: Two points are selected at random. The segment between them is swapped between the parents to produce offspring.
Uniform Crossover: Each gene in the offspring is randomly chosen from one of the two parents with equal probability.


              12345678910111213141516171819
            
import random

def single_point_crossover(parent1, parent2):
    """
    Performs single-point crossover between two parents.
    """
    if len(parent1) != len(parent2):
        raise ValueError("Parents must be of the same length")
    point = random.randint(1, len(parent1) - 1)
    child1 = parent1[:point] + parent2[point:]
    child2 = parent2[:point] + parent1[point:]
    return child1, child2

# Example usage
p1 = [1, 0, 1, 0, 1]
p2 = [0, 1, 0, 1, 0]
offspring1, offspring2 = single_point_crossover(p1, p2)
print("Offspring 1:", offspring1)
print("Offspring 2:", offspring2)

Role of Mutation

Mutation is one of the key mechanisms in genetic algorithms. It introduces new genetic material into the population, helping the algorithm avoid stagnation and continue exploring new solutions. Without mutation, the population may become too similar, causing the search to get stuck in local optima.

Why Mutation Is Important

Prevents premature convergence: mutation ensures that the population does not become too uniform, avoiding suboptimal convergence;
Maintains diversity: by introducing random alterations, mutation keeps a broad range of genetic variation available for future generations;
Enables escape from local optima: small random changes allow the algorithm to explore new areas of the search space that might lead to better solutions;
Balances crossover: while crossover combines existing traits, mutation injects new ones, ensuring the algorithm keeps generating novel possibilities.

Together, these properties make mutation essential for a robust and adaptive search process.

Common Mutation Operators

Different problem representations require different mutation techniques. The two most widely used operators are:

Bit-flip mutation: for binary representations — flips a bit from 0 to 1 or from 1 to 0, introducing small, controlled changes;
Swap mutation: for permutation-based representations (e.g., ordering problems) — swaps two elements within an individual to generate a new configuration.


              1234567891011121314151617181920
            
import random

def bit_flip_mutation(individual, mutation_rate=0.1):
    """
    Performs bit-flip mutation on a binary list.
    """
    mutated = []
    for gene in individual:
        if random.random() < mutation_rate:
            mutated.append(1 - gene)  # Flip bit
        else:
            mutated.append(gene)
    return mutated

# Example usage
original = [1, 0, 1, 1, 0]
mutated = bit_flip_mutation(original, mutation_rate=0.5)
print("Original:", original)
print("Mutated:", mutated)

Oliko kaikki selvää?

Kiitos palautteestasi!

Osio 2. Luku 2

Kysy tekoälyä

Kysy mitä tahansa tai kokeile jotakin ehdotetuista kysymyksistä aloittaaksesi keskustelumme

Suggested prompts:

Can you explain how tournament size affects selection pressure?

What are the advantages and disadvantages of each selection strategy?

How do I choose the right selection strategy for my problem?

Awesome!

Completion rate improved to 6.25

Pyyhkäise näyttääksesi valikon