Genetische Algorithmen: Survival of the Bittest

Die Natur hat über Milliarden Jahre einen erstaunlich effektiven Optimierungsprozess entwickelt: Evolution. Genetische Algorithmen (GA) übertragen dieses Prinzip in die Informatik und lösen Probleme, bei denen klassische Algorithmen scheitern.

Das Grundprinzip

Stell dir vor, du suchst die beste Lösung für ein Problem, aber der Lösungsraum ist riesig. Alle Möglichkeiten durchzuprobieren würde Jahre dauern. Genetische Algorithmen gehen anders vor: Sie simulieren Evolution.

Ein konkretes Beispiel

Unser Ziel: Finde einen Binärstring, bei dem alle Bits auf 1 stehen. Klingt trivial? Ist es auch. Aber dieses einfache Beispiel zeigt alle Konzepte, die bei komplexeren Problemen genauso funktionieren.

Das Individuum: Ein Array von 5 Bits, zufällig mit 0 oder 1 initialisiert.

Die Fitness: Anzahl der Einsen. Maximum ist 5, dann haben wir die perfekte Lösung.

Die Implementierung in Java

Das Individuum

Jedes Individuum repräsentiert eine mögliche Lösung:

public class Individual {
    private int[] genes = new int[5];
    private int fitness = 0;

    // Zufällige Initialisierung
    public Individual() {
        Random rn = new Random();
        for (int i = 0; i < genes.length; i++) {
            genes[i] = rn.nextInt(2); // 0 oder 1
        }
    }

    // Fitness = Anzahl der Einsen
    public void calcFitness() {
        fitness = 0;
        for (int gene : genes) {
            if (gene == 1) fitness++;
        }
    }
}

Die Population

Eine Population verwaltet mehrere Individuen:

public class Population {
    private Individual[] individuals = new Individual[10];
    private int fittest = 0; // Beste Fitness der Population

    public Individual getFittest() {
        int maxFit = Integer.MIN_VALUE;
        Individual fittestIndividual = null;

        for (Individual ind : individuals) {
            if (ind.getFitness() > maxFit) {
                maxFit = ind.getFitness();
                fittestIndividual = ind;
            }
        }
        return fittestIndividual;
    }

    public Individual getSecondFittest() {
        // Ähnlich, aber zweitbestes
        ...
    }
}

Selektion

Die zwei besten Individuen werden als Eltern ausgewählt. Es gibt verschiedene Selektionsmethoden wie Turnier oder Roulette. Hier nutzen wir Elitist Selection (Eliteselektion): einfach und effektiv.

public void selection() {
    fittest = population.getFittest();
    secondFittest = population.getSecondFittest();
}

Crossover

Das Herzstück: An einem zufälligen Punkt werden die Gene der beiden Eltern getauscht. Die Gene bis zum Crossover-Punkt werden zwischen den Eltern ausgetauscht.

public void crossover() {
    Random rn = new Random();
    int crossOverPoint = rn.nextInt(fittest.genes.length);

    for (int i = 0; i < crossOverPoint; i++) {
        int temp = fittest.genes[i];
        fittest.genes[i] = secondFittest.genes[i];
        secondFittest.genes[i] = temp;
    }
}

Mutation

Mutation verhindert, dass der Algorithmus in lokalen Optima stecken bleibt. Ein zufälliges Bit wird geflippt.

public void mutation() {
    Random rn = new Random();

    // 10% Wahrscheinlichkeit für Mutation
    if (rn.nextDouble() < 0.1) {
        int mutationPoint = rn.nextInt(fittest.genes.length);

        // Bit flippen: 0 → 1 oder 1 → 0
        fittest.genes[mutationPoint] = 1 - fittest.genes[mutationPoint];
    }
}

Der Algorithmus

Alles zusammen: Iteriere bis die perfekte Lösung gefunden ist.

public static void main(String[] args) {
    GeneticAlgorithm ga = new GeneticAlgorithm();

    // 1. Initialisiere Population
    ga.population.initializePopulation(10);
    ga.population.calculateFitness();

    int generation = 0;

    // 2. Evolutionsschleife
    while (ga.population.fittest < 5) {
        generation++;

        // Selektion
        ga.selection();

        // Crossover
        ga.crossover();

        // Mutation
        ga.mutation();

        // Ersetze schwächstes Individuum
        ga.addFittestOffspring();

        // Neu berechnen
        ga.population.calculateFitness();

        System.out.println("Generation: " + generation +
            " Fitness: " + ga.population.fittest);
    }

    System.out.println("Lösung gefunden in Generation " + generation);
}

Typischer Output

Generation: 1  Fitness: 3
Generation: 2  Fitness: 3
Generation: 3  Fitness: 4
Generation: 4  Fitness: 4
Generation: 5  Fitness: 5
Lösung gefunden in Generation 5
Gene: [1, 1, 1, 1, 1]

Mit nur 5 Generationen und 10 Individuen findet der Algorithmus die perfekte Lösung. Bei komplexeren Problemen dauert es länger, aber das Prinzip bleibt identisch.

Reale Anwendungsfälle

Dieses einfache Beispiel lässt sich auf komplexe Probleme übertragen:

Key Learnings

"Genetische Algorithmen finden keine garantiert optimale Lösung, aber oft eine sehr gute in akzeptabler Zeit."

1. Encoding ist entscheidend

Wie du das Problem als Gene darstellst, bestimmt den Erfolg. Binär ist einfach, aber Permutationen, Floats oder komplexe Strukturen sind oft besser geeignet.

2. Balance zwischen Exploration und Exploitation

Zu viel Mutation = chaotische Suche. Zu wenig = vorzeitige Konvergenz. Die richtige Mutationsrate ist problemspezifisch.

3. Fitness-Funktion ist der Schlüssel

Eine schlechte Fitness-Funktion führt zu schlechten Lösungen. Investiere Zeit in eine präzise Bewertungsfunktion.

4. Diversity erhalten

Wenn alle Individuen ähnlich werden, stagniert die Evolution. Techniken wie Crowding oder Niching helfen.

Fazit

Genetische Algorithmen sind ein mächtiges Werkzeug für Optimierungsprobleme, bei denen der Lösungsraum zu groß für erschöpfende Suche ist. Die Implementierung ist überraschend einfach: Population, Fitness, Selektion, Crossover, Mutation. Die Kunst liegt im richtigen Encoding und der passenden Fitness-Funktion.

Das Schöne: Du musst nicht verstehen, wie die optimale Lösung aussieht. Du musst nur bewerten können, wie gut eine Lösung ist. Den Rest erledigt die Evolution.

---

Verwendete Technologien:

Interesse an Optimierungsalgorithmen oder KI-gestützten Lösungen? Schreib mir, ich freue mich auf den Austausch.