Information Technology Reference
In-Depth Information
Kapitel 10
Evolutionäre Algorithmen
Evolutionäre Algorithmen stellen eine Klasse von Optimierungsverfahren dar, die
Prinzipien der biologischen Evolution nachahmen. Sie gehören zur Gruppe der Me-
taheuristiken. Das sind Algorithmen zur näherungsweisen Lösung, z. B. eines kom-
binatorischen Optimierungsproblems. Diese sind definiert durch eine abstrakte Fol-
ge von Schritten, die auf beliebige Problemstellungen anwendbar sind. Jeder ein-
zelne Schritt muss allerdings problemspezifisch implementiert werden. Aufgrund
dessen sprechen wir auch von problemspezifischen Heuristiken.
Metaheuristiken werden bei Problemen eingesetzt, für die kein effizienterer Lö-
sungsalgorithmus bekannt ist. Das Finden einer optimalen Lösung ist in der Regel
nicht garantiert. Jede gute Lösung kann beliebig schlecht sein, wenn sie mit der op-
timalen Lösung verglichen wird. Der Erfolg und die Laufzeit hängen ab von der
Problemdefinition und der Implementierung der einzelnen Schritte. Iterativ wird ei-
ne Menge an sogenannten Lösungskandidaten stetig verbessert. Ein großer Vorteil
der Metaheuristiken ist, dass sie nach jedem Iterationsschritt abgebrochen werden
können, beispielsweise aufgrund von Laufzeitbeschränkungen. Von den zuletzt kon-
struierten Lösungskandidaten wird dann meisten nur einer, nämlich der Beste als
Näherungslösung ausgegeben.
10.1 Biologische Evolution
Die Klasse der evolutionäre Algorithmen basiert auf der biologischen Evolutions-
theorie von Charles Darwin (1809-1882). Vor über 150 Jahren gelang Darwin [1859]
mit der Veröffentlichung des Werkes “On the Origin of Species” die Grundsteinle-
gung zur modernen Evolutionsbiologie. Die Evolutionstheorie erklärt die Vielfalt
und Komplexität der Lebewesen. Sie erlaubt es, alle Disziplinen der Biologie zu ver-
einen.
Das grundsätzliche Prinzip der Evolutionstheorie besagt, dass durch zufällige
Va r i a t i on ent s t ehende , vor t e i l ha f t e E i gens cha f t en durch na tür l i che Aus l e se ausge -
wählt werden. D. h., dass Individuen mit vorteilhaften Eigenschaften bessere Fort-
pflanzungs- und Vermehrungschancen haben. Dies wird auch als differentielle Re-
produktion bezeichnet.
Search WWH ::




Custom Search