VERLAGERUNG DES SCHWERPUNKTES

Entsprechend den Überlegungen meiner Startseite verlagert sich mein Schwerpunkt zusehends von den offiziellen Lehrverastaltungen der Frankfurt University of Applied Sciences weg hin zu neuen Projekten, die ausschliesslich im INM Frankfurt verankert sind. Neben meinem bisherigen Philosophieblog PHILOSOPHIE JETZT gehören dazu die Akademie für Emergent Life (ELA), das Emerging Mind Projekt (EMP), sowie das neue Performance Format PHILOSOPHY-IN-CONCERT.

Dies hat zur Folge, dass meine theoretischen Texte im Umfeld lerndner Systeme sich jetzt vornehmlich auf das Emerging-Mind Projekt konzentrieren werden. Es ist aber nicht ausgeschlossen, dass es  (bedingt durch die Einschränkungen von CMS-Systemen) parallel zu den Webseiten von EMP doch noch LaTex-basierte Texte geben wird, die dann möglicherweise  als Skripte über uffmm zugänglich gemacht werden.

POINT OF NO RETURN: ELEMENTARWELTEN: START

ES TUT SICH WAS

1. Nachdem ich seit mindestens 25 Jahren das Thema lernende Systeme von sehr vielen Seiten her umkreise und in immer wieder neuen Ansätzen versucht habe, die Problemstellung so zu durchdringen, dass sie sowohl aus philosophischer und kognitionswissenschaftlicher Sicht ‚Sinn‘ macht, aber auch aus Sicht der Informatik und der Programmierung, kam es in den letzten Wochen zu einer Konstellation, die einen Blick in eine mögliche Zukunft erlaubt, von der man zwar nicht mit Sicherheit sagen kann, dass dies nun die ‚einzig mögliche‘ sei oder ‚die Allerbeste‘, aber doch so viel, dass sie ein Maximum von Anforderungen aus der Vergangenheit zu erfüllen scheint (wobei jede Idee, mag sie in einer Gegenwart noch so ‚gut‘ erscheinen, immer nur der Durchgangspunkt zu noch besseren Ideen ist, wenn man erst mal die aktuelle Idee ‚ernst‘ genommen hat).

2. An dieser Stelle kann – und will – ich jetzt nicht den gesamten Zusammenhang im Detail entfalten, sondern nur die wichtigsten Koordinaten andeuten, innerhalb deren das Projekt der Realisierung lernender Systeme weiter vorangetrieben werden soll.

3. Unmittelbare Auslöser in den letzten Wochen und Tagen waren zwei Dinge: (i) die rekonstruierende
Lektüre von Avicennas Abhandlung über die Logik (siehe dazu die entsprechenden Blogeinträge im Parallel-Blog von cognitiveagent.org) sowie (ii) die Experimente von VL mit der Software Unity und das gestrige lange Gespräch, über das Verhältnis einer Lerntheorie und der Realisierung in Software.

TURING GLAUBTE NOCH AN ….

4. Die Frage der Rekonstruktion und (ingenieurmäßigen) Konstruktion von lernenden Systemen kreist seit Jahren – mindestens seit Alan Matthew Turing – um die Frage, wie man es schaffen kann, in einem künstlichen lernenden System die Welt so ‚aufzubereiten‘, dass sich in diesem Sinn die Welt einerseits in ‚Objekte‘ zerlegt, andererseits in ‚Ausdrücke‘ (die natürlich in gewisser Weise auch Objekte sind), und dass aus diesen beiden Komponenten im einzelnen wie im Großen ‚Zeichengebilde entstehen, so dass die Ausdrücke ‚Bedeutungen‘ bekommen und die Bedeutungen ‚kommuniziert‘ werden können. D.h. diese sich selbst organisierenden ‚Netzwerke von Zeichen‘ müssen ‚verteilt‘ und ’synchronisiert‘ entstehen.

DER FLUCH DES FORMAL-QUANTITATIVEN

5. So herausfordernd diese Fragestellung für sich alleine schon ist, so wurde (und wird) sie durch den Gang der Wissenschaften bis heute zusätzlich dadurch erschwert, dass sich am Ende des 18.Jahrhunderts die ‚moderne formale Logik‘ mit Frege & Co. bei der Behandlung von wahrheitserhaltenden Schlussfolgerungen von der Bindung an die alltagssprachliche Bedeutung von Ausdrücken losgesagt haben. Dies führte zwar in einem gewissen Sinne zu einem riesigen Erfolg in der Entwicklung formaler Logiksysteme und zu allerlei herausragenden Beweisen, gerade auch im Bereich der Mathematik, trennte aber die moderne Logik vom alltäglichen Denken. Aktuell ist es praktisch ausgeschlossen, mit Hilfe der modernen formalen Logik irgendetwas Interessantes im Kontext des alltäglichen Denkens zu erschließen. Zwischen der modernen formalen Logik und dem alltäglichen bedeutungsdurchtränkten Denken existiert eine Kluft, wie sie tiefer nicht sein könnte.

6. Dieses Problem wird weiter verschärft dadurch, dass die moderne computergestützte Textwissenschaften sich diesem Ansatz mehr oder weniger angeschlossen haben. Sogenannte ‚quantitative‘ Ansätze in der Analyse von Texten dominieren alles. Die scheinbaren Erfolge der ‚google Algorithmen‘ beim Indizieren und Suchen oder von Statistik-Basierten Frage-Antwort Programmen a la ‚Watson‘ scheinen dem Recht zu geben. Die zunehmende Gleichsetzung von ‚Lernenden Systemen‘ mit ‚Algorithmen des maschinellen Lernens‘ tun ihr Übriges.

7. Nah besehen jedoch kann jeder, der sehen will, sehen, dass alle diese Ansätze, die mit der Ausklammerung der Bedeutungsdimension von Ausdrucksmengen (Texten) arbeiten, sich auf die Oberfläche eines Phänomens beschränken, dass ungleich tiefer und komplexer ist, als offiziell eingeräumt wird [Anmerkung: in stillen Stunden abseits des offiziellen Wissenschaftsdiskurses räumen einzelne Forscher in diesem Bereich sehr wohl ein, dass sie mit dieser rein quantitativen Ausdrucksorientierung das eigentliche Problem in keiner Weise gepackt haben. In der Öffentlichkeit des Wissenschaftsbetriebes wird aber — schon im Ansatz — eine Diskussion über die Bedeutungsdimension schlicht abgewürgt. Sie gilt als unhantierbar, unlösbar, zu komplex, stört nur die die aktuellen Paradigmen, und dergleichen mehr.]

DENKEN UND SPRACHE

8. Auf Seiten einer Realisierung in Software existiert auch ein Problem. Um einem Computer zu sagen, ‚was er tun soll‘, benötigt es ‚Befehle‘. Diese Befehle muss man in einer ‚Sprache‘ ausdrücken und hinschreiben. Aus der Geschichte des modernen Computers (seit ca. 70 Jahren) ist bekannt, dass die zur Verwendung kommenden Sprachen sich von primitiven Folgen von binären Zahlen über Hexadezimalzahlen und Akronymen hin immer mehr zu sprachlichen Ausdrücken hin entwickelt haben, die Ausdrücken der Alltagssprache ähnlich erscheinen. Neuerdings benutzt man auch immer mehr ‚diagrammgestützte‘ Sprachen, ‚visuelle Programmierung‘, die auf unterschiedliche Weise die ‚gemeinten‘ Inhalte visuell repräsentieren sollen. Faktisch gibt es zur Zeit mehr als hundert unterschiedliche Programmiersprachen mit unterschiedlicher Syntax, unterschiedlichen Ausdrucksmengen, und unterschiedlichen Konzepten. Die sogenannte ‚Objektorientierung‘ oder das ‚modellgetriebene Entwickeln‘ (meist verstanden als die Benutzung von sogenannten ‚UML-Diagrammen‘ als Hauptsprache) gehören auch in diesen Bereich.

