Lade Inhalt...

Artificial Art: Erzeugung künstlicher Bilder mit evolutionären Algorithmen in Javascript

von Rin Räuber (Autor:in)
©2013 Bachelorarbeit 126 Seiten

Zusammenfassung

Einleitung:
Natural evolution is a very creative problem solver, and the solutions of nature are ever present to remind us just what evolution is capable of. Can we make a machine 3 millimeters long that is capable of flying under its own power? What about giving it sight, or the ability to keep itself functioning by converting chemicals into energy, or even the ability to make copies of itself? We simply do not have the know-how to achieve these marvels. But this is what nature has achieved in a creature as simple as a fly (Corne und Bentley, 2001b, S. 3).
Am 22. März 2006 starteten drei Mikrosatelliten ins Weltall um das Magnetfeld der Erde zu kartieren. An Bord dieser Satelliten befand sich eine Besonderheit: Die Antenne mit deren Hilfe Daten zur Erde gesendet wurden. Sie ist kaum drei Zentimeter groß, und sieht aus als hätte man einem gelangweilten Kind ein Stück Draht in die Hand gegeben (Abbildung 1.2). Diese Antenne ist nicht von einem Menschen konzipiert worden, sondern von einem Programm, das mit Hilfe eines evolutionären Verfahrens Millionen von Entwürfen entwickelte und schließlich einen als optimal auswählte (Bluck, 2004).
über ein halbes Jahrhundert nachdem sich Informatiker zum ersten Mal damit beschäftigten, die natürliche Evolution als Vorbild für Problemlösungsverfahren heranzuziehen (Bremermann, 1958), flog damit zum ersten Mal ein mit künstlicher Evolution entwickeltes Objekt in den Weltraum (Bluck, 2006).
Die Antenne der ST5-Satelliten ist ein Beispiel für die praktische Anwendung einer Gruppe von Optimierungsverfahren, die als Evolutionäre Algorithmen bezeichnet werden. Evolutionäre Algorithmen bilden das Prinzip der natürlichen Evolution nach; sie benutzen Mutation, Rekombination und Selektion um aus einer Anfangsmenge zufälliger Lösungen die besten auszuwählen, deren Merkmale zu kombinieren und weiterzuentwickeln. Evolutionäre Algorithmen finden in zahlreichen Gebieten Anwendung, beispielsweise in den Ingenieurwissenschaften und in der Medizin.
Ein weniger bekanntes, aber nicht weniger spannendes Einsatzgebiet für evolutionäre Algorithmen liegt in der sogenannten generativen Kunst. Generative Kunst ist Kunst, die als Ergebnis eines autonomen Prozesses, beispielsweise eines Programms, entsteht. Evolutionäre Kunst ist dementsprechend Kunst, die als Ergebnis eines evolutionären Prozesses entsteht. Ein Beispiel für evolutionär entwickelte Kunst ist Al Biles’ GenJam, ein genetischer Algorithmus der Jazz-Soli erzeugt (Biles, 1994).[...]

Leseprobe

Inhaltsverzeichnis


Räuber, Rin: Artificial Art: Erzeugung künstlicher Bilder mit evolutionären Algorithmen
in Javascript, Hamburg, Diplomica Verlag GmbH 2013
PDF-eBook-ISBN: 978-3-8428-1545-2
Herstellung: Diplomica Verlag GmbH, Hamburg, 2013
Zugl. Fachhochschule Dortmund, Dortmund, Deutschland, Bachelorarbeit, Februar 2013
Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Jede Verwertung
außerhalb der Grenzen des Urheberrechtsgesetzes ist ohne Zustimmung des Verlages
unzulässig und strafbar. Dies gilt insbesondere für Vervielfältigungen, Übersetzungen,
Mikroverfilmungen und die Einspeicherung und Bearbeitung in elektronischen Systemen.
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in
diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme,
dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei
zu betrachten wären und daher von jedermann benutzt werden dürften.
Die Informationen in diesem Werk wurden mit Sorgfalt erarbeitet. Dennoch können
Fehler nicht vollständig ausgeschlossen werden und die Diplomica Verlag GmbH, die
Autoren oder Übersetzer übernehmen keine juristische Verantwortung oder irgendeine
Haftung für evtl. verbliebene fehlerhafte Angaben und deren Folgen.
Alle Rechte vorbehalten
© Diplom.de, Imprint der Diplomica Verlag GmbH
Hermannstal 119k, 22119 Hamburg
http://www.diplom.de, Hamburg 2013
Printed in Germany

Inhaltsverzeichnis
Inhaltsverzeichnis
1
Einleitung
3
1.1
Motivation
. . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.2
Zielsetzung . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.3
Gliederung
. . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2
Einf¨
uhrung in Evolution¨
are Algorithmen
9
2.1
Ursprung und Historie . . . . . . . . . . . . . . . . . . . . .
10
2.2
Biologische Grundlagen und Terminologie . . . . . . . . . .
11
2.3
Ein einfacher evolution¨
arer Algorithmus . . . . . . . . . . .
11
2.4
Arten Evolution¨
arer Algorithmen . . . . . . . . . . . . . . .
16
2.5
Diskussion . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
2.6
Praktische Anwendung . . . . . . . . . . . . . . . . . . . . .
24
3
Evolution¨
are Kunst
27
3.1
Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
3.2
Exploration versus Optimierung . . . . . . . . . . . . . . . .
28
3.3
Kunst mit interaktiver Evolution . . . . . . . . . . . . . . .
28
3.4
Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
3.5
Rezeption, Probleme und offene Fragen
. . . . . . . . . . .
38
4
Analyse
41
4.1
Evaluation von JS-Grafik-Frameworks . . . . . . . . . . . .
41
4.2
Existierende Projekte
. . . . . . . . . . . . . . . . . . . . .
51
5
Implementierung
57
5.1
Implementierung eines einfachen EA . . . . . . . . . . . . .
58
5.2
Die grundlegende Implementierung . . . . . . . . . . . . . .
59
5.3
Die Fitnessfunktion . . . . . . . . . . . . . . . . . . . . . . .
61
5.4
Die Repr¨
asentation . . . . . . . . . . . . . . . . . . . . . . .
64
5.5
Diversit¨
at . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
5.6
Selektion . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
5.7
Mutation
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
5.8
Rekombination . . . . . . . . . . . . . . . . . . . . . . . . .
81
5.9
Startpopulation . . . . . . . . . . . . . . . . . . . . . . . . .
82
5.10 Javascript-Performance
. . . . . . . . . . . . . . . . . . . .
84
6
Ergebnisse
87
6.1
Einordnung des entwickelten Algorithmus . . . . . . . . . .
87
6.2
Entwickelte Bilder . . . . . . . . . . . . . . . . . . . . . . .
88
7
Fazit und Ausblick
95
7.1
Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
96
7.2
Ausblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99
iii

Inhaltsverzeichnis
8
Anhang
101
8.1
Quellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
101
8.2
Kurz-Einf¨
uhrung Coffeescript . . . . . . . . . . . . . . . . .
111
8.3
Liste aller gefundenen Projekte . . . . . . . . . . . . . . . .
114
8.4
Glossar
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
116
iv

