Software-Projekt SW02

- N a v i g a t i o n - - - - - - - -

Heuristic Induction of Machine Code - Compiling Heuristic Programming

- - - - - - - - - - - - - - - - - - - -

- - - - - - - -

Genetic Programming

Compiling Genetic Programming ist eine spezielle Form des Genetic Programming, bei dem Individuen aus Binärstrings bestehen, die direkt von einer Registermaschine verarbeitet werden können. Dies hat zur Folge, dass diese Vorgehensweise im Vergleich zu einem GP-System auf der Basis interpretierter Lisp-Strukturen bis zu 1000 fach schneller arbeitet. Dieser Ansatz wurde von Peter Nordin eingeführt, der verallgemeinert werden kann, indem die evolutionären Verfahren zur Erzeugung von Varianz, d.h. die Erzeugung von Nachkommen durch Rekombination und Mutation, durch andere Heuristiken ersetzt werden. Beispielsweise kann das Umschalten von einem populationsbasierten Verfahren auf ein sequentielles Verfahren mit einem Lösungsvorschlag pro Iteration zum Ende eines Suchlaufes sinnvoll werden. Diese Argumentation geht davon aus, dass evolutionäre Verfahren durch die Verwendung einer diversiven Population gut in der Lage ist, eine Region mit einem Optimum zu bestimmen, dass der Aufwand der genauen Lokalisation des Optimums innerhalb dieser Region durch die Unterhaltung einer Population dann grösser wird, als bei einem nicht populationsbasierten Verfahren.

Automatic Induction of Machine Code

Prinzipiell kommen alle Heuristiken in Frage, die im Rahmen der kombinatorischen Optimierung eingesetzt werden können, da ein Programm hier als Sequenz von Maschinenbefehlen aus einem begrenzten Befehlssatz betrachtet wird, dem ein Fitnesswert zugeordnet wird. Naheliegend sind beispielsweise Verfahren aus der Klasse des Threshold-Accepting (TA), zu dem auch das Simulated Annealing (SA) gezählt wird. Das kommerzielle Programm Automatic Induction of Machine Colde (AIMC), kann neben der genetischen Heuristik auch SA zur Erzeugung von Binärstrings verwenden, die als Sequenz von Maschinenbefehlen interpretiert wird.

Tabu-Search, PIPE, EP, ES von Machine Code

Daneben sind auch Verfahren aus der Klasse des Tabu-Search (TS) oder Probabilistic Incremental Program Evolution (PIPE) von Interesse, aber auch andere Evolutions-Heuristiken neben dem Genetic-Programming, wie z.B. die Anpassung des Evolutionary Programming (EP) auf die Erzeugung von Programmen durch K. Chellapilla. Die Eignung von EP für die Programmerzeugung deutet darauf hin, dass eine Programmerzeugung mit Hilfe von Evolutions-Strategien (ES) ebenfalls durchführbar ist, wobei von besonderem Interesse die selbst-adaptiven Schrittweitenvektoren als eine Form von Bewegungsmodell in dem betrachteten Suchraum sind. Durch die Einführung von solchen Modellen, und ihre taskübergreifende Nutzung würde eine neue Klasse von Verfahren zur Programmerzeugung definiert, ebenso wie durch die Verwendung von Fitness-Approximationsmodellen, mit denen eine teilweise Substitution der aufwendigen Programmevaluationen ermöglicht wird. Eine ausführliche Darstellung von Fitness-Approximationsmodellen im Kontext der ES findet sich in Bachelier (1999d).

Culture Algorithms

Weiterhin sind die Einbeziehung von Culture Algorithms durch Dr. Robert Reynolds als hybride Lernsysteme relevant für dieses Projekt.

Reactive Search

Eine weitere Klasse von Metastrategien sind reaktive Suchverfahren (Reactive Search), die vergangene Ereignisse innerhalb eines Suchlaufes oder vergangene Suchläufe innerhalb einer Problemdomaine analysieren und verwenden, um die weitere Suche effizienter und effektiver zu gestalten wie z.B. die Reactive-Tabu-Search. Zu beachten ist, dass ES mit ihren selbstadaptiven Schrittweitenvektoren bereits ein Vertreter reaktiver Suchverfahren ist.