9. Wer die Diskussionen in der (Sprach-)Philosophie über die Wechselwirkung zwischen Denken und Sprache noch im Ohr hat, der würde sich sehr wundern, wenn man sieht, wie naiv und unreflektiert in der Informatik (Programmier-)Sprachen zum Einsatz kommen, deren Einfluss auf das Denken eher als ‚destruktiv‘ bezeichnet werden muss denn als ‚konstruktiv‘. Zwar gibt es in Teilbereichen der Informatik den Trend zu mehr ‚Benutzerorientierung‘, aber hier hat man normalerweise den ‚Endbenutzer‘ im Blick, der sein Smartphone kauft, weil es ihm ‚gefällt‘, nicht aber den Softwareentwickler, der komplexe Sachverhalte in Software umsetzen soll.

10. Eine sehr verbreitete Programmiersprache ist z.B. ‚Java‘. Beim aktuellen Stand der Entwicklung (Version 8) kann jeder aber feststellen, dass sich in dieser Sprache so viele Konzepte mischen, so viele Mechanismen und Bibliotheken sich wechselseitig beeinflussen und überlagern, dass jeder, der ‚in dieser Sprache‘ denkt, für generelle theoretische Überlegungen und Strukturen praktisch verloren ist. Das Denken in einer sogenannten ‚modernen‘ Programmiersprache gleich einer Art ‚Gehirnwäsche‘, die es dem betreffenden faktisch unmöglich macht, noch in allgemeinen Konzepten zu denken (ein Paradigma wie UML ist da nur graduell besser).

11. Vor diesem Hintergrund einer Welt von Programmiersprachen, die nicht am tatsächlichen Denken orientiert sind (auch nicht das viel beschworene objektorientierte Programmierparadigma) ist es zusätzlich schwer bis unmöglich, allgemeine theoretische Sachverhalte ‚direkt‘ zu kodieren.

12. Die ‚allgemeine Lage‘ der Umsetzung von Ideen über die Welt in eine bestimmte Software ist im folgenden Schaubild kurz angedeutet.

Engineeringprozessmodell (vereinfacht) mit Konkretisierung des theoretischen Rahmens W-I-S und einer möglichen Realisierung durch SW
Engineeringprozessmodell (vereinfacht) mit Konkretisierung des theoretischen Rahmens W-I-S und einer möglichen Realisierung durch SW

ENGINEERING PROZESS MODELL ALS LEITIDEE

13. International haben sich verschiedene Standards durchgesetzt, wie Ingenieure ein Problem in eine funktionierende Lösung transformieren. im Kern geht es darum, ein Prozessmodell zu definieren und dann entsprechend umzusetzen. Im Schaubild sind – sehr stark vereinfacht — einige Kernelemente angedeutet, die jeder Hervorbringungsprozess umfassen muss:

14. Ausgangspunkt ist immer die Beschreibung eines Problems P, für das eine ‚Lösung‘ in Form einer ‚Verbesserung‘ oder eines ‚ganz neuen Ansatzes‘ gesucht wird.

15. Das gestellte Problem muss dann untersucht, analysiert werden; was ist damit alles impliziert? Was sind wichtige Komponenten? Was würde gebraucht? usw. Im Endergebnis benötigt man klare ‚Anforderungen‘ (‚requirements‘), was alles zu tun ist, damit das Problem im Sinne des Auftraggebers als ‚gelöst‘ gelten kann (einfache Beispiele für solche Analysen finden sich HIER.)

16. Liegen die Anforderungen konkret genug vor, dann braucht man eine Lösungsidee, einen ‚Entwurf‘, ein theoretisches Modell (Entwurfsmodell, Designmodell M_{d}) , aus dem man entnehmen kann, wie eine Lösung aussehen könnte. Dieses Modell sollte den Anforderungen eines theoretischen Modells genügen, das man empirisch überprüfen kann.

17. Liegt ein Design-Modell vor, muss man es technisch so umsetzen, dass ein konkretes, reales Modell (M_{r}) entsteht, das genau all das ‚tut‘, was in den Anforderungen gefordert wird und was im Design-Modell entsprechend ’spezifiziert‘ wurde. Durch entsprechende Tests (Validierung, ‚validation‘) ist dies nachzuweisen.

18. Im Fall (sprach-)lernender Systeme S besteht das Problem P darin, dass wir einerseits erleben, wie alle Menschen scheinbar mühelos Sprachen lernen, von denen es viele tausend Spielarten gibt. Mittels ‚Sprache‘ können Menschen miteinander ‚kommunizieren‘ und sich bis zu einem gewissen Grad ‚koordinieren‘. Wie muss ein künstlicher Sprecher-Hörer, eine künstliche Intelligenz, eine KI, beschaffen sein, die dieses Verhalten von Menschen reproduzieren kann? Wie muss eine KI konstruiert sein, die ‚von sich aus‘ jede beliebige natürliche Sprache so lernen kann, dass sie sich mit anderen Menschen ‚unterhalten‘ kann?

19. Um dieses Problem in ein funktionierendes Modell M_{r} umsetzen zu können, benötigt man ein theoretisches Modell M_{d}, das auf logischer Ebene vorzeichnet, was dann real umgesetzt werden soll.

20. Gibt es solche theoretischen Modelle M_{d}? Schaut man sich in Disziplinen wie Psychologie, Sprachwissenschaften, Linguistik, Neurolinguistik usw. um, dann wird man sehr vieles finden, tausende von partiellen Modellen, man wird aber – soweit ich sehe – kein einziges Modell finden, das die Problemstellung P zufriedenstellend beantwortet.

WELCHES THEORETISCHES MODELL

21. Im engeren Bereich der KI-Forschung hat man zwar schon auch erkannt, dass der Zusammenhang zwischen Ausdrucksseite einer Sprache L und ihrer Bedeutungsseite (Inhaltsseite) irgendwo hergestellt werden muss (das sogenannte ’symbol grounding problem‘), aber die bisherigen – wenngleich vielfältigen – Lösungsversuche können nicht überzeugen.

22. Hilfreich erscheint auf jeden Fall, dass man begonnen hat, die Problemstellung im Paradigma des ‚Sprachspiels‘ (‚language game‘) unter kontrollierten Bedingungen zu untersuchen. Hier unterscheidet man die lernenden Systeme S1, S2, … von der umgebenden Welt W, mit der die Systeme über sensorische Prozesse (Input, Wahrnehmung, …) und Aktionen (Output, Aktoren, motorische Prozesse…) interagieren.

23. Angesichts der Vielzahl an Sprachen und ihrer Komplexität (Anzahl Worte, Wortformen, Redesituationen, Redebedingungen, …) fällt es schwer, zu sagen, mit welchem ‚Sprachausschnitt‘ L_{start} \subseteq L man ‚anfangen‘ soll, so dass sich das System dann nach und nach immer mehr apsekte der Sprache L aneignen kann.

24. Aber schon hier stellen sich die grundlegende Frage, wie man das Verhaältnis von Welt W und lernendem System S ansetzen muss.

25. Wenn man bedenkt, dass das menschliche Gehirn als Medium unseres Wissens, Denkens und Sprechens mit der umgebenden Welt W direkt überhaupt keinen Kontakt hat, sondern nur sensorische Daten, auf deren Basis das Gehirn sich ’seine Welt‘ konstruiert, dann müsste man die Welt und das ‚Innere‘ des Gehirns, sprich sein ‚Wissen‘, mehr der weniger unabhängig voneinander konstruieren (Leibniz alte Idee von den ‚Monaden‘ bekommt neue Aktualität). Tut man dies, dann muss man sich Gedanken machen, wie man die Interaktion zwischen beiden Bereichen W und S theoretisch fassen kann/ muss.

