Universität Hamburg

Fakultät für Mathematik, Informatik und Naturwissenschaften

Department Informatik

Diplomarbeit

Entwicklung hierarchischer Klassifikatoren beim Wabenbau von

Insekten

Vorgelegt von: Marius Zirngibl

Matrikelnummer: 5299377

Betreuer: Prof. Dr. Bernd Page Prof. Dr. Andreas G. Fleischer

Hamburg, Oktober 2009

Inhaltsverzeichnis

2 1 Einleitung 9

2 Theoretische Grundlagen 13

2.1 Nestbau von Bienen und Wespen . . . . . . . . . . . . . . . . . . . . 13 2.1.1 Stigmergie als Kommunikationsprinzip . . . . . . . . . . . . . 16 2.1.2 Nestbau in Insektenstaaten als Komplexes Adaptives System . 17

2.2 Evolutionstheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3 Genetische Algorithmen . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.3.1 Funktionsweise . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3.2 Schrittweiser Ablauf . . . . . . . . . . . . . . . . . . . . . . . 22 2.3.3 Codierung des Genotyps . . . . . . . . . . . . . . . . . . . . . 27 2.3.4 Schematheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.4 Learning Classifier Systems . . . . . . . . . . . . . . . . . . . . . . . 33 2.4.1 Credit Assignment: Reinforcement Learning . . . . . . . . . . 38 2.4.2 Rule Discovery: Genetische Algorithmen . . . . . . . . . . . . 39

2.5 Komplexität der Problemstellung . . . . . . . . . . . . . . . . . . . . 40

3 Methode 43 3.1 Benutzte Werkzeuge . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.2 Konzept des Simulationsmodells . . . . . . . . . . . . . . . . . . . . . 44 3.3 Programmierung der Simulationsumgebung . . . . . . . . . . . . . . . 44

3.3.1 Regelsatz und Parameter . . . . . . . . . . . . . . . . . . . . . 46 3.4 Programmierung der Agentenobjekte . . . . . . . . . . . . . . . . . . 46

3.4.1 Implementation der Klassifikatoren . . . . . . . . . . . . . . . 47 3.4.2 Klassifikation und Manipulation der Umgebung . . . . . . . . 48 3.4.3 Erweiterung durch hierarchische Klassifikatoren . . . . . . . . 50 3.4.4 Bewegung der Agenten . . . . . . . . . . . . . . . . . . . . . . 52

3.5 Berechnung der Gesamtfitness der Wabenstruktur . . . . . . . . . . . 52 3.6 Implementation des Genetischen Algorithmus . . . . . . . . . . . . . 56

3.6.1 Parameter des Genetischen Algorithmus . . . . . . . . . . . . 57 3.6.2 Ablauf des Genetischen Algorithmus . . . . . . . . . . . . . . 57

3.7 Graphische Darstellung . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.7.1 Darstellung des hexagonalen Gitters . . . . . . . . . . . . . . 60 3.7.2 Darstellung der einzelnen Wabenzellen . . . . . . . . . . . . . 61

3.8 Durchführung der Simulationen . . . . . . . . . . . . . . . . . . . . . 61

4 Simulationsergebnisse 63

4.1 Ergebnisse mit einem Regelsatz und variablen Stärkewerten . . . . . . 63 4.1.1 Ergebnisse ohne Beschränkung der Populationsgröße . . . . . 64 4.1.2 Ergebnisse mit beschränkter Populationsgröße . . . . . . . . . 65 4.1.3 Ergebnisse mit Crossover-Wahrscheinlichkeit . . . . . . . . . . 66 4.1.4 Ergebnisse mit Mehrfachauswahl der Elternindividuen . . . . . 68

4.2 Simulation mit statischem Regelsatz ohne Genetischen Algorithmus . 68 4.3 Simulation mit zwei hierarchisch geordneten Regelsätzen . . . . . . . 71

5 Diskussion 75

A MATLAB-Quellcode 91 A.1 simulationsumgebung.m . . . . . . . . . . . . . . . . . . . . . . . . . 91 A.2 bauagent.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 A.3 classifier.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 A.4 fitness.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 A.5 EckPunkte.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 A.6 strengthga.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 A.7 nachbarn.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 A.8 plotgitter.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 A.9 plotwabe.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 A.10 plotwaben.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

Danksagung

Ich danke meinen beiden Betreuern Prof. Dr. Page und Prof. Dr. Fleischer für die Ermöglichung dieser Arbeit.

Herrn Prof. Fleischer möchte ich für die engagierte und auch in schwierigen Phasen immer motivierende Betreuung, und für all die Zeit und Kraft, die für die langen und aufschlussreichen Diskussionen immer vorhanden war, besonders herzlich danken.

Außerdem danke ich Mieke, Julia, Jones, Andrea, Seb und Sophi für allen seelischen, geistigen und fachlichen Beistand während der Entstehung dieser Arbeit.

Inhaltsverzeichnis 6

Zusammenfassung

Der Nestbau von Wespen und Bienen gilt als ein Beispiel natürlich vorkommender selbstorganisierender Prozesse. Das einzelne Individuum arbeitet nach einfachen Regeln, die in ihrer Gesamtheit eine Struktur entstehen lassen, die trotz fehlender zentraler Koordination den Anforderungen von Brutpflege, Vorratshaltung und Schutz gegen Feinde bei veränderlichen Umweltbedingungen entsprechen. Im Rahmen dieser Arbeit wird untersucht, inwieweit es möglich ist, mit einem agentenbasierten Simulationsmodell unter Verwendung adaptiver lernender Systeme den Nestbau von Wespen abstrakt nachzubilden. Im Mittelpunkt der Arbeit steht die Frage, inwieweit das Modell in der Lage ist, sich selbständig aufgrund von Informationen aus der Umwelt an gegebene Kriterien anzupassen und sein Verhalten entsprechend zu ändern.

Es wird ein vom realen Nestbau abstrahiertes Simulationsmodell vorgestellt, welches einen Schwarm adaptiver Agenten als Lernendes Klassifizierendes System implementiert, der eine Struktur aus hexagonalen Einzelbausteinen zusammensetzen kann. Das Bauverhalten der Agenten wird dabei durch einfache lokal definierte Regeln (Klassifikatoren) bestimmt, welche durch Rückmeldung aus der Simulationsumgebung an das erwünschte Verhalten angepasst werden. Um dem Modell den Bau komplexerer Strukturen zu ermöglichen, werden hierarchisch geordnete Ebenen von Klassifikatoren eingeführt, die das Verhalten der Agenten in unterschiedlichen Phasen der Simulation steuern.

Anhand des Modells wird im Rahmen dieser Arbeit überprüft, ob die Anpassung der Agenten an ihre Umgebung im Sinne der oben beschriebenen Hypothese bestätigt werden kann. Dazu werden die Ergebnisse verschiedener Simulationsexperimente analysiert und bewertet. Auch wenn sich die Hypothese nicht vollständig belegen lässt, lassen sich wertvolle Schlüsse aus den Ergebnissen der durchgeführten Simulationen ziehen. Vor allem kann die Eignung hierarchischer Ebenen von Klassifikatoren zum Bau komplexer Strukturen bestätigt werden.

Abbildung 0.1: Eine Papierwespe (Polistes dominulus) beim Nestbau (Foto: Don Van Dyke, veröffentlicht unter creative commons auf http://www.

             flickr.com/)

1 Einleitung

Ameisen, Bienen und viele Wespenarten bringen in kollektiver Arbeit Nestbauten zustande, deren Größe und Komplexität den menschlichen Beobachter bei oberflächlicher Betrachtung zu der Annahme verleiten könnten, dass eine derartige Struktur nicht ohne einen Bauplan oder einen übergeordneten „Architekten“ entstehen kann (e.g. Matsuura und Yamane, 1990; Winston, 1991; Camazine et al., 2001). Da ein einzelnes Insekt nicht die Fähigkeiten besitzt, eine globale Struktur wie die eines komplexen Nestes zu erfassen, wird im Allgemeinen davon ausgegangen, dass soziale Insekten ihre Nester nach Prinzipien der Selbstorganisation bauen. Das einzelne Individuum arbeitet nach einfachen, genetisch evolvierten lokalen Regeln, die in ihrer Gesamtheit eine Struktur entstehen lassen, die trotz fehlender zentraler Koordination den Anforderungen von Brutpflege, Vorratshaltung und Schutz gegen Feinde bei veränderlichen Umweltbedingungen entsprechen. Der Nestbau sozialer Insekten ist also ein anschauliches Beispiel für in der Natur auftretende emergente Phänomene.

1 Einleitung

Das Ziel der vorliegenden Arbeit ist es, zu untersuchen inwieweit die bei Bienen und Wespen beobachteten Mechanismen des Wabenbaus auf vom Menschen geschaffene lernende Systeme übertragbar sind. Zu diesem Zweck wurde ein vom realen Nestbau abstrahiertes Agentenmodell realisiert, in welchem eine beliebige Anzahl adaptiver Agenten eine wabenförmige Struktur aus hexagonalen Einzelbausteinen zusammensetzen kann. Die adaptiven Agenten repräsentieren dabei die einzelnen Insekten und die aus Bausteinen zusammengesetzte Struktur das Insektennest. Die Agenten bewegen sich auf einem zweidimensionalen Gitternetz und entscheiden anhand definierter Regeln, ob an ihrer aktuellen Position ein Baustein gesetzt wird oder nicht. Die lokale Umgebung des Agenten gibt den Ausschlag für diese Entscheidung. Es wird kein explizites Zielmuster vorgegeben, sondern die entstehenden Wabenstrukturen anhand von festgelegten Kriterien bewertet. Das Verhalten der Agenten wird an die Umgebung angepasst, indem ihre Verhaltensregeln aufgrund dieser Bewertungen verändert werden.

„ […] a few simple behavioural rules lead to coordinated building and the production of amazingly complex architectures without needing to develop a strategy.“ (Theraulaz et al., 1999, S.327)

Die adaptiven Agenten verfügen über einen Satz von Regeln (auch Klassifikatoren), mit dessen Hilfe sie über ihr konkretes Verhalten in einer bestimmten Situation entscheiden können. Die Klassifikatoren stehen hierbei im Wettbewerb zueinander. Der Agent entscheidet mittels eines internen Bewertungssystems, welche der passenden Regeln angewandt werden soll. Die Bewertung der Regeln erfolgt zum größten Teil durch eine numerische Gewichtung, welche die Bedeutung der Regel für das gesamte System repräsentiert. Dieser Wert wird Stärke oder Fitness der Regel genannt, wobei in dieser Arbeit der Begriff Stärke bevorzugt wird, um Verwechslungen zu vermeiden. Um verschiedene Abschnitte im Nestbau von Insekten zu berücksichtigen, werden mehrere hierarchisch geordnete Regelsätze entwickelt und eingesetzt. Als hierarchischer Klassifikator wird ein Klassifikator bezeichnet, der in eine solche Hierarchie eingebettet und somit einer bestimmten Hierarchieebene zugeordnet ist. Durch definierte äußere Triggerereignisse kann von einer zur anderen hierarchischen Ebene von Klassifikatoren umgeschaltet werden. Die Agenten sollen also zu unterschiedlichen Zeitpunkten der Simulation nach verschiedenen Regeln funktionieren, was für den Bau einer komplexeren Neststruktur wichtig ist.

Die Anpassung der Agenten an die Umweltbedingungen erfolgt durch die Anwendung eines Genetischen Algorithmus (Goldberg, 1989; Nissen, 1997), der mittels heuristischer Optimierung die Gewichtung der Klassifikatoren ändert. Es werden Regelsätze in der Simulation angewendet und die jeweils entstandenen Strukturen durch den Genetischen Algorithmus bewertet. Diese Variante selbstorganisierten Lernens orientiert sich am Konzept der Learning Classifier Systems oder kurz LCS (Sigaud und Wilson, 2007; Holland, 1992).

Der Wabenbau von Insekten wird in dieser Arbeit als Optimierungsproblem betrachtet. Die zentrale Hypothese der vorliegenden Arbeit ist, dass es möglich ist, anhand eines agentenbasierten Simulationsmodells unter Einsatz eines adaptiven lernenden Systems den Nestbau von Insekten abstrakt nachzubilden und die Parameter des Modells während der Simulation so anzupassen, dass sich die Strukturen in Bezug auf vorgegebene Kriterien immer weiter verbessern, bis ein Optimum erreicht ist. Außerdem wird betrachtet, inwieweit das Konzept der hierarchischen Klassifikatoren dafür geeignet ist, das Modell zu erweitern und komplexere Wabenstrukturen hervorzubringen. Zur Untersuchung dieser Frage wird versucht, unter Einsatz von zwei hierarchisch geordneten Regelsätzen eine ringförmige Struktur zu erzeugen, wie sie zum Beispiel in den Waben der Honigbiene zu finden ist (vgl. Camazine (1991)).

1 Einleitung 12

2 Theoretische Grundlagen

2.1 Nestbau von Bienen und Wespen

Ob man nun Blattschneiderameisen beobachtet, die in weitverzweigten Bauten zu ihrer Nahrungsversorgung Pilze züchten (Hölldobler und Wilson, 1990), oder Termitenarten, die das Innere ihrer Bauten durch ein ausgefeiltes Belüftungssystem auf nahezu konstanter Temperatur halten (Camazine et al., 2001), man stellt sich unweigerlich die Frage, wie und wovon das kollektive Verhalten von Insektenkolonien gesteuert wird. Aus menschlicher Sicht fehlt dem System eine übergeordnete Kontrollinstanz, die dem einzelnen Individuum mitteilt, was es zu tun hat. Daher werden Verhaltensweisen sozialer Insekten gerne als anschauliches Beispiel für selbstorganisierende Prozesse herangezogen. Das einzelne Insekt hat eine sehr begrenzte Wahrnehmungsund Entscheidungsfähigkeit, vollbringt aber im Kollektiv erstaunliche Leistungen. Es ist im Tierreich zu beobachten, dass die Fähigkeit, komplexe Strukturen zu errichten, nicht zwangsläufig mit der Intelligenz des Individuums zunimmt. So sind beispielsweise Schimpansen oder Delphine, denen hohe Intelligenz nachgesagt wird, im Vergleich zu vielen Insekten unfähig zur Errichtung von Bauwerken (Deneubourg et al., 1992). Die Eigenschaft selbstorganisierender Systeme, komplexe Strukturen hervorzubringen, welche allein durch die Summe der Fähigkeiten der beteiligten Einzelteile des Systems nicht erklärbar sind, wird als Emergenz bezeichnet. Emergente Strukturen entstehen durch die kollektive Arbeit individueller Teile eines Systems, deren Verhalten durch lokale Information gesteuert wird und die keinen globalen Plan des Endresultats besitzen (Floreano und Mattiussi, 2008). Im speziellen Fall des Nestbaus bei sozialen Insekten beschreibt die Emergenz die Beobachtung, dass durch kollektive Zusammenarbeit aller Individuen des Insektenstaates Strukturen entstehen, die in ihrer Komplexität nicht allein durch das Verhalten der einzelnen Individuen erklärbar sind. Anders als bei vom Menschen errichteten Bauwerken gibt es nach dem Stand der Forschung keine zentrale Koordination, die den Ablauf des Nestbaus steuert. Stattdessen kommunizieren viele gleichberechtigte Individuen direkt oder indirekt miteinander, um die Struktur entstehen zu lassen. Man geht davon aus, dass sich die dazu notwendigen Steuerungsmechanismen im Laufe der Evolution entwickelt haben, doch wie genau diese Mechanismen funktionieren, ist nur in Ansätzen erforscht. Obwohl die Bauten vieler Ameisen- und Termitenarten beeindruckende Beispiele von Emergenz in biologischen Systemen sind, beschränkt sich die vorliegende Arbeit auf den Nestbau auf Basis sechseckiger Waben, wie er bei den Kolonien der Honigbiene und verschiedener Wespenarten zu beobachten ist.

Abbildung 2.1: Beginn des Nestbaus der Wespenart Polistes dominulus mit Bau des Pedikels und der ersten Zelle (Theraulaz und Bonabeau, 1995)

Um ein Wespennest an Ästen von Bäumen oder anderen Orten zu befestigen, beginnt die Wespe den Bau mit einer Aufhängung, dem Pedikel (siehe Abbildung 2.1), die als Grundstein für das Nest dient (Theraulaz und Bonabeau, 1995). Auf diesem Grundstein aufbauend wird das Nest von mehreren Individuen des Wespenstaats kollektiv gebaut. Verschiedene Beispiele für komplexe Wespennester sind in Abbildungen 2.2 und 2.3 zu sehen.

2.1 Nestbau von Bienen und Wespen

Abbildung 2.2: Verlassenes Wespennest der Sächsischen Wespe mit mehreren Ebenen

