Lära Selektion, Crossover och Mutation

Urvalsstrategier

Urval är en avgörande process i genetiska algoritmer, avgör vilka individer som bidrar till nästa generation och balanserar fitness och mångfald. Det finns flera allmänt använda urvalsstrategier:

Roulettehjulsurval: Tilldelar varje individ en sannolikhet att väljas, proportionell mot dess fitness. Föreställ dig ett hjul där varje sektors storlek motsvarar fitness; individer med högre fitness har större chans att väljas;
Turneringsurval: Väljer slumpmässigt ut en grupp (turnering) av individer och väljer den bästa bland dem som förälder. Denna metod är enkel och effektiv, och turneringens storlek kan styra urvalstrycket;
Rangbaserat urval: Rankar individer efter fitness och tilldelar urvalssannolikheter baserat på deras rang istället för deras absoluta fitness. Detta hjälper till att undvika dominans av några få individer med hög fitness, särskilt i problem med stora fitnesskillnader.


              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)

Korsningsoperatorer

Efter urval använder genetiska algoritmer korsning för att skapa nya individer genom att kombinera information från två föräldrar. Korsning introducerar variation och gör det möjligt för algoritmen att utforska nya kombinationer av egenskaper inom populationen.

Vanliga typer av korsning:

Enpunktskorsning: En korsningspunkt väljs slumpmässigt. Den första delen av en förälder kombineras med den återstående delen av den andra.
Tvåpunktskorsning: Två punkter väljs slumpmässigt. Segmentet mellan dem byts mellan föräldrarna för att producera avkomma.
Uniform korsning: Varje gen i avkomman väljs slumpmässigt från en av de två föräldrarna med lika sannolikhet.


              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)

Mutationens roll

Mutation är en av de centrala mekanismerna i genetiska algoritmer. Den introducerar nytt genetiskt material i populationen, vilket hjälper algoritmen att undvika stagnation och fortsätta utforska nya lösningar. Utan mutation kan populationen bli alltför likartad, vilket gör att sökningen fastnar i lokala optima.

Varför mutation är viktig

Förhindrar för tidig konvergens: mutation säkerställer att populationen inte blir för enhetlig och undviker suboptimal konvergens;
Bibehåller diversitet: genom att införa slumpmässiga förändringar hålls ett brett spektrum av genetisk variation tillgänglig för framtida generationer;
Möjliggör undvikande av lokala optima: små slumpmässiga förändringar gör det möjligt för algoritmen att utforska nya områden av sökutrymmet som kan leda till bättre lösningar;
Balanserar crossover: medan crossover kombinerar befintliga egenskaper, tillför mutation nya, vilket säkerställer att algoritmen fortsätter att generera nya möjligheter.

Tillsammans gör dessa egenskaper mutation avgörande för en robust och adaptiv sökprocess.

Vanliga mutationsoperatorer

Olika problemrepresentationer kräver olika mutationstekniker. De två mest använda operatorerna är:

Bit-flip-mutation: för binära representationer — vänder en bit från 0 till 1 eller från 1 till 0, vilket introducerar små, kontrollerade förändringar;
Swap-mutation: för permutationsbaserade representationer (t.ex. ordningsproblem) — byter plats på två element inom en individ för att skapa en ny konfiguration.


              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)

Var allt tydligt?

Tack för dina kommentarer!

Avsnitt 2. Kapitel 2

Fråga AI

Fråga vad du vill eller prova någon av de föreslagna frågorna för att starta vårt samtal

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

Svep för att visa menyn