26. Ein radikaler Ansatz besteht darin, zwischen der Welt W und dem Innenbereich von S eine Menge von ‚Abbildungsprozessen‘ anzunehmen (auch ‚Schnittstellen‘ (engl.: ‚interface‘) genannt), die Gegebenheiten aus W in Gegebenheiten von S so transformieren, dass in S einerseits Inputereignisse von W auftreten können und umgekehrt in W Outputereignisse von S. In dieser Sehweise wäre der menschliche Körper in erster Linie eine Sammlung von Schnittstellen zwischen Wissen und Welt. Damit wäre es dann nachvollziehbar, dass der gleiche Gedanke ‚einen Schritt zu machen‘ in einer Umgebung unter Wasser eine andere Wirkung hat als auf der Erdoberfäche oder im Weltraum.

27. Zwar wird die Feinstruktur des Wissens nicht ganz unabhängig sein von der Beschaffenheit des Interfaces INTF(W,S), aber die generelle Struktur ist ‚invariant‘ gegenüber einer möglichen Außenwelt (auch unter Berücksichtigung der Tatsache, dass die biologische Evolution in Wechselwirkung mit der umgebenden Welt W jene ‚Strukturen‘ eines Körpers bevorzugt hat, die zu den Gegebenheiten der Welt W ‚passen‘).

28. Bei dieser Betrachtungsweise würde sich ein theoretisches Modell nahelegen, indem der Gegenstandsbereich in die drei Komponenten umgebende Welt W, das System S sowie das verbindende Interface INTF zerlegt und deren Wechselwirkung INTF(W,S) untersuchen wird. Zusätzlich könnte man auch noch eine bilogisch-evolutionäre Perspektive im Sinne einer ‚evolutionären Programmierung‘ annehmen, mittels der die Strukturen der Komponenten S und INTF ’sich entwickeln‘ können.

29. Für die Frage, mit welcher Sprache L_{start} man beginnen sollte, würde ich aufgrund der aktuellen Diskussion von Avicennas Logik sagen, dass man ‚bei geeigneter Semantik für die Sprache der Logik‘ genau mit der klassischen Logik einsetzen sollte. Das hier einschlägige Sprachspiel ist sehr gut beschrieben und die in der Logik zur Anwendung kommenden Sprache ist eine Teilmenge der natürlichen Sprache. Eine KI, die in dieser Weise Logik lernen würde, würde simultan sowohl eine natürliche Sprache lernen, logisches Denken und – vermutlich – gleich auch noch die Grundlagen des mathematischen Denkens. Was klingt doch interessant.

WELCHE SOFTWARE?

30. Für die Umsetzung in eine Software würde sich – als eine Variante – -nahe legen, als Grundbegriff ‚Input-Output-System‘ zu benutzen. Jede der anvisierten Komponenten W, INTF, S wäre dann ein System (wobei S eine Menge von Systemen repräsentieren kann). Softwaretechnisch wäre es ferner interessant, die Interaktion dieser Systeme von vornherein über ‚Sockets‘ zu realisieren, die sich über TCP/IP hinaus an ein bestimmtes ‚Protokoll‘ halten. Damit könnten diese System S1, S2, … mit dem Interface INTF und der Welt W über die ganze Welt verteilt sein und miteinander ‚reden‘. Vermutlich müsste man dafür noch einen sogenannten ‚Server‘ bereitstellen, der die Kommunikation mit der Welt ‚koordiniert‘. Für das Lernen könnte es ferner sinnvoll sein, mehrere verschiedene Welten W1, W2, … zulassen.

GENETISCHE ALGORITHMEN UND DAS KRITERIUM K

1. In vielen vorausgehenden Blogeinträgen (siehe z.B. GENETISCHE ALGORITHMEN MIT PHÄNOTYP GA2 – Teil 2) hatte ich bei der Grundstruktur genetischer Algorithmen die Fitnessfunktion fit() an ein Kriterium K gekoppelt. Für viele ist es unklar, welche Rolle dieses Kriterium K spielt. Die bisherigen Beispiele bieten einige Hinweise, wie man das Kriterium K verstehen kann.

2. Ausgangspunkt bei der Bestimmung der Rolle des Kriteriums K ist die Fitnessfunktion fit(). Ihre Aufgabe ist es, den Elementen der jeweiligen Population POP einen ‚Fitnesswert‘ [F] zuzuordnen, als Strukturformel fit: POP \longrightarrow POP x F.

3. Damit stellt sich die Frage, wo kommen diese Fitnesswerte F her?

4. In dem einführenden Beispiel von Goldberg (1989) bestehen die Elemente der Population POP aus Informationsketten k, die jeweils im binären Format BIN eine natürliche Zahl n \in NAT repräsentieren. D.h. mit einer Übersetzungsfunktion bin2dec: BIN \longrightarrow NAT kann man die binären Zeichenketten jeweils in eine natürliche Zahl verwandeln.

5. Als Fitnessfunktion hatte Goldberg dann die einfache Funktion y=x^{2} gewählt, d.h. wir haben letztlich eine Kette fit(b)=(bin2dec(b))^2 mit b \in BIN.

6. In diesem Fall ist das Kriterium K die Operation ‚(bin2dec(b))^2‘, also F=(bin2dec(b))^2. Das Kriterium K wäre dann die mathematische Operation, die notwendig ist, einem gegebenen Informationselement k aus POP einen Wert f \in F zu ‚berechnen‘.

7. Dann könnte man auch direkt schreiben: fit: POP \longrightarrow POP x F mit F=K(POP), oder K: POP \longrightarrow F.

8. Das Kriterium K ‚erzeugt‘ einen Fitnesswert und die Fitnessfunktion fit() ordnet die Fitnesswerte den Elementen von POP zu.

9. Im Beispiel mit dem Traveling Salesman Problem (TPS) besteht die Population POP aus Informationsketten, wo jede Informationskette eine endliche Folge von ‚Ortsnamen‘ darstellt, wobei die Namen mittels natürlicher Zahlen NAT realisiert werden. Gesucht wird ein Fitnesswert f \in F , der die ‚Länge‘ des Weges repräsentiert, den man zurücklegt, wenn man die Orte, die in der Informationskette k ‚benannt‘ werden, nacheinander bereist.

10. Das Kriterium K muss also eine Verbindung herstellen zwischen ‚Namen von Orten‘ und einer berechenbaren Weglänge.

11. Im Beispiel wurde jeder Ortsnamen o \in O in einer Informationskette k einer Y-X-Koordinate c \in C zugeordnet, deren Koordinatenwerte jeweils reelle Zahlen REAL waren, also C \subseteq REAL \times REAL bzw. name2c: O \longrightarrow C. Im Bereich dieser Koordinaten kann man z.B. mit einer Formel für die ‚euklidische Distanz‘ dist() für je zwei beliebige Y-X-Koordinaten c, c‘ die Distanz zwischen diesen berechnen, dies wiederholt dann für alle Punkte eines Weges: sumDist(name2c(chain(k))) mit chain(k) als Übersetzung einer Informationskette k in Ortsnamen. Dann würde gelten F=sumDist(name2c(chain(k))) und das Kriterium K wäre genau dieser Übersetzungsprozess von einer Informationskette k \in POP in einen Wert, der als Fitnesswert f \in F benutzt werden kann.

12. Betrachtet man die Informationsketten in POP als ‚Zeichenmaterial‘ bzw. als ‚Ausdrücke einer Sprache L‘, dann kann man das Kriterium K auch als eine ‚Bedeutungszuordnung‘ auffassen, als eine ’semantische Interpretation‘ I, die den Ausdrücken POP der Sprache L eine ‚Bedeutung‘ M zuordnen, die dann als Fitnesswerte F genutzt werden.