Abstract
This thesis was aimed at developing an evolutionary algorithm in clientside
Javascript which gradually evolves an artistic rendering for a given image
by placing graphic primitives on a canvas.
As a prerequisite, evolutionary algorithms and their main paradigms and
characteristics are discussed, followed by a introduction to evolutionary art
and a presentation of some of its works. In addition, similar existing projects
and candidates for the graphic framework are evaluated.
The implementation focuses on the choice of suitable methods and para-
meters like population size, selection method etc. and tests different com-
binations. For mutation operator probabilities, Niehaus' Individual-Level
Dynamic Probabilities (IDP) were implemented successfully.
The resulting evolutionary artistic rendering technique, called the Ballpit
Effect, is capable of producing interesting results, while the underlying im-
plementation is readable and compact, and therefore might serve to spark
the interest of developers outside of the EA community looking for a gentle
introduction to the topic.
Zusammenfassung
Ziel dieser Arbeit war die Entwicklung eines evolution¨
aren Algorithmus
in clientseitigem Javascript, der ausgehend von einem gegebenen Bild ein
sogenanntes Artistic Rendering entwickelt indem grafische Primitive auf
einer Leinwand platziert werden.
Einf¨
uhrend werden evolution¨
are Algorithmen, ihre wichtigsten Paradigmen
und Eigenschaften diskutiert. Anschließend folgt ein ¨
Uberblick ¨
uber evo-
lution¨
are Kunst und ihre wichtigsten Werke. Als Vorarbeit zur Implemen-
tierung werden ausserdem ¨
ahnliche, bereits existierende Projekte evaluiert
und ein geeignetes Grafikframework ausgew¨
ahlt.
Der Fokus der Implementierung liegt auf der Wahl geeigneter Methoden
und Parameter wie Populationsgr¨
oße, Selektionsmethode, Mutationsrate
etc., f¨
ur die verschiedene Kombinationen erprobt werden. Zur dynamischen
Anpassung der Wahrscheinlichkeit der Mutationsoperatoren wurden erfolg-
reich Niehaus' Individual-Level Dynamic Probabilities (IDP) implementiert.
Die entwickelte evolution¨
are Rendering-Technik, der Ballpit Effect, ist in
der Lage interessante Ergebnisse zu produzieren, w¨
ahrend die zugrundelie-
gende Implementierung aufgrund ihrer Kompaktheit und Lesbarkeit dazu
dienen kann, bei Entwicklern ausserhalb der EA-Community das Interesse
an diesem Thema zu wecken.


1
Kapitel 1
Einleitung
1
Natural evolution is a very creative problem solver, and the solu-
tions of nature are ever present to remind us just what evolution
is capable of.
Can we make a machine 3 millimeters long that is capable of
flying under its own power? What about giving it sight, or the
ability to keep itself functioning by converting chemicals into en-
ergy, or even the ability to make copies of itself ?
We simply do not have the know-how to achieve these marvels.
But this is what nature has achieved in a creature as simple as
a fly.
(Corne und Bentley, 2001b, S. 3)
1
Bild aus (Chamberlain und Etter, 1984, S. 23)
3

Abbildung 1.2: Prototyp der Antenne der ST5-Mission. (Lohn et al., 2005, S. 11).
Am 22. M¨
arz 2006 starteten drei Mikrosatelliten ins Weltall um das Ma-
gnetfeld der Erde zu kartieren. An Bord dieser Satelliten befand sich eine
Besonderheit: Die Antenne mit deren Hilfe Daten zur Erde gesendet wur-
den. Sie ist kaum drei Zentimeter groß, und sieht aus als h¨
atte man einem
gelangweilten Kind ein St¨
uck Draht in die Hand gegeben (Abbildung 1.2).
Diese Antenne ist nicht von einem Menschen konzipiert worden, sondern
von einem Programm, das mit Hilfe eines evolution¨
aren Verfahrens Millio-
nen von Entw¨
urfen entwickelte und schließlich einen als optimal ausw¨
ahlte
(Bluck, 2004).
¨
Uber ein halbes Jahrhundert nachdem sich Informatiker zum ersten Mal
damit besch¨
aftigten, die nat¨
urliche Evolution als Vorbild f¨
ur Probleml¨
o-
sungsverfahren heranzuziehen (Bremermann, 1958), flog damit zum ersten
Mal ein mit k¨
unstlicher Evolution entwickeltes Objekt in den Weltraum
(Bluck, 2006).
Die Antenne der ST5-Satelliten ist ein Beispiel f¨
ur die praktische Anwen-
dung einer Gruppe von Optimierungsverfahren, die als Evolution¨
are Algo-
rithmen bezeichnet werden. Evolution¨
are Algorithmen bilden das Prinzip
der nat¨
urlichen Evolution nach; sie benutzen Mutation, Rekombination und
Selektion um aus einer Anfangsmenge zuf¨
alliger L¨
osungen die besten auszu-
ahlen, deren Merkmale zu kombinieren und weiterzuentwickeln. Evolutio-
are Algorithmen finden in zahlreichen Gebieten Anwendung, beispielsweise
in den Ingenieurwissenschaften und in der Medizin.
4

1.1. MOTIVATION
Abbildung 1.3: Beispiel f¨
ur ein Electric Sheep
3
.
Ein weniger bekanntes, aber nicht weniger spannendes Einsatzgebiet f¨
ur
evolution¨
are Algorithmen liegt in der sogenannten generativen Kunst. Ge-
nerative Kunst ist Kunst, die als Ergebnis eines autonomen Prozesses, bei-
spielsweise eines Programms, entsteht. Evolution¨
are Kunst ist dementspre-
chend Kunst, die als Ergebnis eines evolution¨
aren Prozesses entsteht. Ein
Beispiel f¨
ur evolution¨
ar entwickelte Kunst ist Al Biles' GenJam, ein geneti-
scher Algorithmus der Jazz-Soli erzeugt (Biles, 1994)
2
. Ein anderes promi-
nentes Beispiel ist der Mondriaan Evolver, ein Programm, das evolution¨
ar
Bilder ¨
ahnlich der streng geometrischen Gem¨
alde des niederl¨
andischen Ma-
lers Piet Mondriaan entwickelt (Eiben, 2008). Ein zeitgem¨
aßes Beispiel ist
das Programm Electric Sheep, das als Bildschirmschoner funktioniert und
so sich im Leerlauf bedindliche Rechner als Renderfarm benutzt um mit ge-
netischen Algorithmen fraktale Animationen zu entwickeln und diese von
Benutzern bewerten l¨
asst (Draves, 2005) (siehe Beispiel in Abbildung 1.3).
1.1 Motivation
ur gew¨
ohnlich wird ein Computerprogramm definiert als eine Menge ge-
ordneter Instruktionen, die einen Computer bef¨
ahigen eine bestimmte Auf-
gabe automatisch auszuf¨
uhren
4
. Bei unerwartetem Verhalten eines Pro-
gramms handelt es sich in diesem Zusammenhang meist um einen Feh-
ler. Die Instruktion
BE CREATIVE AND INVENT STUFF
geh¨
ort typischerwei-
2
Ein aktueller Vortrag mit Demonstration findet sich unter
http://www.youtube.com/
watch?v=rFBhwQUZGxg
(Stand 18.02.2013)
3
Quelle:
http://v2d7c.sheepserver.net/cgi/dead.cgi?id=59383
(Stand 18.02.2013)
4
aus
Britannica
Concise
Encyclopedia,
siehe
http://www.answers.com/topic/
computer-program
(Stand 18.02.2013); interessanterweise sind die meisten aktuellen
Definitionen sehr viel weiter gefasst.
5

