Lernen Selektion, Kreuzung und Mutation

Selektionsstrategien

Selektion ist ein entscheidender Prozess in genetischen Algorithmen und bestimmt, welche Individuen zur nächsten Generation beitragen. Dabei wird ein Gleichgewicht zwischen Fitness und Diversität angestrebt. Es gibt mehrere weit verbreitete Selektionsstrategien:

Roulette-Rad-Selektion: Weist jedem Individuum eine Auswahlwahrscheinlichkeit proportional zu seiner Fitness zu. Stellen Sie sich ein Rad vor, bei dem die Größe jedes Abschnitts der Fitness entspricht; Individuen mit höherer Fitness haben eine größere Chance, ausgewählt zu werden;
Turnierselektion: Wählt zufällig eine Gruppe (Turnier) von Individuen aus und bestimmt das beste unter ihnen als Elternteil. Diese Methode ist einfach und effektiv; die Turniergröße kann den Selektionsdruck steuern;
Rangbasierte Selektion: Ordnet Individuen nach Fitness und weist Auswahlwahrscheinlichkeiten basierend auf ihrem Rang statt auf ihrer absoluten Fitness zu. Dies verhindert die Dominanz weniger Individuen mit sehr hoher Fitness, insbesondere bei Problemen mit großen Fitnessunterschieden.


              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

Nach der Selektion verwenden genetische Algorithmen Crossover, um neue Individuen zu erzeugen, indem Informationen von zwei Elternteilen kombiniert werden. Crossover bringt Variation ein und ermöglicht es dem Algorithmus, neue Kombinationen von Merkmalen in der Population zu erkunden.

Gängige Arten von Crossover:

Einpunkt-Crossover: Ein Crossover-Punkt wird zufällig gewählt. Der erste Teil eines Elternteils wird mit dem verbleibenden Teil des anderen kombiniert.
Zweipunkt-Crossover: Zwei Punkte werden zufällig ausgewählt. Das Segment zwischen ihnen wird zwischen den Eltern ausgetauscht, um Nachkommen zu erzeugen.
Uniformes Crossover: Jedes Gen im Nachkommen wird mit gleicher Wahrscheinlichkeit zufällig von einem der beiden Elternteile übernommen.


              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)

Rolle der Mutation

Mutation ist einer der zentralen Mechanismen in genetischen Algorithmen. Sie bringt neues genetisches Material in die Population ein und hilft dem Algorithmus, Stagnation zu vermeiden und weiterhin neue Lösungen zu erkunden. Ohne Mutation könnte die Population zu ähnlich werden, was dazu führt, dass die Suche in lokalen Optima stecken bleibt.

Warum Mutation wichtig ist

Verhindert vorzeitige Konvergenz: Mutation stellt sicher, dass die Population nicht zu einheitlich wird und verhindert so suboptimale Konvergenz;
Erhält Diversität: Durch zufällige Veränderungen bleibt eine breite genetische Vielfalt für zukünftige Generationen erhalten;
Ermöglicht das Verlassen lokaler Optima: Kleine zufällige Änderungen erlauben es dem Algorithmus, neue Bereiche des Suchraums zu erkunden, die zu besseren Lösungen führen können;
Balanciert Crossover: Während Crossover bestehende Merkmale kombiniert, bringt Mutation neue ein und sorgt so dafür, dass der Algorithmus weiterhin neue Möglichkeiten generiert.

Diese Eigenschaften machen Mutation zu einem wesentlichen Bestandteil eines robusten und adaptiven Suchprozesses.

Gängige Mutationsoperatoren

Verschiedene Problemrepräsentationen erfordern unterschiedliche Mutationsverfahren. Die zwei am häufigsten verwendeten Operatoren sind:

Bit-Flip-Mutation: Für binäre Repräsentationen — kehrt ein Bit von 0 auf 1 oder von 1 auf 0 um und führt so kleine, kontrollierte Änderungen ein;
Swap-Mutation: Für permutationsbasierte Repräsentationen (z. B. Reihenfolgeprobleme) — tauscht zwei Elemente innerhalb eines Individuums, um eine neue Konfiguration zu erzeugen.


              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)

War alles klar?

Danke für Ihr Feedback!

Abschnitt 2. Kapitel 2

Fragen Sie AI

Fragen Sie alles oder probieren Sie eine der vorgeschlagenen Fragen, um unser Gespräch zu beginnen

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

Swipe um das Menü anzuzeigen