13. Dieser letzte Gedanke mit der Deutung des Kriteriums K als ’semantische Interpretation‘ von POP drängt sich insbesondere im Fall des Beispiels mit dem kleinen Roboter auf (siehe GENETISCHE ALGORITHMEN MIT PHÄNOTYP GA1.5– Teil 1). Die Informationsketten in POP sind Zeichenketten einer Sprache Lal, die aussagenlogische Ausdrücke in Präfixschreibweise erlaubt. Der Fitnesswert einer solchen Formel soll etwas darüber aussagen, wie viel % der Bewegungen in einer definierten Spielrunde in direkter Nachbarschaft zu einer Wand stattfanden. Dazu muss ein ‚Zusammenhang konstruiert‘ werden, der im Kriterium K zu hinterlegen ist.

14. Verschiedene Konstruktionen sind möglich. Hier als Beispiel jene Version, die Nilsson (1998) im Kap.7 benutzt, ergänzt um eigene Annahmen. Nilsson nimmt eine ‚Umgebung‘ (‚environment‘, [E]) mit Zellen (Positionen) und Wänden an. Ich nehme zusätzlich den ‚Körper‘ eines ‚Input-Output-Systems‘ [S] an, der Signale von der Umgebung empfangen INP und Aktionen ausführen ACT kann; dazu Interfacefunktionen zwischen der Umgebung E und dem System S wie z.B. inp() und act(). ferner gibt es eine Interpretationsfunktion Int von den Ausdrücken der Sprache L in den Informationsketten von POP in die Inputwerte IN des Systems. Falls die Interpretationsfunktion in den Inputwerten eine ‚benachbarte Wand‘ ‚erkennt‘, ist dies ein positiver Fitnesswert, andernfalls nicht. Zusätzlich gibt es einen ‚Simulationsrahmen‘ mit n-vielen Durchläufen für ein Experiment.

15. M.a.W. das Kriterium K umfasst hier eine komplexe Struktur \langle E,S,inp,act \rangle mit S als \langle INP, ACT,POP, F,Int\rangle . Alle Faktoren in diesem Kriterium sind ‚fest‘ außer POP. POP stellt eine Menge von Informationsketten dar, bei der jede Kette k aus POP eine mögliche Verhaltensfunktion \phi: INP \longrightarrow ACT darstellt.

16. Informell besteht folgende Prozesskette: (i) Gegeben ist die Umgebung E mit den Interfacefunktionen und der Struktur des Input-Outputsystems samt der Interpretationsfunktion. (ii) Eine anfänglich zufällig gebildete Population von potentiellen Verhaltensprogrammen POP wird mit der Interpretationsfunktion Int ‚interpretiert‘. Dieser Zyklus wird n-mal wiederholt. (iv) Dann wird die Fitnessfunktion auf die interpretierten Werte angewendet. Dann folgt (v) die Anwendung des genetischen Operators \gamma (Selektion, Crossover, Mutation). (vi) Falls das Abbruchkriterium nicht zutrifft, wird der Vorgang ab (ii) wiederholt.

Anmerkung: Man kann an diesem Beispiel sehen, wie man einen GA1.5-TYP von genetischem Algorithmus zu einem GA2-TYP von Algorithmus erweitern könnte, indem man die Erzeugung der Körperhülle von S mit \langle INP, ACT\rangle separiert. Man muss dann allerdings noch klären, wie man die Interpretationsfunktion Int: L \longrightarrow INP erzeugen kann.

QUELLEN

Goldberg, D.E. Genetic Algorithms in Search, Optimization & Machine Learning, Reading (MA): Addison-Wesley Publ.Company, Inc., 1989

Nilsson, N. J., Artificial Intelligence: A New Synthesis, San Francisco (CA): Morgan Kaufmann Publ, 1998

GENETISCHE ALGORITHMEN MIT PHÄNOTYP GA1.5– Teil 1

Diesem Blogeintrag gingen drei Blogeinträge voraus:

In diesem Blogeintrag soll es um die Übersetzung/ Abbildung von Theorie in Software gehen. Zunächst als ‚Schema‘, dann ‚real‘.

GA1.5-Typ: Körper ohne Verhaltensfunktion; Übersetzung in eine Bedeutung D
GA1.5-Typ: Körper ohne Verhaltensfunktion; Übersetzung in eine Bedeutung D

Bei einem GA1.5-Typ eines genetischen Algorithmus wird kein Phänotyp erzeugt, allerdings wird eine ‚Hülle‘ mit Input [I] und Output [O] vorausgesetzt, die in einer ‚geeigneten Welt‘ operiert.

Wichtig in diesem Kontext ist, dass dieser Körperhülle eine Verhaltensfunktion fehlt; der Körper (Phänotyp) ist quasi ‚leer‘.

Der genetische Algorithmus kommt hier insofern ins Spiel, als die Verhaltensfunktion \phi nun ’simuliert‘ wird durch eine ‚Population‘ POP von Verhaltensfunktions-Kandidaten. D.h. es gibt eine Menge von Informationsketten k \in POP, wo jede Informationskette k die Beschreibung einer möglichen Verhaltensfunktion \phi darstellt.

Jede Informationskette k stellt damit den Ausdruck (‚Expression‘) einer zugehörigen Sprache L dar (k \in L).

Dieser Ausdruck als solcher hat keine ‚Bedeutung‘. Im genetischen Algorithmus ist es die Fitnessfunktion fit(), die eine Informationskette k mit Hilfe eines Kriteriums K ‚evaluiert‘. Von einem anderen Standpunkt aus kann sagen, dass das Kriterium K ein Bereich (‚domain‘, [D]) möglicher ‚Bedeutungen‘ ist, und dass die Fitnessfunktion in diesem Kontext verstanden wird als eine ‚Interpretationsfunktion‘ [I], die die Ausdrücke der Sprache L abbildet auf die Bedeutungselemente O von D.

Im Computer wird die Fitnessfunktion als Interpretationsfunktion I realisiert durch ein Programm, das die Ausdrücke k der Sprache L mit Hilfe eines Betriebssystems und der zugehörigen Hardware ‚interpretiert‘. Der Bedeutungsbereich D wird dann repräsentiert durch das Betriebssystem zusammen mit der Hardware.

Mit dieser Sehweise hat man Anschluss an den semiotischen Zeichenbegriff von Charles Sanders Peirce (1839-1914) (siehe Überblick in Noeth; Details in den Collected Papers).

Die Ausdrücke einer Sprache, die als Teil eines ‚Zeichens‘ auftreten, nennt er u.a. ‚(Zeichen-)Repräsentant‘ [R], die Bedeutungsobjekte, auf die er sich bezieht, ‚Objekte‘ [O], und die interpretierende Beziehungen zwischen beiden ‚Interpreter‘ [I]; dies kann entweder eine bloße Beziehung sein oder ein semiotischer Agent, der eben Zeichenausdrücke benutzt, um damit Bedeutungen zu kommunizieren. Damit kann man die interpretierende Beziehung als eine bijektive Abbildung auffassen I: R \leftrightarrow O, oder, wenn R \in L und O \in D dann I:L \leftrightarrow D.

Greift man hier schon mal vor auf die späteren Einsichten von Ludwig J.J. Wittgenstein (1889 – 1951), dann muss man das semiotische Zeichenkonzept erweitern im Kontxt des Begriffs ‚Sprachspiel‘. Der wesentliche Punkt ist, dass ein Zeichen niemals ‚rein‘, ‚isoliert‘ vorkommt, sondern immer in einem Kontext (‚context‘, [C]), der wesentliche Informationen enthält, wann, wo, wie, wer, … ein Zeichen tatsächlich benutzt werden kann, um eine bestimmte Bedeutung O zu ‚repräsentieren‘. In einer ersten Annäherung könnte man dann schreiben I:L x C \leftrightarrow C x D.