von Waben (Foto von http://www.honighaeuschen.de/)

(a)  (b)  (c)  (d)

Abbildung 2.3: Nester verschiedener Wespenarten im Vergleich. (a) Ropalidia variegata, (b) Mischocyttarus drewseni, (c) Angiopolybia pallens, (d) Epipona morio (Theraulaz und Bonabeau, 1995)

2.1.1 Stigmergie als Kommunikationsprinzip

Es ist davon auszugehen, dass beim Nestbau sozialer Insekten indirekte Kommunikation in Form von Stigmergie ein zentrales Steuerungsprinzip darstellt (Bonabeau et al., 1999; Karsai, 1999). Der Begriff Stigmergie wurde von Grassé (1959) geprägt und ist von den griechischen Wörtern στιγμα (stigma: Zeichen, Markierung) und ϵργoν (ergon: Arbeit, Aktion) abgeleitet. Als Stigmergie wird eine Form der indirekten Kommunikation verstanden, die sich dadurch auszeichnet, dass Individuen durch Manipulation ihrer Umgebung Informationen austauschen. Die gesetzten Zeichen oder Markierungen (stigma), auch Stimuli genannt, beeinflussen also das Verhalten bzw. die Aktionen (ergon) der Individuen. Bonabeau et al. (1999) unterscheiden zwei Arten der Stigmergie: die quantitative Stigmergie, bei der die Stärke der relevanten Stimuli über das Verhalten des Individuums entscheidet, und die qualitative oder diskrete Stigmergie, bei der qualitativ verschiedene Stimuli unterschiedliches Verhalten hervorrufen. Die Wegmarkierung mittels Pheromonen, welche von Ameisen zur Anzeige einer Futterquelle genutzt wird, ist ein Beispiel für quantitative Stigmergie, da die Intensität der Pheromonspur dafür verantwortlich ist, wie stark deren Anziehungskraft auf die einzelne Ameise ist. Ein Beispiel für qualitative Stigmergie stellt der Nestbau verschiedener Wespenarten dar, wobei das Individuum aufgrund unterschiedlicher Wabenstrukturen entscheidet, an welcher Stelle eine zusätzliche Wabe angebaut wird (Karsai, 1999).

In Abbildung 2.4 ist schematisch zu sehen, wie Stigmergie beim Wabenbau von Wespen funktioniert. Verschiedene Individuen kommen zeitlich nacheinander an die gleiche Stelle eines Nestes und entscheiden aufgrund der lokal vorgefundenen Wabenstruktur darüber, ob und an welcher Stelle eine neue Wabenzelle gebaut wird. Empirische Untersuchungen haben ergeben, dass die statistische Wahrscheinlichkeit für den Bau einer neuen Zelle bei Wespen von der Anzahl der direkt angrenzenden bereits gebauten Zellen abhängt. Je höher die Anzahl der bereits bebauten benachbarten Zellen ist, desto höher ist auch die Wahrscheinlichkeit für den Bau einer neuen Zelle (siehe Abbildung 2.6). Findet ein Individuum also beispielsweise die in Abbildung 2.5 gezeigte Struktur vor, ist die Wahrscheinlichkeit eines Bauvorgangs an der Position S_{3} wesentlich höher als an den Positionen S_{2} und S_{1}.

Abbildung 2.4: Kommunikation durch Stigmergie beim Wabenbau einer Papierwespe (Camazine et al., 2001)

2.1.2 Nestbau in Insektenstaaten als Komplexes Adaptives System

Große Teile der in der vorliegenden Arbeit verarbeiteten Theorie basieren auf dem Werk von John Henry Holland, der mit der Einführung des Begriffs der Komplexen Adaptiven Systeme (engl. CAS, Complex Adaptive Systems) einen grundlegenden Beitrag zur Theorie selbstorganisierender Prozesse geleistet hat (Holland, 1975). Wichtige Eigenschaften Komplexer Adaptiver Systeme sind nach Holland (1992) unter anderem, dass sie aus sehr vielen hochgradig vernetzten Einzelbausteinen bestehen, was ihr Verhalten schwer vorhersehbar macht. Solche Systeme sind in der Lage, sich an ihre Umwelt anzupassen. Ein Insektenstaat besitzt diese Eigenschaften und kann daher als Beispiel eines natürlich vorkommenden CAS betrachtet werden.

Abbildung 2.5: Unterschiedliche Anzahl von Nachbarzellen S_{1}, S_{2}, S_{3} (Camazine et al., 2001)

Abbildung 2.6: Wahrscheinlichkeit für den Bau einer neuen Zelle abhängig von der Anzahl der Nachbarzellen (Camazine et al., 2001)

2.2 Evolutionstheorie

Holland stellt auch bereits eine Verbindung zwischen adaptiven Systemen und Optimierungsprozessen her:

„ Adaptive processes are fundamentally optimization processes made difficult because the structures being modified are complex and their performance is uncertain.“ (Holland, 1976, S. 264)

Diese Ideen stellen eine Verbindung zwischen natürlichen und künstlichen adaptiven Systemen her. Besonders auch im Zusammenhang dieser Arbeit stellt sich die Frage, inwieweit die Regeln, die das Verhalten sozialer Insekten steuern, und die charakteristischen Eigenschaften natürlicher adaptiver Systeme wie Selbstorganisation und Emergenz auf künstliche adaptive Agentensysteme übertragbar sind.

2.2 Evolutionstheorie

Das auf Darwin zurückgehende biologische Evolutionsmodell spielte eine entscheidende Rolle bei der Entwicklung der Genetischen Algorithmen, weswegen an dieser Stelle ein kurzer Überblick über die elementaren Begriffe der Evolutionstheorie gegeben wird. Die Darstellung folgt im Wesentlichen Nissen (1997).

Grundsätzlich wird die Evolution von Darwin (1988) als Zusammenspiel von Mutation als stochastischer Veränderung des Erbguts und Selektion als natürlicher Auslese unter den Individuen beschrieben. Außerdem wird bei der Zeugung von Nachkommen das Erbmaterial beider Elternteile miteinander kombiniert, was Rekombination genannt wird. Die Nachkommen unterscheiden sich aufgrund der Mutationen und Rekombinationen genetisch voneinander und weisen unterschiedliche Anpassungsfähigkeit an ihre Umwelt auf. Der Grad der Angepasstheit an die Umweltbedingungen wird als Fitness bezeichnet. Im biologischen Zusammenhang lässt sich der Fitness-Wert eines Individuums nicht direkt bestimmen, sondern wird unter anderem von seiner Überlebensfähigkeit und der Anzahl seiner Nachkommen abgeleitet. Man geht hierbei davon aus, dass sich nach den Mechanismen der Selektion Individuen mit höherer Fitness häufiger fortpflanzen. Lebewesen die aufgrund ihrer besseren Anpassung an ihre Umgebung eine höhere Überlebenschance haben, können sich demnach mit höherer Wahrscheinlichkeit fortpflanzen, was zu einer natürlichen Auslese (Selektion) führt.

Alle Lebewesen haben gemeinsam, dass ihre Erbinformationen als sogenannter genetischer Code in Form von DNA (engl. deoxyribonucleic acid) in den Chromosomen in jedem einzelnen Zellkern gespeichert sind. Als Gen wird ein DNA-Abschnitt bezeichnet, der unter anderem eine Bauanleitung für die Proteinsynthese darstellt. Die unterschiedlichen Ausprägungen, in denen ein Gen auftreten kann, werden Allele genannt. Zur Veranschaulichung betrachte man z.B. ein Gen, das im menschlichen Erbgut die Haarfarbe codiert und in verschiedenen Allelen für blonde, schwarze oder rote Haare ausgeprägt sein kann.

Man bezeichnet die Gesamtheit der Erbinformationen als Genotyp und das äußere Erscheinungsbild als Phänotyp des Lebewesens. Diese Unterscheidung ist in unserem späteren Kontext relevant, weil es in der Biologie keine zwangsläufig eineindeutige Relation zwischen Genotyp und Phänotyp gibt. Eineiige Zwillinge etwa besitzen identisches Erbgut (gleicher Genotyp), haben aber trotzdem eindeutige Unterscheidungsmerkmale wie z.B. unterschiedliche Fingerabdrücke (unterschiedlicher Phänotyp).

Zusammenfassend sei festgehalten, dass in der biologischen Evolution ein Anpassungsprozess der Arten an ihre jeweiligen Umweltbedingungen stattfindet, wobei sich der genetische Code der Individuen von einer Generation zur nächsten in relativ kleinen Schritten ändert (Weicker, 1999). Die Veränderung biologischen Lebens im größeren Maßstab, wie z.B. die Entstehung neuer Arten, resultiert aus der ständigen Wiederholung kleiner genetischer Änderungen über viele Generationen hinweg. Die zentralen Faktoren dieses Evolutionsmodells sind Mutation und Selektion, wobei die Mutation durch Fehler bei der Zellteilung „zufällige“ Veränderungen einzelner Elemente des Erbmaterials verursacht und die Selektion eine natürliche Auslese beschreibt, welche zur Folge hat, dass sich besser angepasste Individuen mit höherer Wahrscheinlichkeit fortpflanzen können und sich somit auch ihr Erbgut weiter verbreitet. Mutationen treten nach heutigem Wissensstand nicht zielgerichtet auf. Eine Bewertung der zufälligen Änderungen im Genpool wird durch die Selektion vorgenommen.

Obwohl die Evolution als Anpassungsprozess betrachtet werden kann, muss sie klar von klassischen mathematischen Optimierungsproblemen abgegrenzt werden, da es kein globales Optimum gibt, auf das die Evolution zwangsläufig zusteuert. Die Evolution füllt vielmehr möglichst viele biologische Nischen aus, was an der weltweiten Artenvielfalt sehr anschaulich wird.

2.3 Genetische Algorithmen

Nach einer Theorie von Eigen und Schuster (1979) könnten selektive Selbstorganisation und Evolution biologischer Makromoleküle die Grundlage biologischer Information darstellen. Die Selbstreproduktion von Informationsträgern wird hier als autokatalytische Reaktion verstanden. Nach Darwin ist das Zusammenwirken von Mutation und natürlicher Selektion die Basis der biologischen Evolution. Eigens Theorie wird aufgrund der Parallen zu Darwins Evolutionstheorie auch Molekular-Darwinismus genannt. Die Idee des survival of the fittest wird hierbei von der Ebene der Individuen auf die genetische Ebene übertragen, was bedeutet, dass sich auch nur diejenigen Gene ausbreiten, welche die größte Zahl von Nachkommen erzeugen.

2.3 Genetische Algorithmen

Genetische Algorithmen sind heuristische Optimierungsverfahren, die sich an den in der biologischen Evolution beobachteten Anpassungsmechanismen orientieren. Sie arbeiten auf Grundlage einer Menge von möglichen Lösungen für ein spezifisches Problem, wobei in Anlehnung an die biologischen Begriffe die einzelne Lösung Individuum und die Gesamtmenge der Lösungen Population genannt wird. Das Ziel eines Genetischen Algorithmus ist es, aus einer großen Anzahl möglicher Lösungen für ein Problem eine oder mehrere möglichst gute Lösungen herauszufinden. Besonders interessant ist die Methode zur Lösung von Problemen mit hoher Komplexität und dementsprechend großem Zustandsraum, da eine analytische Lösung derartiger Probleme oft nicht möglich ist.

Das Grundkonzept der Genetischen Algorithmen basiert im Wesentlichen auf Arbeiten von John Holland, der sich als einer der ersten Wissenschaftler mit der Beschreibung und Analyse adaptiver Systeme beschäftigt hat. Den Entwurf des Konzepts, das heute unter dem Begriff Genetischer Algorithmus (im Folgenden auch GA genannt) große Verbreitung gefunden hat, nannte Holland ursprünglich reproductive plan (Holland, 1992). Obwohl oder vielleicht gerade weil dieses Konzept eine sehr einfache Version eines Genetischen Algorithmus darstellt, wird im Folgenden mit einer detaillierten Vorstellung dieses in der heutigen Literatur oft kanonischer GA genannten Verfahrens begonnen. Anschließend wird auf einige ausgewählte interessante Erweiterungen und Modernisierungen sowie Hollands Schematheorie eingegangen.

2.3.1 Funktionsweise

Um die elementare Funktionsweise eines Genetischen Algorithmus zu verdeutlichen, wird hier der kanonische GA nach Holland vorgestellt (vgl. Nissen (1997)). Jedes Individuum a⃗ wird als Bitstring dargestellt, dessen Länge L je nach Anwendung auf eine feste Anzahl von Bits festgelegt wird. Dabei wird eine binäre Darstellung gewählt, das heißt die Bits können entweder den Wert 0 oder 1 haben:

a⃗ = (a_{1}, a_{2}, …, a_{L−1}, a_{L}) ∈ {0, 1}^{L}

Der Bitstring a⃗ wird Genotyp des Individuums genannt. Jeder Genotyp wird in n Segmente variabler Länge aufgeteilt. Analog zur Betrachtung des gesamten Strings als interne Repräsentation einer Lösung entspricht jedes Segment der internen Repräsentation einer Variable des zu lösenden Optimierungsproblems.

Man betrachtet bei einem Optimierungsproblem eine zu maximierende Zielfunktion F (x⃗), die im Kontext Genetischer Algorithmen auch Fitnessfunktion genannt wird. x⃗ = x_{1}, x_{2}, …, x_{n} stellt den Vektor aller Variablen der Funktion dar. Da durch die binäre Codierung die Anzahl verschiedener Werte für eine Variable beschränkt ist, muss für jede Variable x_{j} mit (j = 1, 2, …, n) festgelegt werden, welchen Wertebereich sie annehmen kann. Auf die Verfahren binärer Codierungen wird in Abschnitt 2.3.3 noch näher eingegangen. Ziel des GA ist es, einen Eingabevektor x⃗ zu finden, der die Fitnessfunktion maximiert.

In Anlehnung an das biologische Vorbild wird der Bitstring auch als Chromosom, eine bestimmte Bitposition im String als Gen und deren konkreter Wert analog dazu als Allel bezeichnet. Eine mögliche Lösung wird Individuum genannt, wobei hier das konkrete Ergebnis einer einzelnen Lösung als Phänotyp und ihre interne binäre Repräsentation als Genotyp des Individuums bezeichnet wird.

2.3.2 Schrittweiser Ablauf

Im Folgenden soll der Ablauf eines Genetischen Algorithmus schrittweise beschrieben werden.

Initialisierung

Als erster Schritt muss eine initiale Population P von μ Individuen a⃗_{i} mit (i = 1, 2, …, μ) erzeugt werden, wobei die Anzahl μ der Individuen je nach Anwendung sehr unterschiedliche Werte besitzen kann. In den meisten Fällen wird die Ausgangspopulation stochastisch erzeugt, d.h. sämtliche Bits aller Genotypen a⃗_{i} werden in allen erzeugten Individuen stochastisch unabhängig voneinander per Zufall auf 0 oder 1 gesetzt.

Bewertung der Lösungen

Um einen Genetischen Algorithmus erfolgreich einsetzen zu können, benötigt man eine geeignete Fitnessfunktion F. a⃗_{i} wird von F auf seinen Fitnesswert abgebildet. Geht man von einer zu maximierenden Zielfunktion F aus, so folgt aus einem hohen Fitnesswert eine gute Eignung des Individuums für das zu lösende Problem. Der Erfolg eines Genetischen Algorithmus hängt in hohem Ausmaß von der Wahl einer geeigneten Fitnessfunktion ab.

Selektion und Replikation

Im Selektionsschritt werden aus der aktuellen Population P diejenigen Individuen ausgewählt, die als „Eltern“ für die nächste Generation fungieren sollen. Es werden n Individuen stochastisch ausgewählt, wobei n eine gerade Zahl zwischen 2 und μ sein muss. Jedes Individuum a⃗_{i} ∈ P besitzt eine spezifische Selektionswahrscheinlichkeit p_{s}:

p_{s}(a⃗_{i}) = \frac{F (a⃗_{i})}{∑_{j=1}^{μ} F (a⃗_{j})}

Dieses Selektionsverfahren wird fitnessproportionale Selektion genannt und zählt zu den nicht diskriminierenden Selektionsverfahren (engl. not extinctive), so genannt da jedes Individuum eine positive Selektionswahrscheinlichkeit besitzt und damit eine theoretische Chance auf Reproduktion besitzt. Einzelne Individuen dürfen beliebig oft gewählt werden, was zur Folge hat, dass sich in der Praxis Individuen mit hohem Fitnesswert mehrmals und solche mit niedrigem Fitnesswert selten bis gar nicht „fortpflanzen“ können.

In der Literatur wird hierzu gerne der anschauliche Vergleich mit einem Glücksrad benutzt, welches in μ Abschnitte eingeteilt ist. Jeder Abschnitt entspricht einem Individuum aus P und hat eine der Selektionswahrscheinlichkeit des Individuums entsprechende Breite auf dem Glücksrad. Das Rad wird n-mal gedreht und das Ergebnis jeder Drehung festgehalten. Aufgrund des Vergleichs wird dieses Auswahlverfahren auch Roulette-Wheel-Selektion genannt.

Von den zur Reproduktion ausgewählten Individuen aus der Population P werden Kopien erstellt und in einen Behälter M_{t} gelegt, in welchen n Individuen passen. Nach n Selektionsvorgängen erhält man ein M_{t}, das mit n Kopien von Individuen aus P gefüllt ist. Dabei darf jedes Individuum aus P beliebig oft vom Selektionsalgorithmus ausgewählt und in M_{t} kopiert werden, weswegen man von einer stochastischen Auswahl mit Zurücklegen spricht. Der beschriebene Kopierprozess wird als Replikation bezeichnet.

Reproduktion

Die folgenden Schritte 1 bis 4 müssen jeweils \frac{n}{2}-mal durchlaufen werden, da in jedem Durchlauf zwei Individuen aus M_{t} reproduziert werden.

Schritt 1: Partnerwahl Es werden zufällig zwei Elternindividuen a⃗_{E_{1}} und a⃗_{E_{2}} aus M_{t} ausgewählt, aus denen in den nächsten drei Teilschritten zwei Nachkommen entstehen werden. Dabei wird in dieser einfachen Variante des GA jedes Individuum in M_{t} mit gleicher Wahrscheinlichkeit \frac{1}{n} gezogen. Die Fitness der einzelnen Individuen wird bei der Auswahl nicht mehr berücksichtigt, weil schon die Wahrscheinlichkeit für die Übernahme in M_{t} von den jeweiligen Fitnesswerten abhängt und Individuen mit außergewöhnlich hoher Fitness statistisch häufiger in M_{t} vorhanden sind.

Die stochastische Auswahl aus M_{t} erfolgt „ohne Zurücklegen“, das bedeutet jedes Individuum kann nur einmal gewählt werden und steht im nächsten Durchlauf nicht mehr zur Verfügung.

Schritt 2: Crossover Das Crossover im Genetischen Algorithmus entspricht der Rekombination des Erbguts zweier sich miteinander fortpflanzender Lebewesen in der Natur. Es wird als zentraler Operator des GA betrachtet, da durch das Crossover die größten Veränderungen im digitalen Genpool passieren.

Im hier betrachteten kanonischen GA wird als einfachste Variante das Ein-Punkt-Crossover verwendet. Im Vorfeld wird eine Wahrscheinlichkeit p_{xover} festgelegt, die bestimmt, mit welcher Wahrscheinlichkeit bei der Reproduktion ein Crossover stattfinden soll. Dabei wird ein stochastischer Auswahlprozess benutzt, der mit Wahrscheinlichkeit p_{xover} für ein Crossover und mit Wahrscheinlichkeit 1 − p_{xover} gegen ein Crossover entscheidet. Im Allgemeinen wird p_{xover} in einer Größenordnung von p_{xover} ≥ 0, 6 gewählt. Bei zu groß gewähltem p_{xover} besteht die Gefahr, dass sinnvolle Ergebnisse und auftretende Schemata zerstört werden (siehe Abschnitt 2.3.4).

Entscheidet der Zufall gegen ein Crossover, so werden die beiden Elternstrings (a⃗_{E_{1}} und a⃗_{E_{2}}) unverändert in zwei Nachkommenstrings (a⃗_{K_{1}} und a⃗_{K_{2}}) kopiert:

a⃗_{K_{1}} = a⃗_{E_{1}}
a⃗_{K_{2}} = a⃗_{E_{2}}

Soll ein Crossover stattfinden, so wird stochastisch ein Crossover-Punkt c zwischen 1 und L − 1 festgelegt. Beim Kopieren der Elternstrings in die Nachkommenstrings werden nun jeweils die Bits hinter dem Crossover-Punkt mit denen des Reproduktionspartners ausgetauscht, was zur Folge hat, dass zwei Individuen entstehen, die aus dem Erbgut der Eltern zusammengesetzt sind:

a⃗_{K_{1}} = (a_{E_{1},1}, a_{E_{1},2}, …, a_{E_{1},c}, a_{E_{2},c+1}, …, a_{E_{2},L})
a⃗_{K_{2}} = (a_{E_{2},1}, a_{E_{2},2}, …, a_{E_{2},c}, a_{E_{1},c+1}, …, a_{E_{1},L})

Schritt 3: Mutation Im Allgemeinen wird die Mutation als weniger bedeutend für die Funktion eines Genetischen Algorithmus eingestuft als das Crossover. Sie ist allerdings wichtig um zu gewährleisten, dass die Population auch dann noch Veränderungen aufzeigt, wenn sich alle Individuen weitgehend ähnlich sind und durch Rekombination kaum noch Veränderungen zu erreichen sind.

Für die Mutation wird ebenso eine feste Wahrscheinlichkeit festgelegt wie für das Crossover, nur dass die Mutationswahrscheinlichkeit p_{mut} meist sehr viel kleiner gewählt wird. Übliche Werte sind etwa p_{mut} = 0, 01 oder p_{mut} = 0, 001. Jedes Bit in jedem Individuum der Population wird nun mit dieser Wahrscheinlichkeit p_{mut} invertiert. Ein Wert von p_{mut} = 0, 01 hätte beispielsweise zur Folge, dass im Mittel eines von hundert Bits invertiert würde.

Schritt 4: Übergang in die neue Population Die beiden Nachkommen a⃗_{K_{1}} und a⃗_{K_{2}} werden in die neue Population übernommen. Für jeden Nachkommen wird ein Individuum aus der ursprünglichen Population entfernt, wobei die Auswahl der zu entfernenden Individuen analog zur Auswahl der Elternindividuen erfolgt, mit dem Unterschied, dass Individuen mit niedrigerem Fitnesswert mit höherer Wahrscheinlichkeit entfernt werden.

Die Schritte 1 bis 4 werden wiederholt, bis alle Individuen aus M_{t} verarbeitet wurden. Die Populationsgröße μ bleibt dabei konstant, weil für jedes neu entstandene Individuum ein anderes Individuum aus der Population entfernt wird.

Abbruchkriterium

Die Schritte Bewertung, Selektion, Replikation und Reproduktion werden nun wiederholt, bis ein festgelegtes Abbruchkriterium greift. Abbruchkriterien können verschiedenartig sein, z.B. kann man eine Maximallaufzeit oder eine maximale Generationenzahl t_{max} definieren, nach deren Ablauf der Algorithmus terminiert. Alternativ kann man die Termination des GA auch von Qualitätsmerkmalen des Ergebnisses abhängig machen. Wenn z.B. über mehrere Generationen keine Verbesserung in den Ergebnissen mehr beobachtet werden kann oder sich die Individuen einer Population weitgehend gleichen, ist meist keine Verbesserung mehr zu erwarten und ein Abbruch vermutlich sinnvoll. Diese Festlegung eines Abbruchkriteriums ist notwendig, da Genetische Algorithmen mathematisch gesehen nicht konvergieren. Nach Termination des Genetischen Algorithmus wird im Allgemeinen die beste der gefundenen Lösungen (sprich das Individuum mit dem höchsten Fitnesswert) ausgegeben.

2.3.3 Codierung des Genotyps

Bei den meisten Varianten Genetischer Algorithmen wird eine binäre Form der Lösungsrepräsentation oder Codierung verwendet. Es muss festgelegt werden, von welcher Art der codierte Wert ist, da ein Bitstring theoretisch alles mögliche repräsentieren kann, z.B. eine Fließkommazahl, eine ganze Zahl, oder auch einen Buchstaben oder einen Farbwert. Auch wenn in unserem Zusammenhang hauptsächlich numerische Werte interessant sind, muss doch festgelegt werden, in welchen Grenzen sich die codierten Werte befinden, und ob sie als ganze Zahlen oder Fließkommazahlen zu interpretieren sind. Selbst bei Festlegung auf einen bestimmten Datentyp ist zu spezifizieren, welche Codierung genau verwendet wird.

In den meisten Fällen arbeiten Genetische Algorithmen mit numerischen Werten, die ganze Zahlen repräsentieren. Der hierfür benutzte Standard-Binärcode ist allerdings nicht unbedingt die beste Lösung. Der Grund dafür ist, dass im Standard-Binärcode jedes Bit eine unterschiedliche Wertigkeit besitzt: wird das Bit mit der niedrigsten Wertigkeit verändert, ändert sich der Wert der codierten Zahl nur um 1. Wird dagegen das höchstwertige Bit geändert, hat das je nach Länge des Bitstrings einen ungleich größeren Einfluss auf den Zielwert. Arbeitet man beispielsweise mit Binärstrings der Länge L = 8, kann man mit einem String 2^{8} = 256 verschiedene Werte codieren. Bei der Standardcodierung hat das letzte Bit den Wert 2^{0} = 1 und das erste Bit den Wert 2^{7} = 128. Das bedeutet, das Kippen des letzten Bits ändert den Zielwert um 1, beim ersten Bit ändert er sich um 128.

Diese Diskrepanzen möchte man bei Genetischen Algorithmen möglichst vermeiden, daher wird häufig eine Codierung verwendet, die als Gray-Code bekannt ist. Die Besonderheit des Gray-Code ist, dass sich aufeinanderfolgende Dezimalzahlen in Gray-Codierung nur in jeweils einem Bit unterscheiden, was beim Standard-Binärcode nicht immer der Fall ist. Eine Auswahl von Dezimalzahlen mit entsprechender binärer Gray-Code- und Standardcodierung ist in Tabelle 2.1 zu finden.

2.3.4 Schematheorie

Der Begriff des Schemas wurde von John Holland (1975) zur formalen Beschreibung der von ihm untersuchten Vorgänge in adaptiven Systemen eingeführt. Hollands Defi-

dezimal Standard binär Gray-Code binär
0  00000000  00000000
1  00000001  00000001
2  00000010  00000011
3  00000011  00000010
4  00000100  00000110
5  00000101  00000111
6  00000110  00000101
7  00000111  00000100
8  00001000  00001100
9  00001001  00001101
10  00001010  00001111
31  00011111  00010000
32  00100000  00110000
63  00111111  00100000
64  01000000  01100000
127  01111111  01000000
128  10000000  11000000
255  11111111  11111111

Tabelle 2.1: Zahlenwerte in Dezimal-, Standardbinär- und Gray-Codierung

nition des Schemas ist ein Muster, welches eine Menge von Strings definiert, indem es Bits an bestimmten Positionen im String festlegt. Zur Veranschaulichung kann man sich ein Schema als Schablone vorstellen, die über die einzelnen Strings gelegt und auf Übereinstimmung getestet wird. Die ursprüngliche Definition bezog sich auf den einfachen kanonischen Genetischen Algorithmus, mit binären Individuen bzw. Strings und Ein-Punkt-Crossover, wie er in Abschnitt 2.3.1 vorgestellt wurde. Später wurde die Schematheorie von anderen Autoren unter anderem auf nicht-binäre Lösungsrepräsentationen verallgemeinert. Hier wird das ursprüngliche Konzept dargestellt, wie es u.a. in Holland (1986, 1992) zu finden ist.

Die zentrale Aussage der Schematheorie ist, dass sich Schemata mit bestimmten Eigenschaften in evolutionären Prozessen (wie z.B. Genetischen Algorithmen) besser durchsetzen können als andere. Im Zusammenhang der vorliegenden Arbeit ist die Schematheorie relevant, weil sich die Idee der Schemata auf die Klassifikatoren der bauenden Wespenagenten übertragen lässt und die aus ihr folgenden Überlegungen in die Konzipierung des LCS miteinfließen.

Legt man eine binäre Codierung zugrunde, das heißt für jeden String a⃗ mit Länge L gelte

a⃗ ∈ (0, 1)^{L}

so gilt für ein Schema H analog

H ∈ (0, 1, ∗)^{L}

Ein Schema kann somit für jedes der L Bits entweder festsetzen, dass es 0 oder 1 sein muss, oder aber mittels des don’t-care-Symbols ∗ anzeigen, dass der Wert des entsprechenden Bits für das Schema nicht relevant ist. Ein String, der einem Schema H entspricht, wird Instanz von H genannt. Hierbei kann jeder beliebige binäre String mit Länge L Instanz von genau 2^{L} Schemata sein, da für jedes Bit im String gilt, dass es im korrespondierenden Schema entweder gleich oder egal sein muss.

Man betrachte beispielsweise Strings der Länge L = 5 und das Schema H_{1} = ∗1∗10. Dieses Schema steht für alle Individuen mit Länge L = 5, deren zweites Bit eine 1, viertes Bit eine 1 und fünftes Bit eine 0 ist. Dies entspricht der folgenden Menge von Individuen: {01010, 01110, 11010, 11110}. Diese vier Individuen sind also Instanzen des Schemas H_{1}. Wichtig ist hierbei zu verstehen, dass jedes Individuum Instanz verschiedener Schemata sein kann. So sind alle Instanzen des Schemas H_{1} auch gleichzeitig Instanzen des Schemas H_{2} = ∗1∗1∗. Die Menge aller Instanzen von H_{1} ist eine echte Teilmenge aller Instanzen von H_{2}, da H_{2} ein Bit weniger definiert als H_{1}.

In diesem Zusammenhang wird die Ordnung o(H) eines Schemas H als Anzahl der in H festgelegten Bits definiert. Beispielsweise ist o(H_{1}) = 3 und o(H_{2}) = 2. Als weitere Eigenschaft wird die definierende Länge δ(H) eines Schemas H als Abstand zwischen erstem und letztem vorgegebenen Bit festgelegt, also δ(H_{1}) = 5 − 2 = 3 und δ(H_{2}) = 4 − 2 = 2.

So wie in Abschnitt 2.3.2 die Fitness eines einzelnen Individuums definiert wurde, kann ebenso die Fitness eines Schemas bewertet werden. Es bezeichnet hierbei I(H) die Menge aller möglichen Instanzen von H, P (t) die Population zum Zeitpunkt t und N(H, t) die tatsächliche Anzahl von Instanzen von H in der Population zum Zeitpunkt t.

Die durchschnittliche Fitness aller Instanzen von H zum Zeitpunkt t wird folgendermaßen berechnet:

F (H, t) = \frac{∑ F (a⃗(t))}{N(H, t)} für alle a⃗(t) ∈ I(H) ∩ P (t)  (2.1)

Für eine Anzahl von μ Individuen in der Population ergibt sich die durchschnittliche Fitness \overline{F} (t) aller Individuen in P (t):

\overline{F} (t) = \frac{1}{μ} · ∑_{i=1}^{μ} a⃗_{i}(t)  (2.2)

Im Verhältnis von F (H, t) zu \overline{F} (t) drückt sich nun implizit die Qualität oder Fitness des Schemas H aus. Unter Vernachlässigung externer Einflussfaktoren wie Mutation und Crossover ergibt sich für die Anzahl der Instanzen von H in der nächsten Generation folgende Differenzengleichung:

N(H, t + 1) = N(H, t) · \frac{F (H, t)}{\overline{F} (t)}  (2.3)

Dies bedeutet, dass das Verhältnis von F (H, t) zu \overline{F} (t) darüber bestimmt, ob sich ein Schema H in einer Population durchsetzt oder nicht. Falls die durchschnittliche Fitness der Instanzen eines bestimmten Schemas H über dem Durchschnitt aller Individuen liegt (F (H, t) > \overline{F} (t)), so wird die Anzahl der Instanzen dieses Schemas von einer Generation zur nächsten zunehmen und über die Zeit exponentiell wachsen. Gilt dagegen F (H, t) < \overline{F} (t), so kann man eine Verminderung der Instanzen von H in der nächsten Generation sowie eine exponentielle Abnahme im zeitlichen Verlauf erwarten.

Durch Mutation und Crossover wird das Überleben einzelner Individuen und demzufolge bestimmter Schemata zusätzlich beeinflusst. Die Wahrscheinlichkeit, dass ein Schema H eine Mutation bzw. ein Ein-Punkt-Crossover überlebt, kann über die Ordnung o(H) und die definierende Länge δ(H) berechnet werden.

Wie bereits erwähnt, wird bei der Mutation jedes Bit stochastisch unabhängig mit der Mutationswahrscheinlichkeit p_{mut} invertiert. Die Wahrscheinlichkeit, dass ein einzelnes Bit eines Schemas H einen Mutationsschritt überlebt, ist daher 1 − p_{mut}, und für das gesamte Schema H mit o(H) Bits ergibt sich folgende Überlebenswahrscheinlichkeit bei der Mutation:

p_{mu_survive}(H) = (1 − p_{mut})^{o(H)}

Für p_{mut} ≪ 1, also eine sehr geringe und in der Praxis oft gegebene Mutationswahrscheinlichkeit gilt näherungsweise:

p_{mu_survive}(H) = (1 − p_{mut})^{o(H)} ≈ 1 − p_{mut} · o(H)  (2.4)

Die Weiterverbreitung eines Schemas wird aber nicht nur von der Mutation, sondern auch vom Crossover bedroht. Betrachtet man als einfachste Variante das Ein-Punkt-Crossover, so wird ein Schema H durch das Crossover genau dann zerstört, wenn ein Crossover-Punkt zwischen erstem und letztem definierendem Bit des Schemas gewählt wird. Auf der anderen Seite muss der Fall berücksichtigt werden, dass beide Eltern Instanzen von H sind, da das Schema dann auch bei einem Austausch bestehen bleibt. Für eine allgemeine Crossover-Wahrscheinlichkeit p_{xover} und eine Population von μ Individuen mit Stringlänge L ergibt sich für H folgende Überlebenswahrscheinlichkeit beim Ein-Punkt-Crossover:

p_{xo_survive}(H) = 1 − p_{xover} · \frac{δ(H)}{L − 1} · (1 − \frac{N(H)}{μ})  (2.5)

Bei großen heterogenen Populationen ist die Wahrscheinlichkeit für den Fall, dass beide Elternindividuen Instanzen des Schemas H sind, vergleichsweise gering. Somit ist die Zahl der Individuen, die ein Schema H repräsentieren, im Vergleich zur Gesamtpopulation sehr gering. Es gilt also N(H) ≪ μ und daraus resultierend 1 − \frac{N(H)}{μ} ≈ 1. Als vereinfachte Näherung für Gleichung 2.5 wird daher auch folgende Gleichung verwendet:

p_{xo_survive}(H) = 1 − p_{xover} · \frac{δ(H)}{L − 1} · (1 − \frac{N(H)}{μ}) ≈ 1 − p_{xover} · \frac{δ(H)}{L − 1}  (2.6)

Aus den Gleichungen 2.3, 2.4 und 2.5 lässt sich die Ungleichung zusammensetzen, die als Hollands Schematheorem (Holland, 1992) bekannt wurde:

N(H, t+1) ≥ N(H, t)· \frac{F (H, t)}{\overline{F} (t)} ·[1−p_{xover} · \frac{δ(H)}{L − 1} ·(1− \frac{N(H)}{μ})]·(1−p_{mut})^{o(H)} (2.7)

Um die Gleichung 2.7 zu vereinfachen, werden die Näherungsgleichungen 2.4 und 2.6 verwendet, woraus die folgende Version des Schematheorems resultiert:

N(H, t + 1) ≥ N(H, t) · \frac{F (H, t)}{\overline{F} (t)} · [1 − p_{xover} · \frac{δ(H)}{L − 1} − p_{mut} · o(H)]  (2.8)

Die zentralen Aussagen des Schematheorems sind:

1. Schemata mit überdurchschnittlicher Fitness (F (H, t) > \overline{F} (t)) überleben mit höherer Wahrscheinlichkeit.

2. Je kleiner die Ordnung o(H) des Schemas, desto höher die Überlebenswahrscheinlichkeit

3. Je kürzer die definierende Länge δ(H), desto höher die Überlebenswahrscheinlichkeit

Eine höhere Überlebenswahrscheinlichkeit bedeutet gleichzeitig, dass sich die Instanzen des betreffenden Schemas gegen andere Individuen besser durchsetzen können. Instanzen von Schemata mit überdurchschnittlicher Fitness, niedriger Ordnung und kurzer definierender Länge nehmen im Laufe mehrerer Generationen exponentiell zu.

Goldberg (1989) nannte diejenigen Schemata mit oben angeführten Eigenschaften building blocks und formulierte die anschauliche aber inzwischen umstrittene Building-Block-Hypothese, welche besagt, dass ein Genetischer Algorithmus seine endgültige Lösung aus einzelnen building blocks zusammensetzt:

2.4 Learning Classifier Systems

„Because highly fit schemata of low defining length and low order play such an important role in the action of genetic algorithms, we have already given them a special name: building blocks. Just as a child creates magnificent fortresses through the arrangement of simple blocks of wood, so does a genetic algorithm seek near optimal performance through the juxtaposition of short, low-order, high-performance schemata, or building blocks.“ (Goldberg, 1989, S.41)

Der von Goldberg hier benutzte Vergleich eines Genetischen Algorithmus mit einem Kind, das komplexe Gebilde aus vielen kleinen Holzklötzen erschafft, veranschaulicht sehr klar auch den zentralen Kritikpunkt an der Building-Block-Hypothese: sie vereinfache die Funktionsweise des GA zu stark. Kritiker sehen den Fehler unter anderem darin, dass vorausgesetzt wird, das vom GA zu lösende Problem ließe sich in voneinander unabhängige Teilprobleme aufspalten, was in der Realität eher die Ausnahme darstellt.

2.4 Learning Classifier Systems

Da die Agenten des implementierten Simulationsmodells nach dem Vorbild der Learning Classifier Systems entworfen wurden, wird die Funktionsweise dieser Systeme im Folgenden erläutert. Lernende Klassifizierende Systeme (LCS, engl. Learning Classifier Systems) gehen wie die Genetischen Algorithmen zurück auf Arbeiten von Holland (1976). LCS wurden als regelbasierte Systeme für Maschinelles Lernen konzipiert, die ihr Verhalten durch Verarbeitung von Rückmeldungen aus ihrer Umgebung optimieren sollen. Interessant sind LCS für die Lösung von Problemen, deren Bewertung nicht sofort nach einer einzelnen Aktion, sondern erst nach mehreren Aktionsschritten erfolgen kann.

Abbildung 2.7: Illustration des Animat-Problems (Bernauer, 2007)

Ein einfaches Beispiel für derartige Fragestellungen ist das Animat-Problem (Bernauer, 2007), bei dem es darum geht, dass eine Figur sich durch ein Labyrinth bewegt und auf schnellstem Weg zu einem Ziel kommen soll (Abbildung 2.7). Die Figur bekommt eine Belohnung, wenn sie das markierte Ziel erreicht. Da sich die Figur in jedem Zeitschritt aber nur um ein Feld weiterbewegen kann, stellt sich die zentrale Frage, wie die Figur lernen kann, dass vor Erreichen des Ziels und der Belohnung scheinbar sinnlose (weil unbelohnte) Schritte ausgeführt werden müssen.

Abbildung 2.8: Schematische Darstellung eines Learning Classifier System (verändert, nach Bernauer (2007))

Ein LCS besteht im Wesentlichen aus einem beliebig großen Satz von Klassifikatoren, welche das Verhalten des LCS steuern. Jeder Klassifikator R besteht für sich aus einem Detektor-String B, einem Effektor-String A und einem numerischen Stärkewert S (siehe Abbildung 2.8). Für den Begriff Klassifikator wird synonym auch der Begriff Regel verwendet, deswegen wird die Menge aller im LCS vorhandenen Klassifikatoren als Regelsatz R bezeichnet. Nachrichten aus der Umgebung werden von Detektoren angenommen und mit den Detektor-Strings der einzelnen Klassifikatoren verglichen. Die Codierung und Länge der Nachrichten muss bekannt sein und mit den Detektor-Strings übereinstimmen. Im einfachsten Fall wird eine binäre Codierung mit fester Stringlänge verwendet.

In LCS ist jede Regel mit einem numerischen Wert verknüpft, der ihre Stärke oder auch Fitness definiert. Um Verwechslungen mit der globalen Fitness der Wabenstrukturen zu vermeiden soll im Folgenden der Begriff Stärke verwendet werden. Die Stärke eines Klassifikators beeinflusst wesentlich die Wahrscheinlichkeit für seine Anwendung. In Hollands Modell wird jedem erfüllten Klassifikator ein bestimmter Wert zugeordnet, der bid (dt. Gebot) genannt wird. Holland vergleicht die Auswahl eines Klassifikators mit einer Auktion, in der jeder passende Klassifikator ein Gebot abgibt und die Höhe des Gebots die Wahrscheinlichkeit bestimmt, mit der der Klassifikator tatsächlich Anwendung findet. Außer von der Stärke S(R) des Klassifikators R ist bid(R) noch abhängig von einem Wert, den Holland Spezifizität sp(R) nennt. Die Spezifizität des Klassifikators entspricht der Anzahl der Stellen in seinem Detektor-String B, die an der entsprechenden Stelle im Input-String I einen bestimmten Wert erwarten. Bei der hier verwendeten binären Codierung entspricht das die Anzahl der Nullen und Einsen in B. Das sogenannte don’t-care-Symbol bedeutet, dass der Wert von I an dieser Stelle nicht relevant für die Regel ist. In Abbildung 2.8 wird das don’t-care-Symbol als # bezeichnet, sonst meistens als ∗.

Sind in einem Zeitschritt mehrere Regeln gleichzeitig gültig, so wird anhand ihrer entsprechenden bid-Werte entschieden, welche Regel zur Anwendung kommt. Wird ein Input I als passend zu einem Klassifikator R klassifiziert, wird R einer Liste von passenden Klassifikatoren (engl. match set) M_{t} hinzugefügt. Nach einem stochastischen Verfahren wird aus allen Klassifikatoren in M_{t} derjenige ausgewählt, der ausgeführt werden soll, wobei der Stärkewert S in diese Auswahl miteinfließt. Der Effektor-String A der ausgewählten Regel bestimmt die von den Effektoren auszuführende Aktion des LCS. Analog zu den Detektoren, die die „Sinnesorgane“ des LCS repräsentieren, bezeichnen Effektoren diejenigen Komponenten des LCS, die aktiv mit der Umwelt kommunizieren bzw. diese manipulieren.

Von der Umgebung bekommt das LCS Rückmeldungen darüber, wie das Verhalten des LCS zu bewerten ist. Eine positive Rückmeldung wird als Belohnung und eine negative Rückmeldung als Bestrafung interpretiert. Allerdings kommen diese Rückmeldungen im Allgemeinen nicht nach jeder einzelnen Aktion, so dass das LCS dafür sorgen muss, die positive bzw. negative Rückmeldung an die verantwortlichen Klassifikatoren zurückzugeben. Ziel dieses Verfahrens ist es, dass sich das System mit der Zeit an das erwünschte Verhalten anpasst, da der Stärkewert von Klassifikatoren mit positiver Rückmeldung erhöht und von solchen mit negativer Rückmeldung abgeschwächt wird. Positiv bewertete Regeln sollen in Zukunft mit höherer Wahrscheinlichkeit ausgewählt werden als negativ bewertete.

Im Folgenden werden die Bestandteile eines einfachen Learning Classifier Systems formal eingeführt. Die Darstellung geht von einer binären Codierung aus und orientiert sich an Weicker (2002). Eine schematische Darstellung der Funktionsweise ist in Abbildung 2.8 zu sehen.

Ein Klassifikator R besteht aus einer Bedingung (Detektor-String) B der Länge l, einer Ausgabe (Effektor-String) A der Länge m und einem numerischen Stärkewert S. Jeder binäre Input-String I hat wie der Detektor-String die Länge l.

Für jede Bedingung (Detektor-String) B gilt:

B ∈ B = {0, 1, ∗}^{l}  (2.9)

Für jede Ausgabe (Effektor-String) A gilt:

A ∈ A = {0, 1}^{m}  (2.10)

Für jeden Stärkewert S gilt:

S ∈ ℝ  (2.11)

Die Stärkewerte S werden bei Initialisierung des Systems auf bestimmte Werte gesetzt, was in der implementierten Version mit Zufallszahlen geschieht.

Jeder Klassifikator R besteht also aus einer Bedingung B, einer Ausgabe A und einem Fitnesswert S:

R = (B, A, S) ∈ B × A × ℝ  (2.12)

Die Gesamtheit aller Klassifikatoren eines LCS wird Regelsatz R genannt:

R ⊂ B × A × ℝ  (2.13)

Ein Klassifikator R heißt genau dann aktiviert oder passend zum Zeitpunkt t, wenn die Eingabe I zum Zeitpunkt t mit der Bedingung des Klassifikators übereinstimmt.

In diesem Zusammenhang bedeutet Übereinstimmung, dass jedes Zeichen des Input-Strings I dem entsprechenden Zeichen im Detektor-String B entspricht, außer wenn bei B an der Stelle ein don’t-care-Symbol ∗ steht, was bedeutet dass die Zeichen nicht übereinstimmen müssen. Formal geschrieben heißt das mit I ∈ I = {0, 1}^{l}, dass ein Klassifikator R zum Zeitpunkt t mit Input I aktiviert ist, wenn folgendes Prädikat wahr ist:

⋀_{i=1}^{l}(B_{i} ≠ ∗ ⇒ B_{i} = I_{i})  (2.14)

B_{i} bezeichnet das Zeichen an Stelle i im Detektor-String B.

Alle zum Zeitpunkt t aktivierten Klassifikatoren im Regelsatz R werden zum match set M_{t} hinzugefügt. Werden verschiedene Ausgaben von den Klassifikatoren in M_{t} vorgeschlagen, so wird durch ein stochastisches Verfahren für jede Ausgabe A eine Auswahlwahrscheinlichkeit berechnet. Diese berücksichtigt sowohl den Stärkewert S als auch die Spezifizität sp aller Klassifikatoren R in M_{t}, die A vorschlagen. sp ist die Anzahl der Zeichen in B, die für die entsprechende Stelle in I ein spezifizisches Zeichen verlangen. Grundsätzlich sind das alle Zeichen, die kein don’t-care-Symbol ∗ sind. Es gilt z.B. sp(∗∗0011∗∗) = 4 und sp(101∗∗010) = 6. Je höher Spezifizität und Fitness von R sind, desto höher ist die Wahrscheinlichkeit dafür, dass R ausgewählt wird.

Das Gebot eines Klassifikators R mit Stärke S(R) berechnet sich wie folgt:

bid(R) = S(R) · log_{2}[sp(R)]  (2.15)

Die Spezifizität wird logarithmisch in die Formel mit einberechnet, um ihren Einfluss gegenüber der Stärke zu reduzieren.

Die Aktion A der so ausgewählten Regel wird ausgeführt, und das System wartet auf den nächsten Input I zum Zeitpunkt t + 1.

Learning Classifer Systeme kombinieren zwei grundlegende Mechanismen für Maschinelles Lernen (Bull und Kovacs, 2005). Beide Mechanismen adressieren jeweils ein grundlegendes Teilproblem, das in Zusammenhang mit LCS auftritt. Das erste Teilproblem wird Credit Assignment oder „apportionment of credit problem“ (Geyer-Schulz, 1995) genannt und dreht sich um die Frage, wie das System entscheiden soll, welche der zu einem Zeitpunkt t aktivierten Regeln zur Erreichung eines Ziels zu einem zukünftigen Zeitpunkt t + n beigetragen haben und wie das positive bzw. negative Feedback auf diese Regeln verteilt werden soll (siehe Abschnitt 2.4.1). Das zweite Teilproblem ist das Finden neuer Klassifikatoren (engl. Rule Discovery), wofür in LCS ein Genetischer Algorithmus verwendet wird. Die Grundprinzipen Genetischer Algorithmen wurden bereits in Abschnitt 2.3.1 erläutert, wobei die Anwendung im Kontext der LCS in Abschnitt 2.4.2 beschrieben wird.

2.4.1 Credit Assignment: Reinforcement Learning

In einem Learning Classifier System werden die Fitnesswerte der einzelnen Klassifikatoren durch Rückmeldung aus der Umgebung schrittweise angepasst, was Credit Assignment genannt wird. Das zugrundeliegende Verfahren heißt Reinforcement Learning (RL) (Sutton und Barto, 1998) und basiert darauf, dass Klassifikatoren mit positivem Effekt auf die Umgebung verstärkt und solche mit negativem Effekt abgeschwächt werden sollen. Eine mögliche Definition von Reinforcement Learning lautet „ […] learning from interaction with an environment, from the consequences of action, rather than from explicit teaching.“ (Sutton, 2004) Die Herausforderung für das System besteht darin, die Rückmeldung der Umgebung an alle beteiligten Klassifikatoren zu verteilen, da normalerweise nicht nach einem einzelnen Zeitschritt beurteilt werden kann, ob der Gesamteffekt auf die Umwelt positiv oder negativ ist. Sehr anschaulich wird dies bei Betrachtung eines Brettspiels wie Schach, wo oft erst nach sehr vielen Schritten beurteilt werden kann, ob ein Zug zu Beginn des Spiels gut oder schlecht war.

Die im ursprünglichen Modell von Holland (1975) eingesetzte Methode für das Credit Assignment wurde Bucket-Brigade-Algorithmus (BBA) genannt. Das System merkt sich in jedem Zeitschritt t alle passenden nach M_{t} übertragenen Regeln. Im nächsten Zeitschritt t + 1 wird das Gebot jeder ausgewählten Regel in einem sogenannten bucket abgespeichert. Der Inhalt dieses bucket wird dann zu gleichen Teilen unter den in Zeitschritt t aktivierten Regeln aufgeteilt (Bull und Kovacs, 2005). Das heißt, der Stärkewert S(R) wird mit dem entsprechenden Anteil des Inhalts des bucket verrechnet. Bekommt das System eine Rückkopplung aus der Umgebung, so wird diese Rückkopplung ihrerseits mit dem Stärkewert der letzten aktivierten Regel verrechnet.

Holland modellierte den Bucket-Brigade-Algorithmus bewusst in Analogie zu einem Wirtschaftskreislauf. Das System kann als Handelskette gesehen werden, in dem jede Regel als Geschäftspartner mit ihrer Stärke als Kapital agiert. In den meisten neueren LCS-Varianten wie XCS (Wilson, 1995) wird ein RL-Algorithmus namens Q Learning eingesetzt, der erstmals von Watkins (1989) beschrieben wurde.

2.4.2 Rule Discovery: Genetische Algorithmen

Das Finden neuer Klassifikatoren geschieht in Learning Classifier Systemen mithilfe Genetischer Algorithmen (GA, siehe Abschnitt 2.3). Es gibt verschiedene Möglichkeiten, den Genetischen Algorithmus im LCS einzusetzen, wobei grundsätzlich zwei Varianten der LCS unterschieden werden: Pittsburgh- und Michigan-LCS (Sigaud und Wilson, 2007). Pittsburgh-LCS, so genannt, weil der Ansatz von Smith (1980) an der University of Pittsburgh entwickelt wurde, setzen, wie oben beschrieben, einen GA auf einer Population von Regelsätzen ein. Im Gegensatz dazu betrachten Michigan-LCS, entwickelt von John Holland an der University of Michigan, den einzelnen Klassifikator als Individuum. Es wird also nur ein einziger Regelsatz betrachtet, der für den GA eine Population von Klassifikatoren darstellt, und der durch Reinforcement Learning und den Genetischen Algorithmus optimiert werden soll. Im Folgenden wird die Pittsburgh-Variante für den Einsatz Genetischer Algorithmen in LCS beschrieben, da diese im Rahmen der vorliegenden Arbeit für die Implementation verwendet wurde.

In Pittsburgh-LCS operiert ein Genetischer Algorithmus auf einer Population von Regelsätzen. Es werden mehrere Simulationsläufe mit verschiedenen Regelsätzen durchgeführt und die Ergebnisse der Simulationen jeweils von einer Fitnessfunktion F bewertet. Das Ergebnis dieser Bewertung wird Globaler Fitnesswert oder englisch Overall Fitness genannt. Zu jedem verwendeten Regelsatz wird der erzielte globale Fitnesswert gespeichert.

Der GA wählt nun nach einem stochastischen Selektionsverfahren Regelsätze aus und erzeugt durch Rekombination und Mutation (siehe Abschnitt 2.3) neue Regelsätze, die dann im nächsten Durchlauf getestet werden und im Idealfall bessere Ergebnisse erzielen. Als Selektionsverfahren wird hier die Roulette-Wheel-Selektion (siehe Abschnitt 2.3.2) verwendet, bei der die Wahrscheinlichkeit für die Auswahl eines Individuums, also eines Regelsatzes R, von seinem globalen Fitnesswert F (R) abhängt, also von der Rückmeldung der Umgebung.

2.5 Komplexität der Problemstellung

Die in der vorliegenden Arbeit betrachtete Fragestellung ist formal gesehen ein Optimierungsproblem. Die zentrale Frage lautet, wie man eine Struktur im zweidimensionalen Raum so erzeugen kann, dass eine festgelegte Fitnessfunktion maximiert wird. Die Gesamtheit aller möglichen Zustände des Wabengitters stellt den Zustandsraum des Problems dar. Als Zustand eines Punktes wurde die Art der dort gebauten Wabenzelle definiert. Bei einem Gitternetz mit W Punkten und n möglichen Zuständen eines einzelnen Punktes ergibt sich ein Zustandsraum der Größe n^{W}, was schon im einfachsten Fall von nur einem Wabentyp zu einem exponentiell zu W wachsenden Zustandsraum führt. Jeder Punkt hat in diesem Fall zwei mögliche Zustände - bebaut oder nicht bebaut - daher gilt n = 2 und für die Größe des Zustandsraums 2^{W}.

Da jede Fitnessfunktion, die die Qualität einer entstandenen Wabenstruktur beurteilen soll, von allen Zellen des Gitters abhängt, wächst daher auch die Berechnungszeit für die optimale Lösung der Fitnessfunktion exponentiell zu W, was die Fragestellung zu einem NP-vollständigen Problem macht. NP-vollständig bedeutet, dass ein solches Problem nicht in polynomieller Zeit lösbar ist, weil der Zustandsraum des Problems schneller wächst als polynomiell (in diesem Beispiel etwa exponentiell). NP-vollständige Probleme gelten in der Theoretischen Informatik als nicht effizient lösbar.

Eine Möglichkeit, dennoch akzeptable Lösungen für derartige Probleme zu finden, stellen heuristische Optimierungsverfahren dar. Diese werden dadurch charakterisiert, dass die gefundenen Lösungen nicht unbedingt ein globales Maximum der Zielfunktion darstellen, aber für viele Probleme trotzdem näherungsweise optimale oder gute Lösungen erzielen. Zur Analyse des Problems wurde ein Simulationsmodell entwickelt, das verschiedene heuristische Verfahren wie Genetische Algorithmen und Learning Classifier Systems einsetzt, um eine möglichst optimale Lösung zu finden. Der Einsatz hierarchischer Ebenen von Klassifikatoren verspricht eine Möglichkeit, komplexe Strukturen zu erzeugen, deren Fitness von mehreren Parametern abhängt.

2.5 Komplexität der Problemstellung

Je nach Zustand der Umwelt kann von einer zur anderen hierarchischen Ebene umgeschaltet werden, wodurch komplexere Wabenstrukturen möglich werden.

3 Methode

2 Theoretische Grundlagen 42 Um eine Antwort auf die in Abschnitt 2.5 erläuterte Frage zu erhalten, wurde im Rahmen dieser Arbeit eine Simulationsumgebung entwickelt. Ziel der damit durchgeführten Simulationsläufe war es zu klären, ob die Vorgänge beim Wabenbau von Insekten auf ein Modell übertragbar und inwieweit die Ergebnisse eines solchen Systems mit realen Insektennestern vergleichbar sind. Aufgrund der Größe des Zustandsraumes der Problemstellung ist eine direkte Berechnung der optimalen Lösung nicht praktikabel (siehe Abschnitt 2.5), weswegen eine Simulationsumgebung auf Basis Lernender Klassifizierender Systeme entwickelt wurde. Zur Veranschaulichung der Ergebnisse wurde außerdem eine graphische Darstellung der durch die Simulation entstandenen Wabenstrukturen realisiert.

Da Begriffe wie Population und Individuum sowohl im Kontext staatenbildender Insekten als auch in der Nomenklatur der Genetischen Algorithmen eine zentrale Bedeutung besitzen, ist es wichtig, klar voneinander abzugrenzen, was die Bedeutung welchen Begriffes im jeweiligen Zusammenhang ist. Ein Insektenstaat - natürlich wie simuliert - besteht aus einer Menge von Insekten. Das einzelne Insekt wird als Individuum, die Gesamtheit aller Individuen als Population bezeichnet. Im Kontext des Simulationsmodells wird das simulierte Insekt vorwiegend als Agent bezeichnet, um Verwechslungen zu vermeiden. Ein Genetischer Algorithmus arbeitet ebenfalls mit einer Population von Individuen, wobei die interne Repräsentation eines Individuums Genotyp und die von ihm vorgeschlagene Problemlösung Phänotyp genannt werden.

In diesem Kapitel werden die Komponenten des implementierten Modells im Einzelnen beschrieben. Sofern Bezug auf den in Anhang A beigefügten MATLAB-Quellcode genommen wird, bezeichnen in Schreibmaschinenschrift geschriebene Wörter die entsprechenden Variablen- oder Funktionsnamen. <dateiname>.m bezeichnet die entsprechende Datei.

3.1 Benutzte Werkzeuge

Die Simulationsumgebung wurde in MATLAB^{®} 7.7.0.471 (R2008b) implementiert und die Simulationen auf einem PC mit 2 Gigabyte RAM und Ubuntu mit Linux-Kernel 2.6.28 als Betriebssystem durchgeführt. MATLAB ist eine proprietäre Skriptsprache mit Möglichkeit zu objektorientierter Programmierung und umfangreicher graphischer Darstellung.

3.2 Konzept des Simulationsmodells

Zur Simulation des Wabenbaus wurde ein zeitdiskretes Simulationsmodell implementiert. Zeitdiskrete Simulationsmodelle zeichnen sich dadurch aus, dass Änderungen des Systemzustands nur zu bestimmten, diskreten Zeitpunkten betrachtet werden und der Systemzustand zwischen den diskreten Zeitpunkten für die Simulation als konstant angenommen wird (Page et al., 2000). Konkret bedeutet das in diesem Modell, dass jeder Agent pro Zeitschritt einen neuen Baustein bauen und sich danach um eine festgelegte Schrittweite auf der Wabe in eine zufällig gewählte Richtung bewegen kann. Im nächsten Zeitschritt ist der Baustein gebaut und der Agent befindet sich auf seiner neuen Position, die verstrichene Zeit wird nicht direkt berücksichtigt. Hierin unterscheiden sich diskrete Simulationsmodelle von kontinuierlichen Modellen, bei denen sich der Systemzustand stetig über die Zeit ändert.

3.3 Programmierung der Simulationsumgebung

Das Skript simulationsumgebung.m stellt das Rahmenwerk für den gesamten Simulationsablauf zur Verfügung. Hier wird der Simulationsraum und die Bauagenten als Modelle der nestbauenden Insekten erzeugt. Auch die global geltenden Parameter werden hier eingestellt. Bei Ausführung des Skripts wird eine von den angegebenen Parametern abhängige Anzahl von Simulationsläufen gestartet. Über den zweidimensionalen kontinuierlichen Raum wird eine Struktur aus regelmäßigen Sechsecken gelegt, welche den Raum in gleich große Zellen aufteilt. Die Größe des Raumes ist frei wählbar und wird vom Sechseckgitter maximal ausgenutzt.

3.3 Programmierung der Simulationsumgebung

Abbildung 3.1: Eine begonnene Simulation nach sechs Bauschritten. Der schwarze Baustein markiert die Ausgangswabe, die roten und grünen Steine markieren die gebauten Zellen von Typ 1 (rot) und Typ 2 (grün). Der kleine blaue Punkt auf der schwarzen Zelle markiert die Position des Agenten.

Abbildung 3.2: Initialzustand der Simulation mit bebauten Anfangszellen

Auf jedem sechseckigen Feld des Gitters können verschiedene Arten von Wabenzellen gebaut werden, die in der graphischen Darstellung mit verschiedenen Farben markiert werden (siehe Abschnitt 3.7). Vor Beginn der Simulation werden sieben Zellen in der Mitte des Gitters als Ausgangspunkt mit Bausteinen vom Typ 1 bebaut, was als Analogie zum Aufhängepunkt eines realen Wespennestes (siehe Abschnitt 2.1) verstanden werden kann. Zur Unterscheidung von den anderen Bausteinen werden die initial gebauten Zellen schwarz markiert (siehe Abbildung 3.2).

3.3.1 Regelsatz und Parameter

Der genaue Ablauf einer Simulation ist abhängig von mehreren variablen Parametern sowie dem Regelsatz, nach dem die Agenten ihre Umgebung klassifizieren. Im Folgenden sind alle Parameter der Simulationsumgebung aufgeführt:

• Größe des Simulationsraumes in X- (DX) und Y-Richtung (DY)

• Anzahl der gleichzeitig aktiven Agenten (wespenanzahl)

• Maximale Anzahl der Schritte pro Agent und Simulationsdurchgang (MaxSteps)

• Größe der Population des Genetischen Algorithmus - entspricht der Anzahl der Simulationen, die mit der Population pro Durchlauf des GA durchgeführt

     werden (numberofruns)

• Anzahl der Anwendungen des Genetischen Algorithmus (numberofgaruns)

• In jedem Simulationslauf arbeitet der einzelne Agent mit dem gleichen statischen Regelsatz von 31 Regeln (siehe Tabelle 3.2), der im Array RuleSet1 abgelegt ist. Eine detaillierte Erklärung der Regelcodierung findet sich in Abschnitt 3.4.2.

3.4 Programmierung der Agentenobjekte

Die Insekten, die im Rahmen der Simulation an der Wabenstruktur bauen, wurden als autonome Agenten modelliert, die sich unabhängig voneinander frei im zweidimensionalen Raum bewegen können. Hierzu wurden die Möglichkeiten von MATLAB zur objektorientierten Programmierung genutzt und in der Datei bauagent.m (Listing in Anhang A.2) eine eigene Objektklasse zur Beschreibung der Agenten programmiert.

Die Position der Agentenobjekte im Raum wird als kontinuierlicher Wert angegeben und gespeichert, das heißt jeder Agent besitzt zu jedem Zeitpunkt einen absoluten zweidimensionalen Positionsvektor bestehend aus X- und Y-Koordinate. Die Position wurde derart modelliert, um möglichst nah am biologischen Vorbild zu bleiben. Da für die Regelverarbeitung des Agenten entscheidend ist, auf welcher Zelle des Gitternetzes er sich befindet, wird die Nummer der entsprechenden Zelle in jedem Zeitschritt berechnet.

3.4 Programmierung der Agentenobjekte

Die Funktionsweise der Agenten entspricht in den Grundzügen der eines Learning Classifier Systems (siehe Abschnitt 2.4). Jeder Agent besitzt einen Satz von Klassifikatoren, mit deren Hilfe die lokale Umgebung klassifiziert und über eine entsprechende Aktion entschieden wird. Die Agenten können nicht miteinander kommunizieren, haben keine Wahrnehmung der globalen Wabenstruktur und auch keinen Bauplan, wie die fertige Wabe auszusehen hat. Die einzige Wahrnehmungsfähigkeit ist die Erkennung ihrer direkten Umgebung, wie sie in Abschnitt 3.4.2 detailliert beschrieben ist.

Zu jedem diskreten Zeitpunkt t wird für jeden Agenten die Funktion movebuild aufgerufen, die die Aktivität des Agenten steuert. Diese Aktivität setzt sich aus zwei Einzelschritten zusammen. Zuerst erfolgt die Klassifikation der Umgebung mit eventueller Manipulation des Wabengitters, danach die Bewegung des Agenten auf eine neue Position im Raum.

3.4.1 Implementation der Klassifikatoren

In der Datei classifier.m (Listing in Anhang A.3) wird die interne Struktur der Klassifikatoren festgelegt. Dazu wird wie für die Agenten eine eigene Objektklasse classifier definiert. Die Klasse enthält außer einer Konstruktor-Funktion zur Erzeugung der classifier-Objekte alle Eigenschaften zur Beschreibung des Klassifikators, die in objektabhängigen Variablen gespeichert werden.

In der folgenden Liste sind alle Eigenschaften der classifier-Klasse aufgeführt:

• detector enthält den Detektor-String als Zeichenkette (siehe Abschnitt 3.4.2).

• effector enthält die bei Aktivierung des Klassifikators auszuführende Aktion als numerischen Wert. 0 steht hier für nicht bauen und die Zahlen 1,2,3 für den entsprechenden Bausteintyp.

• strength ist eine ganze Zahl, die die Stärke des Klassifikators angibt. Dieser Wert wird bei Erzeugung des bauagent-Objektes für alle Klassifikatoren stochastisch unabhängig voneinander per Zufall auf einen Wert zwischen 0 und 255 gesetzt.

• fitnessstring enthält den Stärke-Wert aus strength als 8-bit-Gray-Code (siehe Abschnitt 2.3.3) in Form einer binären achtstelligen Zeichenkette. Ein strength-Wert von 11 wäre in fitnessstring z.B. als ’00001111’ gespeichert. Diese Form der Codierung ist wichtig für die Funktion des Genetischen Algorithmus (siehe Abschnitt 3.6).

• specificity bezeichnet die Spezifizität sp(R) des Klassifikators. Das entspricht der Zahl der Stellen im Detektor-String, die ungleich dem don’t-care-Symbol ∗ sind.

• bid ist der aus strength und specificity für alle passenden Klassifikatoren in einem Zeitschritt berechnete Wert, der zur Entscheidung über die Aktivierung eines Klassifikators verwendet wird. Die genaue Beschreibung des Verfahrens ist in Abschnitt 3.4.2 zu finden.

3.4.2 Klassifikation und Manipulation der Umgebung

Die Klassifikation der Umgebung erfolgt durch eine Verknüpfung von Umgebungsmustern mit entsprechenden Aktionen. Im String-Array RuleSet1 werden die Muster und die damit verknüpfte Aktion abgespeichert. Die ersten sechs Zeichen in einer solchen Zeichenkette repräsentieren die direkte Umgebung der potentiellen Bauposition und werden wie bei LCS-Systemen Detektor-String genannt. Das siebte Zeichen steht für die Aktion, die der Agent bei Aktivierung des Klassifikators ausführt, und wird als Effektor-String bezeichnet.

Da der Agent sich nur auf bereits bebauten Zellen befinden darf, muss zunächst eine leere Zelle in unmittelbarer Umgebung ausgewählt werden, auf der ein neuer Baustein gebaut werden könnte. Dazu werden die direkt angrenzenden Zellen - bei der senkrecht oberhalb angrenzenden Zelle angefangen - im Uhrzeigersinn getestet, ob sie noch unbebaut sind. Findet der Agent eine unbebaute Zelle, ist dies eine potentielle Bauposition.

Im nun folgenden eigentlichen Klassifizierungsvorgang wird der Zustand der die potentielle Bauposition direkt umgebenden Zellen - ebenfalls bei der oberen Zelle angefangen im Uhrzeigersinn - nacheinander abgefragt. Die Zustände der umgebenden Zellen bilden aneinandergereiht die Input-String I genannte Eingabe in das System. Eine 0 in I steht dabei für eine unbebaute Zelle, 1, 2 oder 3 steht für eine mit Bausteintyp 1, 2 bzw. 3 bebaute Zelle. I wird dann nacheinander mit allen im Regelsatz vorhandenen Klassifikatoren verglichen. Für jeden Klassifikator werden die einzelnen Positionen in I der Reihe nach mit den einzelnen Positionen des Detektor-String B verglichen. Die getestete Regel gilt als passend, wenn es keine Widersprüche zwischen I und B gibt. Die Symbole 0, 1, 2 und 3 haben in B die gleiche Bedeutung wie in I. Zusätzlich sind für B noch die Symbole B und ∗ definiert. B steht für eine Zelle, die mit einem beliebigen Baustein besetzt ist, und ∗ wird don’t-care-Symbol genannt, das heißt dass die entsprechende Position für die Regel nicht relevant ist.

Für I = 110011 würde z.B. sowohl B_{1} = 110011 wie auch B_{2} = 11**11 oder B_{3} = BB**11 als passend erkannt werden. Eine graphische Übersicht über die Regelsyntax ist in Tabelle 3.1 zu finden.

Zeichen  Bedeutung  Graphische Darstellung
0  leeres Feld
1  Baustein von Typ 1
2  Baustein von Typ 2
3  Baustein von Typ 3
B  beliebiger Baustein
*  don’t-care - Zustand egal

Tabelle 3.1: Vom Regelwerk verwendete Zeichen und ihre Bedeutung

Wie in Abschnitt 2.4 bereits erläutert werden alle zu einem Zeitpunkt t als passend erkannte Klassifikatoren in einer Menge M_{t} zuammengefasst. Aus M_{t} wird nun ein Klassifikator ausgewählt. Dazu wird für jeden Klassifikator R ein entsprechendes Gebot bid(R) berechnet. Es gilt

bid(R) = S(R) · log_{2}(sp(R))

bid(R) berechnet sich also aus Stärke und Spezifizität des Klassifikators.

Mittels Roulette-Wheel-Selektion (siehe Abschnitt 2.3.2) wird nun anhand der bid-Werte einer der Klassifikatoren aus M_{t} ausgewählt. Die Auswahlwahrscheinlichkeit ist hierbei direkt proportional zum bid-Wert des Klassifikators.

Wurde ein Klassifikator R aus M_{t} ausgewählt, so wird die in effector als Zahlenwert gespeicherte Aktion ausgeführt. Mögliche Aktionen sind in diesem Modell das Bauen verschiedener Typen von Zellen (effector = 1, 2 oder 3) oder das explizite Nicht-Bauen einer Zelle (effector = 0). Die verschiedenen Bausteintypen haben keine konkrete Bedeutung, sondern sollen auf das Modell abbilden, dass Wespen und Bienen die Wabenzellen ihrer Nester für unterschiedliche Aufgaben nutzen. Es könnten z.B. Zellen von Typ 1 für Zellen stehen, in denen die Brut gepflegt wird, Zellen von Typ 2 für die Lagerung von Nahrung und Zellen von Typ 3 für eine beliebige andere Nutzung.

Der komplette verwendete Regelsatz RuleSet1 ist in Tabelle 3.2 zu sehen. Die graphische Darstellung ist folgendermaßen zu interpretieren, dass die mittlere sechseckige Zelle die zu bebauende Position darstellt und die umgebenden sechs Zellen den für den Klassifikator relevanten Input I repräsentieren. Die farbige Markierung entspricht der in Tabelle 3.1 angegebenen.

3.4.3 Erweiterung durch hierarchische Klassifikatoren

Zur Implementierung einer zweiten hierarchischen Ebene von Klassifikatoren wurde das ursprüngliche Modell um einen zweiten Regelsatz erweitert, der analog zum ersten Regelsatz im Array RuleSet2 abgelegt ist. Es wurde eine neue globale Variable rulesetanzahl in simulationsumgebung.m angelegt, die die Zahl der hierarchisch hintereinandergeschalteten Regelsätze angibt. Gültige Werte für rulesetanzahl sind 1 und 2. Setzt man die Variable auf 1, verhält sich das Modell so, als existiere der zweite Regelsatz nicht. Setzt man sie auf 2, wird nach Ausführung der Simulationen mit Regelsatz 1 derjenige Regelsatz mit der höchsten erreichten Fitness ausgewählt und in bestclassifierset1 zwischengespeichert. Die neu gestartete Simulation arbeitet zunächst nach wie vor mit Regelsatz RuleSet1, jedoch nur so lange bis die maximale Schrittzahl MaxSteps erreicht ist. An diesem Punkt wird auf den zweiten Regelsatz RuleSet2 umgeschaltet. Alle vorhandenen Klassifikatoren der Agenten werden gelöscht und durch die neuen Regeln aus RuleSet2 ersetzt. Die Initialisierung der Stärkewerte erfolgt wie beim ersten Regelsatz zufällig. Danach läuft die Simulation auf der bereits entstandenen Struktur mit dem neuen Regelsatz weiter, bis die maximale Schrittzahl MaxSteps2 erreicht ist.

Index  B  A Grafik

1  BBBBBB 1
2  BBBBB0 1
3  0BBBBB 1
4  B0BBBB 1
5  BB0BBB 1
6  BBB0BB 1
7  BBBB0B 1
8  BBBB00 1
9  0BBBB0 1
10 00BBBB 1
11 B00BBB 1
12 BB00BB 1
13 BBB00B 1
14 BBB000 1
15 0BBB00 1
16 00BBB0 1

Index  B  A Grafik

17 000BBB 1
18 B000BB 1
19 BB000B 1
20 BB0000 1
21 0BB000 1
22 00BB00 1
23 000BB0 1
24 0000BB 1
25 B0000B 1
26 B00000 0
27 0B0000 0
28 00B000 0
29 000B00 0
30 0000B0 0
31 00000B 0

Tabelle 3.2: Die 31 Klassifikatoren aller Simulationen in Abschnitt 4.1 mit Indexnummer, Detektor-String B, Effektor-String A und graphischer Darstellung Der komplette Regelsatz aus RuleSet2 ist in den Tabelle 3.3 und 3.4 aufgelistet.

Ergebnisse der Simulationen mit zwei hierarchisch geordneten Sätzen von Klassifikatoren sind in Abschnitt 4.3 zu finden.

3.4.4 Bewegung der Agenten

Die Ausgangsposition aller Agenten befindet sich auf der mittleren der zu Beginn bebauten Zellen. Nachdem die Klassifizierung und Manipulation der Umgebung durch den Agenten innerhalb eines Zeitschrittes abgeschlossen ist (siehe Abschnitt 3.4.2), wird die Drehrichtung des Agenten nach dem Zufallsprinzip neu festgelegt. Hierzu wird eine Zufallszahl zwischen 0 und 1 mit 360 multipliziert. Das Ergebnis bestimmt den Drehwinkel des Agenten. Anschließend bewegt sich der Agent in der bestimmten Drehrichtung um eine in der Variable Speed festgelegte Entfernung im zweidimensionalen Raum. Die Agenten bewegen sich nur auf Zellen, die bereits bebaut sind und verlassen die gebaute Wabenstruktur nicht.

3.5 Berechnung der Gesamtfitness der

Wabenstruktur

Die Funktion fitness (Listing siehe Anhang A.4) dient zur Berechnung der Gesamtfitness einer in der Simulation entstandenen Wabenstruktur. Als Grundlage der Berechnung dient das Kriterium der Kompaktheit. Kompaktheit bedeutet in diesem Kontext, dass die Wabenstruktur möglichst wenige Verästelungen oder Löcher aufweist, wobei eine kreisförmige Wabenstruktur den Idealfall von Kompaktheit darstellt. In Abbildung 3.3 a) ist eine stark verästelte Struktur mit relativ niedrigem Fitnesswert zu sehen, in Abbildung 3.3 b) eine kompaktere Struktur mit wenig Verzweigungen und entsprechend höherem Fitnesswert.