Bezug zu anderen Projekten

Dieses Software-Projekt kann als eine Spezialisierung des Internet-basierten EA-Systems (Software-Projekt SW01) betrachtet werden, da mit den Binärstrings, die durch Constraints zusätzlich eingeschränkt sind, eine spezielle Datenstruktur betrachtet wird. Die dort geforderte möglichst grosse Flexibilität, die eine Vielzahl von Verfahren zur kombinatorischen Optimierung erlaubt, kann bei dieser Spezialisierung direkt genutzt werden.

Sub-machine-code GP

Neben der Verwendung von Binärstrings, die eine Sequenz von Maschinenbefehlen kodieren, existiert mit dem Sub-machine-code GP (SMC-GP) von R. Poli eine weitere Form der direkten Nutzung der Registerstruktur von von-Neumann-Architekturen, indem ein Register in eine Anzahl disjunkter Teilregister zerlegt wird. Ein 64 bit-Register kann beispielsweise in 8 mal 8 bit-Register zerlegt werden, wobei diese 8 Register unabhängig und parallel an der Evaluation von Individuen beteiligt werden können, wobei die Individuen entsprechend durch Fix-Punkt-Repräsentationen kodiert sein müssen.

Die Darstellungen in Poli (1999) beziehen sich auf Nicht-Compiling-GP, doch eine Anpassung an CGP lässt sich leicht durchführen, indem beispielsweise 8 bit-Repräsentationen von Daten und Befehlen verwendet werden, anstatt 32 bit-Repräsentation wie in den Arbeiten von Nordin, welche die SPARC-Architektur verwenden. Dies ist insbesondere dann sinnvoll, wenn ein minimaler Basis-Befehlssatz der notwendigsten arithmetischen und logischen Operationen verwendet wird.

Ein Teilprojekt sollte sich mit der Effizienzsteigerung der entwickelten CGP/CHP-Verfahren beschäftigen, indem zunächst ein minimaler Basis-Befehlssatz verwendet wird, der Individuen als Binärstrings, d.h. als Sequenz von Maschinenbefehlen auf diesem eingeschränkten Befehlssatz definiert. Die Individuen werden auf den unabhängigen Teilregistern reproduziert und evaluiert, sodass SMC-GP/HP-Verfahren entstehen.

- - - - - - - -

Referenzen

Chellapilla, K.: Evolutionary Programming with tree mutations: evolving computer programs without crossover. In: Genetic Programming 1997: Proc. of the Second Annual Conference on Genetic Programming. S. 431-438, CA, Morgan Kaufmann.

Dueck, G.; Scheuer, T.: Threshold Accepting: A General Purpose Optimization Algorithm Superior to Simulated Annealing. In: Journal of Computational Physics, 90, S. 161 - 175, 1990.

Dueck, G.: New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-Record Travel. Technical report, IBM Germany, Heidelberg Scientific Center, 1990.

Glover, Fred; Laguna, Manuel: Tabu Search. 1997.

Nordin, Peter: Evolutionary Program Induction of Binary Machine Code and its Applications. Münster, 1997.

Osman, I.H.; Kelly, J.P. (eds.): Meta-Heuristics. Kluver, 1996.

Poli, Riccardo: Sub-machine-code GP. In: Poli et al. (1999), S. 65 - 82.

Poli, R.; Nordin, P.; Langdon, W.B.; Fogarty, T.C. (eds.): Genetic Programming, Second European Workshop, EuroGP'99. Springer Verlag, LNCS 1598, S. 65 - 82, 1999.

Salustowicz, R.P. ; Schmidhuber, J.: Probabilistic Incremental Program Evolution (PIPE). In: Evolutionary Computation, 5(2), S. 123 - 141.

Zum Seitenanfang

Dokument zuletzt geändert am 05.12.1999