Lære Selektion, Crossover og Mutation

Udvælgelsesstrategier

Udvælgelse er en afgørende proces i genetiske algoritmer, der bestemmer hvilke individer der bidrager til næste generation, og balancerer fitness og diversitet. Der findes flere udbredte udvælgelsesstrategier:

Roulettehjulsudvælgelse: Tildeler hver individ en udvælgelsessandsynlighed proportional med dets fitness. Forestil dig et hjul, hvor hver sektors størrelse svarer til fitness; individer med højere fitness har større sandsynlighed for at blive udvalgt;
Turneringsudvælgelse: Udvælger tilfældigt en gruppe (turnering) af individer og vælger det bedste blandt dem som forælder. Denne metode er enkel og effektiv, og turneringsstørrelsen kan styre udvælgelsespresset;
Rangbaseret udvælgelse: Rangerer individer efter fitness og tildeler udvælgelsessandsynligheder baseret på deres rang i stedet for deres absolutte fitness. Dette hjælper med at undgå dominans af få individer med høj fitness, især i problemer med store fitnessforskelle.


              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)

Krydsningsoperatorer

Efter udvælgelse anvender genetiske algoritmer krydsning for at skabe nye individer ved at kombinere information fra to forældre. Krydsning introducerer variation og gør det muligt for algoritmen at udforske nye kombinationer af egenskaber i populationen.

Almindelige typer af krydsning:

Enkeltpunktskrydsning: Et krydsningspunkt vælges tilfældigt. Den første del af den ene forælder kombineres med den resterende del af den anden.
Topunktskrydsning: To punkter vælges tilfældigt. Segmentet mellem dem byttes mellem forældrene for at producere afkom.
Uniform krydsning: Hvert gen i afkommet vælges tilfældigt fra en af de to forældre med lige stor sandsynlighed.


              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 rolle

Mutation er en af de centrale mekanismer i genetiske algoritmer. Den introducerer nyt genetisk materiale i populationen, hvilket hjælper algoritmen med at undgå stagnation og fortsætte med at udforske nye løsninger. Uden mutation kan populationen blive for ensartet, hvilket kan føre til, at søgningen går i stå i lokale optima.

Hvorfor mutation er vigtig

Forhindrer for tidlig konvergens: mutation sikrer, at populationen ikke bliver for ensartet og undgår suboptimal konvergens;
Opretholder diversitet: ved at tilføre tilfældige ændringer bevares en bred genetisk variation til fremtidige generationer;
Muliggør undvigelse af lokale optima: små tilfældige ændringer gør det muligt for algoritmen at udforske nye områder af søgeområdet, som kan føre til bedre løsninger;
Balancerer crossover: hvor crossover kombinerer eksisterende egenskaber, tilfører mutation nye, hvilket sikrer, at algoritmen fortsat genererer nye muligheder.

Disse egenskaber gør tilsammen mutation afgørende for en robust og adaptiv søgeproces.

Almindelige mutationsoperatorer

Forskellige problemrepræsentationer kræver forskellige mutationsteknikker. De to mest anvendte operatorer er:

Bit-flip mutation: til binære repræsentationer — vender en bit fra 0 til 1 eller fra 1 til 0 og indfører små, kontrollerede ændringer;
Swap mutation: til permutationsbaserede repræsentationer (f.eks. rækkefølgeproblemer) — bytter to elementer inden for et individ for at generere 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 alt klart?

Tak for dine kommentarer!

Sektion 2. Kapitel 2

Spørg AI

Spørg om hvad som helst eller prøv et af de foreslåede spørgsmål for at starte vores chat

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

Stryg for at vise menuen