Die Kompaktheit bzw. der globale Fitnesswert F der entstandenen Wabenstruktur wird nach jedem einzelnen Simulationslauf bestimmt. Die dazu verwendete Fitnessfunktion berechnet einen Wert, der den Grad der Kompaktheit der entstandenen Struktur angeben soll. Um die Kompaktheit einer Struktur als numerischen Wert

3.5 Berechnung der Gesamtfitness der Wabenstruktur

\begin{matrix}Index & B & A & Grafik \\ 1 & 110000 & 2 \\ 2 & 011000 & 2 \\ 3 & 001100 & 2 \\ 4 & 000110 & 2 \\ 5 & 000011 & 2 \\ 6 & 100001 & 2 \\ 7 & 211000 & 2 \\ 8 & 021100 & 2 \\ 9 & 002110 & 2 \\ 10 & 000211 & 2 \\ 11 & 100021 & 2 \\ 12 & 110002 & 2 \\ 13 & 112000 & 2 \\ 14 & 011200 & 2 \\ 15 & 001120 & 2 \\ 16 & 000112 & 2 \\ 17 & 200011 & 2 \\ 18 & 120001 & 2 \\ 19 & 211200 & 2 \\ 20 & 021120 & 2 \end{matrix}  \begin{matrix}Index & B & A & Grafik \\ 21 & 002112 & 2 \\ 22 & 200211 & 2 \\ 23 & 120021 & 2 \\ 24 & 112002 & 2 \\ 25 & 212000 & 2 \\ 26 & 021200 & 2 \\ 27 & 002120 & 2 \\ 28 & 000212 & 2 \\ 29 & 200021 & 2 \\ 30 & 120002 & 2 \\ 31 & 120000 & 2 \\ 32 & 012000 & 2 \\ 33 & 001200 & 2 \\ 34 & 000120 & 2 \\ 35 & 000012 & 2 \\ 36 & 200001 & 2 \\ 37 & 210000 & 2 \\ 38 & 021000 & 2 \\ 39 & 002100 & 2 \\ 40 & 000210 & 2 \end{matrix}