1.1. MOTIVATION
se nicht zum Repertoire der Instruktionen; f¨
ur die meisten Erfinder und
unstler d¨
urfte der Computer ein Werkzeug wie Reißbrett oder Pinsel sein,
aber kein mit eigener Kreativit¨
at ausgestatteter Gehilfe, geschweige denn
Konkurrent. F¨
ur andere ist er jedoch genau das ­ er erm¨
oglicht, aus un-
ahligen m¨
oglichen Kombinationen von Farben, Formen, Materialien, be-
stimmte auszuw¨
ahlen und weiterzuentwickeln. Unerwartete Entwicklungen
­ Innovation und Originalit¨
at ­ sind hier erw¨
unscht.
Besonders f¨
ur interessierte Laien d¨
urfte evolution¨
are Kunst ein willkom-
mener Farbklecks in der Landschaft der Informatik sein. Trotzdem exis-
tieren bisher nur wenige Beispiele
5
evolution¨
arer Kunst, die zeitgem¨
aße
Web-Technologien nutzen und damit dieses immer noch etwas exotische
Gebiet in nutzerfreundlicher Form einer gr¨
oßeren ¨
Offentlichkeit zug¨
anglich
machen. Mit der vorliegenden Arbeit soll diese L¨
ucke gef¨
ullt werden.
1.1.1 Exkurs: Warum Javascript/Coffeescript?
Zum ersten Mal ver¨
offentlich wurde Javascript 1995 als Teil der Netscape
Navigator 2.0 Beta. Die erste Anwendung war die Validierung von For-
mularen. Neun Jahre sp¨
ater verwendete Google in seinem Webmail-Dienst
Google Mail als einer der ersten Javascript um Daten mit dem Server aus-
zutauschen, ohne dass die Webseite neu geladen werden musste.
6
Die als
Ajax (Asynchronous Javascript and XML) bekannt gewordene Technolo-
gie ist maßgeblich f¨
ur die heutige Popularit¨
at von Javascript verantwort-
lich. (Swartz, 2005) Auf Ajax folgten Javascript-Frameworks wie Prototype
(Stephenson), JQuery (Resig) und MooTools (Proietti), die die Entwick-
lung vollwertiger Applikationen erm¨
oglichten, welche sich f¨
ur den Nutzer
wie Desktop-Anwendungen anf¨
uhlen. Auch hier stammt mit Google Docs
das prominenteste Beispiel von Google. Aus dem Browser, der urspr¨
unglich
nur ein Betrachtungswerkzeug f¨
ur strukturierten Text war, ist eine Anwen-
dungsplattform geworden ­ und zwar eine der am weitesten verbreiteten,
die sowohl auf mobilen Ger¨
ate als auch auf Desktop-Rechnern verf¨
ugbar ist.
Damit eignet sich Javascript besonders um die Idee der Erzeugung k¨
unst-
licher Bilder mit evolution¨
aren Algorithmen einer gr¨
oßeren ¨
Offentlichkeit
bekannt zu machen; zur Ausf¨
uhrung wird lediglich ein aktueller Browser
ben¨
otigt. Technologien wie die HTML5 Canvas, SVG und die verf¨
ugba-
ren Grafikframeworks f¨
ur Javascript machen die Bilderzeugung ausserdem
relativ entwicklerfreundlich.
Im akademischen Kontext hat Javascript immer noch einen gewissen Exo-
tenstatus
7
; das Thema der Arbeit ist in der Hoffnung gew¨
ahlt, dass die
5
ur existierende Projekte, siehe Kapitel 5.
6
Die XMLHttpRequest -API (kurz XHR), die dies erm¨
oglicht, war bereits seit 1999 Teil
des Internet Explorers, wurde aber bis dahin kaum verwendet.
7
Als Indiz kann man beispielsweise eine Suche in der Zitationsdatenbank CiteSeer heran-
ziehen: F¨
ur den Zeitraum von 2010 bis heute finden sich knapp 300 Ver¨
offentlichungen
mit dem Wort "JavaScript", w¨
ahrend es zu "Java"¨
uber 1.600 sind.
6

1.2. ZIELSETZUNG
Verwendung von Javascript auch f¨
ur etwas anspruchsvollere Aufgaben im
akademischen Kontext zuk¨
unftig keine Seltenheit bleibt
8
.
Die Verwendung von Javascript f¨
ur eine rechenaufw¨
andige Aufgabe wie evo-
lution¨
are Algorithmen stellt ausserdem eine interessante Herausforderung
dar: Clientseitiges Javascript war bis zur Ver¨
offentlichung von HTML5s
Web Workern traditionell ausschließlich single-threaded
9
(Flanagan, 2002,
S. 318).
Coffeescript ist eine Skriptsprache, die in Javascript transkompiliert wird.
Sie bietet eine elegante, vereinfachte und entschlackte Syntax und soge-
nannten
Syntactic Sugar. Im Gegensatz zu anderen Sprachen die eben-
falls zu Javascript transkompiliert werden
10
, wie beispielsweise Dart
11
, ist
das erkl¨
arte Ziel von Coffeescript, syntaktisch m¨
oglichst nah an Javascript
zu bleiben dessen
"
good parts" herauszustellen (Ashkenas). Coffeescript ver-
spricht, dass der generierte Javascript-Code in etwa so performant sei als
atte man ihn urspr¨
unglich in Javascript geschrieben
12
. Eine Kurzeinf¨
uh-
rung in Coffeescript findet sich im Anhang unter Abschnitt 8.2.
1.2 Zielsetzung
Thema dieser Arbeit ist die Erzeugung von Bildern mit evolution¨
aren Al-
gorithmen in Javascript. Hierf¨
ur wird eine Anwendung implementiert, die
anhand eines von einem Benutzer hochgeladenen Bilds evolution¨
ar durch
sogenanntes Artistic Rendering
13
ein ¨
ahnliches Bild erzeugt, gewissermaßen
eine k¨
unstlich erzeugte, k¨
unstlerische Interpretation des Bildes.
8
Ein w¨
unschenswerter Nebeneffekt w¨
are ausserdem, dass mit der Ver¨
offentlichung der
Implementierung in Javascript Web-Entwickler auf das eher akademische Thema evo-
lution¨
arer Algorithmen aufmerksam w¨
urden.
9
Auch
wenn
es
unter
Umst¨
anden
nebenl¨
aufiges
Verhalten
zeig-
te,
siehe
Diskussion
http://stackoverflow.com/questions/2734025/
is-javascript-guaranteed-to-be-single-threaded
(Stand 18.02.2013).
10
ur
eine
Liste
siehe
https://github.com/jashkenas/coffee-script/wiki/
List-of-languages-that-compile-to-JS
(Stand 22.02.2013)
11
siehe
http://www.dartlang.org/
(Stand 22.02.2013)
12
Diese
Behauptung
wird
immer
wieder
diskutiert,
siehe
beispielswei-
se
http://www.quora.com/How-is-CoffeeScripts-performance
(Stand
18.02.2013)
und
http://stackoverflow.com/questions/9047276/
is-coffeescript-faster-than-javascript
. (Stand 18.02.2013)
13
Artistic Rendering oder auch Non-Photorealistic Rendering (NPR) bezeichnet eine
Methode zum Erzeugen von Computergrafiken in einem von Malerei, Zeichnung und
Illustration inspirierten Stil.
7

1.3. GLIEDERUNG
1.3 Gliederung
Nachdem in diesem einleitenden Kapitel Motivation und Zielsetzung der
Arbeit dargelegt wurden, f¨
uhrt Kapitel 2 in die Grundlagen evolution¨
arer
Algorithmen ein. Nach einem kurzen Abriss ¨
uber m¨
ogliche Selektionsmetho-
den und Repr¨
asentationen werden die wichtigsten Paradigmen im Bereich
evolution¨
arer Algorithmen vorgestellt, diskutiert und einige Beispiele zur
praktischen Anwendung dieser Algorithmen genannt.
Kapitel 3 widmet sich dem Thema evolution¨
arer Kunst: Hier werden Bei-
spiele f¨
ur existierende Arbeiten aus verschiedenen Gebieten aufgef¨
uhrt und
Probleme und offene Fragen diskutiert.
Das 4. Kapitel enth¨
alt die Vorarbeit zur Implementierung: Es werden ver-
schiedene Javascript-Frameworks zur Bilderzeugung evaluiert und eine sub-
jektive Auswahl existierender Projekte vorgestellt..
In Kapitel 5 wird mit Hilfe der ausgew¨
ahlten Frameworks eine Anwendung
implementiert, die evolution¨
ar Bilder erzeugt.
In Kapitel 6 werden beispielhaft Ergebnisse der entwickelten Anwendung
vorgestellt und an zwei Beispielen die Entstehung dokumentiert.
Die Arbeit schließt mit dem Fazit ab, in dem die gewonnenen Erkenntnisse
zusammengefasst werden.
Im Anhang schließlich finden sich die verwendeten Quellen, ein Glossar, das
Abbildungsverzeichnis, sowie eine kurze Einf¨
uhrung in Coffeescript.
Begriffskl¨
arung
Der Begriff
"
Evolution¨
arer Algorithmus" wird in der vor-
liegenden Arbeit nicht im strengen Sinn eines Algorithmus
14
gebraucht,
sondern allgemein f¨
ur evolution¨
are Systeme, d. h. f¨
ur die Kombination aus
evolution¨
arem Algorithmus, Repr¨
asentation, Operatoren, Fitnessfunktion
etc. und deren Implementierung.
Anmerkung zur Textauszeichnung und Screenshots
Fachbegriffe und Ei-
gennamen sind bei ihrem ersten Auftreten kursiv gesetzt, bei weiterem
Auftreten werden sie nicht mehr hervorgehoben. Durch einen
Pfeil ge-
kennzeichnete Begriffe k¨
onnen im Glossar (Abschnitt 8.4) nachgeschlagen
werden. Screenshots wurden mit einer m¨
oglichst hohen Aufl¨
osung erstellt,
onnen im Druck aber pixelig wirken.
14
Ein Algorithmus ist
"
eine Menge von Regeln, die eine Abfolge von Operationen exakt
derart beschreibt, dass jede Regel effektiv und eindeutig ist und dass die Abfolge in
endlicher Zeit terminiert". (nach (Stone, 1971, S. 8))
8

