Genetische Algorithmen

9.1 Einführung in genetische Algorithmen.

Genetische Algorithmen (GA) sind ein Optimierungs- und Suchverfahren, das vom natürlichen Selektionsprozess inspiriert ist und biologische evolutionäre Prozesse nachahmt.

Genetische Algorithmen werden eingesetzt, um komplexe Probleme zu lösen, bei denen herkömmliche Methoden möglicherweise ineffizient sind. Diese Algorithmen nutzen Mechanismen wie Selektion, Kreuzung (Crossover) und Mutation zur Evolution von Lösungen.

Arbeitsprinzipien:

1. Initialisierung:

Eine anfängliche Population möglicher Lösungen (Chromosomen) wird erstellt. Jede Lösung wird in Form einer Zeichenkette codiert (Bitfolge, Zeichenkette oder andere Strukturen).

2 Fitnessfunktion:

Bewertet die Qualität jeder Lösung in der Population.

3. Bewertung:

Jede Lösung (Individuum) wird mit einer Fitnessfunktion bewertet, die bestimmt, wie gut die Lösung das Problem löst.

4. Selektion:

Lösungen mit besserer Fitness haben höhere Chancen, für die Reproduktion ausgewählt zu werden. Häufig verwendete Methoden sind Roulette-Rad-Selektion, Turnierselektion und Rangselektion.

5. Kreuzung (Crossover):

Ausgewählte Lösungen (Eltern) werden kombiniert, um neue Lösungen (Nachkommen) zu erstellen. Der Crossover kann einpunkt-, zweipunkt- oder mehrpunktbasiert sein.

6. Mutation:

Zufällige Änderungen in neuen Lösungen (Mutationen) werden angewendet, um Vielfalt einzuführen. Dies hilft dem Algorithmus, lokale Minima zu vermeiden.

7. Ersatz:

Die neue Population ersetzt die alte und der Prozess wird wiederholt, bis eine Abbruchbedingung erfüllt ist (z.B. Erreichen einer bestimmten Generationenanzahl oder einer bestimmten Fitness).

Vorteile und Nachteile

Vorteile:

• Breites Anwendungsspektrum: Können zur Lösung verschiedener Probleme eingesetzt werden, einschließlich solcher, bei denen analytische Methoden nicht funktionieren.
• Globale Optimierung: In der Lage, globale Optima in mehrdimensionalen und komplexen Räumen zu finden.
• Flexibilität: Können mit jeder Fitnessfunktion verwendet werden.

Nachteile:

• Hoher Rechenaufwand: Benötigen erhebliche Rechenressourcen, insbesondere bei großen Populationen und komplexen Aufgaben.
• Schwierigkeiten bei der Parametereinstellung: Die Auswahl von Parametern (Populationsgröße, Mutations- und Crossover-Wahrscheinlichkeit) kann schwierig sein und die Leistung stark beeinflussen.
• Keine Garantie für eine optimale Lösung: Es gibt keine Garantie, dass die gefundene Lösung global optimal ist.

Im Grunde genommen ist ein genetischer Algorithmus eine hocheffiziente Heuristik. Er garantiert nicht, das beste Lösung zu finden, selbst wenn er Zugriff auf alle Daten hat. Aber für komplexe Situationen und riesige Datenmengen liefert er sehr schnell eine Lösung, die nahe an der idealen ist.

9.2 Anwendungsbeispiel

Betrachten wir ein Beispiel für die Anwendung eines genetischen Algorithmus zur Optimierung einer Funktion.

import random

# Parameter des genetischen Algorithmus
POPULATION_SIZE = 100
GENERATIONS = 1000
MUTATION_RATE = 0.01
TOURNAMENT_SIZE = 5
            
# Definition der Fitnessfunktion
def fitness_function(x):
    return -x**2 + 10*x
            
# Initialisierung der Population
def initialize_population(size):
    return [random.uniform(-10, 10) for _ in range(size)]
            
# Selektion (Turnierselektion)
def tournament_selection(population):
    tournament = random.sample(population, TOURNAMENT_SIZE)
    return max(tournament, key=fitness_function)
            
# Kreuzung (einpunktbasiert)
def crossover(parent1, parent2):
    alpha = random.random()
    return alpha * parent1 + (1 - alpha) * parent2
            
# Mutation
def mutate(individual):
    if random.random() < MUTATION_RATE:
        return individual + random.gauss(0, 1)
    return individual
            
# Hauptschleife des genetischen Algorithmus
population = initialize_population(POPULATION_SIZE)
            
for generation in range(GENERATIONS):
    new_population = []
    for _ in range(POPULATION_SIZE):
        parent1 = tournament_selection(population)
        parent2 = tournament_selection(population)
        offspring = crossover(parent1, parent2)
        offspring = mutate(offspring)
        new_population.append(offspring)
    population = new_population
            
# Ausgabe der besten Lösung
best_individual = max(population, key=fitness_function)
print("Beste Lösung:", best_individual)
print("Funktionswert:", fitness_function(best_individual))
            
        

Vorteile und Nachteile

9.3 Optimierung einer mehrdimensionalen Funktion

Aufgabe:

Finde den minimalen Wert einer mehrdimensionalen Funktion.

Lösung:

Wir verwenden das vorherige Muster

import numpy as np

def fitness_function(x):
    return np.sum(x ** 2)
            
def create_individual(dim):
    return np.random.uniform(-10, 10, dim)
            
def create_population(pop_size, dim):
    return np.array([create_individual(dim) for _ in range(pop_size)])
            
def select_individuals(population, fitness, num_parents):
    parents = np.empty((num_parents, population.shape[1]))
    for parent_num in range(num_parents):
        min_fitness_idx = np.where(fitness == np.min(fitness))
        min_fitness_idx = min_fitness_idx[0][0]
        parents[parent_num, :] = population[min_fitness_idx, :]
        fitness[min_fitness_idx] = float('inf')
    return parents
            
def crossover(parents, offspring_size):
    offspring = np.empty(offspring_size)
    crossover_point = np.uint8(offspring_size[1] / 2)
    for k in range(offspring_size[0]):
        parent1_idx = k % parents.shape[0]
        parent2_idx = (k + 1) % parents.shape[0]
        offspring[k, 0:crossover_point] = parents[parent1_idx, 0:crossover_point]
        offspring[k, crossover_point:] = parents[parent2_idx, crossover_point:]
    return offspring
            
def mutate(offspring, mutation_rate):
    for idx in range(offspring.shape[0]):
        if np.random.rand() < mutation_rate:
            random_value = np.random.uniform(-1.0, 1.0, 1)
            offspring[idx, 4] = offspring[idx, 4] + random_value
    return offspring
            
def genetic_algorithm(dim, pop_size, num_parents, mutation_rate, num_generations):
    population = create_population(pop_size, dim)
    for generation in range(num_generations):
        fitness = np.array([fitness_function(ind) for ind in population])
        parents = select_individuals(population, fitness, num_parents)
        offspring_crossover = crossover(parents, (pop_size - parents.shape[0], dim))
        offspring_mutation = mutate(offspring_crossover, mutation_rate)
        population[0:parents.shape[0], :] = parents
        population[parents.shape[0]:, :] = offspring_mutation
    best_solution = population[np.argmin(fitness)]
    return best_solution
# Beispiel der Verwendung:
dim = 10
pop_size = 100
num_parents = 20
mutation_rate = 0.01
num_generations = 1000
best_solution = genetic_algorithm(dim, pop_size, num_parents, mutation_rate, num_generations)
print(f"Beste Lösung: {best_solution}")