Tabelle 3.3: Die 78 Klassifikatoren des Regelsatzes der zweiten Hierarchieebene (Teil 1) mit Indexnummer, Detektor-String B, Effektor-String A und graphischer Darstellung

    \begin{matrix}Index & B & A & Grafik \\ 41 & 000021 & 2 \\ 42 & 100002 & 2 \\ 43 & 211100 & 2 \\ 44 & 021110 & 2 \\ 45 & 002111 & 2 \\ 46 & 100211 & 2 \\ 47 & 110021 & 2 \\ 48 & 111002 & 2 \\ 49 & 111200 & 2 \\ 50 & 011120 & 2 \\ 51 & 001112 & 2 \\ 52 & 200111 & 2 \\ 53 & 120011 & 2 \\ 54 & 112001 & 2 \\ 55 & 211110 & 2 \\ 56 & 021111 & 2 \\ 57 & 102111 & 2 \\ 58 & 110211 & 2 \\ 59 & 111021 & 2 \end{matrix}  \begin{matrix}Index & B & A & Grafik \\ 60 & 111102 & 2 \\ 61 & 111120 & 2 \\ 62 & 011112 & 2 \\ 63 & 201111 & 2 \\ 64 & 120111 & 2 \\ 65 & 112011 & 2 \\ 66 & 111201 & 2 \\ 67 & 211111 & 2 \\ 68 & 121111 & 2 \\ 69 & 112111 & 2 \\ 70 & 111211 & 2 \\ 71 & 111121 & 2 \\ 72 & 111112 & 2 \\ 73 & 211120 & 2 \\ 74 & 021112 & 2 \\ 75 & 202111 & 2 \\ 76 & 120211 & 2 \\ 77 & 112021 & 2 \\ 78 & 111202 & 2 \end{matrix}

Tabelle 3.4: Die 78 Klassifikatoren des Regelsatzes der zweiten Hierarchieebene (Teil 2) mit Indexnummer, Detektor-String B, Effektor-String A und graphischer Darstellung

(a) F = 0.23  (b) F = 0.57

Abbildung 3.3: Vergleich zwischen zwei Wabenstrukturen mit (a) niedrigem und (b) hohem Fitnesswert F

darzustellen, wird die Gesamtfläche der Wabe durch ihren Umfang geteilt. Die Ausgangsidee für diese Berechnung ist, dass ein Kreis von allen geometrischen Figuren für eine gegebene Fläche den kleinsten Umfang besitzt und eine kreisförmige Wabe einen (nicht erreichbaren) Idealzustand darstellen würde. Zur Berechnung der Fitness wird das Verhältnis der Oberfläche A_{W} der Wabe zu ihrem Umfang U_{W} berechnet und angenommen, dass der Grad der Kompaktheit proportional zu diesem Wert verläuft. Da dieses Verhältnis bei einer kreisförmigen Figur maximal wäre, wird der Umfang U_{K} eines hypothetischen Kreises mit gleicher Fläche wie der entstandenen Wabenstruktur berechnet, und das Verhältnis des Kreisumfangs zur Fläche als idealer Fitnesswert F_{ideal} betrachtet. Aus den bekannten Kreisgleichungen U_{K} = 2 · r · π und A_{K} = r^{2} · π ergibt sich das Verhältnis

F_{ideal} = \frac{A_{K}}{U_{K}} = \frac{r}{2} = \frac{U_{K}}{4 · π}  (3.1)

Der Quotient aus tatsächlichem Fitnesswert F und idealem Fitnesswert F_{ideal} ist der endgültige Fitnesswert F_{GA}, den der Genetische Algorithmus verwendet. Im Unterschied zum üblichen Vorgehen bei Lernenden Klassifizierenden Systemen, wird in diesem Modell der globale Fitnesswert nicht wie in Abschnitt 2.4.1 beschrieben mittels Reinforcement Learning zu allen beteiligten Regeln zurückpropagiert. Stattdessen erfolgt die Bewertung ausschließlich durch einen Genetischen Algorithmus, wie im folgenden Abschnitt erläutert wird.

3.6 Implementation des Genetischen Algorithmus

In der Funktion strengthga (Listing in Anhang A.6) ist ein Genetischer Algorithmus implementiert, der die in Abschnitt 2.3 beschriebenen Methoden verwendet, um neue Regelsätze für die Simulation des Wabenbaus zu erzeugen. In dieser Implementation bleiben dabei Detektor- und Effektor-String aller Klassifikatoren gleich, der Genetische Algorithmus verändert jedoch die Stärke-Werte der Klassifikatoren, mit dem Ziel, eine möglichst gute Verteilung der Stärke-Werte zu erreichen.

Es gibt zwei prinzipiell zu unterscheidende Möglichkeiten, einen Genetischen Algorithmus in Zusammenhang mit einem LCS anzuwenden. Diese unterscheiden sich darin, was als Individuum und Population für den GA definiert wird:

1. Das Individuum entspricht einem Regelsatz, also der Gesamtheit aller Klassifikatoren eines Agenten. Man arbeitet mit Agenten mit unterschiedlichen Regelsätzen, die zusammen genommen die Population des GA darstellen. Man testet das System mit den verschiedenen Regelsätzen und lässt den GA den bestmöglichen Regelsatz suchen. Dies entspricht dem Pittsburgh-Ansatz für LCS (siehe Abschnitt 2.4.2).

2. Das Individuum entspricht einem einzelnen Klassifikator. Der gesamte benutzte Regelsatz ist damit die Population des Genetischen Algorithmus. Das entspricht dem Michigan-Ansatz für LCS (siehe Abschnitt 2.4.2). Man arbeitet mit einem anfangs festgelegten Regelsatz, wobei die einzelnen Klassifikatoren durch den GA verändert werden.

Im Rahmen der vorliegenden Arbeit wurde ein LCS nach dem Pittsburgh-Ansatz implementiert und beschrieben. Eine ausführliche Betrachtung von Learning Classifier Systemen nach dem Michigan-Ansatz ist bei Butz (2006) zu finden und soll hier nicht näher behandelt werden. Eine Implementation für das vorliegende Problem könnte trotzdem interessante Ergebnisse bringen. Für den Genetischen Algorithmus stellt die Gesamtheit der verwendeten Regelsätze und die aus ihnen resultierenden Wabenstrukturen seine Population dar, in der jeder einzelne Regelsatz als Individuum zu sehen ist. Genotyp des Individuums ist die Menge der Stärke-Werte aller Klassifikatoren des entsprechenden Regelsatzes. Es wird die in fitnessstring gespeicherte Gray-Code-Darstellung jeder einzelnen Regel aneinandergehängt und in classifierfitnessstring abgespeichert. Hätte man zum Beispiel einen aus drei

3.6 Implementation des Genetischen Algorithmus

Klassifikatoren R_{1}, R_{2} und R_{3} bestehenden Regelsatz R und die drei Klassifikatoren hätten die folgenden Fitnesswerte in Gray-Code-Darstellung: fitnessstring(R_{1}) = ’11010011’, fitnessstring(R_{2}) = ’00101101’ und fitnessstring(R_{3}) = ’01011010’, dann wäre classifierfitnessstring (R) = ’110100110010110101011010’ und repräsentierte den Genotyp des Individuums für den Genetischen Algorithmus.

Im beschriebenen Regelsatz von 31 Klassifikatoren (siehe Abbildung 3.2) mit einem 8-bit-Stärkewert besteht der Genotyp eines Individuums somit aus einer Kette von 8 × 31 = 248 Nullen und Einsen. Als Phänotyp des Individuums kann die durch Anwendung des Regelsatzes entstandene Wabenstruktur gesehen werden.

3.6.1 Parameter des Genetischen Algorithmus

In strengthga.m können drei Parameter für den Genetischen Algorithmus direkt angegeben werden:

• probcrossover gibt die Wahrscheinlichkeit p_{xover} an, mit der bei der Reproduktion der Individuen eine Rekombination der genetischen Codes der Eltern stattfindet.

• probmutation definiert die Mutationswahrscheinlichkeit p_{mut}, mit der ein ausgewähltes Bit in einem neu erzeugten Individuum verändert wird (siehe Abschnitt 2.3.2).

• elternzahl ist die Anzahl der Individuen, die pro Durchlauf des Genetischen Algorithmus für eine „Fortpflanzung“ ausgewählt werden. Der Wert muss ein Vielfaches von 2 sein, da jeweils zwei Individuen für einen Rekombinationsvorgang benötigt werden.

3.6.2 Ablauf des Genetischen Algorithmus

Selektion der Elternindividuen

Zur Selektion der Elternindividuen wird ein Roulette-Wheel-Selektionsalgorithmus (siehe Abschnitt 2.3.2) verwendet, der als Funktion roulettemz implementiert ist.

Anhand der in overallfitness gespeicherten Fitnesswerte der gebauten Strukturen wird in jedem Durchlauf des Selektionsalgorithmus ein Agent ausgewählt, wobei die Auswahlwahrscheinlichkeit direkt proportional zum Fitnesswert ist. Es handelt sich um stochastische Auswahl mit Zurücklegen, das heißt jedes Individuum kann beliebig oft zur Replikation ausgewählt werden. Dadurch wird erreicht, dass sich Individuen mit überdurchschnittlich hoher Fitness auch überdurchschnittlich vermehren können.

Rekombination

Nach Auswahl der Elternindividuen erfolgt ihre Replikation durch die Funktion onepointxover. Die genetischen Strings der Elternindividuen (gespeichert in classifierfitnessstring) werden zuerst in zwei neue Strings kopiert. Danach wird eine stochastische Auswahl darüber getroffen, ob eine Rekombination der beiden Strings erfolgt. Mit Wahrscheinlichkeit p_{xover} werden die Strings rekombiniert, mit Wahrscheinlichkeit 1 − p_{xover} wird die Rekombination übersprungen. Entscheidet der Zufall für eine Rekombination, wird einfaches Ein-Punkt-Crossover angewendet (siehe Abschnitt 2.3.2), das heißt es wird eine zufällige Stelle auf dem Bitstring ausgewählt und die Teile der beiden neu erzeugten Strings werden hinter diesem Crossover-Punkt miteinander vertauscht. Abbildung 3.4 veranschaulicht diesen Vorgang.

Abbildung 3.4: Schematische Darstellung von Ein-Punkt-Crossover (Nissen, 1997)

Mutation

Auf die so entstandenen genetischen Strings wird im nächsten Schritt die Funktion mutation angewendet. Sie implementiert den in Abschnitt 2.3.2 beschriebenen Mutationsvorgang. Wie bei der Rekombination erfolgt vor der eigentlichen Durchführung der Mutation eine stochastische Entscheidung darüber, ob tatsächlich eine Mutation durchgeführt wird oder nicht. Mit Wahrscheinlichkeit p_{mut} wird ein Bit im String

3.7 Graphische Darstellung

mutiert, mit Wahrscheinlichkeit 1 − p_{mut} nicht. Wird für eine Mutation entschieden, wird zufällig eine Stelle auf dem String gewählt und das entsprechende Bit gekippt, d.h. aus einer ’0’ wird eine ’1’ und aus einer ’1’ eine ’0’.

Einfügen in die Population

Da die Größe der Population konstant gehalten werden soll, unter anderem um einen Selektionsdruck aufzubauen und Individuen mit niedrigerer Fitness aus der Population zu entfernen, müssen ebenso viele Individuen aus der bisherigen Population entfernt werden, wie bei der Elternselektion zur Vermehrung ausgewählt wurden. Die Auswahl der zu entfernenden Individuen erfolgt ebenfalls durch Roulette-Wheel-Se-lektion, die in Funktion roulette implementiert wurde. Es gibt zwei entscheidende Unterschiede zu dem bei der Selektion der Elternindividuen verwendeten Algorithmus. Die Auswahlwahrscheinlichkeit hängt nicht direkt proportional vom erreichten Fitnesswert ab wie bei der Elternselektion, sondern umgekehrt proportional. Je geringer die vom Individuum erreichte Fitness ist, desto höher ist die Wahrscheinlichkeit, dass es aus der Population gelöscht wird. Außerdem erfolgt in dieser Variante eine Auswahl aus der Population ohne Zurücklegen, d.h. jedes Individuum darf in einem Durchgang des GA nur einmal gewählt werden. Dies ist äußerst wichtig, da für jedes neu dazukommende Individuum ein anderes aus der Population gelöscht werden muss. Würde man ein Individuum in diesem Schritt zweimal auswählen, könnte man es trotzdem nur einmal aus der Population entfernen, was eine relative Vergößerung der Population zur Folge hätte. Die beschriebenen Schritte des Genetischen Algorithmus werden so oft wiederholt, bis die festgelegte Anzahl von neuen Individuen erzeugt wurde.