2
Kapitel 2
Einf¨
uhrung in Evolution¨
are
Algorithmen
1
"Ich habe Ihnen doch gesagt, dass ich meine Maschinen vervollkommnen
will."
"Na und? Nehmen Sie Ihre Zeichnungen und ¨
uberlegen Sie, wie Sie das ma-
chen k¨
onnen. Was soll diese Fehde untereinander? So fangen die Biester
ja an, sich gegenseitig aufzufressen!"
"Sehr richtig. Und nur die vollkommensten bleiben ¨
ubrig. [. . . ] Erfolgreich
werden diejenigen sein, in denen rein zuf¨
allig gerade die Eigenschaften
der Konstruktion zusammentreffen, die sie besonders lebenst¨
uchtig machen.
[. . . ] Darum habe ich auch nicht die Absicht, mich mit Zeichnungen und
Entw¨
urfen aufzuhalten. Ich brauche nur abzuwarten, bis die Maschinen alles
Metall auf dieser Insel verschlungen haben und einen Krieg untereinander
anfangen, wobei sie sich gegenseitig auffressen und neu produzieren werden.
Dadurch werde ich genau die Maschine erhalten, die ich haben will."
aus: Anatoly Dneprov ­ Die Insel der Krebse
2
.
1
Bild Crab Robot von Christopher Myers, Quelle:
http://www.isopoddesign.com/9.
html
, Stand 11.02.2013
2
Quelle:
http://www.bionik.tu-berlin.de/institut/skript/inskreb.htm
, Stand
11.02.2013
9

2.1. URSPRUNG UND HISTORIE
Dieses Kapitel f¨
uhrt in evolution¨
are Algorithmen ein. Nach einem kurzen
Abriss ¨
uber die Entwicklungsgeschichte evolution¨
arer Algorithmen wird in
die biologischen Grundlagen und die daraus abgeleitete Terminologie einge-
uhrt. Anschließend werden verschiedene Arten evolution¨
arer Algorithmen
vorgestellt und ihre Vor- und Nachteile diskutiert. Schließlich werden bei-
spielhaft einige Anwendungen vorgestellt.
Anmerkung: Der Begriff Evolution¨
are Algorithmen wird hier synonym mit
dem ¨
Uberbegriff Evolutionary Computation verwendet.
2.1 Ursprung und Historie
Zu der Zeit als Charles Darwin sein "On the Origin of Species" ver¨
offent-
lichte, war die vorherrschende Erkl¨
arung f¨
ur die Vererbung von Merkma-
len, dass sich die Eigenschaften beider Eltern ¨
ahnlich zweier Fl¨
ussigkeiten
mischen w¨
urden (Sivanandam und Deepa, 2010, S. 6)
3
. Die Kreuzungs-
experimente die Gregor Mendel mit Erbsen durchf¨
uhrte widerlegten diese
Theorie, doch seine Ergebnisse blieben dreissig Jahre weitgehend unbeach-
tet ­ bis Hugo de Vries, Carl Correns und Erich von Tschermak sie Anfang
des zwanzigsten Jahrhunderts wiederentdeckten.
Mit Hilfe der Gene konnten viele Fragen beantwortet werden, die Darwins
Evolutionstheorie offen gelassen hatte (Schwartz, 2009, S. 105ff). Sechzig
Jahre sp¨
ater, 1964, wurde der genetischen Code entschl¨
usselt. Etwa um
die gleiche Zeit begannen einige Informatiker unabh¨
angig voneinander zu
untersuchen, wie das Prinzip der Evolution als Werkzeug zur Optimierung
bei technischen Problemen angewandt werden k¨
onnte (Michell, 1998, S. 2).
Sie legten die Grundlage f¨
ur die vier Arten evolution¨
arer Algorithmen die
man heute unterscheidet (Kenneth De Jong und Schwefel, 1997, A.2.3.4ff):
die Evolutionsstrategien von Ingo Rechenberg und Hans-Paul Schwefel,
genetische Algorithmen
von John Henry Holland, evolution¨
ares Pro-
grammieren
von Lawrence J. Fogel und genetisches Programmieren
von John Koza.
Die verschiedenen Paradigmen unterscheiden sich in der Repr¨
asentation
oglicher L¨
osungen, ihren Reproduktionsoperatoren und ihrer Selektions-
methode (Sivanandam und Deepa, 2010, S. 2). Sie werden in den folgenden
Abschnitten eingehend erl¨
autert.
3
Diese schon damals h¨
aufig bezweifelte Hypothese wird als blending inheritance bezeich-
net.(Schwartz, 2009, S. 3)
10

2.2. BIOLOGISCHE GRUNDLAGEN UND TERMINOLOGIE
2.2 Biologische Grundlagen und Terminologie
Jeder lebende Organismus besteht aus Zellen, in deren Kern die geneti-
sche Information in Form von Chromosomen-Paaren gespeichert sind
4
.
Chromosomen werden in Gene unterteilt. Gene bestimmen die Merkmale
eines Individuums. Die Gesamtheit der Gene eines Individuums werden als
Genotyp
bezeichnet; das physische Erscheinungsbild das man erh¨
alt, wenn
man den Genotyp dekodiert ist der sogenannte Ph¨
anotyp
. (Sivanandam
und Deepa, 2010, S. 16ff) (Michell, 1998, S. 5)
Bei der sexuellen Fortpflanzung werden die Gene der Elternindividuen re-
kombiniert um die Chromosomen-Paare des Nachkommens zu erhalten; die-
ser Prozess der Rekombination wird als Crossover
5
bezeichnet. Weiterhin
kann es beim Nachkommen zur Mutation kommen, beispielsweise durch
Fehler beim Kopieren von Teilen der Eltern-Gene (Michell, 1998, S. 5). ­
So entsteht genetische Variation.
Individuen, die besser an ihre Umwelt angepasst sind haben eine h¨
ohere
Wahrscheinlichkeit zu ¨
uberleben und sich fortzupflanzen, w¨
ahrend schlech-
ter angepasste eine geringere ¨
Uberlebenschance und weniger Nachkommen
haben. So f¨
uhrt die genetische Variation zu einer nat¨
urlichen Selektion,
die ¨
uber mehrere Generation dazu f¨
uhrt, dass die Population vorwiegend
aus besser angepassten Individuen besteht. (Sivanandam und Deepa, 2010,
S. 19) Die Anpassungsg¨
ute eines Individuums wird als Fitness bezeichnet.
2.3 Ein einfacher evolution¨
arer Algorithmus
Ein evolution¨
arer Algorithmus wird typischerweise eingesetzt, um ein Op-
timierungsproblem zu l¨
osen ­ oder besser: um einen m¨
oglichst guten N¨
ahe-
rungswert an eine L¨
osung zu erzeugen (Weicker, 2002, S. 20). Eine m¨
ogliche
osung wird, analog zum biologischen Vorbild, als Individuum bezeichnet;
eine Menge m¨
oglicher L¨
osungen dementsprechend als Population.
Diese L¨
osungskandidaten werden je nach Problem verschieden repr¨
asen-
tiert; bei genetischen Algorithmen wird als Repr¨
asentation traditioneller-
weise ein Bitstring benutzt; eine Alternative sind beispielsweise reellwertige
Vektoren oder Integer-Listen. (Weicker, 2002, S. 131). Die enkodierte L¨
o-
sung wird entsprechend des biologischen Vorbilds als Ph¨
anotyp bezeichnet,
die dekodierte als Genotyp.
Der Algorithmus beginnt mit einer zuf¨
allig erzeugten Population m¨
ogli-
cher L¨
osungen P
t
(in der Abbildung die initial population). F¨
ur jedes In-
4
Diese vereinfachte Darstellung soll an dieser Stelle gen¨
ugen; sie trifft jedoch nicht auf
Lebewesen ohne Zellkern zu.
5
in der deutschen Literatur chromosomales Crossing-over
11

