Information Technology Reference
In-Depth Information
John Henry Holland (* 2. Februar 1929 in Indiana) studierte
am Massachusetts Institute of Technology (MIT) und schloss
an der University of Michigan als erster Absolvent des Faches
Informatik mit Promotion ab. Heute lehrt er dort Psychologie,
Elektrotechnik und Informatik. Sein Interesse galt der An-
wendung von Evolutionären Algorithmen in den Bereichen
der künstlichen Intelligenz, des maschinellen Lernens bzw.
der Ökonomie. Im Jahre 1975 erschien sein Buch
Adaption
in Natural and Artiicial Systems
. Aus den dortigen Theo-
rien entstand die Richtung der Genetischen Algorithmen. Als
erster gebrauchte diesen Begriff jedoch bereits
J. D. Bagley
von der University of Michigan in seiner 1967 erschienenen
Dissertation, die sich mit der Programmierung von Schach-
problemen beschäftigte.
Schon ab Mitte der 1950er-Jahre beschäftigten sich Wis-
senschaftler mit der Fragestellung, ob es möglich ist, Com-
puter zu befähigen, selbstständig Probleme zu lösen, ohne
dass sie dafür explizit programmiert werden müssen. Diese
„selbstständige Generierung“ von Programmen war allerdings
mit den damaligen technologischen Fähigkeiten der Computer
noch nicht lösbar. Der entscheidende Durchbruch gelang
John
R. Koza
(
Abb. 3.34d
)
erst Anfang der 90er-Jahre auf der Basis
evolutionärer Prinzipien. Er veröffentlichte seine Idee unter
dem Begriff „Genetic Programming“ und schuf durch seine
Arbeiten eine inzwischen eigenständige Variante der Geneti-
schen Algorithmen. Ziel der Genetischen Programmierung ist
es, anhand von Trainingsdaten automatisch ein Computerpro-
gramm zu generieren, welches eine gegebene Aufgabenstel-
lung löst. Dieses Ziel nennt man auch Programm-Instruktion.
Die Individuen sind entsprechend Repräsentanten von Com-
puterprogrammen und setzen sich daher aus Programmkom-
ponenten wie z. B. Funktionen, Variablen und Konstanten
zusammen. Prinzipiell existiert keine Einschränkung hinsicht-
lich der Wahl der Programmiersprache.
Ähnliche Ziele wie die des „Genetic Programming“ ver-
folgt das „Evolutionäre Programmieren“. Das Evolutionäre
Programmieren wurde ab dem Beginn der 60er-Jahre von
Lawrence
J. Fogel
als Optimierungsmethode für Künstliche
Intelligenz entwickelt und von seinem Sohn
David B. Fogel
ab 1990 ergänzt. Zwar existierten bereits vorher erste An-
sätze, darunter der von Friedberg 1958 verwendete, aber erst
Fogel konnte mit seiner Strategie den ersten relevanten Mei-
lenstein des Evolutionären Programmierens setzen. Neu an
Fogels Überlegungen war, dass er eine Population von endli-
chen Automaten einsetzte und diese sich nach den natürlichen
Prinzipien der Evolution weiterentwickeln ließ.
Fogels Motivation bestand darin, ein möglichst efizientes
Verfahren zur Optimierung von Algorithmen zu inden. Wäh-
rend Friedberg einen binärcodierten Algorithmus benutzte,
der sich durch Zufallsänderungen der Anweisungen der Um-
gebung anpasst, trennte sich Fogel vom heuristischen Pro-
grammieren. Verfahren, die eine Optimierung mit Neuronalen
Netzen anstrebten, fand er nicht ausreichend, da diese seiner
Meinung nach dem (beschränkten) menschlichen Denken
nachempfunden sind. Hierbei arbeitete er eng mit A. J. Owens
und M. J. Walsh zusammen. Die Individuen stellten einfache
endliche Automaten (inite-state machines) dar. Neue Indi-
viduen wurden durch zufällige Änderungen im
transition
table
erstellt. Ein Nachkomme wurde bewertet, indem ein
Vergleich der durch das Individuum erzeugten Sequenz von
Symbolen mit einer gegebenen Sequenz durchgeführt wurde.
Der Prozentsatz der Übereinstimmungen ergab die Güte. Der
Nachkomme und sein Elternteil wurden miteinander vergli-
chen und nur der bessere überlebte. Das schlechtere Indivi-
duum wurde verworfen.
Fogel, Owens und Walsh war bekannt, dass so ein Algo-
rithmus in lokalen Minima hängen bleiben kann. Deshalb ar-
beiteten sie mit einer Population von Individuen. Es wurden
genauso viele Nachkommen erstellt, wie Individuen in der
Population waren. Durch Selektion wurde die jeweils bessere
Hälfte der Eltern und Nachkommen ausgewählt und bildete
die neue Population. Obwohl Mutation als der hauptsächli-
che Operator angesehen wurde, erwähnten Fogel, Owens und
Walsh die Möglichkeit der Verwendung einer Rekombination,
die sogar zwischen mehr als zwei Eltern stattinden könne.
Die Arbeiten von Fogel, Owens und Walsh können, neben
den Arbeiten an der TU Berlin, als erste erfolgreiche Anwen-
dung Evolutionärer Algorithmen angesehen werden. Sie wur-
den aber für viele Jahre nicht beachtet bzw. abgelehnt.
Erst in den 80er-Jahren kam es wieder zu einer Belebung
des Evolutionären Programmierens. Dies ist insbesondere
ein Verdienst von David Fogel, der die über lange Zeit ig-
norierten Arbeiten seines Vaters wieder aufnahm bzw. fort-
führte. Dennoch sind die „Evolutionäre Programmierung“
und das „Genetic Programming“ diejenigen Teildisziplinen
innerhalb der Evolutionären Algorithmen, die die geringste
Verbreitung gefunden haben. Dagegen haben inzwischen
„Genetische Algorithmen“ und die „Evolutionsstrategien“
ein breites Anwendungsspektrum gefunden, wobei aller-
dings bisher vor allem Optimierungsprobleme im Vor-
dergrund stehen.
3.6
Neurocomputer
3.6.1
Erste Entwicklungen
Die ersten Ansätze, Rechner zu konstruieren, die menschliche
Denkweise nachvollziehen können, gehen bis ins 13. Jahr-
hundert zurück. Der katalanische Theologe
Raymond Lulle
(1235-1315), auch bekannt unter dem Namen
Doctor Illu-
minatus
, schlug eine spezielle Formalisierung des logischen
Schließens vor. In seinem Werk
Ars magna
, welches im
Jahre 1275 erschien, beschrieb er eine Maschine mit kon-
zentrischen Rädern. Diese Räder sollten speziell ausgesuchte
Wörter enthalten. Durch Drehen der Räder konnten aus den
