Information Technology Reference
In-Depth Information
Eine
blinde Zufallssuche
ist immer anwendbar, aber meist sehr ineffizient, weil sel-
ten eine gute Lösung nach endlichen Schritten gefunden werden kann. Evolutionäre
Algorithmen gehören zur letzten Kategorie, der
gesteuerten Suche
.Dieseistnuran-
wendbar unter der Voraussetzung, dass die zugehörigen Funktionswerte ähnlicher
Elemente aus dem Suchraum
sich ebenfalls ähnlich sind. Nur dann sind EA in der
Lage, von einer Generation zur nächsten wertvolle Informationen weiterzutragen.
Typi sche Be i spi e l e für Opt imi erungsprobl eme s ind folgende Anwendungsgebi e-
te. Bei einer
Parameteroptimierung
soll ein Satz an günstigen Parametern gefunden
werden, sodass eine gegebene reellwertige Funktion ein (möglichst globales) Op-
timum annimmt. Beispielsweise können EA dazu benutzt werden, um nach einer
bestimmten Krümmung von Rohren zur Minimierung des Reibungswiderstands zu
suchen. Die Klasse der
Packprobleme
wie z. B. das Befüllen eines Rucksacks mit ma-
ximalem Wert oder das Packen möglichst weniger Kisten mit gegebenen Gütern ist
ein weiteres Anwendungsgebiet der EA.
Wegeprobleme
z. B. das berühmte Problem
des Handlungsreisenden (z. B. zum Bohren von Platinen) können ebenfalls elegant
mit EA gelöst werden. Hierbei wird nach einer Reihenfolge anzufahrender Ziele ge-
sucht, um die zu optimieren Fahrtroute. Praktisch ist jedes Logistikunternehmen an
der Lösung dieses Problems interessiert. Technisch gesehen fällt das Verlegen von
Leiterbahnen auf Platinen oder integrierten Schaltkreisen ebenfalls unter diese Pro-
blemklasse. Beim
Anordnungsprobleme
wie z. B. dem Steinerproblem (engl.
facility
allocation problem
)gehtesumdiePositionierungvonVerteilerknotenbeispielswei-
se in einem Telefonnetz.
Planungsprobleme
können ebenfalls sehr anschaulich durch
evolutionäre Algorithmen gelöst werden. Zu diese Art von Problemen zählen z. B.
Ablaufpläne (engl.
scheduling
), Arbeitspläne, Operationenfolgen (auch bei der Opti-
mierung in Compilern zur Umordnung der Befehle). EA werden auch zur Lösung
von
Strategieproblemen
genutzt z. B. für das Gefangenendilemma und andereModelle
der Spieltheorie. Dabei geht es um die Verhaltenssimulation von Akteuren im Wirt-
schaftsleben. Später im Abschnitt 13.1 werden wir näher auf die Verhaltenssimulati-
on eingehen.
Natürlich können evolutionäre Algorithmen aus für die
biologische Modellbildung
benutzt werden. Krink u. Vollrath [1997] haben das Programm „Netspinner“ ent-
wickelt, dass beschreibende Regeln zum Bau von natürlichen Spinnennetzen bein-
haltet. Ein EA optimiert dabei Parameter zum Bau des Netzes. Im Vergleich zur Rea-
lität liefert Netspinner ein gutes Modell.
10.2.2 Grundbegriffe der biologischen und simulierten Evolution
Wir nutzen einige Grundbegriffe der biologischen Evolution für die simulierte Evo-
lution aus, um den Zusammenhang zwischen diesen beiden Arten von Evolution zu
verdeutlichen. Diese Begriffe und deren Bedeutung in der Biologie und der Informa-
tik stellen wir im Folgenden kurz gegenüber.
Ein
Individuum
stellt in der belebten Evolutionstheorie ein Lebewesen dar. In der
Informatik hingegen wird von einem Lösungskandidaten gesprochen. Dies liegt dar-
an, dass die Problembeschreibung in der Informatik das Finden eines Optimums
impliziert (siehe Abschnitt 10.2.1).
Ein
Chromosom
(aus demAltgriechischem:
µ
Farbe,
µ
Körper, demnach
„Farbkörper“) besteht aus dem Träger der Erbinformation, der sogenannten Des-