2.3. EIN EINFACHER EVOLUTION ¨
ARER ALGORITHMUS
INITIAL POPULATION
of random individuals
1
2
3
FITNESS RANKING
according to fitness function
SELECTION AND
REPRODUCTION
GENETIC VARIATION
through recombination and mutation
Abbildung 2.2: Vereinfachte Funktionsweise eines evolution¨
aren Algorithmus (eige-
ne Grafik).
dividuum dieser Startpopulation wird mit Hilfe einer Fitnessfunktion eine
Bewertung erstellt (in der Abbildung: ranking). Anhand dieser Bewertung
werden einige Individuen als Elternindividuen selektiert (Elternselektion,
(Weicker, 2002, S. 24)). Durch Rekombination dieser Elternindividuen wer-
den Nachkommen erzeugt, und zwar je mehr, je besser die Bewertung der
Elternindividuen ist (in der Abbildung: reproduction). Bei den Nachkom-
men treten ausserdem mit einer gewissen Wahrscheinlichkeit Mutationen
auf.
Rekombinations- und Mutationsoperatoren werden entsprechend der Re-
pr¨
asentation gew¨
ahlt; im einfachsten Fall der Repr¨
asentation als Bitstring
besteht eine Mutation beispielsweise darin, ein Bit zu tauschen. Alternative
Repr¨
asentationen sind B¨
aume (speziell beim sp¨
ater vorgestellten Geneti-
schen Programmieren, bei dem die gesuchte L¨
osung ein als Baum repr¨
asen-
tiertes Programm ist) oder reelle Werte (Michell, 1998, S. 118).
Abbildung 2.2 zeigt einen einfachen evolution¨
aren Algorithmus: Er beginnt
mit einer Anfangspopulation zuf¨
allig erzeugter Individuen, die anschließend
anhand ihrer Fitness sortiert werden. Dann werden Elternindividuen se-
lektiert und durch Rekombination neue Nachkommen aus ihnen erzeugt,
von denen ein gewisser Prozentsatz durch Mutation ver¨
andert wird. Diese
Nachkommen bilden die n¨
achste Generation von Individuen, die wiederum
wieder nach Fitness sortiert werden ­ und so weiter.
12

2.3. EIN EINFACHER EVOLUTION ¨
ARER ALGORITHMUS
Algorithmus 1 zeigt eine beispielhafte Implementierung eines evolution¨
aren
Algorithmus in Pseudocode: Die Variable t steht f¨ur die Zahl der Generati-
on, P (t) ist die Population der Generation t. Die Abbruchbedingung kann
beispielsweise eine minimal zu erreichende Bewertung oder eine maximale
Anzahl an Generationen sein. Bei jedem Schleifendurchlauf wird eine neue
Generation erzeugt, indem aus der Vorg¨
angergeneration Eltern selektiert
werden. Diese werden anschließend rekombiniert und mutiert. Nach einer
Fitnessbewertung werden ¨
Uberlebende selektiert
6
.
Algorithmus 1:
Ein einfacher evolution¨
arer Algorithmus (B¨
ack, 1996,
S. 66), (Friedrich, 2005, S. 68).
t
0
P
t
Zufallspopulation
evalFitness(P
t
)
while
not Abbruchbedingung do
t
t + 1
P
t
selektiereEltern(P
t-1
)
P
t
rekombiniere(P
t
)
P
t
mutiere(P
t
)
evalFitness(P
t
) P
t
selektiere(P
t
)
end
Zur Erstellung eines evolution¨
aren Algorithmus ben¨
otigt man also mindes-
tens eine geeignete Repr¨
asentation, eine geeignete Fitnessfunktion, Selek-
tionsmethode(n), Rekombinationsoperator(en) und Mutationsoperator(en).
Ausserdem m¨
ussen weitere Parameter wie Mutationswahrscheinlichkeit und
Gr¨
oße der Population festgelegt werden.
2.3.1 Selektionsmethoden
Die Aufgabe der Selektionsmethode ist es, bessere L¨
osungen einer Popu-
lation h¨
oher zu gewichten (Deb, 1997b, C2.1.1). Die beiden am h¨
aufigs-
ten verwendeten Selektionsmethoden sind die Roulette-Selektion und die
Turnier-Selektion.
Bei einer proportionalen Selektion werden die Individuen proportional
zu ihrer Fitness ausgew¨
ahlt (Deb, 1997b, C2.1:2). Die einfachste Variante
der proportionalen Selektion ist die sogenannte Roulette-Selektion. Da-
bei wird jedem Individuum der Population proportional zu seiner Fitness
ein Teil der Fl¨
ache eines Roulette-Rads zugewiesen; dann wird das Rad so
oft gedreht wie die selektierte Population groß sein soll. So wird ein Indivi-
duum mit h¨
oherer Fitness mit gr¨
oßerer Wahrscheinlichkeit ausgew¨
ahlt als
eines mit geringerer Fitness.
6
Der Algorithmus unterscheidet zwischen der Elternselektion (Auswahl der Elternindi-
viduen) und der Umweltselektion (Auswahl der ¨
Uberlebenden), worauf in Abbildung
2.2 der Einfachheit wegen verzichtet wurde.
13

2.3. EIN EINFACHER EVOLUTION ¨
ARER ALGORITHMUS
Abbildung 2.3: Beispiel einer Roulette-Selektion (Friedrich, 2005, S. 61)
Die Roulette-Selektion hat allerdings auch Nachteile: Existiert in der Popu-
lation ein Individuum mit aussergew¨
ohnlich hoher Fitness (eine sogenannte
supersolution), dann wird diese den gr¨
oßten Teil des Roulette-Rads beset-
zen; dadurch geht Diversit¨
at verloren und der Algorithmus wird eventuell
(zu) fr¨
uh in Richtung einer suboptimalen L¨
osung konvergieren. Enth¨
alt die
Population hingegen viele Individuen mit ¨
ahnlicher Fitness, dann entspricht
die Roulette-Selektion einer rein zuf¨
alligen Auswahl.
Eine Alternative zur proportionalen Selektion ist die Turnier-Selektion:
Dabei w¨
ahlt man eine Anzahl von Individuen aus der Population und l¨
asst
sie in einem Turnier gegeneinander antreten; das Individuum mit der besten
Fitness gewinnt. Turnier-Selektion kann mit oder ohne Zur¨
ucklegen erfol-
gen. Ein Vorteil ist, dass Turnier-Selektion parallel implementiert werden
kann, weil immer nur eine Auswahl von Individuen miteinander verglichen
werden m¨
ussen. (Blickle, 1997, C2.3:1)
Weitere Selektionsmethoden, wie beispielsweise die Boltzmann-Selektion,
werden in (Fogel, 1997b, C2.6) diskutiert.
2.3.2 Repr¨
asentationen und Suchraum
Die Wahl der passenden Repr¨
asentation bestimmt wesentlich die Effizienz
und Komplexit¨
at eines evolution¨
aren Algorithmus; ein Problem kann ver-
einfacht werden, indem man die Repr¨
asentation der L¨
osungen ¨
andert (Deb,
1997a, S. C1.1.1).
Die Menge aller m¨
oglichen L¨
osungen eines Suchproblems wird als Such-
raum bezeichnet: Jede Position in diesem Suchraum stellt eine m¨
ogliche
osung dar, den Prozess des Suchens kann man sich dementsprechend als
das Navigieren im Suchraum vorstellen (Corne und Bentley, 2001b, S. 4).
14

