Evolutionary Algorithms

Evolutionäre Algorithmen (EAs) sind eine Gruppe von Optimierungsalgorithmen, die die natürliche Selektion nachahmen. Sie verwalten eine Population möglicher Lösungen, bewerten jede anhand einer Fitnessfunktion, lassen die besten Kandidaten durch Rekombination und zufällige Mutation Nachkommen erzeugen und wiederholen diesen Vorgang über viele Generationen. Dadurch entwickelt sich die Population hin zu besseren Lösungen. Ein EA muss einen Kandidaten nur bewerten und keinen Gradienten berechnen. Deshalb eignet er sich für Probleme, mit denen Gradientenabstieg nicht zurechtkommt: diskrete Entscheidungen, nicht differenzierbare oder verrauschte Zielfunktionen und unwegsame Landschaften voller lokaler Optima. Daher sind EAs ein Standardwerkzeug für die Hyperparameterabstimmung, die Suche nach neuronalen Architekturen, den technischen Entwurf und die Ablaufplanung.

So funktionieren evolutionäre Algorithmen#

Jeder EA besteht aus denselben Grundelementen:

1. Repräsentation: Jeder Kandidat wird als Genom codiert, zum Beispiel als Bitfolge, Vektor reeller Zahlen oder Programmbaum.
2. Initialisierung: Die erste Generation wird üblicherweise zufällig erzeugt und manchmal mit bekannten guten Lösungen gestartet.
3. Fitnessbewertung: Eine Fitnessfunktion bewertet jeden Kandidaten anhand der zu optimierenden Zielfunktion.
4. Selektion: Kandidaten mit höherer Fitness werden mit größerer Wahrscheinlichkeit zu Eltern. Bei der Turnierselektion wird beispielsweise der bessere von einigen zufällig ausgewählten Kandidaten gewählt. Beim Elitismus wird der beste Kandidat unverändert in die nächste Generation übernommen.
5. Variation: Bei der Kreuzung werden Teile zweier Eltern kombiniert. Mutationen nehmen kleine zufällige Änderungen vor, damit die Population weiter den Suchraum erkundet.

Im maschinellen Lernen (ML) ist die Fitnessfunktion oft eine Validierungsmetrik wie Genauigkeit oder mittlere durchschnittliche Präzision (mAP). Einen Kandidaten zu bewerten bedeutet daher, ein Modell zu trainieren und zu testen – mit Abstand der kostspieligste Schritt. Der Vorgang wird wiederholt, bis das Budget aufgebraucht ist oder sich die Fitness nicht mehr verbessert:

Selektionsdruck und Mutationsstärke bestimmen das Gleichgewicht zwischen Ausnutzung und Erkundung. Starke Selektion mit kleinen Mutationen führt schnell zur Konvergenz, kann aber in einem lokalen Optimum stecken bleiben. Schwache Selektion mit großen Mutationen erkundet den Suchraum umfassend, verschwendet jedoch Auswertungen.

Wichtige Arten evolutionärer Algorithmen#

• Genetische Algorithmen (GAs): Kandidaten werden als Zeichenfolgen, oft als Bits, codiert, und der Schwerpunkt liegt auf der Kreuzung. John Holland formalisierte sie 1975 in seinem Buch Adaptation in Natural and Artificial Systems.
• Evolutionäre Strategien (ES): Optimieren Vektoren reeller Zahlen mit Gaußschen Mutationen, deren Schrittweiten sich im Verlauf anpassen. CMA-ES lernt die vollständige Kovarianz seiner Mutationsverteilung und gehört zu den leistungsfähigsten allgemeinen Verfahren für kontinuierliche Black-Box-Probleme.
• Genetische Programmierung: Entwickelt Programme oder mathematische Ausdrücke, die als Bäume dargestellt werden. Sie wird für symbolische Regression und den automatischen Programmentwurf verwendet.
• Neuroevolution: Entwickelt die Gewichte und manchmal auch die Struktur neuronaler Netze weiter. OpenAI zeigte 2017, dass auf mehr als tausend parallel arbeitenden Prozessen ausgeführte evolutionäre Strategien einen 3D-Humanoiden in 10 Minuten das Laufen beibringen konnten – eine skalierbare Alternative zum bestärkenden Lernen.

Ein genetischer Algorithmus im Code#

Beim Rucksackproblem geht es darum, welche Gegenstände eingepackt werden sollen, um den Gesamtwert zu maximieren, ohne eine Gewichtsgrenze zu überschreiten. Es handelt sich um ein diskretes Problem ohne Gradienten. Dieser genetische NumPy-Algorithmus entwickelt 50 Genome als Bitfolgen weiter, ein Bit pro Gegenstand. Dabei nutzt er Turnierselektion, gleichmäßige Kreuzung, Bit-Flip-Mutation und Elitismus. Anschließend vergleicht er das Ergebnis mit allen 1,048,576 möglichen Auswahlen:

import itertools

import numpy as np

rng = np.random.default_rng(0)
# Knapsack problem: pick from 20 items to maximize total value within a weight limit of 200
values, weights, limit = rng.integers(10, 100, 20), rng.integers(5, 50, 20), 200


def fitness(pop):
    """Return each selection's total value, or 0 if it exceeds the weight limit."""
    return np.where(pop @ weights <= limit, pop @ values, 0)


