Information Technology Reference
In-Depth Information
schnitt 10.2 führen wir nun die simulierte Evolution im Gegensatz zur biologischen
Evolution ein.
10.2 Simulierte Evolution
Die evolutionstheoretischen Prinzipien der Zufälligkeit, der Variation und sexuellen
Reproduktion bieten für eine simulierte Evolution auf einem Rechner ideale Voraus-
setzungen. Mit dem extrem wichtigen Prinzip der Selektion, welches in der Evolu-
tionstheorie enthalten ist, ist ein sehr wirkungsvoller Steuerungsmechanismus für
den blinden Zufall gegeben. Dieser natürliche Prozess kann auf dem Computer un-
ter einfachen Bedingungen simuliert werden.
Evolutionären Algorithmen funktionieren, weil sie auch auf beide Prinzipien zu-
fällige Variation
und
Selektion basieren wie die biologische Evolution. Somit besteht
die berechtigte Hoffnung, mit ihnen gute Lösungen für Optimierungsprobleme (sie-
he Abschnitt 10.2.1) zu finden. Die Voraussetzung dafür ist eine Fitnessfunktion, die
so definiert ist, dass eine
graduelle Verbesserung
möglich ist. Die Fitnessfunktion ist in
Analogie zur biologischen Angepasstheit/Tauglichkeit in der Umwelt motiviert. Sie
muss die tatsächlich besseren von schlechteren Lösungskandidaten unterscheiden
können.
Beispielsweise brächte einer evolutionärer Optimierung eine Fitnessfunktion, die
nur einer Lösung bzw. einem Lösungskandidaten eine Fitness von 1 zuweist, allen
anderen dagegen eine Fitness von 0, verschwindend geringe Erfolgsaussichten ge-
genüber einer zufälligen Suche. Es würden dann per Zufall Lösungen kreiert, die
nicht gerichtet oder gesteuert für ein schrittweises Weiterverbessern ausgewählt wer-
den können. Mit der Fitnessfunktion muss ein gewisser Selektionsdruck modelliert
werden, der den Umweltbedingungen in der Biologie entspricht. Ähnliche Individu-
en sollten ähnliche Fitnesswerte erhalten.
10.2.1 Optimierungsprobleme
Definition 10.1 (Optimierungsproblem)
Das Dreitupel
(
,
f
,
)
beschreibt ein Opti-
mierungsproblem, dass gegeben ist durch einen Suchraum
,eineBewertungsfunktionf
:
IR
,diejedemLösungskandidateneinenGütewertzuweist,sowieeinerVergleichsrela-
tion
{
<
,
>
}
.
Dann ist die
Menge der globalen Optima
H
definiert als
x
|
x
:
f
(
x
)
f
(
x
H =
)
.
Allgemein sucht ein evolutionärer Algorithmus nach einer Näherungslösung ei-
nes Optimierungsproblems. Also lautet die Aufgabe eines EA wie folgt: Gegeben
ein Optimierungsproblem
(
,
f
,
)
,findeeinElement
x
,dasdieFunktion
f
(global) optimiert.
Prinzipiell gibt es viele verschiedene Lösungsansätze zumOptimieren von Funk-
tionen. Diese lassen sich generell in 4 Kategorien einteilen: Eine
analytische Lösung
ist sehr effizient, aber nur seltenen anwendbar, da viel Vorwissen zur Problemlö-
sung benötigt wird. Eine
vollständige Durchforstung
ist imGegensatz zur analytischen
Lösung sehr ineffizient und daher nur bei sehr kleinen Suchräumen
anwendbar.