Bedenkt man die hier aufscheinende Komplexität von Zeichenbeziehungen, dann erscheint die Erzeugung von Verhaltensfunktionen mit ‚einfachen‘ genetischen Algorithmen gewagt. Andererseits hat die biologische Evolution dieses Wunderwerk fertig gebracht. Allerdings mit einer Modifikation: (i) Die biologische Evolution hat die ‚Hülle‘ zur Verhaltensfunktion erzeugt, den Körper mit Input (Sensorik) und Output (Aktorik) und einer adaptiven Verhaltensstruktur (Nervensystem), die als solche ad hoc, lokal die eigentliche ‚Feinabstimmung‘ per ‚Lernen‘ vornimmt.

Im folgenden soll dieses Programm schrittweise umgesetzt werden (Anmerkung: unser Etat umfasst 0 € und wir haben keine Planstellen).

QUELLEN

Noeth, W., Handbuch der Semiotik, 2. vollst. neu bearb. und erw. Aufl. mit 89 Abb. Stuttgart/Weimar: J.B. Metzler, xii + 668pp, 2000

Peirce, C. S. Collected Papers of Charles Sanders Peirce, Vols. 1-6., ed. by Charles Hartshorne, & Pauls Weiss; Vols.7-8. ed. by Arthur W.Burks. Cambridge (MA): Harvard University Press, 1931-1958

Wittgenstein, L.; Philosophische Untersuchungen, 3rd ed., Frankfurt am Main: Suhrkamp, 1971

GENETISCHE ALGORITHMEN MIT PHÄNOTYP GA2 – Teil 2

Eine grobe Typologie genetischer Algorithmen
Eine grobe Typologie genetischer Algorithmen

Diesem Blogeintrag gingen zwei Blogeinträge voraus:

KORREKTUR: NICHT GA1, NICHT GA2, ABER VIELLEICHT GA1.5

Wie ich im Nachhinein feststellen durfte, habe ich in der Klassifizierung des aktuellen Beispiels einen Fehler gemacht. Das Beispiel mit dem einer Wand-Folgenden-Roboter ist natürlich nicht vom Typ GA2, da hier keine Genotypen in Phänotypen übersetzt werden, die dann handeln. Stattdessen wird ein bestimmter Phänotyp vorausgesetzt – so eine Art ‚Hülle‘ – und nur die Verhaltensfunktion ‚in‘ dieser Hülle, im Phänotyp, nur diese wird mittels eines genetischen Operators verändert und – hoffentlich – ‚optimiert.

Also ein reiner TYP ‚Genetischer Algorithmus mit Phänotyp (GA2)‘ liegt nicht vor, andererseits ist es aber auch nicht der typische ‚Genetische Algorithmus ohne Phänotyp (GA1)‘.

Ein Lösungsvorschlag könnte sein, einen ‚Mischtyp‘ einzuführen, etwa ‚Genetischer Algorithmus unter Voraussetzung eines Phänotyps (GA1.5)‘.

FITNESS UND KRITERIUM K

Wie im aktuellen Beispiel mit dem einer Wand-Folgenden-Roboter die Fitness berechnet werden soll, wurde im vorausgehenden Beitrag GENETISCHE ALGORITHMEN MIT PHÄNOTYP GA2 – Teil 1 schon beschrieben. Nach der Korrektur der Typzuweisung könnte man in einer Meta-Reflexion feststellen, dass das Kriterium K beim Typ GA1.5 von der definierten Welt mitsamt den definierten möglichen Aktionen des Phänotyps ‚geliefert‘ wird. D.h. anstatt nur eine einfache mathematische Formel zu haben, die einen Fitnesswert berechnet, haben wir hier eine vollständige Welt samt Interface, aus der heraus mögliche Fitnesswerte berechnet werden (Natürlich ist die Welt selbst mit dem Interface letztlich auch eine mathematische Formel, aber jene Aspekte, die den aktuellen Fitnesswert konstituieren, sind nur Teilaspekte an dem Gesamtmodell. Je komplexer die Welt bei einem GA1.5-Typ ist, umso unpraktischer bis praktisch unmöglich wäre der Ansatz, dies alles mit einer Fitnessfunktion abzudecken).

Ferner ist zu beachten, dass die Informationsketten, auf die der genetische Operator angewendet wird, hier – wie in vielen anderen Beispielen aus der Literatur auch – keine Informationsketten sind, die das Entstehen (die ‚Ontogenese‘) eines Phänotyps beschreiben, sondern jeweils eine komplette Verhaltensfunktion eines als ‚Hülle‘, sprich ‚Struktur‘, vorgegebenen Phänotyps.

Wenn man bedenkt, welche komplexen Aufgaben eine Phänotyp letztlich zu bewältigen hat, dann erscheint ein solcher Ansatz grundsätzlich wenig zielführend zu sein. Das Beispiel eignet sich möglicherweise, um den Einsatz von baumartigen Informationsketten (oder auch von ‚binären Schemata‘ a la Classifier) zu demonstrieren, es wird aber mit Sicherheit nicht ausreichen, um anspruchsvolle Verhaltensfunktionen zu repräsentieren.

Aus eigenen Experimenten der vorausgehenden Jahre ist bekannt, dass GA1.5-Typen im Stile von Classifiern gerade in ihrer Begrenztheit dennoch wertvolle Hinweise liefern können, warum sie bestimmte Aufgaben nicht lösen können und welche strukturellen Änderungen man vornehmen muss, um sie lösen zu können. Solche Ansatzpunkte sind erheblich besser, als nur ‚im Nebel‘ herum zu stochern indem man wilde Strukturen zum Einsatz bringt, die zwar ‚an sich‘ mathematisch ‚wunderbare Eigenschaften‘ aufweisen, aber letztlich nicht zielführend sind.

Mit Blick auf das Fernziel ‚Sprache lernen‘ und unter Berücksichtigung der schon bekannten Experimente aus den letzten Jahren bliebe dann zur ‚Rettung der Idee‘ eines GA2-Typs in diesem Kontext noch die Möglichkeit offen, nicht einen kompletten Phänotyp zu erzeugen, sondern ’nur‘ die Struktur einer Verhaltensfunktion \phi .

Da aber – bei meinem aktuellen Kenntnisstand – niemand auf der Welt eine funktionierende Lösung für solche eine Verhaltensfunktion \phi hat, weiß auch niemand, wie eine Informationskette g (den Genotyp repräsentierend) aussehen sollte, um solch einen – bislang noch unbekannten – Phänotyp p zu erzeugen.

Daraus leite ich die Forderung ab, dass wir zunächst in mühsamen Experimenten ermitteln müssen, welche Grundstrukturen eine geeignete Verhaltensfunktion \phi benötigt, um dann vielleicht per genetischer Erzeugung diese ‚automatisch‘ erzeugen zu lassen mit ‚eingebauter‘ genetischer Optimierung.

Fortsetzung folgt.

