Untersuchung von Seeding-Mechanismen und der Entstehung von Building Blocks, um die Effizienz des GeLog-System zu verbessern

Student:Tim Fühner
Title:Untersuchung von Seeding-Mechanismen und der Entstehung von Building Blocks, um die Effizienz des GeLog-System zu verbessern
Type:diploma thesis
Advisors:Kókai, G.; Schneider, H.
State:submitted on January 16, 2002
Prerequisits:

Das Ziel des GeLog-System ist, die Vorteile der Methoden der genetischen Algorithmen und induktiv logischen Programmierung zu nutzen. Dieses System ist auch bei umfangreichen Problemstellungen noch effizient einsetzbar und lässt sich sehr leicht auf das Erlernen von Zusammenhängen aus verschiedenen Aufgabenbereichen anpassen.
Mit dem automatischen Lernsystem Gelog können logische Programme erzeugt werden, die eine Lösung für eine gegebene Aufgabe darstellen. Die erlernten Programme liegen anschließend als Quelltext in der logischen Programmiersprache PROLOG vor und sind in dieser Form direkt ausführbar.
Zur Formulierung der Aufgabenstellung werden aus der induktiv logischen Programmierung bekannte Komponenten verwendet. Anhand von Beispieldaten erlernt das System dielogischen Zusammenhänge und formuliert diese mit Hilfe von Bausteinen aus dem Hintergrundwissen als PROLOG-Programm.
Der eigentliche Lernvorgang basiert auf einem genetischen Algorithmus. Zu Beginn wird aus Elementen des Hintergrundwissens zufällig eine Menge von Programmen erzeugt, die eine sogenannte Population von Individuen bildet. Diese Individuen durchlaufen einen wiederkehrenden Evolutionszyklus, in dem Generation für Generation das Erbgut der Individuen weitergegeben, kombiniert und mutiert wird.
Dabei wird der Lernfortschritt eines einzelnen Individuums mit Hilfe der Beispieldaten ermittelt und bestimmt die Eignung des Individuums. Daraus leitet sich die Wahrscheinlichkeit ab, mit der die Erbinformation eines Individuums in die nächste Generation weitergegeben wird.
Um ein Programm an das Beispielwissen anzupassen, haben die Operatoren zur Rekombination und Mutation die gleichen Auswirkungen auf die Erbinformation wie die Generalisierungs- und Spezialisierungsmethoden der induktiv logischen Programmierung.
Genetische Algorithmen sind in der Lage auch große Ergebnisräume auf effiziente Weise zu durchsuchen und die darin enthaltenen vielversprechenden Regionen ausfindig zu machen. Dies ist ein entscheidender Vorteil für die Bearbeitung umfangreicher und komplexer Problemstellungen.
Die aus der induktiv logischen Programmierung stammenden Elemente Hintergrundwissen und Beispieldaten erlauben dabei eine einfache und flexible Anpassung des genetischen Algorithmus an die jeweilige Aufgabenstellung, ohne dass Eingriffe in das System selbst nötig sind.
Durch eine universelle Datenrepräsentation und die vielseitigen Möglichkeiten den Evolutionsverlauf durch Parameter zu beeinflussen, kann eine Vielzahl verschiedener Problemstellungen bearbeitet werden.

Topic:

GeLog benutzt eine Konfigurationsdatei, um wichtige Parameter des Evolutionsablaufs zu definieren, es können die selben für jede Population sei, aber bei unterschiedlichen Konfigurationsfiles können die Evolutionsparameter und die Menge der darin enthaltenen Grundbausteine je Population verändert werden. Durch eine solche Vorgehensweise kann der als Seeding bezeichnetet Mechanismus erzielt werden.
Sind bereits vor dem Evolutionslauf Teile des Suchgebietes bekannt, die einen grösseren Erfolg der Suche versprechen, gestatten Seedingmechanismen die Erzeugung von Individuen in eben diesen Regionen.
Durch die Verwendung erfolgversprechender Basisliterale und die Angabe einer Einbauwahrscheinlichkeit zu jedem der Grundbausteine aus dem Hintergrundwissen kann der Benutzer das Seeding beeinflussen.
Die erste Aufgabe der Bearbeiter ist:

  • Suche nach in der Literatur vorhandenen Seeding-Mechanismen
  • Implementierung eines Seeding für GeLog
  • Ausarbeitung von Methoden, um die möglichst optimale Einbauwahrscheinlichkeit und die zu der Lösung notwendige Menge von Basisliteralen festzustellen.

Die zweite Aufgabe ist die Erkennung von Building Blocks Als Building Blocks werden Konstrukte bezeichnet, die immer wieder im Laufe der Evolution in verschiedenen Individuen entstehen und sich positiv auf die Fitness auswirken. Ein zu erstellender Mechanismus müsste in der Lage sein, diese Strukturen im Prolog-Programm zu erkennen, sie zu extrahieren und in das Grundwissen einzutragen. Auf diese Weise könnten sie durch die Operatoren in andere Individuen eingebaut werden.

watermark seal