3.7 Graphische Darstellung

Um eine Vorstellung davon vermitteln zu können, wie die in der Simulation entstandenen Strukturen aussehen, wurde eine graphische Darstellung des Simulationsraumes implementiert. MATLAB stellt umfangreiche Möglichkeiten zur Graphikprogrammierung zur Verfügung. Als Anforderungen an die Darstellung wurden eine übersichtliche Repräsentation des sechseckigen Gitternetzes, die farbige Markierung von bebauten

Abbildung 3.5: Unbebaute sechseckige Gitterstruktur

Zellen mit je nach Bausteintyp unterschiedlichen Farben und die Möglichkeit der Markierung der momentanen Agentenposition festgelegt.

3.7.1 Darstellung des hexagonalen Gitters

Die Darstellung des Gitternetzes wurde in der Funktion plotgitter (Listing in Anhang A.8) realisiert. Um den Mittelpunkt jeder sechseckigen Zelle wird ein regelmäßiges sechseckiges patch-Objekt erzeugt, welches genau die Umrisse der Zelle nachzeichnet. patch-Objekte sind graphische Objekte in MATLAB und können beliebige Formen und Farben haben. Die hier benutzten Objekte haben eine weiße Oberfläche und schwarze Ränder, wodurch in ihrer Aneinanderreihung das Gitternetz entsteht (siehe Abbildung 3.5).

3.8 Durchführung der Simulationen

Abbildung 3.6: Graphisches Beispiel einer von vier Agenten mit drei Bausteintypen gebauten Wabe

3.7.2 Darstellung der einzelnen Wabenzellen

Um die bebauten Wabenzellen zu markieren, wurde die Funktion plotwabe geschrieben. Die Funktion benötigt als übergebene Parameter den logischen Index der zu markierenden Zelle und ihre Farbe. Es wird ein zusätzliches sechseckiges patch-Objekt an der Position der Zelle erzeugt, wobei die Flächen des Objekts in der dem Bausteintyp entsprechenden Farbe eingefärbt werden. Um das Modell für eine spätere dreidimensionale Erweiterung offenzuhalten, wurden die Bausteine nicht als flache Sechsecke sondern als dreidimensionale Polygonobjekte modelliert. Ein Beispiel für eine von vier Agenten gleichzeitig gebaute Wabenstruktur findet sich in Abbildung 3.6.

3.8 Durchführung der Simulationen

Der Ablauf der mit Hilfe des in diesem Kapitel beschriebenen Modells durchgeführten Simulationen erfolgte nach dem folgendem Schema:

1. Festlegen der Simulationsparameter: Größe des Feldes, Anzahl der Agenten, Anzahl der Schritte pro Simulationslauf, Größe der Population des GA, Anzahl der Durchläufe des Genetischen Algorithmus

2. Festlegen des Ausgangsregelsatzes: Es wird ein Satz von Klassifikatoren definiert und für jeden Klassifikator seine Bedingung (Detektor-String B), die entsprechende Aktion (Effektor-String A) und sein anfänglicher Stärkewert S definiert. Die Stärkewerte der einzelnen Regeln werden für jede Simulation von neuem vergeben, wobei S für jeden Klassifikator als zufälliger ganzzahliger Wert zwischen 0 und 255 zugewiesen wird. Die Beschränkung auf ganze Zahlen S mit 0 ≤ S ≤ 255 ist notwendig, da die Stärkewerte in 8-bit-Gray-Code abgespeichert werden (siehe Abschnitt 2.3.3).

3. Durchführung der Simulationsläufe

4. Auswertung der Ergebnisse

Die genauen Parameter der durchgeführten Simulationen sowie die erzielten Ergebnisse werden in Abschnitt 4 im Einzelnen betrachtet.

Die zum Sechseckgitter relative Positionsbestimmung stellte sich im Verlauf der Simulationen als sehr zeitraubend heraus. Ein Simulationslauf mit einer Population von 100 Individuen und 100 Durchläufen des Genetischen Algorithmus benötigte ca. 70 Stunden Rechenzeit. Ein Großteil der Rechenzeit entfiel dabei auf die Positionsbestimmung. Eine Neuimplementierung mit weniger Zeitaufwand wäre von Vorteil, wobei man alternativ dazu das Modell auch dahingehend vereinfachen könnte, dass die Position des Agenten nur durch den Index der Zelle definiert wird, auf dem sich der Agent befindet. Der Agent könnte sich damit nur von Zellenmittelpunkt zu Zellenmittelpunkt bewegen, was die zeitaufwendige Positionsbestimmung überflüssig machen würde. Es bleibt allerdings zu prüfen, ob dies nicht eine Vereinfachung wäre, die sich negativ auf das Verhalten des Modells auswirken würde.

4 Simulationsergebnisse

4.1 Simulationsergebnisse mit einem statischen

Regelsatz und genetisch variierten Stärkewerten

Dieser Abschnitt stellt die Ergebnisse einer Simulationsreihe dar, für die der Regelsatz aus Tabelle 3.2 verwendet wurde. Es wurde jeweils eine Population von Agenten erzeugt, deren Anzahl durch den Parameter numberofruns definiert wurde. Mit jedem der Agenten wurde eine einzelne Bausimulation durchgeführt und die Fitnesswerte der jeweils erzeugten Struktur gespeichert. Die Detektor- und Effektor-Strings der Klassifikatoren sind für jeden Agenten in RuleSet1 festgelegt und damit gleich. Nur die Stärkewerte der einzelnen Klassifikatoren werden für jeden Agenten per Zufall zugewiesen und unterscheiden die Individuen dadurch voneinander. In jedem Lauf gibt es nur einen einzelnen Agenten, der immer die gleiche Zahl von Zeitschritten läuft. Wenn alle Individuen ihre Bausimulation beendet hatten, wurde wie in Abschnitt 3.6 detailliert erläutert der Genetische Algorithmus auf die Population angewendet, um die Stärkewerte der Klassifikatoren zu variieren. Mit der so veränderten Population wurde dann erneut gebaut, wobei die Anzahl der Durchläufe durch numberofgaruns festgelegt ist.

In allen in diesem Abschnitt beschriebenen Simulationen wurden die folgenden Parameter verwendet (Bedeutung siehe Abschnitt 3.3.1), soweit nicht anders angegeben:

• DX = 41

• DY = 41

   • wespenanzahl = 1

Um die Ergebnisse besser bewerten zu können, wurde mit nur einem gleichzeitig aktiven Agenten simuliert.

   • MaxSteps = 200
   • probmutation = 0.2

Die sich unterscheidenden Parameter sind im jeweiligen Unterabschnitt angegeben.

4.1.1 Ergebnisse ohne Beschränkung der Populationsgröße

In diesem Abschnitt werden die Ergebnisse einer Simulation vorgestellt, in der die Größe der Population nicht beschränkt wurde und sich daher in jedem Durchlauf erhöhte. Die Simulation wurde mit folgenden zusätzlichen Parametern durchgeführt:

• Größe der Population numberofruns = 20

• Anzahl der Durchläufe des GA numberofgaruns = 20

• Anzahl der pro Durchlauf des GA erzeugten neuen Individuen elternzahl = 2

Es wurde eine Anfangspopulation von 20 Agenten erzeugt, die wie zuvor beschrieben mit dem gleichen Regelsatz und unterschiedlichen Stärkewerten der einzelnen Regeln einen Bauvorgang simulierten. In dieser Simulation wurden durch den Genetischen Algorithmus keine Individuen aus der Population gelöscht. Wegen elternzahl = 2 kommen mit jedem Durchlauf des GA zwei neue Individuen zur Population dazu, weswegen die Population im Laufe der Simulation wächst. Am Ende der Simulation, nach 20 Durchläufen, umfasst die Population 60 Inidviduen. Nach Beendigung aller Simulationsläufe wurde jeweils die maximal erreichte globale Fitness F_{max} der entstandenen Strukturen festgehalten. Die Entwicklung des maximalen Fitnesswertes F_{max} ist in Abbildung 4.1 zu sehen.

Trotz stochastischer Schwankungen ist in der Grafik ein deutlicher Aufwärtstrend zu erkennen, der vermuten lässt, dass der Genetische Algorithmus den gewünschten Effekt hat und seine weitere Anwendung noch zu einer weiteren Verbesserung geführt hätte.

4.1 Ergebnisse mit einem Regelsatz und variablen Stärkewerten

4.1.2 Ergebnisse mit beschränkter Populationsgröße

In dieser Simulation wurde für jedes neu erzeugte Individuum je ein Individuum aus der Population entfernt, wie in Abschnitt 3.6.2 beschrieben. Dies entspricht dem biologischen Vorbild des Selektionsdruckes (siehe Abschnitt 2.2) und verspricht eigentlich bessere Ergebnisse. Für die Simulation galten die folgenden zusätzlichen Parameter:

   • numberofruns = 100
   • numberofgaruns = 100
   • elternzahl = 4

Unter allen 100 Individuen wurde der maximal erreichte Fitnesswert F_{max} ermittelt und abgespeichert. Zusätzlich wurde in diesem Versuch ein Wert F_{avg} berechnet, der den durchschnittlichen Fitnesswert der Population nach jedem Durchlauf des Genetischen Algorithmus repräsentiert. Die Entwicklung von F_{max} und F_{avg} nach wiederholter Anwendung des GA ist in Abbildung 4.2 dargestellt.

Für beide Werte ist in Grafik 4.2 keine eindeutige Tendenz nach oben oder unten zu erkennen. Beide Werte schwanken zwar mehr oder weniger stark, tendieren aber

Abbildung 4.1: Entwicklung der maximal erreichten Overall-Fitness einer Anfangspopulation von 20 Individuen nach 20 Anwendungen des GA Abbildung 4.2: Entwicklung der durchschnittlich (F_{avg}, rot) und maximal (F_{max},

blau) erreichten globalen Fitness einer Population von 100 Individuen über 100 Anwendungen des GA

nicht eindeutig zu einer Verbesserung. Wie dieses Ergebnis zu bewerten ist, wird ausführlich in Abschnitt 5 diskutiert.

4.1.3 Ergebnisse mit stochastischer Entscheidung über Crossover

Da die Ergebnisse der vorhergehenden Simulation (s. Abschnitt 4.1.2) nicht zufriedenstellend waren, wurde das Programm nochmals um einen entscheidenden Punkt verändert; es wurde ein Parameter p_{xover} als Variable probxover in strengthga.m eingeführt, der die Crossover-Wahrscheinlichkeit für den Genetischen Algorithmus festlegt. Mit Wahrscheinlichkeit p_{xover} wird also ein Crossover durchgeführt, mit Wahrscheinlichkeit 1 − p_{xover} werden die genetischen Strings der Eltern-Individuen unverändert auf die Kinder kopiert. Diese Änderung kann unter Umständen verhindern, dass Individuen mit hoher Fitness durch Crossover zerstört werden. Außerdem wurde in diesem Simulationslauf der Selektionsdruck dadurch erhöht, dass pro Durchlauf des Genetischen Algorithmus 20 Eltern-Individuen mit Roulette-Wheel-Selektion ausgewählt und somit auch 20 neue Individuen erzeugt wurden.

Es wurde also mit folgenden Parametern simuliert:

   • numberofruns = 100
   • numberofgaruns = 20
   • elternzahl = 20

• Crossover-Wahrscheinlichkeit (p_{xover}) probxover = 0.6

Abbildung 4.3: Entwicklung von F_{max} (blau) und F_{avg} (rot) bei einer Population von 100 Individuen über 20 Anwendungen des GA

Die erreichten maximalen bzw. durchschnittlichen Fitnesswerte F_{max} und F_{avg} nach jedem Lauf des GA sind in der Grafik 4.3 zu sehen. Die Ergebnisse unterscheiden sich kaum von denen in Abschnitt 4.1.2. Auch hier ist keine Verbesserung oder Verschlechterung des erreichten Fitnesswertes mit wiederholter Anwendung des GA zu erkennen. Vielmehr bleibt der Fitnesswert von stochastischen Abweichungen abgesehen mehr oder weniger konstant.

4.1.4 Ergebnisse mit Mehrfachauswahl der Elternindividuen

In den vorherigen Simulationsläufen konnte ein Individuum aus der Population nur einmal als Elternindividuum gewählt werden. Da dies der Vorstellung widerspricht, dass sich Individuen mit hoher Fitness überdurchschnittlich oft vermehren, wurde die Implementation für diese Simulation abgeändert, so dass ein Individuum in einem Durchlauf des GA beliebig oft ausgewählt werden kann. Der Roulette-Wheel-Selek-tionsalgorithmus wurde also mit Zurücklegen programmiert (siehe Abschnitt 3.6.2).

Die Simulationsparameter waren wie folgt:

   • numberofruns = 200
   • numberofgaruns = 100
   • elternzahl = 100
   • probxover = 0.6

Die minimal (F_{min}), durchschnittlich (F_{avg}) und maximal (F_{max}) erreichten Fitnesswerte nach jedem Durchlauf des Genetischen Algorithmus sind in Abbildung 4.4 dargestellt.

4.2 Simulation mit statischem Regelsatz ohne

Genetischen Algorithmus

Um zu ermitteln, inwieweit das Schwanken der Fitnesswerte in Abschnitt 4.1 zufällig ist und ob überhaupt ein direkter Zusammenhang zwischen der Verteilung der Stärkewerte der einzelnen Klassifikatoren und der Fitness der gebauten Struktur besteht, wurde eine Simulation durchgeführt, in der wie in Abschnitt 4.1 der Regelsatz aus Tabelle 3.2 verwendet wurde. Der Programmcode wurde für diese Simulation angepasst. Für die jedem Klassifikator des Individuums zu Beginn der Simulation zugewiesenen Stärkewerte wurden keine zufälligen Werte zwischen 0 und 255 erzeugt, sondern jeder Regel ein bestimmter Wert zugewiesen. Der Genetische Algorithmus wurde außerdem deaktiviert. In diesem Experiment wurden also hintereinander 100 Wabenstrukturen

4.2 Simulation mit statischem Regelsatz ohne Genetischen Algorithmus

Abbildung 4.4: Entwicklung von F_{max} (blau), F_{avg} (grün) und F_{min} (rot) bei einer Population von 200 Individuen über 100 Anwendungen des Genetischen Algorithmus

von 100 identischen Individuen mit identischem Regelsatz gebaut und die erzielten Ergebnisse verglichen.

Die relevanten Simulationsparameter im Detail:

• DX = 41
• DY = 41
• wespenanzahl = 1
• MaxSteps = 200
• numberofruns = 100

• Regelsatz siehe Tabelle 3.2

• Stärkewerte der Klassifikatoren siehe Tabelle 4.1. Die Werte wurden so gewählt, dass die Wahrscheinlichkeit für den Bau einer Zelle mit der Anzahl der bereits bebauten Nachbarzellen ansteigt. Dies entspricht den empirischen Beobachtungen beim Nestbau realer Wespen (siehe Abschnitt 2.1.1) und sollte der Erwartung nach Strukturen mit hoher Fitness erzeugen.

Abbildung 4.5: Vergleich der Fitnesswerte der von 100 identischen Individuen gebauten Wabenstrukturen

(a) F_{21} = 0.24  (b) F_{18} = 0.63

Abbildung 4.6: Von identischen Individuen (a) Nr. 21 und (b) Nr. 18 gebaute Strukturen mit zugehörigem Fitnesswert F

In Abbildung 4.5 sind die von den 100 identischen Individuen erzielten Fitnesswerte dargestellt. Es ist sehr starkes Schwanken festzustellen. Die Fitnesswerte schwanken zwischen F_{min} = 0.24 und F_{max} = 0.63 bei einer durchschnittlichen Fitness F_{avg} = 0.43. Zur weiteren Veranschaulichung zeigt Abbildung 4.6 die beiden zu F_{min}

4.3 Simulation mit zwei hierarchisch geordneten Regelsätzen

und F_{max} gehörenden Strukturen. Die beiden Waben wurden von identischen Individuen mit gleichem Regelsatz und ebenso gleicher Stärkeverteilung der Klassifikatoren erzeugt. Die starken Unterschied in optischem Erscheinungsbild und Fitnesswert können daher nur durch die zufällige Bewegung der Agenten und die stochastische Auswahl über die zu aktivierende Regel zustande kommen.

4.3 Simulation mit zwei hierarchisch geordneten

Regelsätzen

Durch die Erweiterung des Simulationsmodells um einen zweiten Regelsatz, der nach einer festgesetzten Anzahl von Simulationsschritten an Stelle des ersten Regelsatzes aktiviert wird (siehe Abschnitt 3.4.3), konnten komplexere Strukturen gebaut werden. Mit dem verwendeten zweiten Regelsatz (siehe Tabellen 3.3 und 3.4) wurde um die bereits mit Regelsatz 1 gebaute Struktur (Bausteintyp 1, rot) ein geschlossener Ring gebaut (Bausteintyp 2, grün). Das Ergebnis ist in Abbildung 4.7 zu sehen.

Der Simulation lagen die folgenden Parameter zugrunde:

   • DX = 41
   • DY = 41
   • wespenanzahl = 1
   • MaxSteps = 100
   • MaxSteps2 = 1000

• Zahl der hierarchischen Ebenen von Klassifikatoren: rulesetanzahl = 2

• Regelsatz der ersten hierarchischen Ebene: RuleSet1 (Tabelle 3.2)

• Regelsatz der zweiten hierarchischen Ebene: RuleSet2 (Tabellen 3.3 und 3.4)

MaxSteps und MaxSteps2 sind so zu interpretieren, dass die Simulation nach MaxSteps Schritten auf den zweiten Regelsatz umschaltet und dann nach insgesamt MaxSteps2 Schritten die Simulation beendet. In diesem Beispiel wurde also 100 Schritte lang RuleSet1 verwendet und danach 900 Schritte lang RuleSet2. MaxSteps2 wurde vergleichsweise hoch gewählt, um zu gewährleisten, dass der Agent trotz stochastischer 4 Simulationsergebnisse Bewegung die Gelegenheit bekommt, an jede Randposition der Struktur zu kommen, und dadurch einen geschlossenen Ring grüner Bausteine zu bauen.

Abbildung 4.7: Endzustand einer Beispielsimulation mit zwei hierarchisch hintereinandergeschalteten Regelsätzen 4.3 Simulation mit zwei hierarchisch geordneten Regelsätzen

Regelindex Stärkewert S
1  255
2  250
3  250
4  250
5  250
6  250
7  250
8  230
9  230
10  230
11  230
12  230
13  230
14  150
15  150
16  150
17  150
18  150
19  150
20  50
21  50
22  50
23  50
24  50
25  50
26  250
27  250
28  250
29  250
30  250
31  250

5 Diskussion

Tabelle 4.1: Stärkewerte des Regelsatzes in Simulation 4.2 4 Simulationsergebnisse 74 Die zentrale Hypothese dieser Arbeit war, dass es möglich ist, anhand eines agentenbasierten Simulationsmodells auf Basis Genetischer Algorithmen und Lernender Klassifizierender Systeme den Nestbau von Insekten abstrakt nachzubilden. Es wurde weiterhin angenommen, dass es möglich ist, die Parameter des Modells während der Simulation so anzupassen, dass sich die erzeugten Strukturen nach vorgegebenen Fitness-Kriterien immer weiter verbessern, bis ein Optimum erreicht ist. Diese Hypothesen konnten anhand der durchgeführten Simulationen nicht vollständig bestätigt werden.

Abbildung 5.1: Wabe eines Bienenschwarms mit drei konzentrischen Zellregionen (Bonabeau et al., 1999)

Was gezeigt werden konnte ist, dass das Modell bei Wahl eines geeigneten Regelsatzes in der Lage ist, eine zusammenhängende Wabenstruktur zu erzeugen, die keine Löcher aufweist. Außerdem wurde in dieser Arbeit gezeigt, dass sich hierarchische Klassifikatoren zum Bau komplexer Strukturen eignen. Durch eine Kombination von zwei nacheinander benutzten Regelsätzen konnte eine Ringstruktur erzeugt werden, die an die Strukturen erinnert, die in den Waben der Honigbiene zu finden sind. Eine genauere Beschreibung der gewählten Vorgehensweise ist in Abschnitt 4.3 zu finden. In Abbildung 5.1 ist eine Bienenwabe zu sehen, die eine ringförmige Struktur aufweist. Im inneren Ring wird die Brut der Bienen aufgezogen und in den äußeren Ringen Honig und Pollen gelagert. Im Vergleich mit Abbildung 4.7 zeigt sich die Ähnlichkeit der Ringstrukturen. Es ist kein einzelner Regelsatz denkbar, mit dem eine derartige Struktur erzeugt werden könnte.

Bei dem gewählten Fitness-Kriterium der Kompaktheit konnte jedoch in keinem der Simulationsläufe eine Verbesserung durch Anwendung eines Genetischen Algorithmus beobachtet werden. Die durchschnittliche Fitness der Population blieb auch bei häufiger Anwendung des Genetischen Algorithmus von stochastischen Abweichungen abgesehen mehr oder weniger konstant. Die einzige beobachtete Verbesserung bei der Simulation mit unbeschränkter Populationsgröße (siehe Abschnitt 4.1.1) ist vermutlich dadurch zu erklären, dass die Größe der Population im Laufe der Simulation auf das dreifache ihrer Ausgangsgröße anwächst (von 20 auf 60) und dadurch stochastisch auch die Anzahl guter Lösungen in der Population. Der Genetische Algorithmus konvergiert also nicht zu einem Optimum hin, wobei sich die Frage stellt, warum er das nicht tut. Im Folgenden wird versucht, eine Antwort auf diese Frage zu geben, und diskutiert, wie Mechanismen und Parameter verändert werden könnten, um bessere Ergebnisse zu erzielen.

In der vorliegenden Arbeit wurde ein Genetischer Algorithmus auf die Stärkewerte der Klassifikatoren angewendet, um diese zu optimieren. In den meisten Lernenden Klassifizierenden Systemen wird im Gegensatz dazu der Genetische Algorithmus auf die Klassifikatoren selbst angewendet, das heißt es entstehen in solchen Systemen tatsächlich neue Regelsätze (vgl. Bernauer (2007)), während im hier implementierten Modell der Regelsatz selbst gleich bleibt und sich nur die Wahrscheinlichkeit für die Anwendung der einzelnen Regeln ändert. Es gilt zu prüfen, ob der Einsatz von Reinforcement Learning (siehe Abschnitt 2.4.1) für die Rückpropagierung der globalen Fitness auf die beteiligten Klassifikatoren geeignet ist, um bessere Ergebnisse zu erzielen. Der Genetische Algorithmus könnte in Kombination damit wie oben beschrieben zur Erzeugung neuer Regelsätze implementiert werden.

Auch in der Implementation der Fitnessfunktion sind Änderungen denkbar. Um eine Wabenstruktur zu erzeugen, die den an reale Nester gestellten Ansprüchen nahekommt, müssten außer dem Kriterium der Kompaktheit noch andere Parameter in die Berechnung der Fitness miteinfließen. Bei Betrachtung der erzeugten Strukturen fällt auf, dass diese meist nicht konzentrisch um den Mittelpunkt gebaut sind. Fasst man den Mittelpunkt der Wabe als Aufhängung an einem Ast (Pedikel, siehe Abschnitt 2.1) auf, so müsste die Wabe eine gewisse Symmetrie in Bezug auf diesen Mittelpunkt aufweisen, um stabil zu sein. Ein wichtiger zusätzlicher Faktor für die Fitness wäre also die Symmetrie der Wabe. Mit dem hier vorgestellten Modell wird es allerdings schwierig sein, eine symmetrische Wabe zu bauen. Die Schwierigkeit, symmetrische Waben zu bauen, hängt mit der rein stochastischen Bewegung der Agenten auf der Wabe zusammen. Ein neues Bewegungsmodell für die Agenten, das zielgerichtete Bewegungen erlaubt, könnte dieses Problem lösen. Die Agenten könnten sich zum Beispiel spiralförmig vom Mittelpunkt ausgehend mit größer werdendem Radius über die Wabe bewegen, ähnlich wie dies beim Bau von Spinnennetzen zu beobachten ist (Krink und Vollrath, 1997). Auch die Schrittweite der Agenten, die im Modell konstant ist, könnte verändert werden. In der aktuellen Implementierung bewegen sich die Agenten pro Zeitschritt um eine festgelegte konstante Schrittweite in eine zufällig ausgewählte Richtung. Da dieses vereinfachte Bewegungsmodell die Realität nicht exakt abbildet, könnte es eine Verbesserung für das Simulationsmodell darstellen, die Bewegung der Agenten komplexer zu gestalten. Eine mögliche Lösung könnte es sein, auch die Bewegungsrichtung von Regeln abhängig zu machen, so dass sich die Agenten gezielt in die Richtung bewegen könnten, in der noch gebaut werden muss. Man könnte dazu die Mege der möglichen Aktionen, die im Moment auf Bauaktionen beschränkt sind, um Bewegungsaktionen erweitern. Jeder Agent würde dann in jedem Zeitschritt entweder eine Bewegung ausführen oder eine neue Zelle bauen.

Eine weitere wichtige Frage ist, ob der Wahrnehmungsbereich der Agenten groß genug gewählt ist. Die Regeln, nach denen die Agenten bauen, berücksichtigen zur Zeit lediglich diejenigen Zellen, die direkt an die potentielle Bauposition angrenzen. Dieser Ansatz ist eventuell zu eng, um dem realen Vorbild gerecht zu werden. Auch wenn ein einzelnes Insekt nicht in der Lage ist, eine komplexe Struktur wie ein großes Wespennest im Ganzen zu erfassen, kann es den Zustand von Zellen berücksichtigen, die weiter entfernt von ihm sind. Es ist daher davon auszugehen, dass der Zustand der Wabe an einem weiter entfernten Ort durchaus Einfluss auf das Verhalten des einzelnen Individuums nimmt. Es wird also vorgeschlagen, das Modell in der Form zu erweitern, dass für weiter entfernte Zustände eigene Regelsätze aufgestellt werden, die hierarchisch zueinander geordnet parallel aktiv sind. Dabei haben Regelsätze für den Nahbereich Vorrang vor Regelsätzen für den Fernbereich. Es entstände so eine weitere Form der hierarchischen Ordnung von Klassifikatoren, in der die Regelsätze nicht nacheinander aktiviert wären (wie im Beispiel in Abschnitt 4.3), sondern gleichzeitig.

