Evolutionäre Algorithmen

Allgemein

Ein evolutionärer Algorithmus ahmt die biologischen Evolution nach und orientiert sich an ihren Entwicklungsmustern. Evolutionäre Algorithmen eignen sich zum Lösen von komplexeren Problemen. Es handelt sich hierbei um ein Optimierungsverfahren, das eine möglichst gute Näherungslösung finden soll.

Vorgehen

Im ersten Schritt wird nach dem Zufallsprinzip eine Menge von Lösungskandidaten erzeugt. Die Kadidaten werden anschließend mithilfe der Qualitätsfunktion bewertet: je höher, desto besser. Auf Grundlage dieser Werte werden die besten Kandidaten ausgewählt. Diese stellen die erste Generation dar.
Mithilfe von Rekombination und Mutation wird aus der Elterngeneration ein neuer Lösungskandidat erzeugt. Rekombination wird dabei auf mindesens zwei Kandidaten angewendet, wohingegen Mutation immer nur einen Kandidaten betrifft.
Mithilfe der Qualitätsfunktion werden anschließend die neu erzeugten Kandidaten bewertet. Diese konkurrieren nun mit ihren Eltern um einen Platz in der neuen Generation. Nur die besten Kandidaten werden aufgenommen, die schlechtesten werden verworfen.
Der beschriebene Prozess kann so lange wiederholt werden, bis ein Kandidat von ausreichender Qualität bzw. eine Lösung gefunden wurde, oder es wird eine zuvor festgelegte Rechnergrenze erreicht. ^[1],[2]

Pseudocode

BEGIN
INITIALISE population with random candidate solutions;
EVALUATE each candidate;
REPEAT UNTIL ( TERMINATION CONDITION is satisfied ) DO
1 SELECT parents;
2 RECOMBINE pairs of parents;
3 MUTATE the resulting offspring;
4 EVALUATE new candidates;
5 SELECT individuals for the next generation;
OD
END

^[1:1]

Anwendungsgebiete

Evolutionäre Algorithmen werden zur Optimierung und zur Suche verwendet. Weitere Anwendungsgebiete sind:

• Kunst
• Modellierung
• Simulation
• Entwicklung von Sensornetzen
• Analyse vom Aktienmarkt
• Vorhersage von RNA-Strukturen ^[3]

Literaturliste