Information Technology Reference
In-Depth Information
or
or
not
not
and
and
x
1
x
3
x
1
x
3
x
2
x
2
or
or
x
2
not
and
and
x
2
x
3
x
1
x
3
not
x
1
Abbildung 12.13: Vorteil eines GP-Crossover gegenüber den bisherigen Rekombina-
tionsoperationen: Aus zwei identischen Individuen können zwei unterschiedliche
Programme erzeugt werden.
23 Ausdrücke haben eine Fitness von 1280, einer davon entspricht einem 3-Mul-
tiplexer: (if
a
0
d
1
d
2
). Die Selektion erfolgt fitnessproportional, wobei wir 90% (lies
3600) der Individuen dem Crossover unterwerfen und die restlichen 10% (also 400)
unverändert übernehmen. Die in Abbildung 12.15 dargestellte Lösung mit einer ma-
ximalen Fitness von 2048 hat Koza [1992] nach nur 9 Generationen gefunden. Diese
Lösung ist aufgrund der Unübersichtlichkeit eher schwer zu interpretieren für Men-
schen. Sie kann jedoch vereinfacht werden durch Umformungsregeln (engl.
editing
).
Die
Umformung
ist eine asexuelle Operation eines Individuums. Sie dient der Ver-
einfachung durch generelle und spezielle Regeln. Eine
generelle Umformung
evalu-
iert eine Funktion und ersetzt einen Teilbaum mit einem Ergebnis, wenn die Funk-
tion ohne Nebeneffekte im Baum mit konstanten Argumenten auftaucht.
Speziel-
le Umformungen
wie hier in der Aussagenlogik sind Tautologien, wie
¬(¬
A
)
A
,
(
A
A
)
A
,
(
A
A
)
A
,diedeMorganschenGesetze,usw.DieUmfor-
mung kann z. B. als Operator während der GP-Suche ablaufen. Dies reduziert aufge-
blähte Individuen auf Kosten der Diversität. Normalerweise nutzt man die Umfor-
mung nur zur Interpretation der Ergebnisse. Die beste Lösung gestutzt durch eine
Aufbereitung ist in Abbildung 12.16 gezeigt.
Wir merken an, dass die beste Lösung, die durch den GP gefunden wurde, hier-
archisch ist. Sie zerlegt das 11-Multiplexer-Problems in zwei kleinere: einen 6-Mul-
tiplexer mit zwei Adressbits und 4 Datenbits und einen 3-Multiplexer mit einem
Adressbit und zwei Datenbits. Somit setzt sich die GP-Lösung aus einer Komposi-
tion zweier 6-Multiplexer zusammen.
a
0
wird genutzt, um zu entscheiden ob ent-