Diese Idee der gleichzeitig aktiven hierarchisch geordneten Klassifikatoren lässt sich beliebig erweitern. Man könnte für verschiedene Fitnesskriterien wie Größe, Symmetrie oder Stabilität der Wabe eigene Sätze von Klassifikatoren einführen, die parallel aktiv sind und zwischen denen abhängig vom äußeren Systemzustand umgeschaltet werden kann. Bei diesen Ideen zur Erweiterung des Modells muss allerdings berücksichtigt werden, dass jeder zusätzliche Parameter des Modells das Optimierungsproblem komplexer macht. Ein lernendes Sytem zu entwerfen, das zu einem Optimum konvergiert, würde so noch schwieriger als im aktuell implementierten Modell.

Abbildung 5.2: Dreidimensionale Wabenstrukturen, erzeugt durch den Baulgorithmus von Bonabeau et al. (2000)

Der Ansatz der im Rahmen dieser Arbeit realisierten Implementation orientiert sich im Wesentlichen an den Arbeiten von Theraulaz und Bonabeau über ihr Simulationsmodell zum Bau komplexer Strukturen durch Schwärme von Agenten (Theraulaz und Bonabeau, 1995; Bonabeau et al., 1999, 2000). Es gibt jedoch einige entscheidende Unterschiede in der Implementation. Bei Bonabeau et al. (1999) wurde ein deterministischer Algorithmus zur Regelauswahl der Agenten realisiert. Bei deterministischen Algorithmen werden Zufallsentscheidungen ausgeschlossen, daher wird bei Bonabeau et al. (1999) eine passende Regel immer mit Wahrscheinlichkeit 1 angewendet. Das impliziert auch, dass in dem dort implementierten Modell keine Regeln gleichzeitig zu einem bestimmten Input passen dürfen, weil der deterministische Algorithmus nicht dafür konzipiert ist, zwischen zwei passenden Regeln zu entscheiden. In der vorliegenden Arbeit wurde im Gegensatz dazu ein stochastischer Algorithmus zur Regelauswahl implementiert. Bei stochastischen Algorithmen werden zufällige Auswahlkriterien berücksichtigt, so dass wie in Abschnitt 3.4.2 beschrieben auch mehrere Regeln auf einen Input passen können, da der stochastische Algorithmus in der Lage ist, eine der passenden Regeln auszuwählen. Bonabeau et al. (1999) hatten ihr Modell dreidimensional erweitert, um die Erzeugung komplexer Strukturen zu ermöglichen und dem Erscheinungsbild realer Wespennester näher zu kommen als dies im zweidimensionalen Raum möglich wäre. Einige Beispiele für so entstandene dreidimensionale Strukturen finden sich in Abbildung 5.2.

Es wird vorgeschlagen, das in dieser Arbeit vorgestellte zweidimensionale Modell in den dreidimensionalen Raum zu erweitern. Eine solche Erweiterung wäre mit relativ wenig Aufwand möglich, indem man eine Anzahl von Ebenen übereinanderlegt. Das wäre kein streng genommen dreidimensionales Modell, da der Agent weiterhin nur eine zweidimensionale Position hätte und die Position in der dritten Dimension nur durch die Nummer der Ebene, in der sich der Agent befindet, angegeben wäre. Für die hier betrachtete Anwendung wäre es jedoch vermutlich ausreichend, da auch Bonabeau et al. (2000) mit einem vergleichbaren Modell arbeiten. Es wäre allerdings nötig, die Bauregeln der Agenten dahingehend zu erweitern, dass auch die über und unter dem Agenten liegenden Ebenen berücksichtigt werden. Außerdem müsste festgelegt werden, wann ein Agent in eine andere Ebene wechselt.

In der implementierten Regelverarbeitung werden Einzelaktionen betrachtet. Wird ein Klassifikator aktiviert, so baut der entsprechende Agent genau eine neue Zelle. Um komplexere Strukturen zu erzeugen, wird vorgeschlagen, mehrere Aktionen zu einer Sequenz zusammenzufassen, die als Ganzes aktiviert und bewertet wird. Da Aktionen vorstellbar sind, die nur in Zusammenhang mit anderen Aktionen sinnvoll sind, erscheint eine solche Erweiterung der Regeldefinitionen vielversprechend.

Eine weitere interessante Frage ist, inwieweit sich die von einem einzelnen Agenten gebauten Wabenstrukturen von denen eines Schwarms von Agenten unterscheidet. In der vorliegenden Arbeit wurden nur Simulationen mit einem einzelnen gleichzeitig aktiven Agenten vorgestellt. Simulationen mit Schwärmen von mehreren Agenten würden unter Umständen zu anderen Ergebnissen führen. Vor allem stellt sich bei Simulationen mit mehreren gleichzeitig bauenden Agenten die Frage, ob alle Agenten den gleichen Regelsatz verwenden, oder ob sich die Regelsätze unterscheiden. Eine Betrachtung der Natur würde auf den ersten Blick nahe legen, für jeden Agenten einen individuellen Regelsatz zu definieren, da es in Kolonien sozialer Wespen wie bei allen staatenbildenden Insekten verschiedene Kasten von Individuen gibt, die für verschiedene Aufgaben zuständig sind (z.B. Arbeiterin, Drohne, Königin bei Bienen), und Angehörige verschiedener Kasten innerhalb eines Insektenstaates offensichtlich unterschiedlichen Verhaltensregeln unterliegen (Wilson, 1971). Auf der anderen Seite können sich die Regeln, nach denen Insekten einer einzelnen Spezies agieren, auch nicht völlig grundsätzlich voneinander unterscheiden, sonst würde man die entstehenden Strukturen nicht so eindeutig bestimmten Arten zuordnen können. So haben die Nester der meisten Wespenarten charakteristische architektonische Eigenschaften, durch die sie sich eindeutig einer bestimmten Spezies zuordnen lassen (Wenzel, 1989; Matsuura und Yamane, 1990). Auch hier wäre die Methode, Hierarchien von Klassifikatoren einzuführen, ein Lösungsansatz. Jeder Agent bekommt die gleichen Regelsätze, wobei sich die hierarchische Ordnung der Regelsätze untereinander von Individuum zu Individuum unterscheidet.

Zusammenfassend lässt sich festhalten, dass mit dem vorliegenden Modell zum Wabenbau von Insekten ein Ansatz geschaffen wurde, dessen weitere Verfolgung große Fortschritte verspricht. Das vorgestellte Modell ist in der aktuellen Form noch nicht komplex genug, um die in der Natur zu beobachtenden Vorgänge abzubilden. Auch die Hypothese, dass durch Einsatz von Genetischen Algorithmen und Lernenden Klassifizierenden Systemen eine Anpassung der Bauregeln an festgelegte Fitnesskriterien erfolgen müsste, konnte nicht bestätigt werden. Vermutlich liegt dies an der Art und Weise, wie das LCS und der Genetische Algorithmus im Detail implementiert wurden. Hier wären noch Experimente mit unterschiedlichen Implementationen nötig, um zu einem funktionierenden Modell zu kommen. Vor allem der Einsatz hierarchisch geordneter Klassifikatoren stellt jedoch eine entscheidende Neuerung für diese Anwendung dar, deren Resultate sehr vielversprechend sind. Eine Weiterentwicklung dieses Konzepts wäre möglicherweise in der Lage, viele der momentanen Einschränkungen des Modells zu beseitigen und Wabenstrukturen zu bauen, die den Strukturen realer Wespennester ähnlicher sind als die, die bisher mit vergleichbaren Modellen erzeugt wurden.

Literaturverzeichnis

5 Diskussion 82 [Bernauer 2007] Bernauer, Andreas: Das Learning Classifier System XCS.

2007. – URL http://www-ti.informatik.uni-tuebingen.de/~bernauer/
Bernauer07_XCS.pdf

[Bonabeau et al. 1999] Bonabeau, Eric ; Dorigo, Marco ; Theraulaz, Guy: Swarm Intelligence. From Natural to Artificial Systems. Oxford University Press, 1999

[Bonabeau et al. 2000] Bonabeau, Eric ; Guérin, Sylvain ; Snyers, Dominique ; Kuntz, Pascale ; Theraulaz, Guy: Three-dimensional architectures grown by simple ’stigmergic’ agents. In: BioSystems 56 (2000), S. 13–32

[Bull und Kovacs 2005] Bull, Larry ; Kovacs, Tim: Foundations of Learning Classifier Systems: An Introduction. In: Bull, Larry (Hrsg.) ; Kovacs, Tim (Hrsg.): Foundations of Learning Classifier Systems. Berlin : Springer, 2005, S. 1–17

[Butz 2006] Butz, Martin V.: Studies in Fuzziness and Soft Computing. Bd. 191: Rule-Based Evolutionary Online Learning Systems : A Principled Approach to LCS Analysis and Design. Berlin : Springer, 2006

[Camazine 1991] Camazine, Scott: Self-organizing pattern formation on the combs of honey bee colonies. In: Behav Ecol Sociobiol 28 (1991), S. 61–76

[Camazine et al. 2001] Camazine, Scott ; Deneubourg, Jean-Louis ; Franks, Nigel R. ; Sneyd, James ; Theraulaz, Guy ; Bonabeau, Eric: Self-Organization in Biological Systems. Princeton University Press, 2001

[Darwin 1988] Darwin, Charles: On the Origin of Species by Means of Natural Selection. London : William Pickering, 1988 [Deneubourg et al. 1992] Deneubourg, Jean-Louis ; Theraulaz, Guy ;

Beckers, Ralph: Swarm-Made Architectures. In: Varela, Francisco J. (Hrsg.) ; Bourgine, Paul (Hrsg.): Toward a Practice of Autonomous Systems : Proceedings of the First European Conference on Artificial Life. Cambridge, MA, USA : MIT Press, 1992, S. 123–133

[Eigen und Schuster 1979] Eigen, Manfred ; Schuster, Peter: The Hypercycle : a principle of natural self-organization. Berlin : Springer, 1979

[Floreano und Mattiussi 2008] Floreano, Dario ; Mattiussi, Claudio: Bio-Inspired Artificial Intelligence. Cambridge, MA, USA : MIT Press, 2008

[Geyer-Schulz 1995] Geyer-Schulz, Andreas: Holland classifier systems. In: APL ’95: Proceedings of the international conference on Applied programming languages. New York, NY, USA : ACM, 1995, S. 43–55

[Goldberg 1989] Goldberg, David E.: Genetic Algorithms in Search, Optimization & Machine Learning. Addison Wesley Longman, 1989

[Grassé 1959] Grassé, Pierre-Paul: La reconstruction du nid et le coordinations inter-individuelles chez Bellicositermes natalensis et Cubitermes sp. La theorie de la stigmergie: Essai d’interpretation du comportement des termites constructeurs. In: Insectes Sociaux 6 (1959), S. 41–81

[Holland 1975] Holland, John H.: Adaptation in natural and artificial systems : an introductory analysis with applications to biology, control, and artificial intelligence. Ann Arbor : University of Michigan Press, 1975

[Holland 1976] Holland, John H.: Adaptation. In: Rosen, Robert (Hrsg.) ; Snell, Fred M. (Hrsg.): Progress in Theoretical Biology 4. New York : Academic Press, 1976, S. 263–293

[Holland 1986] Holland, John H.: A Mathematical Framework for Studying Learning in Classifier Systems. In: Physica D 2 (1986), Nr. 1-3, S. 307–317

[Holland 1992] Holland, John H.: Adaptation in Natural and Artificial Systems: an introductory analysis with applications to biology, control, and artificial intelligence. 2. Auflage. Cambridge, MA, USA : MIT Press, 1992 [Hölldobler und Wilson 1990] Hölldobler, Bert ; Wilson, Edward O.: The

Ants. Berlin : Springer, 1990

[Karsai 1999] Karsai, István: Decentralized control of construction behavior in paper wasps: an overview of the stigmergy approach. In: Artif. Life 5 (1999), Nr. 2, S. 117–136

[Krink und Vollrath 1997] Krink, Thiemo ; Vollrath, Fritz: Analysing Spider Web-building Behaviour with Rule-based Simulations and Genetic Algorithms. In: Journal of Theoretical Biology 185 (1997), Nr. 3, S. 321–331. –

URL http://www.sciencedirect.com/science/article/B6WMD-45KKS7X-6W/
2/16b87cde2eb3c825de73d5d7493ba37e

[Matsuura und Yamane 1990] Matsuura, Makoto ; Yamane, Seiki: Biology of the Vespine Wasps. Berlin : Springer, 1990

[Nissen 1997] Nissen, Volker: Einführung in Evolutionäre Algorithmen. Braunschweig : Vieweg Verlag, 1997

[Page et al. 2000] Page, Bernd ; Lechler, Tim ; Claassen, Sönke: Objektorientierte Simulation in Java mit dem Framework DESMO-J. Norderstedt : Libri Books on Demand, 2000

[Sigaud und Wilson 2007] Sigaud, Olivier ; Wilson, Stewart W.: Learning Classifier Systems: A Survey. In: Soft Comput. 11 (2007), Nr. 11, S. 1065–1078

[Smith 1980] Smith, S. F.: A Learning System Based on Genetic Algorithms. Pittsburgh, University of Pittsburgh, Dissertation, 1980

[Sutton 2004] Sutton, Richard S.: Reinforcement Learning FAQ : Frequently Asked Questions about Reinforcement Learning. Februar 2004. – URL http:

//www.cs.ualberta.ca/~sutton/RL-FAQ.html

[Sutton und Barto 1998] Sutton, Richard S. ; Barto, Andrew G.: Reinforcement learning : an introduction. Cambridge, MA, USA : MIT Press, 1998

[Theraulaz und Bonabeau 1995] Theraulaz, Guy ; Bonabeau, Eric: Modelling the Collective Building of Complex Architectures in Social Insects with Lattice Swarms. In: Journal of theoretical Biology 177 (1995), S. 381–400 [Theraulaz et al. 1999] Theraulaz, Guy ; Bonabeau, Eric ; Deneubourg, Jean-

Louis: The mechanisms and rules of coordinated building in social insects. In: Detrain, Claire (Hrsg.) ; Deneubourg, Jean-Louis (Hrsg.) ; Pasteels, Jacques M. (Hrsg.): Information Processing in Social Insects. Basel : Birkhäuser, 1999, S. 309–330

[Watkins 1989] Watkins, Christopher: Learning from Delayed Rewards. Cambridge, England, King’s College, Dissertation, 1989

[Weicker 1999] Weicker, Karsten: Evolutionäre Algorithmen. In: Weicker, Karsten (Hrsg.): Softcomputing - Tagungsband zum ersten Softcomputing-Treffen. Stuttgart : Informatikverbund Stuttgart, 1999, S. 27–39

[Weicker 2002] Weicker, Karsten: Evolutionäre Algorithmen. Stuttgart : Teubner, 2002

[Wenzel 1989] Wenzel, John W.: Endogenous Factors, External Cues, and Eccentric Construction in Polistes annularis (Hymenoptera: Vespidae). In: Journal of Insect Behavior 2 (1989), Nr. 5, S. 679–699

[Wilson 1971] Wilson, Edward O.: The Insect Societies. Cambridge, MA, USA : Belknap Press of Harvard University Press, 1971

[Wilson 1995] Wilson, Stewart W.: Classifier Fitness Based on Accuracy. In: Evolutionary Computation 3 (1995), Nr. 2, S. 149–175

[Winston 1991] Winston, Mark L.: The Biology of the Honey Bee. Harvard University Press, 1991

Abbildungsverzeichnis

0.1 Wespe beim Nestbau (Foto: Don Van Dyke) . . . . . . . . . . . . . . 8