QUELLEN (Auswahl)

  • Goldberg, D.E. Genetic Algorithms in Search, Optimization & Machine Learning, Reading (MA): Addison-Wesley Publ.Company, Inc., 1989
  • John R.Koza, „Genetic Programming. On the Programming of Computers by Means of Natural Selection, London – Cambridge (MA): MIT, 1992
  • Holland, J.H. Adaptation in Natural and Artificial Systems, London:UK, The MIT-Press, 1992 (first 1975 Univ. of Michigan)
  • Kaufmann, S.A., ‚The Origins of Order. Self-Organization and Selection in Evolution‘, New York – Oxford: Oxford University Press, 1993
  • John R.Koza, „Genetic Programming II. Automatic Discovery of Reusable Programs, London – Cambridge (MA): MIT, 1994
  • Holland, J.H. Hidden Order. How adaptation Builds Complexity, New York: USA, Basic Books, 1995
  • Banzhaf, W.; Nordin, P.; Keller, R.E.; Francone, F.D. Genetic Programming. An Introduction, Publisher: Morgan Kaufmann; 1st edition (December 15, 1997), ISBN-10: 155860510X, ISBN-13: 978-1558605107
  • Wilson, S.W. ZCS: a zeroth level classifier system, Evolutionary Computation, 2(1), 1-18 (1994)
  • Holland, J.H., ‚Emergence. From chaos to Order‘, New York: Basic Books, 1998
  • Nilsson, N. J., Artificial Intelligence: A New Synthesis, San Francisco (CA): Morgan Kaufmann Publ, 1998 /* Evolutionäre Berechnung, Genetische Programmierung wird an einem Beispiel illiustriert (SS.59-70) */
  • William B. Langdon, Riccardo Poli, „Foundations of Genetic Programming, Berlin – Heidelberg – New York et al: Springer Berlin – Heidelberg – New York, 2002
  • Sigaud, O.; Wilson, S.W., Learning classifier systems: A survey, Soft Computing, vol. 11, no. 11, September, 2007, pp. 1065-1078
  • Riccardo Poli, William B. Langdon, Nicholas Freitag McPhee, „A Field Guide to Genetic Programming (ISBN 978-1-4092-0073-4) (online: http://www.gp-field-guide.org.uk/ ), 2008 /* Authors: An introduction to genetic programming (GP). GP is a systematic, domain-independent method for getting computers to solve problems automatically starting from a high-level statement of what needs to be done. Using ideas from natural evolution, GP starts from an ooze of random computer programs, and progressively refines them through processes of mutation and sexual recombination, until solutions emerge. All this without the user having to know or specify the form or structure of solutions in advance. GP has generated a plethora of human-competitive results and applications, including novel scientific discoveries and patentable inventions. */
  • S.Russell, P.Norvig, Artificial Intelligence, 3rd ed., Boston – Indiana – Minneapolis et al: Pearson Education Inc., 2011 /* Das Thema ‚genetische/ evolutionäre‘ Algorithmen sowie ‚genetische/ evolutionäre‘ Programmierung wird sowohl in seinem historischen Kontext (S.155f) wie auch als eigener Sachpunkt SS.126ff kurz behandelt */
  • „Genetic Programming (GP) in Wikipedia (EN): http://en.wikipedia.org/wiki/Genetic_programming (Überblick, Quellen, Links)
  • IEEE, Technische Arbeitsgruppe Spiele: http://cis.ieee.org/games-tc.html
  • ACM, Special Interest Group SIGEVO, http://sigevo.hosting.acm.org/wiki/tiki-index.php?page=Mission%20statement%20of%20SIGEVO
  • EVOSTAR Konferenz: http://evostar.dei.uc.pt/2012/call-for-contributions/evomusart/
  • GP und Musik: http://sonicstudies.org/post/69772945837/evo-2014-evomusart-3rd-international-conference-on

GENETISCHE ALGORITHMEN MIT PHÄNOTYP [GA2] – Teil 1

Eine grobe Typologie genetischer Algorithmen
Eine grobe Typologie genetischer Algorithmen

Entsprechend der im Blogeintrag VOLUTIONÄRE (= GENETISCHE) PROGRAMMIERUNG (ALGORITHMEN) – EINE TYPOLOGIE eingeführten Typologie soll hier jetzt ein Beispiel für den Fall 4 vorgestellt werden. Ausgangspunkt ist das Beispiel des Roboters, der einer Wand folgen soll, skizziert im Kap.4 des Buches von Nilsson (1998), SS.59ff.

PROBLEMSTELLUNG, FITNESS UND KRITERIUM K

Nilsson geht aus von einem Roboter [R1], der in einer zweidimensionalen Fläche lebt, die von einer Mauer umgeben ist. Egal, wo er startet, soll er lernen, immer der Wand entlang zu laufen.

Wir führen hier folgende Varianten ein:

1. 1 Roboter R1
2. 1 Richtung der Wand entlang (entweder im Uhrzeigersinn D1 oder umgekehrt D2)
3. 2 Richtungen D1 und D2
4. n-viele Roboter R1, …, Rn

Das Kriterium K für den Erfolg, anhand dessen die Fitness gemessen werden soll, ist die Anzahl der Wandelemente die ‚unmittelbar‘ passiert werden: wenn im Uhrzeigersinn D1, dann Wandelement ‚links‘, wenn gegen den Uhrzeigersinn D2, dann Wandelement ‚rechts‘ (bei 3×8 + 11 Elementen ergibt dies 36 mögliche ‚Passagen‘ pro Runde; Nilsson setzt 60 Runden pro Experiment an. 100% Erfolg wären dann eben 36×60 = 2160.

EXPERIMENTELLER RAHMEN

Beispiel Robot-Welt in Anlehnung an Nilsson 1998 mit Abwandlungen
Beispiel Robot-Welt in Anlehnung an Nilsson 1998 mit Abwandlungen

Wir nehmen an, dass es eine Welt [W] gibt, hier Welt W1 mit 8×8 Feldern (siehe Bild) und einer Einbuchtung. Es werden 8 Richtungen unterschieden (analog der WOOD1-Welt aus den Classifier-Experimenten von Wilson), einmal kodiert durch die Ziffern ‚1‘ bis ‚8‘, dann kodiert durch die Zeichenketten ’n‘, ’ne‘, …, ’nw‘.

Die Roboter in der Welt sollen eine Population [POP] von Systemen bilden. Die Kodierung soll wie folgt sein: System 1 := 0000 := ‚*0‘, System 2 := 0001 := ‚*1‘, System 3 := 0010 := ‚*2‘, System 4 := 0011 := ‚*3‘, usw.

Jedes Element p der Population POP besteht aus einer ‚Struktur‘ [SSTR] sowie einer ‚Verhaltensfunktion‘ [sdyn]. Die Struktur repräsentiert den aktuellen ‚Zustand‘ eines Systems und die Verhaltensfunkion sdyn() beschreibt das mögliche ‚Verhalten‘ des Systems relativ zu einem gegebenen Zustand.

Die Interaktion zwischen der Welt W und den Elementen der Population POP wird über das Weltinterface ‚INTERFACE‘ geregelt. Es umfasst die beiden Interfacefunktionen ainp: WORLD —> SSTR sowie aout: SSTR —> WORLD[World Input Buffer, WIB].

Für das Gesamtprotokoll W – INTERFACE -POP siehe HIER.

KODIERUNG DER PROBLEMSTELLUNG

Für die Kodierung der Verhaltensregeln benutzt Nilsson eine baumartige Regelstruktur. Dieser Typ von Kodierung wird in Poly et al. (2008) Kap.6 ausführlich diskutiert (ähnliche Formen wären ‚graphbasierte‘ Programmierung oder ‚linearisierte Versionen von Bäumen/ Graphen‘).

Die Elemente der Bäume (Knoten und Kanten) repräsentieren eine formale Sprache, die aussagenlogische Operatoren in Präfixschreibweise enthalten sowie Aussagenamen, die für Richtungen stehen.

Für alle Aussagenamen gilt, dass sie ‚wahr‘ = ‚1‘ sind, wenn das Feld, auf das die jeweilige Richtung zeigt, ‚frei‘ ist; andernfalls ist die Aussage ‚falsch‘ = ‚0‘. Also bei der Aussage ’n‘ ist diese wahr, wenn das Feld in Richtung ’n‘ (vom aktuellen Standpunkt aus) ‚frei‘ ist. Wenn das Feld frei ist, wird das System in diese Feld bewegt. Andernfalls passiert nichts.

Abweichend von Nilsson wird hier festgelegt:

(AND x y) = 1, wenn x und y beide 1 sind, sonst 0
(OR x y) = 1, wenn wenigstens eine von beiden Aussagen 1 ist, sonst 0.
(NOT x) = 1, wenn x =0
(IF x y z) = y wenn x=1, ansonsten z

Erfolg: ist ein Nachbarfeld des neuen Feldes eine ‚Wand‘, dann 1 Punkt, andernfalls 0 Punkte.

Jede Systemstruktur enthält minimal die Komponenten INPUT, ACTION sowie RULES.

INPUT := Der Input repräsentiert ein sensorisches Gedächtnis, das die aktuellen Informationen von der Welt W repräsentiert. Es wird angenommen, dass eine binäre Kodierung vorliegt, analog derjenigen wie sie mit der WOOD1-Welt von Wilson eingeführt worden ist. Konkret wird hier angenommen dass es nur drei mögliche Werte gibt: (i) Freier Raum ’00 00′, Wand ’01 00′ sowie ‚anderes System ’10 00′ (bei mehreren Systeme bis ’10 11‘). Dabei hat eine Objektbeschreibung die Struktur ‚TYP IDX‘ mit TYP = Frei/ Hindernis/ System mit 00/ 01/ 10 und mit jeweils einem Index IDX mit 00/ 00/ 00 bis 11.
ACTION := Das Aktionspuffer enthält eine Aktionsangabe in Form einer Richtungsangabe aus [0,1, …, 8], die als Bewegung in diese Richtung interpretiert wird. ‚0‘ steht für ‚keine Bewegung‘ und wird zugelassen.
RULES := Menge von Regeln; jede Regel stellt eine Informationskette dar die die Form eines Ausdrucks der Sprache Lal hat.

DEFINITION SPRACHE DER REGELN

1. Elemente aus [0,8] sind Aussagenamen A
2. Ein Aussagename A ist ein Aussage S
3. Wenn s ein Aussage S ist, dann ist auch (NOT s) ein Aussage S.
4. Wenn s, s‘, s“ Aussagen sind, dann sind auch (AND s s‘) oder (OR s s‘) oder (IF s s‘ s“) Aussagen
5. Alle Ausdrücke, die nach (1) – (4) Aussagen sind, bilden die Sprache Lal.

BEISPIELE ZUR NUTZUNG DER SPRACHE LaL

Sehfelder in der Beispielwelt
Sehfelder in der Beispielwelt

Im Fall 2 befindet sich ein System an der Stelle Y=4 und X=5. Alle angrenzenden Felder sind ‚leer‘. Jedes Feld hat die Kodierung ’00 00′, und dies 8fach.

Im Fall 1 befindet sich ein System in der ‚linken oberen Ecke‘ der Welt mit den Koordinaten Y=1 X=1. Die Kodierung der angrenzenden Felder hier ist wie folgt:

1. ’01 00′
2. ’01 00′
3. ’00 00′
4. ’00 00′
5. ’00 00′
6. ’01 00′
7. ’01 00′
8. ’01 00′

Im Fall 2 mit der Position (4,5) wäre eine Aktion (1) ‚wahr‘, da das Feld frei ist.

Im Fall 1 mit Position (1,1) wäre die Aktion (1) ‚falsch‘, da das Feld in dieser Richtung ein Hindernis = Wand ist.

Würde die Regel im Fall 1 dagegen lauten (AND (NOT 1) 3) dann wäre (NOT 1) ‚wahr‘, da ‚1‘ ‚falsch‘ ist und ‚3‘ ist ‚wahr‘, da das zugehörige Feld leer ist, daher ist (AND …) ‚wahr‘, also kann die Aktion ausgeführt werden.

Eine Evaluation der Regel (AND (NOT 1) 3) für den Fall 1 würde ergeben, dass sich ’neben‘ dem Feld (1,2) ein Hindernisobjekt (Wand) befindet, daher würde die Regel Fitnesspunkte bekommen. Dies lässt sich mittels einer ‚internen Fitnessregel‘ realisieren.

BAUMARTIGE REGELN UND CLASSIFIER SYSTEME; ANMERKUNG

Vergleicht man die baumartigen Regeln mit Classifier Systemen (siehe z.B. Holland 1992, 1995, 1998, Wilson 1997, und Sigaud/ Wilson 2007) dann wird klar, dass die baumartigen Regeln gegenüber den Regeln der Classifier Systeme eine zusätzliche ‚Abstraktion‘ einführen. In einer Classifier Regel hat man die Struktur (IF INPUT THEN ACTION, F). Der INPUT ist bei den Classifiern ein Bitfeld, eventuell angereichert durch Schemazeichen ‚*‘, die für ‚1‘ oder ‚0‘ stehen können. Würde man das vorausgehende Beispiel (AND (NOT 1) 3) auf einen Classifier übertragen, dann müsste man die Regel (AND (NOT 1) 3) erst einmal übersetzen im Sinne von: wenn 3 ‚leer‘ ist und ‚1‘ ’nicht leer‘ ist dann gehe nach 3.

Ein entsprechende Classifier-Regel würde lauten: ((’01 00′ * ’00 00′ * * * * *) 3; F).

Daran kann man sehen, dass der Lal-Ausdruck erst einmal ‚interpretiert/ übersetzt‘ werden muss auf den Inputbereich, und zwar auf seine ‚Wahrheitsbedingungen‘, und diese ‚übersetzte Bedeutung‘ wird verglichen mit dem ‚realen‘ Input.

Die Classifier-Regeln müssen nicht übersetzt werden; sie repräsentieren ihre eigenen Wahrheitsbedingungen.

Es stellt sich die Frage, welche Kodierungsstrategie die ‚günstigere‘ ist?

Fortsetzung folgt.

QUELLEN (Auswahl)

  • Goldberg, D.E. Genetic Algorithms in Search, Optimization & Machine Learning, Reading (MA): Addison-Wesley Publ.Company, Inc., 1989
  • John R.Koza, „Genetic Programming. On the Programming of Computers by Means of Natural Selection, London – Cambridge (MA): MIT, 1992
  • Holland, J.H. Adaptation in Natural and Artificial Systems, London:UK, The MIT-Press, 1992 (first 1975 Univ. of Michigan)
  • Kaufmann, S.A., ‚The Origins of Order. Self-Organization and Selection in Evolution‘, New York – Oxford: Oxford University Press, 1993
  • John R.Koza, „Genetic Programming II. Automatic Discovery of Reusable Programs, London – Cambridge (MA): MIT, 1994
  • Holland, J.H. Hidden Order. How adaptation Builds Complexity, New York: USA, Basic Books, 1995
  • Banzhaf, W.; Nordin, P.; Keller, R.E.; Francone, F.D. Genetic Programming. An Introduction, Publisher: Morgan Kaufmann; 1st edition (December 15, 1997), ISBN-10: 155860510X, ISBN-13: 978-1558605107
  • Wilson, S.W. ZCS: a zeroth level classifier system, Evolutionary Computation, 2(1), 1-18 (1994)
  • Holland, J.H., ‚Emergence. From chaos to Order‘, New York: Basic Books, 1998
  • Nilsson, N. J., Artificial Intelligence: A New Synthesis, San Francisco (CA): Morgan Kaufmann Publ, 1998 /* Evolutionäre Berechnung, Genetische Programmierung wird an einem Beispiel illiustriert (SS.59-70) */
  • William B. Langdon, Riccardo Poli, „Foundations of Genetic Programming, Berlin – Heidelberg – New York et al: Springer Berlin – Heidelberg – New York, 2002
  • Sigaud, O.; Wilson, S.W., Learning classifier systems: A survey, Soft Computing, vol. 11, no. 11, September, 2007, pp. 1065-1078
  • Riccardo Poli, William B. Langdon, Nicholas Freitag McPhee, „A Field Guide to Genetic Programming (ISBN 978-1-4092-0073-4) (online: http://www.gp-field-guide.org.uk/ ), 2008 /* Authors: An introduction to genetic programming (GP). GP is a systematic, domain-independent method for getting computers to solve problems automatically starting from a high-level statement of what needs to be done. Using ideas from natural evolution, GP starts from an ooze of random computer programs, and progressively refines them through processes of mutation and sexual recombination, until solutions emerge. All this without the user having to know or specify the form or structure of solutions in advance. GP has generated a plethora of human-competitive results and applications, including novel scientific discoveries and patentable inventions. */
  • S.Russell, P.Norvig, Artificial Intelligence, 3rd ed., Boston – Indiana – Minneapolis et al: Pearson Education Inc., 2011 /* Das Thema ‚genetische/ evolutionäre‘ Algorithmen sowie ‚genetische/ evolutionäre‘ Programmierung wird sowohl in seinem historischen Kontext (S.155f) wie auch als eigener Sachpunkt SS.126ff kurz behandelt */
  • „Genetic Programming (GP) in Wikipedia (EN): http://en.wikipedia.org/wiki/Genetic_programming (Überblick, Quellen, Links)
  • IEEE, Technische Arbeitsgruppe Spiele: http://cis.ieee.org/games-tc.html
  • ACM, Special Interest Group SIGEVO, http://sigevo.hosting.acm.org/wiki/tiki-index.php?page=Mission%20statement%20of%20SIGEVO
  • EVOSTAR Konferenz: http://evostar.dei.uc.pt/2012/call-for-contributions/evomusart/
  • GP und Musik: http://sonicstudies.org/post/69772945837/evo-2014-evomusart-3rd-international-conference-on

EVOLUTIONÄRE (= GENETISCHE) PROGRAMMIERUNG (ALGORITHMEN) – EINE TYPOLOGIE

Eine grobe Typologie genetischer Algorithmen
Eine grobe Typologie genetischer Algorithmen

Nachdem nun schon zwei Typen von genetischen Algorithmen ohne Phänotyp [GA1] behandelt wurden, soll hier eine kurze ‚Typologie‘ eingeschoben werden, um eine grobe Klassifizierung der großen Zahl an Beispielen zu unterstützen.

Im vorausgehenden Schaubild werden vier Fälle unterschieden. Allen gemeinsam ist, dass sie von einer Menge PWi von Informationsketten ausgehen, die eine echte Teilmenge einer potentiellen Menge MMAX von Informationsketten darstellt. Ferner gibt es in allen Fällen eine Fitnessfunktion fit(), die eine Bewertung aller Informationsketten in der Menge PWi ermöglicht. Die Menge PWi kann mit genetischen Operatoren \gamma bearbeitet werden. Ob die Menge \gamma(PW_{i}) irgendwann ihr ‚Ziel‘ erreicht hat oder nicht wird durch eine Entscheidungsfunktion \chi festgestellt. Trotzdem unterscheiden sich die vier Fälle:

1. Im Fall 1 sind die Informationsketten alle binär und weisen keine besondere innere Struktur auf. Das Kriterium CRIT, anhand dessen die Fitnessfunktion einen Fitnesswert berechnet, ist eine einfache mathematische Formel.

2. Im Fall 2 sind die Informationsketten alle nicht mehr binär, sondern numerisch und sie weisen eine besondere innere Struktur auf (beim Traveling Salesman Problem [TSP] repräsentieren die Zahlen Ortsnamen und ihre Anordnung entspricht der Abfolge eines Weges). Das Kriterium CRIT, anhand dessen die Fitnessfunktion einen Fitnesswert berechnet, ist keine einfache mathematische Formel sondern eine mathematische Struktur, in der sich mittels Berechnungen Werte ermitteln lassen (z.B. Koordinaten, Punkte im n-dimensionalen Raum, Entfernungen …), die dann als Fitnesswerte genutzt werden können.

3. Im Fall 3 sind die Informationsketten auch nicht binär, sondern alpha-numerische Zeichenketten (z.B. Formeln) und sie weisen eine besondere innere Struktur auf (z.B. ein Programmcode in einer Programmiersprache). Das Kriterium CRIT, anhand dessen die Fitnessfunktion einen Fitnesswert berechnet, ist ein kompletter Algorithmus (ein Programm), mit dem man Werte ermitteln kann, die dann als Fitnesswerte genutzt werden können (z.B. wird die Zeichenkette ‚+ 7 3‘ der Informationskette vom Interpreter als eine Formel interpretiert, in der man die Zahlen ‚7‘ und ‚3‘ addieren soll. Die Addition wird ausgeführt und als Fitnesswert zur Verfügung gestellt).

4. Im Fall 4 sind die Informationsketten nicht binär, sondern alpha-numerische Zeichenketten (z.B. Formeln) und sie weisen eine besondere
innere Struktur auf (z.B. ein Programmcode in einer Programmiersprache). Das Kriterium CRIT, anhand dessen die Fitnessfunktion einen Fitnesswert berechnet, umfasst sowohl einen kompletten Algorithmus (ein Programm), mit dem man diese Zeichenketten in funktionsfähige Input-Output-Systeme [IO-Systeme] übersetzen kann, die in einer bestimmten Umgebung [W := World] bestimmte Aufgaben [T := Tasks] lösen müssen. Die Ergebnisse dieses Verhaltens werden dann als Fitnesswerte zur Verfügung gestellt). Die IO-Systeme kann man in diesem Fall als ‚Phänotypen‘ der Informationsketten bezeichnen, die dann die Rolle der ‚Genotypen‘ haben. Algorithmen vom Typ4 bezeichne ich dann als genetische Algorithmen mit Phänotyp [GA2].

QUELLEN – AUSWAHL

Goldberg, D.E. Genetic Algorithms in Search, Optimization & Machine Learning, Reading (MA): Addison-Wesley Publ.Company, Inc., 1989

John R.Koza, „Genetic Programming. On the Programming of Computers by Means of Natural Selection“, London – Cambridge (MA): MIT, 1992

John R.Koza, „Genetic Programming II. Automatic Discovery of Reusable Programs“, London – Cambridge (MA): MIT, 1994

Banzhaf, W.; Nordin, P.; Keller, R.E.; Francone, F.D. Genetic Programming. An Introduction, Publisher: Morgan Kaufmann; 1st edition (December 15, 1997), ISBN-10: 155860510X, ISBN-13: 978-1558605107

Nilsson, N. J., Artificial Intelligence: A New Synthesis, San Francisco (CA): Morgan Kaufmann Publ, 1998 /* Evolutionäre Berechnung, Genetische Programmierung wird an einem Beispiel illiustriert (SS.59-70) */

William B. Langdon, Riccardo Poli, „Foundations of Genetic Programming“, Berlin – Heidelberg – New York et al: Springer Berlin – Heidelberg – New York, 2002

G.Görz, C.-R.Rollinger, J. Schneeberger (Hrsg.), Handbuch der Künstlichen Intelligenz, München-Wien, Oldenbourg Wissenschaftsverlag; 4.korr.Aufl., 2003, ISBN-10: 3486272128, ISBN-13: 978-3486272123, /* Das Thema ‚genetische/ evolutionäre‘ Algorithmen sowie ‚genetische/ evolutionäre‘ Programmierung kommt in diesem Buch nicht vor. */

Riccardo Poli, William B. Langdon, Nicholas Freitag McPhee, A Field Guide to Genetic Programming (ISBN 978-1-4092-0073-4), 2008 /* Authors: An introduction to genetic programming (GP). GP is a systematic, domain-independent method for getting computers to solve problems automatically starting from a high-level statement of what needs to be done. Using ideas from natural evolution, GP starts from an ooze of random computer programs, and progressively refines them through processes of mutation and sexual recombination, until solutions emerge. All this without the user having to know or specify the form or structure of solutions in advance. GP has generated a plethora of human-competitive results and applications, including novel scientific discoveries and patentable inventions. */

S.Russell, P.Norvig, Artificial Intelligence, 3rd ed., Boston – Indiana – Minneapolis et al: Pearson Education Inc., 2011 /* Das Thema ‚genetische/ evolutionäre‘ Algorithmen sowie ‚genetische/ evolutionäre‘ Programmierung wird sowohl in seinem historischen Kontext (S.155f) wie auch als eigener Sachpunkt SS.126ff kurz behandelt */

Genetic Programming (GP) in Wikipedia (EN): Überblick, Quellen, Links.