2.3. EIN EINFACHER EVOLUTION ¨
ARER ALGORITHMUS
Bei evolution¨
aren Algorithmen existiert neben dem Suchraum der enko-
dierten L¨
osungen, der Genotypen, auch der L¨
osungsraum tats¨
achlicher L¨
o-
sungen, der Ph¨
anotypen (Corne und Bentley, 2001b, S. 11).
Ein G¨
utekriterium f¨
ur die Art der Repr¨
asentation ist starke Kausalit¨
at,
das bedeutet, dass sich bei einer kleinen ¨
Anderung des Genotyps auch der
Ph¨
anotyp nur geringf¨
ahig ¨
andert. Benutzt man zur Repr¨
asentation eine
einfache Bin¨
arkodierung ist starke Kausalit¨
at jedoch nicht gegeben: Mu-
tiert man beispielsweise den Bitstring
0000001
durch ¨
Andern eines Bits zu
1000001
findet im Genotyp nur eine kleine ¨
Anderung statt; der Genotyp
¨
andert sich jedoch von
1
zu
65
. Dies wird als Hamming-Klippe bezeichnet
7
.
Hamming-Klippen
"
zerkl¨
uften" den Suchraum und erschweren die Optimie-
rung. (Weicker, 2002, S. 56)
Die L¨
osung zur Vermeidung bzw. Eind¨
ammung von Hamming-Klippen ist
eine alternative Kodierung, bei der benachbarte Werte idealerweise jeweils
nur eine Hamming-Distanz von 1 besitzen, beispielsweise die Gray-Kodierung.
Die h¨
aufigsten Repr¨
asentationsarten sind bin¨
are Strings und reellwertige
Vektoren. Um Permutationen zu beschreiben wird oft eine Integer-Liste
gew¨
ahlt, beim Genetischen Programmieren sind
Syntaxb¨aume als Re-
pr¨
asentation ¨
ublich.
2.3.3 Exploration, Exploitation und lokale Optima
Ein Vorteil evolution¨
arer Algorithmen gegen¨
uber konventionellen Suchme-
thoden wie beispielsweise
Hill-Climbing (Weicker, 2002, S. 53) besteht
darin, dass das Risiko in lokalen Optima steckenzubleiben bei evolution¨
a-
ren Algorithmen geringer ist
8
(Sivanandam und Deepa, 2010, S. 34).
Bei der Suche mit evolution¨
aren Algorithmen besteht ein Spannungsver-
altnis zwischen der Exploration und der Exploitation des Suchraums. Ex-
ploration beschreibt die Suche nach neuen L¨
osungen, bei der neue Bereiche
des Suchraums erforscht werden. Bei der Exploitation hingegen wird ein
kleinerer Bereich des Suchraums gr¨
undlich abgesucht und gefundene L¨
o-
sungen weiterentwickelt und verfeinert. (Michell, 1998, S. 88)
Idealerweise soll eine Balance zwischen beiden gefunden werden. Dies ist
beispielsweise Aufgabe der Selektionsmethode und der Suchoperatoren Mu-
tation und Crossover (Michell, 1998, S. 124) (Hancock, 1997, C2.8.2). Ver-
ugt der Algorithmus ¨
uber einen Mutationsoperator mit variabler Schritt-
weite, kann dar¨
uber gesteuert werden, ob die Suche zu einem gegebenen
7
Die Hamming-Distanz zweier Strings mit fester L¨
ange ist die Anzahl unterschiedlicher
Stellen. Eine Hamming-Klippe ist dementsprechend jede Hamming-Distanz gr¨
oßer 1.
8
Gen¨
ugend Diversit¨
at und eine ausreichend große Population vorausgesetzt; Populatio-
nen mit geringer Diversit¨
at hingegen neigen dazu zu lokalen Optima zu konvergieren.
(Sivanandam und Deepa, 2010, S. 56)
15

2.4. ARTEN EVOLUTION ¨
ARER ALGORITHMEN
Zeitpunkt eher explorativ (große Schrittweite) oder exploitative (kleine Schritt-
weite) vorgeht.
Exploration und Exploitation k¨
onnen nicht klar von einander abgegrenzt
werden (Crepinsek et al., 2013, A:4); auch wenn in der Literatur traditio-
nell Mutation als explorativ und Crossover als eher exploitative beschrieben
wurden, ist dies nicht zwingend der Fall, sondern h¨
angt vielmehr von der
Implementierung der Operatoren, der Wahl der Parameter und der Selek-
tionsmethode ab (Crepinsek et al., 2013, A:4). Einen guten ¨
Uberblick ¨
uber
das Thema bieten Crepinsek et al. (2013).
2.4 Arten Evolution¨
arer Algorithmen
Man unterscheidet zwischen vier historischen Paradigmen die im Folgen-
den vorgestellt werden: Hollands Genetische Algorithmen, das genetische
Programmieren von Koza, Rechenbergs Evolutionsstrategien und Evolutio-
ares Programmieren.
2.4.1 Genetische Algorithmen (GAs)
1975 beschrieb John Holland in
"
Adaptation in Natural and Artificial Sys-
tems" (Holland, 1992) die Anwendung der Evolution auf Optimierungs-
probleme und entwickelte den bis heute bekanntesten evolution¨
aren Algo-
rithmus
9
(Sivanandam und Deepa, 2010, S. 15) (B¨
ack, 1996, S. 106), der
gewissermaßen die kanonische Grundform evolution¨
arer Algorithmen bil-
det. In seinem Buch versuchte Holland einerseits das Verst¨
andnis nat¨
urli-
cher Adaptionsprozesse zu verstehen und andererseits k¨
unstliche Systeme
zu entwerfen, die ¨
ahnlich diesen nat¨
urlichen Vorbildern funktionierten (Si-
vanandam und Deepa, 2010, S. 23).
Genetische Algorithmen zeichnen sich dadurch aus, dass sie den Crossover-
Operator als prim¨
aren Operator benutzen und Mutationen nur mit sehr ge-
ringer Wahrscheinlichkeit auftreten (Michell, 1998, S. 129). Ausserdem wer-
den Eltern f¨
ur gew¨
ohnlich probalistisch selektiert, wobei die Wahrschein-
lichkeit der Selektion proportional zur Fitness der Individuen ist. Meist wird
eine bin¨
are Repr¨
asentation benutzt (Fogel, 1997a, B1.1:1).
10
Damit ¨
ahneln
genetische Algorithmen der nat¨
urlichen Evolution mehr als die meisten an-
deren Methoden (Bentley, 1999a, S. 8).
9
Der urspr¨
unglich von Holland verwendete Name war reproductive plan oder genetic
plan (Holland, 1992, S. 89).
10
Viele sp¨
atere Implementierungen haben diese urspr¨
unglich Charakteristik von Hol-
lands Algorithmus abgewandelt und benutzen alternative Repr¨
asentationen und eine
andere Selektionsmethode. Sie alle benutzen aber Crossover als prim¨
aren Operator.
(Eshelman, 1997, B1.2:1)
16