2.1 Aufhängung eines Wespennestes (Theraulaz und Bonabeau, 1995) . . 14 2.2 Leeres Wespennest (Foto von http://www.honighaeuschen.de/) . . 15 2.3 Nester verschiedener Wespenarten (Theraulaz und Bonabeau, 1995) . 15 2.4 Stigmergie beim Wabenbau (Camazine et al., 2001) . . . . . . . . . . 17 2.5 Anzahl von Nachbarzellen (Camazine et al., 2001) . . . . . . . . . . . 18 2.6 Bauwahrscheinlichkeit (Camazine et al., 2001) . . . . . . . . . . . . . 18 2.7 Das Animat-Problem (Bernauer, 2007) . . . . . . . . . . . . . . . . . 33 2.8 Schema eines Learning Classifier System (nach Bernauer (2007)) … 34

3.1 Ergebnis einer Simulation nach sechs Bauschritten . . . . . . . . . . . 45 3.2 Initialzustand der Simulation mit bebauten Anfangszellen . . . . . . . 45 3.3 Vergleich zwischen Wabenstrukturen . . . . . . . . . . . . . . . . . . 55 3.4 Schema von Ein-Punkt-Crossover (Nissen, 1997) . . . . . . . . . . . . 58 3.5 Unbebaute sechseckige Gitterstruktur . . . . . . . . . . . . . . . . . . 60 3.6 Wabenstruktur aus drei Bausteintypen . . . . . . . . . . . . . . . . . 61

4.1 Maximale Fitness ohne Beschränkung der Populationsgröße . . . . . . 65 4.2 Fitness bei Population von 100 und 100 GA-Durchläufen . . . . . . . 66 4.3 Entwicklung der Fitness mit Crossover-Wahrscheinlichkeit . . . . . . 67 4.4 Entwicklung der Fitness mit Zurücklegen . . . . . . . . . . . . . . . . 69 4.5 Vergleich von Waben von 100 identischen Individuen . . . . . . . . . 70 4.6 Von identischen Individuen gebaute Wabenstrukturen . . . . . . . . . 70 4.7 Ringstruktur bei Simulation mit zwei Regelsätzen . . . . . . . . . . . 72

5.1 Wabe eines Bienenschwarms (Bonabeau et al., 1999) . . . . . . . . . . 75 5.2 Dreidimensionale Wabenstrukturen (Bonabeau et al., 2000) . . . . . . 78 Abbildungsverzeichnis 88

Tabellenverzeichnis

2.1 Zahlenwerte in Dezimal-, Standardbinär- und Gray-Codierung …. 28

3.1 Vom Regelwerk verwendete Zeichen und ihre Bedeutung . . . . . . . 49 3.2 Kompletter Regelsatz RuleSet1 . . . . . . . . . . . . . . . . . . . . . 51 3.3 Kompletter Regelsatz RuleSet2 (Teil 1) . . . . . . . . . . . . . . . . 53 3.4 Kompletter Regelsatz RuleSet2 (Teil 2) . . . . . . . . . . . . . . . . 54

4.1 Stärkewerte des Regelsatzes in Simulation 4.2 . . . . . . . . . . . . . 73 Tabellenverzeichnis 90

A MATLAB-Quellcode

A.1 simulationsumgebung.m

1 % Simulationsumgebung für den Wabenbau sozialer Insekten

2 global DX;
3 global DY;
4 global Wabengitter ;
5 global Knotenzahl ;
6 global z e i t ;
7 global Grenzen ;
8 global MittelPunkte ;
9 global MittelWabe ;
10 global raumplot ;
11 global b e b a u t e z e l l e n ;
12 global wespenanzahl ;
13 global numberofruns ;
14 global numberofgaruns ;
15 global gadurchlauf ;
16 global animation ;
17 global r i n g ;

18 19 % Parameter der Simulation 20 DX = 41; % Breite des Gitters 21 DY = 41; % Höhe des Gitters 22 wespenanzahl = uint8 ( 1 ) ; % Zahl der aktiven Agenten pro einzelner Wabe 23 MaxSteps = uint16 ( 2 0 0 ) ; % Zahl der Schritte pro Simulationslauf 24 MaxSteps2 = uint16 ( 4 0 0 ) ; % Zahl der Schritte für zweite Hierarchie 25 numberofruns = uint8 ( 2 0 0 ) ; % Größe der GA-Population 26 numberofgaruns = uint8 ( 5 0 ) ; % Zahl der Durchläufe des GA 27 r u l e s e t a n z a h l = uint8 ( 1 ) ; % Zahl der unterschiedlichen Regelsätze 28 animation = true ; % Parameter, um einzustellen, ob der Bauvorgang auch gra-

phisch angezeigt wird 29 30 % Die äußerste Schleife wird pro hierarchischem Regelsatz einmal durchlaufen

31 for r i n g=uint8 ( 1 ) : r u l e s e t a n z a h l

32 33 % Diese Schleife wird für jeden Durchlauf des GA einmal durchlaufen

34 for gadurchlauf=uint8 ( 1 ) : numberofgaruns

35 close a l l ; % schließt alle vorherigen Fenster 36

37  for run=uint8 ( 1 ) : numberofruns
38  Wabengitter = hextop (DX,DY) ;

39 % Erzeugen des hexagonalen Gitters 40 % Struktur der Matrix: 41 % Zeile 1: X-Koordinate des Knotenpunkts 42 % Zeile 2: Y-Koordinate des Knotenpunkts 43 % Zeile 3: Markierung, ob Knotenpunkt Wabenmittelpunkt ist (1/0) 44 % Zeile 4: Belegung des Feldes (0 = leer, 1 = Baustein Typ 1, ...) 45

46 Knotenzahl = size ( Wabengitter , 2 ) ;

47 48 % Algorithmus zur Markierung der Wabenmittelpunkte 49 % - legt eine dritte Zeile in der Matrix Wabengitter an und markiert jeden 50 % Knotenpunkt, der einem Wabenmittelpunkt entspricht, mit einer 1 51 P o s i t i o n = DX + 2 ; % Initialisierung - erster Wabenmittelpunkt

52 for P o s i t i o n=DX+2:3:2∗DX−1

53 % die zweite Reihe vom zweiten bis zum vorletzten Element 54 % mit horizontalem Abstand 3

55 Position2 = P o s i t i o n ;

56 while Position2 < ( Knotenzahl − DX) % oberste Zeile ausschließen 57 Wabengitter (3 , Position2 ) = 1 ; % Setze Markierung für Mittelpunkt

58 Position2 = Position2 + 2 ∗ DX;
59 end

A.1 simulationsumgebung.m

60 Position2 = P o s i t i o n + DX + 2 ;
61 i f (mod( Position2 ,DX) > 1) && (mod( Position2 ,DX) < DX)
62 while Position2 < Knotenzahl − DX
63 Wabengitter (3 , Position2 ) = 1 ;
64 Position2 = Position2 + 2∗DX;
65 end
66 end
67 end

68

69 MittelPunkte = find ( Wabengitter ( 3 , : ) ) ;

70 % erzeugt einen Vektor mit Indizes der Wabenmittelpunkte

71 Grenzen = max( Wabengitter , [ ] , 2 ) ;

72 % ereugt einen Vektor, der die Endkoordinaten des Gitters enthält

73 MittelWabe = MittelPunkte ( c e i l ( length ( MittelPunkte ) / 2 ) ) ;

74 % Index der annähernd mittleren Wabe (Ausgangspunkt für die Simulation)

75 mittelnachbarn = nachbarn ( MittelWabe ) ;

76 Wabengitter (4 , MittelWabe ) = 1 ; % Baustein vom Typ 1 an Mittelpunkt ge-

setzt 77 % Wird als Anfangspunkt benötigt

78 for nachbarindex =1:6
79 Wabengitter (4 , mittelnachbarn ( nachbarindex ) ) = 1 ;
80 end

81 % die sechs direkten Nachbarn des Mittelpunkts werden als bebaut markiert 82

83 i f ( gadurchlauf = numberofgaruns )

84 % nur beim letzten Durchlauf grafisch anzeigen

85 s c r s z = get (0 , ’ ScreenSize ’ ) ;

86 % erzeuge figure für die graphische Anzeige

87 v i s u a l = figure ( ’Name ’ , …
88 [ ’GA␣ ’ num2str( gadurchlauf ) ’ ␣RS␣ ’ num2str( run ) ] , …
89 ’ P o s i t i o n ’ , [ 1 s c r s z (4) s c r s z (3) s c r s z ( 4 ) ] , …
90 ’ NumberTitle ’ , ’ o f f ’ ) ;
91 raumplot = gca ;

92 % verhindern, dass gezeichnetes wieder gelöscht wird:

93 hold on ;

94 95 % Betrachtungswinkel einstellen

96 view ( 3 ) ;
97 axis ( raumplot , ’ manual ’ ) ;

98 set ( raumplot , ’ DataAspectRatio ’ , [ 1 1 1 ] ) ; % , ...

99 axis ( raumplot ,[ −2 ( Grenzen (1)+2) −2 ( Grenzen ( 2 ) + 2 ) ] ) ;
100 camlight ( ’ r i g h t ’ ) ;
101 camproj ( ’ p e r s p e c t i v e ’ ) ;
102 l i g h t i n g gouraud ;

103 104 % leeres Gitter anzeigen

105 p l o t g i t t e r ( Wabengitter , raumplot ) ;

106 plotwabe ( MittelWabe , raumplot , 8 ) ; % die Anfangswabe wird markiert

107 for nachbarindex =1:6
108 plotwabe ( mittelnachbarn ( nachbarindex ) , raumplot , 8 ) ;

109 end % die sechs unmittelbaren Nachbarzellen der Mittelwabe werden auch gesetzt 110 % verhindert die Notwendigkeit einer Einserregel

111 end

112 113 i f ( r i n g = 1) % nur für den ersten Regelsatz 114 115 i f ( gadurchlauf = 1) % Nur im ersten Durchlauf des GA... 116 % ...wird die durch wespenanzahl festgelegte Menge von Objekten der 117 % Klasse agent angelegt.

118 for nummer=uint8 ( 1 ) : wespenanzahl
119  wespe ( run , nummer) = …
120  bauagent ( Wabengitter ( 1 : 2 , MittelWabe ) ’ , nummer ) ;

121 % erzeugt ein Objekt der Klasse Bauagent auf den Koordinaten 122 % der mittleren Wabe

123 end

124 global wespe ; % ’workaround’, um das Array, das die Agenten beinhaltet, 125 % nachträglich als global zu definieren. Gilt als deprecated, 126 % funktioniert aber in der verwendeten Version von MATLAB. 127 % Eine Vorabdeklaration als global funktioniert nicht, weil das Array 128 % dann automatisch als numerisch deklariert wird.

129 else

130 % dieser else-block wird nur in späteren Durchläufen des GA erreicht. 131 % wespe ist dann schon als global deklariert und kann benutzt werden.

132 for nummer=uint8 ( 1 ) : wespenanzahl
133 wespe ( run , nummer ) . BuildCounter = 0 ;
134 wespe ( run , nummer ) . P o s i t i o n = Wabengitter ( 1 : 2 , MittelWabe ) ’ ;
135 end
136 end
137 else

138 % für den zweiten Durchlauf in der Hierarchie mit zwei 139 % hintereinander zu benutzenden Regelsätzen

140 for nummer=uint8 ( 1 ) : wespenanzahl
141 wespe ( run , nummer ) . c l a s s i f i e r s e t = …
142  b e s t c l a s s i f i e r s e t 1 ;
143 wespe ( run , nummer ) . n u m b e r o f c l a s s i f i e r s = …
144  length ( wespe ( run , nummer ) . c l a s s i f i e r s e t ) ;
145 wespe ( run , nummer ) . c l a s s i f i e r f i t n e s s s t r i n g = …
146  s t r c a t ( wespe ( run , nummer ) . c l a s s i f i e r s e t . f i t n e s s s t r i n g ) ;
147 wespe ( run , nummer ) . BuildCounter = 0 ;
148 wespe ( run , nummer ) . P o s i t i o n = Wabengitter ( 1 : 2 , MittelWabe ) ’ ;
149 end
150 end

151 152 153 154 % Simulationsstart

155 %

156 % Update der Liste der Indizes aller bebauten Zellen

157 b e b a u t e z e l l e n = find ( Wabengitter ( 4 , : ) ) ;
158 g r a f i k = gcf ;

159 160 % Simulationsschleife zur äußeren Steuerung der Simulation 161 % - hier werden die Agenten aktivert und bewegt

162 for z e i t=uint16 ( 1 ) : MaxSteps
163  for wespennummer=uint8 ( 1 ) : wespenanzahl

164  wespe ( run , wespennummer ) . movebuild ( ) ;
165  end
166 end

167 168 % Zweiter hierarchischer Regelsatz

169 i f ( r i n g = 2 )
170  for wespennummer=uint8 ( 1 ) : wespenanzahl
171 wespe ( run , wespennummer ) …
172 . u p d a t e c l a s s i f i e r s e t ( wespe ( run , wespennummer ) . RuleSet2 ) ;

173 % Zweites regelwerk wird hier aktiviert

174  end

175 % zweite Zeitschleife für zweite Hierarchieebene

176  for z e i t=MaxSteps+1:MaxSteps2
177  for wespennummer=uint8 ( 1 ) : wespenanzahl
178  wespe ( run , wespennummer ) . movebuild ( ) ;
179  end
180  end
181 end

182 183 % Berechnung des globalen Fitnesswerts der gebauten Wabe

184 [ f i t n e s s w e r t , idealwert , aussenlaenge , wabenanzahl , quotient ] …
185 = f i t n e s s ( Wabengitter ) ;

186 187 % Legt einen Vektor overallfitness an, in dem für den Phänotyp 188 % jedes Regelsatzes seine Overall-Fitness abgespeichert wird. 189 % Dient als Basis für den GA.

190 o v e r a l l f i t n e s s ( run ) = quotient ;
191 end

192

193 strengthga ( o v e r a l l f i t n e s s ) ;

194 % Aufruf des GA zur Erzeugung neuer Regelsätze mit anderen Fitnesswerten 195

196 numberofruns = size ( wespe , 1 ) ;

A.2 bauagent.m

197 % Update der Anzahl der Durchläufe 198 % - wenn neue Individuen (Regelsätze) dazukommen, 199 % müssen diese auch berücksichtigt werden 200

201 [ maxwert , maxindex ] = max( o v e r a l l f i t n e s s ) ;
202 [ minwert , minindex ] = min( o v e r a l l f i t n e s s ) ;

203 % ermittelt den Regelsatz mit bester bzw. niedrigster Fitness 204

205 maxvektor ( gadurchlauf , 1 ) = maxwert ;
206 maxvektor ( gadurchlauf , 2 ) = maxindex ;
207 maxvektor ( gadurchlauf , 3 ) = minwert ;
208 maxvektor ( gadurchlauf , 4 ) = minindex ;
209 maxvektor ( gadurchlauf , 5 ) = mean( o v e r a l l f i t n e s s ) ;
210 end

211

212 i f ( r i n g = 1)

213

214 b e s t c l a s s i f i e r s e t 1 = …
215  wespe ( uint16 ( maxvektor ( gadurchlauf , 2 ) ) ) . c l a s s i f i e r s e t ;

216 % besten Regelsatz zur Wiederverwendung kopieren 217

218 bestwespe1 = wespe ( uint16 ( maxvektor ( gadurchlauf , 2 ) ) ) ;
219 bestwespe1 . BuildCounter = 0 ;
220 bestwespe1 . P o s i t i o n = Wabengitter ( 1 : 2 , MittelWabe ) ’ ;
221 end
222 end

A.2 bauagent.m

1 c l a s s d e f bauagent < handle

2 %BAUAGENT Diese Klasse definiert die Eigenschaften des einzelnen Agenten 3 % Hier werden die Eigenschaften festgelegt, die den einzelnen Agenten 4 % ausmachen, der für den Bau der Wabenstruktur zuständig ist. 5 % Für jeden einzelnen Agenten wird ein Objekt dieser Klasse erzeugt. 6

7 p r o p e r t i e s

8 P o s i t i o n % Vektor, welcher die Position des Agenten in 9 % X-Y(-Z)-Koordinaten enthält. Je nach Umgebung 10 % zwei- oder dreidimensional. 11 Ausrichtung % Blickrichtung des Agenten im Gradmaß (0 bis 360) 12 % Null entspricht Blick waagerecht nach rechts

13 RuleSet1

14 % Enthält die Ausgangsregeln, nach denen gebaut oder nicht 15 % gebaut wird. Hier werden nur Regeln festgelegt, mit 16 % denen begonnen wird, danach werden die Regeln in das 17 % Array classifierset kopiert und nur noch von dort 18 % ausgelesen und auch durch den GA verändert. 19 % Könnte auch aus Datei gelesen werden... 20 RuleSet2 % Regelsatz der zweiten Hierarchieebene 21 BuildCounter % Zählt die Anzahl der gesetzten Bausteine. 22 Abstand % Ein Abstandsvektor, der die absoluten Abstandswerte zu 23 % allen Zellenmittelpunkten enthält 24 Speed = 1 ; % relative Geschwindigkeit, mit der sich der Agent bewegt 25 26 Markierung % graphisches Objekt zur Positionsmarkierung 27 Index % enthält die laufende Nummer des Agenten 28 Farbe % die Farbe zur Markierung 29 c l a s s i f i e r s e t % ein Array, in dem die Objekte vom Typ classifier 30 % abgelegt werden 31 n u m b e r o f c l a s s i f i e r s % Anzahl der vorhandenen Regeln 32 matchset % Array in dem die Indizes aller passenden Klassifikatoren für einen

Zeitschritt abgelegt werden 33 % - wird nach jedem Zeitschritt gelöscht 34 bucket % enthält den Index-Wert des letzten benutzten Klassifikators 35 % wird für den bucket-brigade-Algorithmus benötigt 36 c l a s s i f i e r f i t n e s s s t r i n g % enthält die Fitnessstrings aller Regeln im Gray

code hintereinander

37 end

38

39 methods

40 % Konstruktor

41 function obj = bauagent ( I n i t i a l P o s i t i o n , indexNummer )

42 global Grenzen ;
43 global r i n g ;

44

45 obj . Ausrichtung = 0 ;

46 47 % Definition erster Regelsatz

48 obj . RuleSet1 = [ ’BBBBBB1 ’ ; ’BBBBB01 ’ ; ’ 0BBBBB1 ’ ; …
49  ’B0BBBB1 ’ ; ’BB0BBB1 ’ ; ’BBB0BB1 ’ ; …
50  ’BBBB0B1 ’ ; ’BBBB001 ’ ; ’ 0BBBB01 ’ ; …
51  ’ 00BBBB1 ’ ; ’B00BBB1 ’ ; ’BB00BB1 ’ ; …
52  ’BBB00B1 ’ ; ’BBB0001 ’ ; ’ 0BBB001 ’ ; …
53  ’ 00BBB01 ’ ; ’ 000BBB1 ’ ; ’B000BB1 ’ ; …
54  ’BB000B1 ’ ; ’ BB00001 ’ ; ’ 0BB0001 ’ ; …
55  ’ 00BB001 ’ ; ’ 000BB01 ’ ; ’ 0000BB1 ’ ; ’ B0000B1 ’ ; …
56  ’ B000000 ’ ; ’ 0B00000 ’ ; ’ 00B0000 ’ ; …
57  ’ 000B000 ’ ; ’ 0000B00 ’ ; ’ 00000B0 ’ ] ;

58 59 % Definition zweiter Regelsatz

60 obj . RuleSet2 = [ ’ 1100002 ’ ; ’ 0110002 ’ ; ’ 0011002 ’ ; …
61  ’ 0001102 ’ ; ’ 0000112 ’ ; ’ 1000012 ’ ; …
62  ’ 2110002 ’ ; ’ 0211002 ’ ; ’ 0021102 ’ ; …
63  ’ 0002112 ’ ; ’ 1000212 ’ ; ’ 1100022 ’ ; …
64  ’ 1120002 ’ ; ’ 0112002 ’ ; ’ 0011202 ’ ; …
65  ’ 0001122 ’ ; ’ 2000112 ’ ; ’ 1200012 ’ ; …
66  ’ 2112002 ’ ; ’ 0211202 ’ ; ’ 0021122 ’ ; …
67  ’ 2002112 ’ ; ’ 1200212 ’ ; ’ 1120022 ’ ; …
68  ’ 2120002 ’ ; ’ 0212002 ’ ; ’ 0021202 ’ ; …
69  ’ 0002122 ’ ; ’ 2000212 ’ ; ’ 1200022 ’ ; …
70  ’ 1200002 ’ ; ’ 0120002 ’ ; ’ 0012002 ’ ; …
71  ’ 0001202 ’ ; ’ 0000122 ’ ; ’ 2000012 ’ ; …
72  ’ 2100002 ’ ; ’ 0210002 ’ ; ’ 0021002 ’ ; …
73  ’ 0002102 ’ ; ’ 0000212 ’ ; ’ 1000022 ’ ] ;

74 75 i f ( r i n g = 1) % falls sich die Simulation in der ersten Hierarchieebene befindet,

wird der erste Regelsatz aktiviert...

76 obj . u p d a t e c l a s s i f i e r s e t ( obj . RuleSet1 ) ;

77 e l s e i f ( r i n g = 2) % ...sonst der zweite

78 obj . u p d a t e c l a s s i f i e r s e t ( obj . RuleSet2 ) ;
79 end

80

81 i f nargin > 0

82 obj . Index = indexNummer ; % übergibt den Index aus dem Vektor von Agenten

als Eigenschaft

83 else
84 obj . Index = 0 ;
85 end

86

87 i f (mod( obj . Index , 7) = 1)
88 obj . Farbe = ’ blue ’ ;
89 e l s e i f (mod( obj . Index , 7) = 2)
90 obj . Farbe = ’ cyan ’ ;
91 e l s e i f (mod( obj . Index , 7) = 3)
92 obj . Farbe = ’ green ’ ;
93 e l s e i f (mod( obj . Index , 7) = 4)
94 obj . Farbe = ’ white ’ ;
95 e l s e i f (mod( obj . Index , 7) = 5)
96 obj . Farbe = ’ black ’ ;
97 e l s e i f (mod( obj . Index , 7) = 6)
98 obj . Farbe = ’ yellow ’ ;
99 else
100 obj . Farbe = ’ magenta ’ ;
101 end

102 103 % Anzahl der gebauten Bausteine auf Null

104 obj . BuildCounter = 0 ;

105 106 i f nargin > 0 % falls Positionswert übergeben wird, wird dieser benutzt..

107 obj . P o s i t i o n = I n i t i a l P o s i t i o n ;

108 else % ...ansonsten wird die Position auf 0,0 gesetzt

109 obj . P o s i t i o n ( 1 , 1 ) = 0 ;

110 obj . P o s i t i o n ( 1 , 2 ) = 0 ;
111 end

112

113 obj . Markierung = line ( obj . P o s i t i o n ( 1 ) , obj . P o s i t i o n ( 2 ) , …
114 1 . 1 , ’ Marker ’ , ’ . ’ , ’ MarkerFaceColor ’ , obj . Farbe , …
115 ’ Color ’ , obj . Farbe ) ;

116 % aktuelle Position des Agenten wird graphisch markiert

117 end

118

119 function movebuild ( agent )

120 % Diese Funktion wird einmal pro Zeitschritt für jeden Agenten aufgerufen 121 % Die Umgebung wird verarbeitet und nach den Regeln des Agenten 122 % entschieden, ob der Agent an der aktuellen Position eine Wabe baut 123 % oder sich weiterbewegt.

124 global Wabengitter ;
125 global Knotenzahl ;
126 global Grenzen ;
127 global raumplot ;
128 global b e b a u t e z e l l e n ;
129 global animation ;
130 global gadurchlauf ;
131 global numberofgaruns ;

132 133 % matchset muss gelöscht werden (empty matrix)

134 agent . matchset = [ ] ;

135 136 % dreht den Agenten in eine zufällige Richtung

137 agent . Ausrichtung = mod( agent . Ausrichtung + rand∗360 , 3 6 0 ) ;

138 139 % Index der Zelle, auf dessen Fläche sich der Agent befindet

140 Z e l l e = agent . i n d e x P o s i t i o n ;

141 % Erzeugt in Nachbarn eine Liste der Indizes 142 % der den Agenten unmittelbar umgebenden Zellen

143 Nachbarn = agent . nachbarn ( Z e l l e ) ;

144

145 for nachbarZelle =1:6
146 b u i l t F l a g = 0 ;

147 v a l i d F l a g = 1 ; % Initialisierung 148

149 bauPosition = Nachbarn ( nachbarZelle ) ;

150 % setze potentielle Position für neuen Baustein auf einen 151 % der sechs Nachbarzellen der aktuellen Position 152

153 i f ( ( bauPosition < 1) | | ( bauPosition > Knotenzahl ) | | …

154 % Grenzen des Gitters

155 ( Wabengitter (4 , bauPosition ) ~= 0) | | …

156 % Bebauung der Zelle

157 ( Wabengitter (3 , bauPosition ) = 0) )

158 % und ist die Wabe noch im Gitter?

159 v a l i d F l a g = 0 ;

160

161 end

162 163 % erzeugt Liste der unmittelbaren Nachbarn der potentiellen Bauposition

164 bauNachbarn = agent . nachbarn ( bauPosition ) ;

165 % jeder Klassifikator wird auf Validität geprüft

166 for ruleNumber =1: agent . n u m b e r o f c l a s s i f i e r s

167 % wenn sich die Position außerhalb des 168 % Gitters befindet oder schon bebaut ist, 169 % wird die nächste Position geprüft

170 i f ( v a l i d F l a g = 0)
171 break ;
172 end

173

174 v a l i d F l a g = 1 ;

175 % jede Position der Regel wrd einzeln geprüft

176 for ruleCellNumber =1:6
177 i f ( ( v a l i d F l a g = 0) | | …
178 ( bauNachbarn ( ruleCellNumber ) > Knotenzahl ) | | …
179 ( bauNachbarn ( ruleCellNumber ) < 1) )

180 break ;

181 % Wenn schon die letzte Stelle der Regel ungültig war, 182 % braucht diese nicht mehr getestet zu werden. 183 % Wenn die Position außerhalb des Gitters liegt, auch nicht

184 end

185

186 i f …
187 strcmp( agent . c l a s s i f i e r s e t ( ruleNumber ) ….
188  d e t e c t o r ( ruleCellNumber ) , ’B ’ )
189 i f ( Wabengitter (4 , bauNachbarn ( ruleCellNumber ) ) = 1 …
190  | | Wabengitter (4 , bauNachbarn ( ruleCellNumber ) ) = 2 …
191  | | Wabengitter (4 , bauNachbarn ( ruleCellNumber ) ) = 3 …
192  | | Wabengitter (4 , bauNachbarn ( ruleCellNumber ) ) = 4 …
193  | | Wabengitter (4 , bauNachbarn ( ruleCellNumber ) ) = 5 …
194  | | Wabengitter (4 , bauNachbarn ( ruleCellNumber ) ) = 6 …
195  | | Wabengitter (4 , bauNachbarn ( ruleCellNumber ) ) = 7 )
196  v a l i d F l a g = 1 ;

197 % wenn die Regel an dieser Stelle ’B’ enthält, 198 % wird validFlag ’true’ gesetzt, falls ein 199 % beliebiger Baustein (1-7) vorhanden ist.

200 else
201 v a l i d F l a g = 0 ;
202 end
203 e l s e i f …
204 strcmp( agent . c l a s s i f i e r s e t ( ruleNumber ) ….
205  d e t e c t o r ( ruleCellNumber ) , ’ ∗ ’ )
206 v a l i d F l a g = 1 ;

207 % enthält die Regel an der betreffenden Stelle ein ’*’ 208 % so ist der Zustand der Zelle egal.

209 else
210 v a l i d F l a g = …
211 strcmp(num2str( Wabengitter (4 , bauNachbarn ( ruleCellNumber ) ) ) , …
212 agent . c l a s s i f i e r s e t ( ruleNumber ) . d e t e c t o r ( ruleCellNumber ) ) ;

213 % in allen anderen Fällen (genaue 214 % Spezifikation in der Regel) muss 215 % der Zelleninhalt exakt mit der 216 % Regelposition übereinstimmen.

217 end

218

219 end

220

221 i f ( v a l i d F l a g = 1)

222

223 agent . c l a s s i f i e r s e t ( ruleNumber ) . bid = …

224 % Rückkonvertierung von Gray

225 gray2bin ( agent . c l a s s i f i e r s e t ( ruleNumber ) ….
226 strength , ’ f s k ’ ,256) …
227 ∗ log2 ( agent . c l a s s i f i e r s e t ( ruleNumber ) . s p e c i f i c i t y + 1 ) ;

228 % bid-Wert wird berechnet: 229 % bid(r) = strength(r) * log2(specificity(r)) 230

231 agent . matchset ( length ( agent . matchset )+1) = ruleNumber ;

232 % wenn die Bedingung des Klassifikators gültig ist, 233 % wird seine Indexnummer in matchset übernommen 234

235 end

236 237 v a l i d F l a g = 1 ; % sonst wird die nächste Regel nicht angewendet

238 end

239 % An dieser Position sind alle Regeln ausgewertet und matchset sollte alle passen-

den Regeln enthalten 240 241

242 o v e r a l l b i d = 0 ;
243 cumulativebid = 0 ;
244 chosenrule = 0 ;

245

246 i f ~isempty ( agent . matchset )

247 % bei leerem matchset muss nichts ausgewählt werden

248 for c l s f =1:length ( agent . matchset )

249 o v e r a l l b i d = …
250 o v e r a l l b i d + agent . c l a s s i f i e r s e t ( agent . matchset ( c l s f ) ) . bid ;
251 end

252

253 for c l s f =1:length ( agent . matchset )
254 normalbid = …
255 agent . c l a s s i f i e r s e t ( agent . matchset ( c l s f ) ) . bid / …
256  o v e r a l l b i d ;

257 % Normalisierung des bid-Wertes auf Wert zwischen 0 und 1 258 % (Anteil an der Summe aller bid-Werte aller Regeln)

259 agent . c l a s s i f i e r s e t ( agent . matchset ( c l s f ) ) . m i n f i t = …
260 cumulativebid ;
261 cumulativebid = cumulativebid + normalbid ;
262 agent . c l a s s i f i e r s e t ( agent . matchset ( c l s f ) ) . maxfit = …
263 cumulativebid ;

264 % Unter- und Obergrenzen werden gesetzt

265 end

266

267 d e c i s i o n = rand ;
268 for c l s f =1:length ( agent . matchset )
269 i f …
270 ( d e c i s i o n >=agent . c l a s s i f i e r s e t ( agent . matchset ( c l s f ) ) . m i n f i t …
271 &&d e c i s i o n <=agent . c l a s s i f i e r s e t ( agent . matchset ( c l s f ) ) . maxfit )

272 % Hier wird die zu verwendende Regel ausgewählt und ihr Index in chosenrule ab-

gespeichert. 273 % workaround, um zu verhindern, dass jede regel unbedingt ausgewählt wird

274 i f ( (rand ∗ 255) <= agent . c l a s s i f i e r s e t ( agent . matchset ( c l s f ) ) . strength )
275  chosenrule = agent . matchset ( c l s f ) ;
276 end
277 break ;
278 end
279 end
280 end

281 282 % Wenn eine Regel chosenrule ausgewählt wurde, muss nach 283 % dieser Regel gebaut werden:

284 i f ( chosenrule )
285 Wabengitter (4 , bauPosition ) = …
286 agent . c l a s s i f i e r s e t ( chosenrule ) . e f f e c t o r ;

287 % *hier wird gebaut* 288

289 agent . bucket = chosenrule ;

290 % benutzte Regel wird für (nicht implementierten) BBA zwischengespeichert 291

292 agent . BuildCounter = agent . BuildCounter + 1 ;

293 % Counter erhöhen 294 295 b u i l t F l a g = 1 ; % zeigt an, dass in diesem Zeitschritt gebaut wurde 296

297 i f ( gadurchlauf = numberofgaruns )
298 plotwabe ( bauPosition , raumplot , Wabengitter (4 , bauPosition ) ) ;

299 % die gebaute Wabe wird graphisch markiert 300 % Parameter: 301 % bauPosition = Index der zu bebauenden 302 % Zelle 303 % raumplot = Handle des zu benutzenden 304 % Achsenobjekts 305 % Wabengitter(...) = Typ des Bausteins 306 % (definiert die Farbe)

307 end

308 % Update der Liste der Indizes aller bebauten Zellen

309 b e b a u t e z e l l e n = find ( Wabengitter ( 4 , : ) ) ;
310 end

311

312 i f true ( b u i l t F l a g )
313 b u i l t F l a g = 0 ;
314 break ;

315 % Jeder Agent soll höchstens einmal pro Zeitschritt bauen.

316 end
317 end

318 319 % Bewegung in X-Richtung

320 agent . P o s i t i o n (1) = …
321 agent . P o s i t i o n (1) + cosd ( agent . Ausrichtung ∗ agent . Speed ) ;

322 % Bewegung in Y-Richtung

323 agent . P o s i t i o n (2) = …
324 agent . P o s i t i o n (2) + sind ( agent . Ausrichtung ∗ agent . Speed ) ;

325

326 z e l l e = agent . i n d e x P o s i t i o n ;

327 % wenn Position unbebaut ist...

328 i f ( ( Wabengitter (4 , z e l l e ) = 0) | | …
329 ( agent . P o s i t i o n (1) > Grenzen ( 1 ) ) | | …
330 ( agent . P o s i t i o n (1) < 0) | | …
331 ( agent . P o s i t i o n (2) > Grenzen ( 2 ) ) | | …
332 ( agent . P o s i t i o n (2) < 0) )

333 % .. oder außerhalb des Gitters liegt 334 % ...dann mache Positionsänderung rückgängig

335 agent . P o s i t i o n (1) = agent . P o s i t i o n (1) + …
336 cosd (mod( ( agent . Ausrichtung +180) ,360)∗ agent . Speed ) ;
337 agent . P o s i t i o n (2) = agent . P o s i t i o n (2) + …
338 sind (mod( ( agent . Ausrichtung +180) ,360)∗ agent . Speed ) ;
339 end

340

341 i f ( gadurchlauf = numberofgaruns )
342 agent . Markierung=line ( agent . P o s i t i o n ( 1 ) , agent . P o s i t i o n ( 2 ) , …
343 1 . 1 , ’ Marker ’ , ’ . ’ , ’ MarkerFaceColor ’ , agent . Farbe , …
344 ’ Color ’ , agent . Farbe , ’ Parent ’ , raumplot ) ;

345 % neue Markierung des Agenten wird gesetzt

346 end

347

348 i f ( animation )
349 drawnow;
350 end

351 % zeigt die animierte Bausequenz, wenn animation-flag gesetzt

352 end

353

354 function indexnummer = i n d e x P o s i t i o n ( agent )

355 % Gibt für jeden Agenten den Index des Mittelpunkts derjenigen 356 % Wabe zurück, auf deren Fläche sich der Agent nach seinen 357 % Koordinaten befindet

358 global Wabengitter ;
359 global MittelPunkte ;

360

361 agent . Abstand = …
362 [ abs ( Wabengitter (1 , MittelPunkte ) − agent . P o s i t i o n ( 1 ) ) ; …
363  abs ( Wabengitter (2 , MittelPunkte ) − agent . P o s i t i o n ( 2 ) ) ] ;
364 kandidatenX = find ( agent . Abstand ( 1 , : ) <= 1 ) ;
365 kandidatenY = find ( agent . Abstand ( 2 , : ) <= 1 ) ;

366

367 indexnummer = 0 ;
368 for kandX=1:length ( kandidatenX )
369 for kandY=1:length ( kandidatenY )
370 i f ( kandidatenX (kandX) = kandidatenY (kandY ) )
371 indexnummer = MittelPunkte ( kandidatenX (kandX ) ) ;
372 break ;
373 end
374 end
375 i f ( indexnummer ~= 0)
376 break ;
377 end
378 end

379 380 % Der folgende Code ist exakter, aber auch langsamer und wird nur verwendet, 381 % wenn der andere zu keinem Ergebnis kommt

382 %
383 i f indexnummer = 0
384 agent . Abstand = sqrt ( ( Wabengitter (1 , MittelPunkte ) − …
385 ( agent . P o s i t i o n ( 1 , 1 ) ) ) . ^2 + ( Wabengitter (2 , MittelPunkte ) …
386 − ( agent . P o s i t i o n ( 1 , 2 ) ) ) . ^2 ) ;

387 % erzeugt einen Vektor mit den euklidischen Abständen des Agenten 388 % von allen Wabenmittelpunkten: 389 % D(X, Y) = sqrt(x1 − y1)^{2} + (x2 − y2)^{2} 390

391 [ abstand , I ] = min( agent . Abstand ) ;

392 % Gibt den Abstand zum nächstgelegenen 393 % Wabenmittelpunkt (abstand) und den dazugehörigen 394 % Index im Vektor Abstand (I) zurück

395 indexnummer = MittelPunkte ( I ) ;

396 % Der nächste Mittelpunkt ist der 397 % mit Index I im Vektor Abstand, also ist sein 398 % Index im Array Wabengitter der Wert an Stelle i 399 % im Vektor Abstand

400 end
401 end

402

403 function u p d a t e f i t n e s s ( agent )

404 % Kopiert den Gesamt-Fitnesstring in die Stärkewerte der 405 % einzelnen Regeln.

406 for r e g e l i n d e x =1: agent . n u m b e r o f c l a s s i f i e r s
407 agent . c l a s s i f i e r s e t ( r e g e l i n d e x ) . f i t n e s s s t r i n g = …
408 agent . c l a s s i f i e r f i t n e s s s t r i n g ( ( ( regelindex −1)∗8)+1: …
409 ( ( regelindex −1)∗8)+8);
410 graystrength = …
411 bin2dec ( agent . c l a s s i f i e r s e t ( r e g e l i n d e x ) . f i t n e s s s t r i n g ) ;

412 % Konvertierung von Binärstring in Dezimalzahl(Gray-codiert)

413 agent . c l a s s i f i e r s e t ( r e g e l i n d e x ) . strength = …
414 gray2bin ( graystrength , ’ f s k ’ , 2 5 6 ) ;

415 % konvertiert von Gray nach Standard-Binär und speichert im strength-Feld

416 end
417 end

418

419 function u p d a t e c l a s s i f i e r s e t ( agent , r u l e s e t )

420 % Erzeugt aus den Regeldefinitionen in ruleset einen neuen 421 % Regelsatz für den Agenten und speichert diesen in 422 % classifierset ab. Wird beim Erzeugen des Agenten aufgerufen 423 % und danach bei jedem Wechsel in eine neue Hierarchieebene 424 % zum Wechsel zum neuen Regelsatz.

425 for r u l e =1: size ( r u l e s e t , 1 )
426 c l a s s i f i e r s ( r u l e ) = …
427 c l a s s i f i e r ( r u l e s e t ( rule , : ) , uint8 (rand ∗ 2 5 5 ) ) ;
428 end

429 % Erzeugung des Regelsatzes - 430 % Für jede Regel eine Zufallszahl zwischen 431 % 0 und 255, um mit 8-bit-Gray-Code arbeiten zu können 432

433 agent . c l a s s i f i e r s e t = c l a s s i f i e r s ;
434 agent . n u m b e r o f c l a s s i f i e r s = length ( agent . c l a s s i f i e r s e t ) ;
435 agent . c l a s s i f i e r f i t n e s s s t r i n g = …
436 s t r c a t ( agent . c l a s s i f i e r s e t . f i t n e s s s t r i n g ) ;
437 end

438

439 end

440

441 end

A.3 classifier.m

1 c l a s s d e f c l a s s i f i e r

2 %CLASSIFIER Definiert die Struktur eines Klassifikators 3 % Klassendefinition für die Klassifikatoren 4 % die das Verhalten der Agenten steuern

5 %

6 % Ein Klassifikator in LCS besteht aus einer Regel, die 7 % einen Detektor (hier als String implementiert) und 8 % einen Effektor miteinander verknüpft. 9 % Außerdem werden noch verschiedene zusätzliche Parameter 10 % wie Stärke(Fitness) und Spezifizität der Regel als 11 % Bestandteil des Klassifikators definiert. 12

13 p r o p e r t i e s

A.3 classifier.m

14 d e t e c t o r % enthält den String zur Definition des Detektors zur 15 % Verarbeitung der Umwelt 16 % B = beliebiger Baustein an Position 17 % * = don’t care 18 % 0,1,2,3,... = bestimmter (bzw. kein) Baustein an Position 19 20 e f f e c t o r % Definiert die Aktion des Agenten - in diesem Modell also 21 % den Typ des zu bauenden Bausteins als Zahlenwert (1,2,3, 22 % ...) bzw. auch eben KEINEN Baustein zu setzen (0) 23 24 strength % skalarer Wert zur Bestimmung der Stärke oder Fitness 25 % - normiert auf 0 ≤ W ert ≤ 255 26 % wichtig wegen interner Codierung in 8bit Gray code 27 % für GA 28 29 f i t n e s s s t r i n g % Fitnesswert in 8bit-Gray-Code als Textstring z.B. ’00110110’ 30 31 s p e c i f i c i t y % Wert zur Bestimmung der Genauigkeit der Regel 32 % entspricht der Zahl der Elemente des Detektor-Strings 33 % die nicht "*don’t-care entsprechen 34 35 age % wird in jedem Zeitschritt erhöht, bei Benutzung des Klassifikators erniedrigt 36 % nach Modell von Holland(1978) 37 38 frequency % Häufigkeit der Aktivierung des Klassifikators 39 % Wird bei jeder Aktivierung um 1 erhöht 40 41 attenuation % Dämpfungskoeffizient 42 % wird bei der Berechnung des Feedback aus der Umgebung 43 % miteinbezogen 44 45 d e t e c t o r l e n g t h = 6 ; % Länge des Detektors (im zweidimensionalen Modell 6, 46 % im dreidimensionalen 20 47 48 bid % skalarer Wert, der aus strength und specificity in jedem Zeitschritt neu be-

rechnet wird 49 % wird nur berechnet, wenn Klassifikator im Matchset auftaucht 50 % Je höher der bid-Wert des Klassifikators, desto höher seine 51 % Chance auf Ausführung. Pro Zeitschritt wird nur ein 52 % Klassifikator angewendet. 53 54 m i n f i t % Untergrenze für Roulette-Wheel-Selection 55 maxfit % Obergrenze für Roulette-Wheel-Selection 56 57

58 end

59

60 methods

61 function obj = c l a s s i f i e r ( r u l e s t r i n g , f i t n e s s ) % Konstruktor

62 obj . d e t e c t o r = r u l e s t r i n g ( 1 : obj . d e t e c t o r l e n g t h ) ;

63 % kopiert die relevanten Teile des Strings in den Detektor 64 65 % Konvertierung in 8bit Gray code

66 obj . strength = bin2gray ( f i t n e s s , ’ f s k ’ , 2 5 6 ) ;

67 % Darstellung der Fitness als Bitstring für GA

68 obj . f i t n e s s s t r i n g = dec2bin ( obj . strength , 8 ) ;

69

70 obj . s p e c i f i c i t y = 0 ;

71 % Spezifizität der Regel wird berechnet

72 for pos =1: obj . d e t e c t o r l e n g t h
73 i f (~(strcmp( obj . d e t e c t o r ( pos ) , ’ ∗ ’ ) ) )
74 obj . s p e c i f i c i t y = obj . s p e c i f i c i t y + 1 ;
75 end
76 end

77

78 obj . e f f e c t o r = str2double ( r u l e s t r i n g ( obj . d e t e c t o r l e n g t h + 1 ) ) ;

79 % letzte Position des RuleString ist der Effektor 80 81 % Initialisierung von age, frequency und attenuation

A.4 fitness.m

82 % Anfangswerte bei allen gleich Null

83 obj . age = 0 ;
84 obj . frequency = 0 ;
85 obj . attenuation = 0 ;

86

87 end

88

89 end

90

91 end

A.4 fitness.m

1 function [ f i t n e s s w e r t , idealwert , aussenlaenge , …
2  wabenanzahl , f i t n e s s q u o t i e n t ] = f i t n e s s ( zustandsraum )

3 %FITNESS Berechnet den Fitnesswert für eine beliebige Wabenstruktur 4 % Diese Version berechnet die Fitness anhand der 5 % Kompaktheit der Struktur: man berechnet die 6 % Gesamtlänge der Außenkanten und teilt sie durch die 7 % Anzahl der bebauten Zellen. Je höher dieser Wert, desto 8 % kompakter die Struktur - Idealfall: Kreisform 9 % Löcher in der Struktur führen zur Abwertung der Fitness

10 %

11 % Von der Funktion werden folgende Werte zurückgegeben: 12 % - berechneter Fitnesswert für die Struktur 13 % - Idealwert eines Kreises mit gleicher Fläche 14 % - Gesamtlänge der Außenwand 15 % - Anzahl der bebauten Waben 16 % - Quotient aus berechneter Fitness und idealer Fitness: 17 % dieser Wert wird als Fitnesswert für strengthga benutzt

18 global Knotenzahl ;

19 20 % Die Fläche einer sechseckigen Zelle wird berechnet

21 z e l l e n f l a e c h e = ( 3 / 2 ) ∗ sqrt ( 3 ) ;

22 % Die Indizes der bebauten Zellen werden ermittelt

23 b e b a u t e z e l l e n = find ( zustandsraum ( 4 , : ) ) ;

24 % Die Anzahl der bebauten Zellen wird errechnet

25 wabenanzahl = length ( b e b a u t e z e l l e n ) ;

26 27

28 aussenlaenge = 0 ;
29 for z e l l i n d e x =1: wabenanzahl
30 n a c h b a r l i s t e = nachbarn ( b e b a u t e z e l l e n ( z e l l i n d e x ) ) ;
31 for zindex =1:6
32  i f ( n a c h b a r l i s t e ( zindex ) < 1) | | …
33  ( n a c h b a r l i s t e ( zindex ) > Knotenzahl )
34  bebauung = 0 ;
35  else
36  bebauung = zustandsraum (4 , n a c h b a r l i s t e ( zindex ) ) ;
37  end
38  i f bebauung = 0
39  aussenlaenge = aussenlaenge + 1 ;
40  end
41 end
42 end

43 44 % Kantenlänge des Sechsecks ist 1 45 % Nimmt man als Fitnesswert das Verhältnis von Fläche A zu Umfang U der 46 % Struktur (möglichst groß), so ergibt sich der Idealwert für die Fitness 47 % bei einer Kreisform, für die folgende Gleichungen gelten: 48 % - A = r^{2} · π 49 % - U = 2 · r · π

50 % - A = \frac{U}{(2 · π)^{2}} · π = \frac{U^{2}}{4 · π}

51 % - \frac{A}{U} = \frac{U}{4 · π}

52 i d e a l w e r t = aussenlaenge / ( 4 ∗ pi ) ;
53 f i t n e s s w e r t = ( wabenanzahl ∗ z e l l e n f l a e c h e ) / aussenlaenge ;
54 f i t n e s s q u o t i e n t = f i t n e s s w e r t / i d e a l w e r t ;

55

56 end

A.5 EckPunkte.m

A.5 EckPunkte.m

1 function eckpunkte = EckPunkte ( MittelPunkt )

2 %ECKPUNKTE Berechnet die Eckpunkte einer Zelle 3 % Für einen gegebenen Zellmittelpunkt werden die Eckpunkte der Zelle als 4 % Vektor zurückgegeben. Reihenfolge vom linken Eckpunkt im Uhrzeigersinn. 5

6 global DX;

7

8 eckpunkte = [ MittelPunkt −1, …
9 MittelPunkt+DX−1+mod( i d i v i d e ( MittelPunkt , uint32 (DX) ) , 2 ) , …
10 MittelPunkt+DX+mod( i d i v i d e ( MittelPunkt , uint32 (DX) ) , 2 ) , …
11 MittelPunkt +1, …
12 MittelPunkt−DX+mod( i d i v i d e ( MittelPunkt , uint32 (DX) ) , 2 ) , …
13 MittelPunkt−DX−1+mod( i d i v i d e ( MittelPunkt , uint32 (DX) ) , 2 ) ] ;

14

15 end

A.6 strengthga.m

1 function strengthga ( o v e r a l l f i t n e s s )

2 %STRENGTHGA Genetischer Algorithmus zur Anpassung der Fitnesswerte 3 % Dieser GA soll nach mehreren erfolgten Simulationsläufen mit dem 4 % gleichen Regelsatz aber unterschiedlichen Fitnesswerten der einzelnen 5 % Regeln die Ergebnisse der Läufe miteinander vergleichen und aufgrund 6 % der globalen Fitness der entstandenen Strukturen die einzelnen 7 % Stärkewerte der Regeln genetisch rekombinieren. Dadurch sollen neue 8 % Regelsätze erzeugt werden, die sich nur durch die Fitness der einzelnen 9 % Regeln von den alten Regelsätzen unterscheiden. 10

11 global wespe ;
12 global Wabengitter ;
13 global MittelWabe ;

14 15 % variable Parameter:

16 probcrossover = 0 . 6 ; % Crossoverwahrscheinlichkeit 17 probmutation = 0 . 2 ; % Mutationswahrscheinlichkeit 18 e l t e r n z a h l = 100; % Zahl der auszuwählenden Individuen pro GA-Durchlauf 19 % - Muss ein Vielfaches von 2 sein 20 21 % wWichtig für Roulette-Wheel-Selektion:

22 %

23 % Die reziproken Werte der Gesamtfitness 24 % zur Berechnung der zu löschenden Elemente

25 o v e r a l l r e z i p = 1 . / o v e r a l l f i t n e s s ;
26 %

27 % Normierung auf Gesamtsumme 1

28 o v e r a l l r e z i p = o v e r a l l r e z i p / sum( o v e r a l l r e z i p ) ;
29 %

30 % Normierung auf Gesamtfitness 1

31 o v e r a l l f i t n e s s = o v e r a l l f i t n e s s / sum( o v e r a l l f i t n e s s ) ;

32 33 % Es werden zwei Vektoren (maxfitness und maxrezip) erzeugt, in denen für 34 % jeden Regelsatz in wespe ein Wert abgespeichert ist, der der Position des 35 % jeweiligen Abschnitts auf dem Roulette-Wheel entspricht. Der Vektor ist 36 % normiert auf 1, d.h. der letzte Wert im Vektor beträgt 1.0.

37 c u m u l f i t n e s s = 0 ;
38 cumulrezip = 0 ;
39 for r e g e l s a t z =1:length ( o v e r a l l f i t n e s s )
40 c u m u l f i t n e s s = c u m u l f i t n e s s + o v e r a l l f i t n e s s ( r e g e l s a t z ) ;
41 maxfitness ( r e g e l s a t z ) = c u m u l f i t n e s s ;
42 cumulrezip = cumulrezip + o v e r a l l r e z i p ( r e g e l s a t z ) ;
43 maxrezip ( r e g e l s a t z ) = cumulrezip ;
44 end

45 46 % Selektion

47 e l t e r n = roulettemz ( o v e r a l l f i t n e s s , maxfitness ) ;

48 49 % Rekombination

50 newstrings = onepointxover ( e l t e r n ) ;

A.6 strengthga.m

51 52 % Mutation

53 newstrings = mutation ( newstrings ) ;

54 55 % Selektion der zu löschenden bauagent-Objekte 56 % - Es wird das gleiche Prinzip zur Roulette-Wheel-Selektion angewendet wie 57 % bei der Eltern-Selektion, nur dass auf den Kehrwerten der Fitnesswerte 58 % gearbeitet wird und deshalb die Selektionswahrscheinlichkeit mit 59 % steigender Fitness abnimmt, d.h. dass weniger fitte bauagent-Objekte mit 60 % höherer Wahrscheinlichkeit gelöscht werden.

61 t o d e l e t e = r o u l e t t e ( o v e r a l l r e z i p , maxrezip ) ;

62 63 % Erzeugen von zwei zusätzlichen bauagent-Objekten in wespe 64 % - nicht mehr nötig, da die Populationsgröße konstant gehalten werden soll 65 % und für die neuen Objekte alte überschrieben werden 66 % Stattdessen direktes Ersetzen der zu löschenden Objekte und Einfügen der 67 % neuen Fitnessstrings

68 for e l t e r n i n d e x =1: e l t e r n z a h l
69 wespe ( t o d e l e t e ( e l t e r n i n d e x ) , 1 ) = …
70 bauagent ( Wabengitter ( 1 : 2 , MittelWabe ) ’ , 1 ) ;
71 wespe ( t o d e l e t e ( e l t e r n i n d e x ) , 1 ) . c l a s s i f i e r f i t n e s s s t r i n g …
72 = newstrings ( 1 , : ) ;
73 wespe ( t o d e l e t e ( e l t e r n i n d e x ) , 1 ) . u p d a t e f i t n e s s ;
74 end

75

76 function index = r o u l e t t e ( f i t n e s s v e k t o r , maxvektor )

77 % Roulette-Wheel-Selection ohne Zurücklegen - wird zur Auswahl der aus 78 % der Population zu löschenden Individuen verwendet. Jedes Individuum kann 79 % nur einmal gelöscht werden.

80 for candid =1: e l t e r n z a h l
81 a = rand ;
82 for r u l e s e t=length ( f i t n e s s v e k t o r ): −1:2
83 i f ( ( a >= maxvektor ( r u l e s e t −1)) && …
84  ( f i t n e s s v e k t o r ( r u l e s e t ) > 0 . 0 ) )
85  index ( candid ) = r u l e s e t

86  break ;
87  end
88 end
89 i f ( a < maxvektor (1) )
90 index ( candid ) = 1
91 end

92 93 % Fitness des gewählten Individuums auf 0 setzen

94 f i t n e s s v e k t o r ( index ( candid ) ) = 0 . 0 ;

95 % neue Normierung

96 f i t n e s s v e k t o r = f i t n e s s v e k t o r / sum( f i t n e s s v e k t o r ) ;

97

98 cumul = 0 ;

99 % neuen Vektor mit Maximalwerten für Roulette-Selection erzeugen

100 for r e g e l =1:length ( f i t n e s s v e k t o r )
101 cumul = cumul + f i t n e s s v e k t o r ( r e g e l ) ;
102 maxvektor ( r e g e l ) = cumul ;
103 end
104 end
105 end

106

107 function index = roulettemz ( f i t n e s s v e k t o r , maxvektor )

108 % Roulette-Wheel-Selection mit Zurücklegen - wird zur Auswahl der 109 % Eltern-Individuen verwendet. Jedes Individuum soll mehrmals ausgewählt 110 % werden können.

111 for candid =1: e l t e r n z a h l
112 a = rand ;
113 for r u l e s e t=length ( f i t n e s s v e k t o r ): −1:2
114  i f ( ( a >= maxvektor ( r u l e s e t −1)) && …
115  ( f i t n e s s v e k t o r ( r u l e s e t ) > 0 . 0 ) )
116  index ( candid ) = r u l e s e t
117  break ;
118  end
119 end
120 i f ( a < maxvektor (1) )

121  index ( candid ) = 1
122 end
123 end
124 end

125

126 function kinder = onepointxover ( e l t e r n )
127 for xoverindex =1: uint8 ( e l t e r n z a h l /2)
128 s t r i n g 1 = …
129  wespe ( e l t e r n ( xoverindex ) , 1 ) . c l a s s i f i e r f i t n e s s s t r i n g ;
130 s t r i n g 2 = …
131  wespe ( e l t e r n ( xoverindex +1) ,1). c l a s s i f i e r f i t n e s s s t r i n g ;

132 % kopiert die Fitness-Strings der ausgewählten Eltern in Graycode 133 % in zwei lokale String-Variablen 134 % Es wird der Gesamtstring (Stärke aller Regeln 135 % hintereinander) verwendet

136 xoverpoint = uint16 (rand ∗ length ( s t r i n g 1 ) ) ;

137 % wählt einen zufälligen Crossoverpunkt 138

139 i f (rand <= probcrossover )

140 % Nur dann Crossover, wenn Zufallszahl kleiner als 141 % Crossover-Wahrscheinlichkeit ist...

142 neustring1 = …
143 [ s t r i n g 1 ( 1 : xoverpoint ) s t r i n g 2 ( xoverpoint +1:length ( s t r i n g 2 ) ) ] ;
144 neustring2 = …
145 [ s t r i n g 2 ( 1 : xoverpoint ) s t r i n g 1 ( xoverpoint +1:length ( s t r i n g 1 ) ) ] ;

146 else % ...sonst werden die Elternstrings einfach kopiert

147 neustring1 = s t r i n g 1 ;
148 neustring2 = s t r i n g 2 ;
149 end

150

151 kinder ( xoverindex , : ) = neustring1 ;
152 kinder ( xoverindex +1 ,:) = neustring2 ;
153 end
154 end

155

156 function n e w b i t s t r i n g = mutation ( b i t s t r i n g )
157 for mutindex =1: uint8 ( e l t e r n z a h l /2)
158 b i t s t r i n g 1 = b i t s t r i n g ( mutindex , : ) ;
159 b i t s t r i n g 2 = b i t s t r i n g ( mutindex + 1 , : ) ;

160

161 i f (rand < probmutation )

162 % wenn Zufallszahl unter Mutationswahrscheinlichkeit

163 mutbit = uint16 ( c e i l (rand ∗ length ( b i t s t r i n g 1 ) ) ) ;
164 i f strcmp( b i t s t r i n g 1 ( mutbit ) , ’ 0 ’ )
165 b i t s t r i n g 1 ( mutbit ) = ’ 1 ’ ;
166 end
167 i f strcmp( b i t s t r i n g 1 ( mutbit ) , ’ 1 ’ )
168 b i t s t r i n g 1 ( mutbit ) = ’ 0 ’ ;
169 end

170 end % für bitstring1 171

172 i f (rand <= probmutation )

173 % wenn Zufallszahl unter Mutationswahrscheinlichkeit

174 mutbit = uint16 ( c e i l (rand ∗ length ( b i t s t r i n g 2 ) ) ) ;
175 i f strcmp( b i t s t r i n g 2 ( mutbit ) , ’ 0 ’ )
176 b i t s t r i n g 2 ( mutbit ) = ’ 1 ’ ;
177 end
178 i f strcmp( b i t s t r i n g 2 ( mutbit ) , ’ 1 ’ )
179 b i t s t r i n g 2 ( mutbit ) = ’ 0 ’ ;
180 end

181 end % für bitstring2 182

183 n e w b i t s t r i n g ( mutindex , : ) = b i t s t r i n g 1 ;
184 n e w b i t s t r i n g ( mutindex +1 ,:) = b i t s t r i n g 2 ;
185 end

186

187 end

188

189 end

A.7 nachbarn.m

A.7 nachbarn.m

1 function l i s t e = nachbarn ( mittelpunkt )

2 %NACHBARN Gibt für einen beliebigen Zellenindex eine Liste der Indizes der direk-

ten Nachbarzellen zurück 3 % Die zurückgegebene Liste enthält *immer* sechs Indizes, auch wenn diese 4 % außerhalb des Gitters liegen. Ob ein Index gültig ist, muss separat 5 % geprüft werden.Die Reihenfolge ist vom oberen Nachbarn beginnend im Uhrzei-

gersinn. 6

7 global DX;

8

9 l i s t e = [ mittelpunkt+2∗DX, …
10 mittelpunkt+DX+1+mod( i d i v i d e ( mittelpunkt , uint32 (DX) ) , 2 ) , …
11 mittelpunkt−DX+1+mod( i d i v i d e ( mittelpunkt , uint32 (DX) ) , 2 ) , …
12 mittelpunkt −2∗DX, …
13 mittelpunkt−DX−2+mod( i d i v i d e ( mittelpunkt , uint32 (DX) ) , 2 ) , …
14 mittelpunkt+DX−2+mod( i d i v i d e ( mittelpunkt , uint32 (DX) ) , 2 ) ] ;

15

16 end

A.8 plotgitter.m

1 function p l o t g i t t e r ( zustandsraum , plotachsen )

2 %PLOTGITTER Zeichnet das leere Wabengitter 3 % Zeichnet ein Gitternetz auf den Koordinaten, die in den ersten beiden 4 % Reihen von zustandsraum definiert sind.

5 global MittelPunkte ;
6 global animation ;

7

8 for wabenNummer=1:length ( MittelPunkte )
9  ecken = EckPunkte ( MittelPunkte (wabenNummer ) ) ;
10  patch ( zustandsraum (1 , ecken ) , zustandsraum (2 , ecken ) , …
11  ’ white ’ , ’ EdgeColor ’ , ’ black ’ , ’ Parent ’ , plotachsen ) ;
12 end

13

14 i f ( animation )
15  drawnow;

16 end % sofort zeichnen, falls Animation an 17

18 end

A.9 plotwabe.m

1 function [ ] = plotwabe ( wabenIndex , plotachse , f a r b e )

2 %PLOTWABE Markiert eine einzige Wabe graphisch als bebaut 3 % Detailed explanation goes here

4 global Wabengitter ;
5 global animation ;

6

7 ecken = EckPunkte ( wabenIndex ) ;

8

9 knoten = [ Wabengitter (1 , ecken ) Wabengitter (1 , ecken ) ; …
10  Wabengitter (2 , ecken ) Wabengitter (2 , ecken ) ; …
11  0 0 0 0 0 0 1 1 1 1 1 1 ] ’ ;

12

13 s e i t e n = [ 1 2 3 4 5 6 ; …
14  7 8 9 10 11 12; …
15  1 2 8 7 NaN NaN;
16  2 3 9 8 NaN NaN;
17  3 4 10 9 NaN NaN;
18  4 5 11 10 NaN NaN;
19  5 6 12 11 NaN NaN;
20  6 1 7 12 NaN NaN ] ;

21

22 i f ( f a r b e = 1)
23 wabenFarbe = ’ red ’ ;
24 e l s e i f ( f a r b e = 2)
25 wabenFarbe = ’ green ’ ;
26 e l s e i f ( f a r b e = 3)

A.10 plotwaben.m

27 wabenFarbe = ’ blue ’ ;
28 e l s e i f ( f a r b e = 4)
29 wabenFarbe = ’ yellow ’ ;
30 e l s e i f ( f a r b e = 5)
31 wabenFarbe = ’ magenta ’ ;
32 e l s e i f ( f a r b e = 6)
33 wabenFarbe = ’ cyan ’ ;
34 else
35 wabenFarbe = ’ black ’ ;
36 end

37 38 i f ( f a r b e ~= 0) % Null steht für unbebaut, also wird nichts gezeichnet

39 patch ( ’ V e r t i c e s ’ , knoten , ’ Faces ’ , s e i t e n , …
40  ’ FaceColor ’ , wabenFarbe , …
41  ’ EdgeColor ’ , ’ black ’ , ’ LineWidth ’ ,1 , ’ Parent ’ , p l o t a c h s e ) ;
42 end

43

44 i f ( animation )
45 drawnow;
46 end

47 % sofort zeichnen, falls Animation an 48

49 end

A.10 plotwaben.m

1 function [ ] = plotwaben ( zustandsraum )

2 %PLOTWABEN Graphische Anzeige der Ergebnisse 3 % Markiert alle bebauten Waben mit einer Farbe

4 global raumplot ;
5 global b e b a u t e z e l l e n ;
6 global animation ;

7 8 % Vektor mit Indizes aller bebauten Zellen

9 b e b a u t e z e l l e n = find ( zustandsraum ( 4 , : ) ) ;

A MATLAB-Quellcode 10

11 for wabe=1:length ( b e b a u t e z e l l e n )

12 % hier wird für jede bebaute Zelle plotwabe aufgerufen

13 plotwabe ( wabe , raumplot , zustandsraum (4 , wabe ) ) ;
14 end

15

16 i f ( animation )
17 drawnow;

18 end % sofort zeichnen, falls Animation an 19

20 end

Erklärung

Ich versichere, dass ich die vorstehende Arbeit selbständig und ohne fremde Hilfe angefertigt und mich anderer als der im beigefügten Verzeichnis angegebenen Hilfsmittel nicht bedient habe. Alle Stellen, die wörtlich oder sinngemäß aus Veröffentlichungen entnommen wurden, sind als solche kenntlich gemacht.

Ich bin mit einer Einstellung in den Bestand der Bibliothek des Departments Informatik einverstanden.

Hamburg, den 1. Oktober 2009

Marius Zirngibl