population = rng.random((50, 20)) < 0.2  # 50 random genomes, one bit per item
for generation in range(100):
    scores = fitness(population)
    # Tournament selection: each parent is the better of two random genomes
    pairs = rng.integers(50, size=(50, 2))
    parents = population[np.where(scores[pairs[:, 0]] > scores[pairs[:, 1]], pairs[:, 0], pairs[:, 1])]
    # Uniform crossover with the next parent, then flip each bit with probability 0.05
    children = np.where(rng.random((50, 20)) < 0.5, parents, np.roll(parents, 1, axis=0))
    children ^= rng.random((50, 20)) < 0.05
    children[0] = population[scores.argmax()]  # elitism: keep the best genome
    population = children

all_selections = np.array(list(itertools.product([0, 1], repeat=20)))
print(f"GA best: {fitness(population).max()}, true optimum: {fitness(all_selections).max()}")

Die Ausgabe lautet GA best: 811, true optimum: 811. Der Algorithmus fand nach 5,000 Fitnessauswertungen die bestmögliche Zusammenstellung. Das entspricht etwa 0.5 % der eine Million Möglichkeiten, die bei einer vollständigen Durchsuchung geprüft werden mussten.

Hyperparameter weiterentwickeln#

Trainingseinstellungen wie Lernrate, Gewichte der Verlustfunktion und Stärke der Datenerweiterung beeinflussen sich auf eine Weise, die sich nicht durch eine Formel vorhersagen lässt. Da jeder Kandidat einen vollständigen Trainingslauf erfordert, eignet sich die evolutionäre Suche besonders gut. Die Methode tune() in Ultralytics YOLO nutzt diesen Ansatz für YOLO26-Modelle: Bei jeder Iteration wird ein Elternteil aus den neun bisher besten Konfigurationen ausgewählt, gewichtet nach Fitness. Etwa die Hälfte der 26 Hyperparameter im standardmäßigen Suchraum wird mit Gaußschen Schritten mutiert, deren Größe an den jeweiligen Suchbereich angepasst ist. Anschließend wird ein Modell trainiert und seine Fitness erfasst; bei der Objekterkennung ist das mAP_50-95. Nach 30 Ergebnissen orientieren sich einige Mutationen auch an der Kovarianz der besten 20 % der Konfigurationen – ein Ansatz, der von CMA-ES übernommen wurde. Der Leitfaden zur Hyperparameterabstimmung enthält den vollständigen Suchraum:

from ultralytics import YOLO

# Ein vortrainiertes YOLO26-Nano-Modell laden
model = YOLO("yolo26n.pt")

# Hyperparameter weiterentwickeln: 30 Iterationen, in denen jeweils eine mutierte Konfiguration über 10 Epochen trainiert wird
model.tune(data="coco8.yaml", epochs=10, iterations=30, plots=False)

Der Tuner schreibt jede Konfiguration samt Fitness in tune_results.ndjson und speichert die beste Konfiguration in best_hyperparameters.yaml. Sie kann direkt an einen vollständigen Trainingslauf übergeben werden.

Weitere Anwendungen#

• Suche nach neuronalen Architekturen: Googles AmoebaNet entstand durch regularisierte Evolution, einen EA mit Turnierselektion, der jeweils die ältesten statt der schlechtesten Modelle aussortiert. 2018 erreichte das Modell auf ImageNet eine Top-1-Genauigkeit von 83.9 %.
• Technischer Entwurf: Bei der NASA-Mission Space Technology 5 kam 2006 eine computergestützt entwickelte X-Band-Antenne zum Einsatz. Ihre unregelmäßige, gebogene Drahtform erzielte eine mit einer konventionell entworfenen Antenne vergleichbare Leistung.
• Algorithmusentdeckung: AlphaEvolve, im Mai 2025 von Google DeepMind angekündigt, kombiniert Gemini-Modelle, die Codeänderungen vorschlagen, mit automatisierten Bewertungsverfahren und einer evolutionären Programmdatenbank. Eine von AlphaEvolve entwickelte Ablaufplanungsheuristik gewinnt für Googles Rechenzentren im Durchschnitt 0.7 % der weltweiten Rechenressourcen des Unternehmens zurück.

Evolutionäre Algorithmen und verwandte Methoden#

• Gradientenabstieg: Folgt dem Gradienten einer differenzierbaren Verlustfunktion und ist beim Training von Netzgewichten mit Millionen Parametern wesentlich effizienter. EAs eignen sich für Probleme mit wenigen Parametern, kostspieligen Auswertungen oder ohne Gradienten.
• Schwarmintelligenz: Verfahren wie die Partikelschwarmoptimierung bewegen eine beständige Gruppe von Agenten durch den Suchraum. Jeder Agent passt seine Position anhand seines besten Ergebnisses und der Ergebnisse seiner Nachbarn an. Generationenwechsel, Kreuzung oder Mutation finden dabei nicht statt.
• Bayes'sche Optimierung: Erstellt ein probabilistisches Modell der Zielfunktion und wählt jeden nächsten Versuch dort aus, wo das Modell die größte Verbesserung erwartet. In kleinen, glatten Suchräumen sind dadurch weniger Auswertungen als bei einem EA nötig, doch bei vielen Parametern und parallel arbeitenden Prozessen skaliert die Methode weniger gut.