2.4. ARTEN EVOLUTION ¨
ARER ALGORITHMEN
Hollands Schema-Theorem
Hollands sogenanntes Schema-Theorem ist eine Theorie, die versucht, die
achtigkeit genetischer Algorithmen zu erkl¨
aren mittel sogenannter Sche-
mata zu erkl¨
aren: Ein Schema ist ein Bitmuster, das eine Menge von Strings
beschreibt, deren Zeichen an bestimmten Positionen ¨
ubereinstimmen. Der
Platzhalter
*
markiert eine Stelle im Schema an der ein beliebiges Zei-
chen stehen kann. F¨
ur bin¨
are Strings der L¨
ange 4 beispielsweise beschreibt
das Schema
0**1
die Menge
{0001, 0011, 0101, 0111}. Die Ordnung ei-
nes Schemas ist die Anzahl festgelegter Zeichen (im Beispiel: 2). Hollands
Schema-Theorem besagt, dass die Reproduktion in einem genetischen Al-
gorithmus daf¨
ur sorgt, dass sich Schemata kurzer L¨
ange, niedriger Ordnung
und hoher Fitness in einer Population anreichern. Diese Schemata werden
auch als Building Blocks bezeichnet.
Bewertung und Anwendung
Ein Vorteil von genetischen Algorithmen ist, dass sie robust und relativ feh-
lertolerant sind; auch suboptimal implementiert oder schlecht angewandt
liefern sie h¨
aufig noch akzeptable Ergebnisse (Bentley, 1999a, S. 8). Da-
durch, dass die Suche nach einer optimalen L¨
osung quasi parallel ausge-
uhrt wird (implicit parallelism, (Sivanandam und Deepa, 2010, S. 66)) und
eine Population mehrere m¨
ogliche L¨
osungen enth¨
alt, bleiben genetische Al-
gorithmen weniger leicht in lokalen Optima stecken (Bentley, 1999a, S. 10)
(Holland, 1992, S. 140).
Die Repr¨
asentation als Bitstring fester L¨
ange wird h¨
aufig als unnat¨
urlich
und unn¨
otig einschr¨
ankend kritisiert; sie limitiert die Anzahl m¨
oglicher L¨
o-
sungen von vornherein (Koza, 1992, S. 63). Ausserdem muss zwischen Ge-
notyp (= Bitstring) und Ph¨
anotyp ein Mapping vorgenommen werden
11
.
Die Optimierung findet also nicht im Zielraum statt, sondern in einem se-
paraten Suchraum. Die deswegen n¨
otige Genotyp-Ph¨
anotyp-Konvertierung
wurde lange als eher l¨
astiger Nebeneffekt angesehen; sie kann aber auch als
Vorteil genutzt werden, beispielsweise wenn Genotypen verwendet werden,
die weniger Parameter haben als ihre entsprechenden Ph¨
anotypen; so kann
der Suchraum reduziert werden (Bentley, 1999a, S. 29).
Interessanterweise konnte viel von dem, was Holland Mitte der 1970er theo-
retisch bewies zu dieser Zeit experimentell (noch) nicht beobachtet werden,
weil die n¨
otige Rechenleistung fehlte; die ersten Experimente benutzten
sehr kleine Populationen (Kenneth De Jong und Schwefel, 1997, A2.3:4).
11
Im einfachsten Fall besteht diese in der Konvertierung eines Bitstrings in eine Zahl.
17

2.4. ARTEN EVOLUTION ¨
ARER ALGORITHMEN
max
+
+
x
x
x
*
3
y
Abbildung 2.4: Beispiel f¨
ur einen Syntaxbaum. Die hier dargestellte Funktion ist
max(x + x, x + 3 y), nach (Poli et al., 2008, S. 10).
2.4.2 Genetisches Programmieren (GP)
How can computers learn to solve problems without being explicitly program-
med? In other words, how can computers be made to do what is needed to
be done, without being told exactly how to do it? (Koza, 1992, S. 1) ­ Oder
anders gesagt: K¨
onnen Computer sich selbst programmieren? Diese Frage
versucht John Koza mit genetischem Programmieren zu beantworten.
Das Ziel von Genetischem Programmieren ist, evolution¨
ar einen Algorith-
mus zu entwerfen, welcher in der Lage ist ein gegebenes Problem zu l¨
osen.
Als Repr¨
asentation wird ¨
ublicherweise ein Syntaxbaum variabler Gr¨
oße und
Form gew¨
ahlt
12
(Poli et al., 2008, S. 9). Die Bl¨
atter dieses Baums sind Va-
riablen oder Konstanten, die inneren Knoten sind Funktionen. Der Baum
in seiner Gesamtheit ist eine evaluierbare Funktion. Abbildung 2.4 zeigt ein
Beispiel eines solchen Syntaxbaums.
Der h¨
aufigste Rekombinationsoperator bei GP ist das sogenannte Subtree
Crossover, bei dem ein Teilbaum zwischen zwei Eltern getauscht wird (Si-
vanandam und Deepa, 2010, S. 3). Voraussetzung daf¨
ur, dass der entstan-
dene Baum weiterhin eine korrekt evaluierbare Funktion bleibt, ist, dass
alle Funktionen des Baums jeden m¨
oglichen R¨
uckgabewert jeder Funktion
und jeden Wert des Baums als Argument akzeptieren
13
(Closure Principle,
(Koza, 1992, S. 81), (Poli et al., 2008, S. 21)).
12
Alternative Repr¨
asentationen sind lineare oder graph-basierte GP-Programme, siehe
(Poli et al., 2008, S. 61ff) und (Poli et al., 2008, S. 65)
13
Effektiv bedeutet das meist, dass die R¨
uckgabewerte aller Funktionen und alle Werte
den gleichen Datentyp haben.
18

2.4. ARTEN EVOLUTION ¨
ARER ALGORITHMEN
In seiner urspr¨
unglichen Implementierung verzichtete Koza vollst¨
andig auf
Mutation, und benutzte stattdessen eine sehr große Anfangspopulation
(Angeline, 1997, C3.2.5); er wollte zeigen, dass Mutation f¨
ur GP nicht zwin-
gend n¨
otig ist (Poli et al., 2008, S. 42); tats¨
achlich wird Mutation bei GP
nur mit sehr geringer Wahrscheinlichkeit angewandt (Koza et al., 2001,
S. 280); es existiert jedoch eine große Anzahl an Mutationsoperatoren (Poli
et al., 2008, siehe S. 42). Bei der Subtree Mutation beispielsweise wird ein
Teilbaum durch einen zuf¨
allig erzeugten Teilbaum ersetzt (Poli et al., 2008,
S. 16). Ausserdem existieren weitere Operatoren, beispielsweise Kapselung
(encapsulation), bei der ein Teilbaum in einen einzelnen Knoten konvertiert
wird und so .
Kozas Algorithmus (nach (Michell, 1998, S. 28ff)):
1. W¨
ahle eine Menge Funktionen und Werten aus. Diese Auswahl muss
zuf¨
allig oder von einem Benutzer vorgenommen werden.
14
2. Erzeuge eine Startpopulation zuf¨
allig zusammengestellter Program-
me. Diese m¨
ussen syntaktisch korrekt sein.
3. Berechne die Fitness jedes Programms, indem mit Hilfe einer Reihe
von fitness cases die Abweichung des Ergebnis' vom korrekten Ergeb-
nis bestimmt wird.
4. Selektiere und rekombiniere Programme.
Bewertung und Anwendung
Poli et al. (2008) nennt folgende Szenarien und folgende Bedingungen unter
denen genetisches Programmieren besonders erfolgreich ist:
­ beim Erforschen bisher kaum verstandener Bereiche (Poli et al., 2008,
S. 111)
­ wo konventionelle mathematische Analysen nicht zu L¨
osungen f¨
uhren
(Poli et al., 2008, S. 112)
­ wenn eine ann¨
ahernde L¨
osung ausreichend ist (Poli et al., 2008, S. 113)
­ wo eine große Menge von Testdaten vorhanden ist.
14
ur gew¨
ohnlich werden GP-Programme nicht in den gleichen Sprachen erzeugt, die von
Menschen benutzt werden um Software zu entwickeln, sondern in Sprachen mit be-
grenzterem, oft dom¨
anenspezifischem Vokabular. Mit der Auswahl zu verwendender
Funktionen und Terminalsymbole definiert der Benutzer gewissermaßen eine solche
Sprache. (Poli et al., 2008, S. 19) Koza selbst verwendete Lisp, unter anderem deswe-
gen, weil Funktionen und Programme in Lisp in der gleichen Form vorliegen und weil
ein Lisp-Programm effektiv sein eigener Parsetree ist.
19

