Information Technology Reference
In-Depth Information
teil hat, dass man nach einer beliebigen Genauigkeit die Optimierung abbrechen
kann. Wie gut eine solche Zwischenlösung letztendlich ist, hängt natürlich auch vom
Problem und der verwendeten Kodierung eines Lösungskandidaten ab.
12.1 Genetischer Algorithmus
Der klassische genetische Algorithmus (GA) unterscheidet sich vom evolutionären
Algorithmus lediglich in seiner Kodierung. Die Chromosomen eines GA beruhen
lediglich auf Bitstrings, was uns beispielsweise die Wahl der genetischen Operato-
ren einschränkt. Sollte ein Optimierungsproblem genotypisch binär kodiert werden
können und die so entstehende Kodierung eine kleine Epistasie aufweisen (siehe
Abschnitt 11.1.2), so bietet sich immer ein GA zur Lösung des Problems an. Algo-
rithmus 6 zeigt den Pseudocode eines Standard-GA. Als eine große Ausnahme im
Feld der evolutionären Algorithmen existieren verschiedene Theorien über die Wir-
kung und Arbeitsweise der GA. Die wohl bekannteste Theorie, das Schematheorem,
wollen wir im Folgenden behandeln.
Algorithmus 6
G
ENETISCHER
-A
LGORITHMUS
Eingabe:
Fitnessfunktion
f
1:
t
0
2: pop
(
t
)
erzeuge Population mit
µ
Individuen
//
µ
muss gerade sein
3: bewerte pop
(
t
)
durch
f
4:
while
Terminierungsbedinung nicht erfüllt
do
5:
pop
(
t
)
selektiere
µ
Individuen
s
1
,...,
s
µ
aus pop
(
t
)
mittels
Glücksradauswahl
6: pop
7:
for
i
1, . . . ,
µ
/
2
do
8:
u
wähle Zufallszahl gemäß
U
([
0, 1
))
9:
if
u
p
x
then
// Rekombinationswahrscheinlichkeit
p
x
10:
s
,
s
Ein-Punkt-Crossover
(
s
(2
i
1)
,
s
(2
i
)
)
11:
else
12:
s
s
(2
i
1)
13:
s
s
(
2
i
)
14:
end if
15:
s
Binär-Mutation
(
s
)
C
Binär-Mutation
(
s
16:
)
17: pop
pop
{
s
,
s
}
18:
end for
19: bewerte pop
durch
f
20:
t
t
+
1
21: pop
(
t
)
pop
22:
end while
23:
return
bestes Individuum aus pop
(
t
)
12.1.1 Das Schematheorem
Bisher sind wir nur intuitiv auf die Frage eingegangen, warum evolutionäre Algo-
rithmen funktionieren. Für die Klasse der genetischen Algorithmen existiert ein An-
