Lære Seleksjon, Krysning og Mutasjon

Seleksjonsstrategier

Seleksjon er en avgjørende prosess i genetiske algoritmer, bestemmer hvilke individer som bidrar til neste generasjon, og balanserer tilpasningsevne og mangfold. Det finnes flere mye brukte seleksjonsstrategier:

Rulett-hjul-seleksjon: Tildeler en seleksjonssannsynlighet til hvert individ proporsjonalt med dets tilpasningsevne. Se for deg et hjul der hver seksjons størrelse tilsvarer tilpasningsevnen; individer med høyere tilpasningsevne har større sjanse for å bli valgt;
Turneringsseleksjon: Velger tilfeldig ut en gruppe (turnering) av individer og velger det beste blant dem som forelder. Denne metoden er enkel og effektiv, og turneringsstørrelsen kan kontrollere seleksjonspresset;
Rangbasert seleksjon: Rangerer individer etter tilpasningsevne og tildeler seleksjonssannsynligheter basert på rangering i stedet for absolutt tilpasningsevne. Dette bidrar til å unngå dominans fra noen få individer med svært høy tilpasningsevne, spesielt i problemer med store forskjeller i tilpasningsevne.


              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)

Krysningsoperatorer

Etter seleksjon bruker genetiske algoritmer krysning for å lage nye individer ved å kombinere informasjon fra to foreldre. Krysning introduserer variasjon og gjør det mulig for algoritmen å utforske nye kombinasjoner av egenskaper i populasjonen.

Vanlige typer krysning:

Enpunktskrysning: Et krysningspunkt velges tilfeldig. Første del av én forelder kombineres med resten av den andre.
Topunktskrysning: To punkter velges tilfeldig. Segmentet mellom dem byttes mellom foreldrene for å produsere avkom.
Uniform krysning: Hvert gen i avkommet velges tilfeldig fra en av de to foreldrene med lik sannsynlighet.


              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)

Mutasjonens rolle

Mutasjon er en av de sentrale mekanismene i genetiske algoritmer. Den introduserer nytt genetisk materiale i populasjonen, noe som hjelper algoritmen å unngå stagnasjon og fortsette å utforske nye løsninger. Uten mutasjon kan populasjonen bli for lik, noe som fører til at søket setter seg fast i lokale optima.

Hvorfor mutasjon er viktig

Forhindrer for tidlig konvergens: mutasjon sørger for at populasjonen ikke blir for ensartet, og unngår suboptimal konvergens;
Opprettholder mangfold: ved å introdusere tilfeldige endringer, holder mutasjon et bredt spekter av genetisk variasjon tilgjengelig for fremtidige generasjoner;
Muliggjør flukt fra lokale optima: små tilfeldige endringer gjør det mulig for algoritmen å utforske nye områder av søkeområdet som kan føre til bedre løsninger;
Balanserer krysning: mens krysning kombinerer eksisterende egenskaper, tilfører mutasjon nye, og sikrer at algoritmen fortsetter å generere nye muligheter.

Disse egenskapene gjør mutasjon avgjørende for en robust og adaptiv søkeprosess.

Vanlige mutasjonsoperatorer

Ulike problemrepresentasjoner krever ulike mutasjonsteknikker. De to mest brukte operatorene er:

Bit-flip-mutasjon: for binære representasjoner — bytter en bit fra 0 til 1 eller fra 1 til 0, og introduserer små, kontrollerte endringer;
Byttemutasjon: for permutasjonsbaserte representasjoner (f.eks. rekkefølgeproblemer) — bytter to elementer innenfor et individ for å generere en ny konfigurasjon.


              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)

Alt var klart?

Takk for tilbakemeldingene dine!

Seksjon 2. Kapittel 2

Spør AI

Spør om hva du vil, eller prøv ett av de foreslåtte spørsmålene for å starte chatten vår

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

Sveip for å vise menyen