2.4. ARTEN EVOLUTION ¨
ARER ALGORITHMEN
GP wird gerne als Invention Machine bezeichnet (Poli et al., 2008, S. 121),
weil es ungew¨
ohnliche L¨
osungsvorschl¨
age entwickeln und unerwartete Be-
ziehungen aufzeigen kann. Beispiel daf¨
ur ist die bereits in der Einleitung
erw¨
ahnte von der NASA entwickelte Antenne, deren organisch-anmutende
Struktur ein menschlicher Designer vermutlich nicht entworfen h¨
atte (Lohn
et al., 2005, S. 12). Mit Hilfe von GP wurden erfolgreich bereits von Men-
schen entwickelte Innovationen dupliziert, aber auch patentierbare neue
Funktionen entwickelt. Ein Beispiel hierf¨
ur ist der Entwurf einer analogen
Schaltung f¨
ur einen Tiefpass-Filter (Woolf und Thompson, 2001, S. 238ff).
Weitere Anwendungsbeispiele finden sich im Bereich der Bild- und Signal-
verarbeitung (Poli et al., 2008, S. 121ff), bei finanziellen Vorhersagen (Poli
et al., 2008, S. 123) und in der industriellen Prozesskontrolle (Poli et al.,
2008, S. 124).
2.4.3 Evolutionsstrategien (ES)
1963 h¨
ort der Flugzeugbau-Student Ingo Rechenberg einen Vortrag ¨
uber
Evolution, der ihn zu einem Versuch inspiriert: Mit W¨
urfel, Zirkel und Li-
neal spielt er das Evolutionsmodell auf Papier nach, indem er ein regul¨
ares
Sechseck entwickelt. Ein Jahr sp¨
ater f¨
uhrt er auf einer Tagung ein Ex-
periment vor, bei dem sich eine zur Zickzackform gefaltete Gelenkplatte
evolution¨
ar zur Form des geringsten Widerstands ­ der Ebene ­ entwickelt
(Rechenberg, o.J.). Das evolution¨
are Verfahren, das er verwendet und ge-
meinsam mit Peter Bienert und Hans-Paul Schwefel weiterentwickelt, wird
als Evolutionsstrategie bekannt; die ersten Anwendungen haben alle ge-
meinsam, dass daf¨
ur physikalische Entw¨
urfe benutzt werden, die durch ma-
nuelle Ver¨
anderung ­ beim Beispiel der Gelenkplatte beispielsweise die der
Gelenkpositionen ­ mutiert und anschließend getestet werden.
Die einfachste Variante der Evolutionsstrategie ist dementsprechend ist ein
evolution¨
arer Algorithmus mit einer Populationsgr¨
oße von 1: Ein Indivi-
duum wird zuf¨
allig erzeugt; durch Mutation dieses Individuums entsteht
ein Nachkomme. Der Nachkomme wird evaluiert: Ist seine Fitness gr¨
oßer
als die des Elternindividuums, wird letzteres verworfen; im anderen Fall
wird der Nachkomme verworfen und das Elternindividuum bleibt vorhan-
den. Eine solche Evolutionsstrategie wird (1+1)-ES bezeichnet, wobei die
erste 1 die Anzahl der Elternindividuen angibt und die zweite 1 die Anzahl
der Nachkommen. Hierbei ist der einzige Suchoperator die Mutation; eine
Rekombination findet nicht statt.
Die Evolutionsstrategie benutzt typischerweise eine nat¨
urliche Repr¨
asenta-
tion in Form eines reellwertigen Vektors, so dass Ph¨
anotyp und Genotyp
identisch sind und keine Kodierung stattfindet. (Weicker, 2002, S. 134) Mu-
tation findet durch Addition einer normalverteilten Zufallszahl statt.
20

2.4. ARTEN EVOLUTION ¨
ARER ALGORITHMEN
Abbildung 2.5: Beispiele f¨
ur Anwendung einer Evolutionsstrategie: Entwicklung ei-
ner ¨
Uberschalld¨
use. Die mathematische Berechnung der g¨
unstigsten
usenform war nicht m¨
oglich, also entwickelte Hans-Paul Schwefel
einen Versuchsbau, mit dem durch Segmente mit unterschiedlichen
konischen Innenbohrungen eine große Anzahl unterschiedlicher D¨
u-
senformen erprobt werden konnten.
Quelle: (Rechenberg, 1973, S. 34-35).
21

2.4. ARTEN EVOLUTION ¨
ARER ALGORITHMEN
In den fr¨
uhen 1980ern wurde eine erweiterte Version der Evolutionsstra-
tegien entwickelt: (, )-ES und (+)-ES, wobei wie gehabt f¨ur die
Anzahl Elternindividuen und f¨ur die Anzahl Nachkommen steht; bei der
sogenannten Plus-Strategie wird die Nachfolgepopulation aus der Verei-
nigung von Eltern und Nachkommen gebildet, bei der Komma-Strategie
(auch Truncation Selection genannt (Hancock, 1997, C2.8:4)) hingegen be-
steht die Nachfolgepopulation nur aus Nachkommen. Als vorteilhaft hat
sich ein Verh¨
altnis von Eltern zu Nachkommen zwischen
1
7
und
1
5
erwiesen
(Weicker, 2002, S. 134).
Die Elternindividuen werden zuf¨
allig ausgew¨
ahlt; eine Fitnessselektion fin-
det erst bei der Auswahl der ¨
uberlebenden Individuen statt.
Eine Besonderheit der erweiterten Evolutionsstrategie ist ihre Selbstadap-
tion: Ein Individuum besteht aus der Objektkomponente, die die L¨
osung
enth¨
alt, und der Strategiekomponente, die die Parameter enth¨
alt, die die
Gr¨
oße der ¨
Anderungen bestimmt, die bei einer Mutation auf die Objekt-
komponente angewandt werden (Corne und Bentley, 2001b, S. 22). F¨
ur
die einfachste Version einer selbstadaptiven Evolutionsstrategie besteht die
Strategiekomponente in der Schrittweite, die der Algorithmus bei der Muta-
tion benutzt. In regelm¨
aßigen Abst¨
anden wird das ¨
Uberlebensverh¨
altnis von
Eltern und Nachkommen ¨
uberpr¨
uft: Wird die Fitness der Nachkommen un-
proportional hoch, dann kann davon ausgegangen werden, dass die Distanz
zum Optimum zu groß ist; die Schrittweite wird dementsprechend erh¨
oht.
Falls ein Elternindividuum besonders lange ¨
uberlebt, wird die Schrittweite
hingegen erniedrigt.
2.4.4 Bewertung und Anwendungen
Evolutionsstrategien werden h¨
aufig in simulator-basierten industriellen Ent-
wurfsproblemen eingesetzt (B¨
ack und Emmerich, 2002, S. 2,3). Ihre St¨
arke
ist die Selbstadaption ihrer Suchoperatoren, eine ihrer Schw¨
ache ist (wie
auch bei anderen EAs) die ben¨
otigte Rechenzeit, die aber durch den im-
pliziten Parallelismus der Suche, Nutzung von mehreren Prozessoren oder
durch die Verwendung von weniger genauen Modellen abgeschw¨
acht werden
kann (B¨
ack und Emmerich, 2002, S. 3). Eine neuere Entwicklung, die dieses
Problem l¨
osen will, sind sogenannte Meta-Modelle: Wenn die Auswertung
der Fitnessfunktion einer ES sehr rechenaufw¨
andig ist, kann ihre Perform-
anz deutlich erh¨
oht werden, indem aus den bereits bewerteten L¨
osungen im
Suchraum eine ungenaue, vorl¨
aufige Bewertung f¨
ur neue L¨
osungen interpo-
liert wird (B¨
ack und Emmerich, 2002, S. 6).
Beispiele f¨
ur Anwendungen sind die Optimierung der Kontrollparameter
beim Gießen von Turbinenfl¨
ugeln unter Verwendung erw¨
ahnter Metamo-
delle (Jakumeit und Emmerich, 2004) und die Optimierung vom Entwurf
mehrfachverg¨
uteter Antireflexbeschichtungen (B¨
ack und Sch¨
utz, 1995).
22

Details

Seiten
Erscheinungsform
Originalausgabe
Jahr
2013
ISBN (eBook)
9783842815452
Dateigröße
13.6 MB
Sprache
Deutsch
Institution / Hochschule
Fachhochschule Dortmund – Informatik
Erscheinungsdatum
2014 (April)
Note
1,0

Autor

  • Rin Räuber (Autor:in)

Zurück

Titel: Artificial Art: Erzeugung künstlicher Bilder mit evolutionären Algorithmen in Javascript
book preview page numper 1
book preview page numper 2
book preview page numper 3
book preview page numper 4
book preview page numper 5
book preview page numper 6
book preview page numper 7
book preview page numper 8
book preview page numper 9
book preview page numper 10
book preview page numper 11
book preview page numper 12
book preview page numper 13
book preview page numper 14
book preview page numper 15
book preview page numper 16
book preview page numper 17
book preview page numper 18
book preview page numper 19
book preview page numper 20
book preview page numper 21
book preview page numper 22
book preview page numper 23
book preview page numper 24
book preview page numper 25
book preview page numper 26
126 Seiten
Cookie-Einstellungen