Information Technology Reference
In-Depth Information
12.4.4 Problem der Introns
Mit zunehmender Generationenzahl wachsen die Individuen. Der Grund dafür sind
die sogenannten
Introns
. In der Biologie sind Introns Teile der DNA, die keine In-
formation tragen. Dies können inaktive (eventuell veraltete) Abschnitte außerhalb
eines Gens sein oder funktionslose Abschnitte außerhalb der Gene (engl.
junk DNA
).
Wir müssen Introns in der GP, soweit es geht, verhindern. So können wir z. B. den
arithmetische Ausdruck
a
+(
1
1
)
leicht vereinfachen. In
if
2
<
1
then
...
else
...ist
der
then
-Zweig sinnlos. Veränderungen durch Operatoren in aktiven Teilen des Indi-
viduums haben meist eine negative Wirkung auf die Güte. Änderungen an Introns
sind hingegen güteneutral. Dies führt zu einem künstlichen Aufblähen der Indivi-
duen. Der aktive Programmcode nimmt relativ gesehen ab, sodass die Optimierung
letztendlich stagniert.
Introns können ganz unterschiedlich verhindert werden. So können wir modifi-
zierte Operatoren, wie die
Brutrekombination
nutzen. Dabei erzeugen wir aus zwei
Eltern durch unterschiedliche Parametrisierung sehr viele Kinder, wovon nur das
Beste in die nächste Generation kommt. Wir können auch eine
intelligente Rekombina-
tion
verwenden, die gezielte Crossover-Punkte wählt. Auch können wir durch eine
fortwährend leichte Veränderungen der Bewertungsfunktion
Randbedingungen so verän-
dern, dass inaktive Programmteile (lies Introns) wieder aktiv werden. Dies funktio-
niert allerdings nur bei nicht-trivialen Introns, die durch immer ähnliche Eingabeda-
ten definiert werden. Schlussendlich können wir große Individuen auch bestrafen,
sodass sie während der Selektion benachteiligt werden.
12.4.5 Erweiterungen
Es gibt viele Erweiterungen der genetischen Programmierung [Banzhaf u. a. 1998].
Zum automatischen Definieren von Funktionen können wir beispielsweise eine
Kap-
selung
(engl.
encapsulation
)einführen:PotentiellguteTeilausdrückesolltenwirvor
der Zerstörung durch Crossover und Mutation schützen. Für einen gewissen Teil-
ausdruck (eines guten Chromosoms) definieren wir deshalb eine neue Funktion und
fügen das sie bezeichnende Symbol gegebenenfalls der Menge
F
hinzu. Dabei ist die
Zahl der Argumente der neuen Funktion gleich der Zahl der (verschiedenen) Blätter
des Teilbaums. Wir erwähnen die Erweiterungen
Iterationen
und
Rekursion
in diesem
Rahmen nur beiläufig. Dem geneigten Leser empfehlen wir, sich z. B. in [Banzhaf
u. a. 1998] über diese und weitere Erweiterungen zu informieren.
12.5 Weitere populationsbasierte Verfahren
Die
Schwarm-Intelligenz
ist ein Bereich der künstlichen Intelligenz, der intelligen-
te Multi-Agentensysteme entwickelt. Diese sind inspiriert durch das Verhalten be-
stimmter Tierarten, speziell sozialer Insekten (z. B. Ameisen, Termiten, Bienen etc.)
und in Schwärmen lebender Tiere (z. B. Fische, Vögel etc.). Tiere dieser Arten kön-
nen, indem sie kooperieren, recht komplexe Aufgaben lösen: z. B. das Finden von
Nahrungsquellen, Wegesuche, Nestbau etc. Die grundlegende Idee dabei ist, dass
die Agenten i. Allg. ziemlich einfache Individuen mit begrenzten Fähigkeiten sind.