Leer Selectie, Crossover en Mutatie | Genetische Algoritmen

Selectiestrategieën

Selectie is een cruciaal proces in genetische algoritmen, bepaalt welke individuen bijdragen aan de volgende generatie en balanceert fitheid en diversiteit. Er zijn verschillende veelgebruikte selectiestrategieën:

Roulettewielselectie: Wijs een selectiekans toe aan elk individu, evenredig aan zijn fitheid. Stel je een wiel voor waarbij de grootte van elk segment overeenkomt met de fitheid; individuen met een hogere fitheid hebben een grotere kans om geselecteerd te worden;
Toernooiselectie: Selecteert willekeurig een groep (toernooi) van individuen en kiest de beste daarvan als ouder. Deze methode is eenvoudig en effectief, en de toernooigrootte kan de selectiedruk regelen;
Ranggebaseerde selectie: Rangschikt individuen op basis van fitheid en wijst selectiekansen toe op basis van hun rang in plaats van hun absolute fitheid. Dit helpt dominantie door enkele individuen met hoge fitheid te voorkomen, vooral bij problemen met grote fitheidsverschillen.


              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-operatoren

Na selectie gebruiken genetische algoritmen crossover om nieuwe individuen te creëren door informatie van twee ouders te combineren. Crossover introduceert variatie en stelt het algoritme in staat om nieuwe combinaties van eigenschappen binnen de populatie te verkennen.

Veelvoorkomende typen crossover:

Single-point crossover: Een crossoverpunt wordt willekeurig gekozen. Het eerste deel van de ene ouder wordt gecombineerd met het resterende deel van de andere.
Two-point crossover: Twee punten worden willekeurig geselecteerd. Het segment ertussen wordt uitgewisseld tussen de ouders om nakomelingen te produceren.
Uniform crossover: Elk gen in het nageslacht wordt willekeurig gekozen uit een van de twee ouders met gelijke kans.


              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)

Rol van Mutatie

Mutatie is een van de belangrijkste mechanismen in genetische algoritmen. Het introduceert nieuw genetisch materiaal in de populatie, waardoor het algoritme stagnatie voorkomt en nieuwe oplossingen blijft verkennen. Zonder mutatie kan de populatie te homogeen worden, waardoor de zoektocht vastloopt in lokale optima.

Waarom Mutatie Belangrijk Is

Voorkomt voortijdige convergentie: mutatie zorgt ervoor dat de populatie niet te uniform wordt, waardoor suboptimale convergentie wordt vermeden;
Behoudt diversiteit: door willekeurige veranderingen te introduceren, blijft er een breed scala aan genetische variatie beschikbaar voor toekomstige generaties;
Maakt ontsnapping uit lokale optima mogelijk: kleine willekeurige veranderingen stellen het algoritme in staat nieuwe gebieden van de zoekruimte te verkennen die tot betere oplossingen kunnen leiden;
Balanceert crossover: terwijl crossover bestaande eigenschappen combineert, voegt mutatie nieuwe toe, waardoor het algoritme blijft zorgen voor nieuwe mogelijkheden.

Samen maken deze eigenschappen mutatie essentieel voor een robuust en adaptief zoekproces.

Veelvoorkomende Mutatie-Operatoren

Verschillende probleemrepresentaties vereisen verschillende mutatietechnieken. De twee meest gebruikte operatoren zijn:

Bit-flip mutatie: voor binaire representaties — verandert een bit van 0 naar 1 of van 1 naar 0, wat kleine, gecontroleerde wijzigingen introduceert;
Swap-mutatie: voor permutatie-gebaseerde representaties (bijvoorbeeld volgordeproblemen) — verwisselt twee elementen binnen een individu om een nieuwe configuratie te genereren.


              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)

Was alles duidelijk?

Bedankt voor je feedback!

Sectie 2. Hoofdstuk 2

Vraag AI

Vraag wat u wilt of probeer een van de voorgestelde vragen om onze chat te starten.

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

Veeg om het menu te tonen