Estimation of Distribution Algorithm

Manche Probleme lassen sich nicht einfach durchrechnen — es gibt zu viele mögliche Lösungen. Man sucht dann nicht die eine richtige Antwort, sondern die beste aus einer riesigen Menge. Ein Estimation of Distribution Algorithm, kurz EDA, ist ein Verfahren, das genau das tut. Es erzeugt viele Kandidatenlösungen, wählt die besten davon aus und lernt daraus, wie eine gute Lösung aussieht. Dieses Wissen drückt es als Wahrscheinlichkeitsverteilung aus — eine Beschreibung, welche Merkmale bei guten Lösungen häufig vorkommen. Aus dieser Verteilung zieht es dann neue Kandidaten, die im Schnitt noch besser sind.

EDAs als Antwort auf die Grenzen klassischer Suchalgorithmen

Viele klassische Optimierungsverfahren, etwa genetische Algorithmen, verbessern Lösungen durch kleine zufällige Veränderungen — ähnlich wie biologische Mutationen. Das funktioniert gut, wenn Einzelteile einer Lösung unabhängig voneinander sind. Sobald aber Abhängigkeiten bestehen, versagt dieser Ansatz oft. Wenn zum Beispiel zwei Merkmale nur gemeinsam gut sind, aber einzeln nichts taugen, zerstört eine zufällige Mutation leicht genau die Kombination, die wertvoll wäre.

EDAs umgehen dieses Problem. Statt blind zu mutieren, lernen sie die Struktur des Problems kennen. Das Wahrscheinlichkeitsmodell hält fest, welche Merkmale zusammengehören — und erzeugt neue Lösungen, die diese Abhängigkeiten von Anfang an respektieren. Das macht EDAs besonders stark bei Problemen, bei denen viele Variablen miteinander verknüpft sind.

Vom ersten Kandidaten zur gelernten Verteilung

Ein EDA arbeitet in einer Schleife. Im ersten Schritt erzeugt es eine Startmenge zufälliger Lösungen. Dann bewertet es jede davon: Wie gut ist sie? Anschließend behält es nur die besten — sagen wir, das beste Viertel. Aus diesen Überlebenden schätzt es ein statistisches Modell: Welche Merkmale haben die guten Lösungen gemeinsam, welche kommen oft zusammen vor? Dieses Modell ist keine feste Formel, sondern eine lernbare Wahrscheinlichkeitsverteilung.

Im nächsten Schritt zieht der Algorithmus aus dieser Verteilung eine neue Generation von Kandidaten. Merkmale, die bei guten Lösungen häufig waren, werden mit höherer Wahrscheinlichkeit weitergegeben. Die Schleife beginnt von vorn: bewerten, auswählen, Modell aktualisieren, neue Kandidaten ziehen. Nach vielen Runden nähert sich das Modell einer Verteilung, aus der fast nur noch sehr gute Lösungen stammen.

Wie genau das Modell die Abhängigkeiten erfasst, hängt vom gewählten EDA-Typ ab. Einfache Varianten gehen davon aus, dass alle Merkmale unabhängig sind — das spart Rechenzeit, ist aber ungenau. Fortgeschrittene Varianten wie das Bayesian Optimization Algorithm (BOA) lernen explizit, welche Merkmale miteinander zusammenhängen, und bauen dafür ein Netz aus bedingten Wahrscheinlichkeiten auf.

EDAs in Praxis, Forschung und verwandten Feldern

EDAs tauchen überall dort auf, wo Optimierungsprobleme mit vielen verknüpften Variablen gelöst werden müssen. In der Logistik helfen sie, Routen oder Produktionsabläufe zu planen. In der Bioinformatik suchen sie nach optimalen Genkombinationen. In der Ingenieursbranche unterstützen sie den Entwurf von Bauteilen, bei denen viele Parameter gleichzeitig aufeinander abgestimmt sein müssen.

Im Bereich des maschinellen Lernens sind EDAs eng mit dem Feld der Hyperparameter-Optimierung verwandt — also der Suche nach den besten Einstellungen für ein KI-Modell. Bekannte Bibliotheken wie Googles Vizier oder das Open-Source-Werkzeug Optuna nutzen verwandte Ideen: Sie schätzen anhand bisheriger Versuche, wo sich lohnende Einstellungen befinden dürften, und leiten daraus neue Versuche ab.

Ein häufiger Irrtum ist die Verwechslung mit reinen genetischen Algorithmen. Beide arbeiten mit Populationen von Lösungen und wählen die besten aus. Doch während genetische Algorithmen diese direkt kreuzen und mutieren, werfen EDAs die Lösungen selbst weg und behalten nur das erlernte Modell. Der Unterschied ist grundlegend: Nicht die Lösungen werden weitergegeben, sondern das Wissen über ihre Struktur.