Universität Salzburg, Institut für Computerwissenschaften

PS Programmierpraktikum SS 2000

Optimierte Objektpositionierung

Manfred Bernhard Mayr mmayr@cosy.sbg.ac.at

Florian Angulanza fangulan@cosy.sbg.ac.at Christian Osterrieder coster@cosy.sbg.ac.at Markus Spitzlinger mspitzl@cosy.sbg.ac.at

Projektbetreuer:

Dipl.Ing. Mag. Roland Schwaiger rschwaiger@cosy.sbg.ac.at

Version vom 29. März 2000

Zusammenfassung

Inhaltsverzeichnis

1

Kapitel 1

Einführung

1.1 Genetischer Algorithmus

Nach [?] ist ein Genetischer Alogrithmus ein Algorithmus, der Strategien aus der Evolutionstheorie verwendet, um zu einem Problem eine möglichst gute Lösung zu finden. Bei dieser Heuristik muß man die Lösungen eines Problems als Chromosomen, aufgebaut aus einer Folge oder Menge von elementaren Bausteinen (Gene), formulieren; eine Menge solcher Chromosomen, eventuell erweitert um zusätzliche Attribute, heißt Population. Ausgehend von irgendeiner Anfangspopulation erzeugt man durch biologische Vererbungsmechanismen neue Chromosomen, bewertet diese mit Hilfe einer vorgegebenen Bewertungsfunktion (Fitnessfunktion) m und läßt gewisse Chromosomen überleben. Durch Wiederholung entsteht dann eine Folge von Populationen, in denen man hofft, eine besonders gute Lösung für das vorgegebene Problem zu entdecken. Als Vererbungsmechanismen verwendet man zumeist Kombinationen folgender Strategien:

• Reproduktion: Ein Chromosom wird unverändert an die nächste Population vererbt.

• Mutation: Ein oder mehrere Gene eines Chromosoms werden bei der Vererbung zufällig abgeändert.

• Inversion: Umdrehen eines Teilstücks eines Chromosoms und Vererbung des so modifizierten Chromosoms an die nächste Population.

• Crossover: Teilen zweier Chromosomen und Vererbung des über Kreuz zusammengesetzten Chromosoms. Hierbei muß man darauf achten, daß die Ergebnisse der Neukombination wieder gültige Chromosomen sind.

• Blockung: Zusammenfassen bestimmter Gene zu einer Einheit, deren Teile bei der weiteren Vererbung bei einer Inversion oder einem Crossover nicht mehr getrennt werden dürfen.

• Entblockung: Aufhebung einer Blockung.

• Selektion: Die bzgl. der Bewertungsfunktion besten Chromosomen überleben.

Kapitel 2

Projektbeschreibung

2.1 Einleitung

Es wird ein GA (Genetischer Algorithmus) benützt um Objektgruppierungen o_{1}, ..., o_{n}, in einer 2-dimensionalen Umgebung, mit Hilfe einer gegebenen Fitness-Funktion zu optimieren. Die verschiedenen Objekte o_{i} erhalten in einem vordefinierten Intervall [l_{i}, u_{i}] Werte, gemessen in einem diskreten Zeitintervall, z. B. in einem Tag. Die 2-dimensionale Fläche ist in Teilflächen unterteilt, die einzelnen Teilflächen können

1. verboten sein,

2. zu einer vordefinierten Gruppe gehören,

3. besetzt sein, oder nicht bei einem Objekt o_{i} sein.

Ziel des Projektes ist, das Problem theoretisch zu untersuchen (ist es möglich dieses Problem zu klassifizieren?), eine GUI (grafische Benutzeroberfläche) und einen GA zu implementieren. Ein Ergebnis wird sein, Vorschläge für die Gruppierung in der Fläche zu machen (basierend auf einer allgemeingültigen Fitness-Funktion), z. B. maximal zuweisbare Werte der Objekte mit Rücksicht auf ein zugrundeliegendes Modell der verschiedenen Aufgaben.

Optimierte Objektpositionierung (OOP) ist ein Multiagentensystem, welches im wesentlichen aus zwei Komponenten besteht:

1. Agentenwelt

2. Objektwelt

Das Projekt unterteilt sich hierbei in natürlicher Weise in zwei Teilaufgaben:

1. Initialisierungsphase, welche die Agenten in der Welt simuliert und somit Daten für die zweite Phase generiert.

2. Optimierungsphase, wo mit Hilfe der Daten aus der Initialisierungsphase versucht wird die Objekte möglichst gut zu positionieren.

2.1.1 Agentenwelt

In der Initialisierungsphase werden die Agenten in der Welt W, mit den Dimensionen w_{x} ∈ 1, ..., n und w_{y} ∈ 1, ..., m, in denen die Agenten und Objekte existieren, simuliert. Die Welt ist begrenzt durch Mauern, in denen Markierungen für Eingänge und Ausgänge enthalten sind. Agent a_{i} ∈ A kann die Welt nach einer zugrundeliegenden Verteilung betreten und verlassen. Die Anzahl der Agenten in der Welt besitzt eine Obergrenze. Jeder Agent a_{i} besetzt ein gewisses Feld in der Welt welches 1. nicht besetzt von einem anderen Agenten ist,

2. nicht verboten ist,

3. nicht von einem Objekt besetzt ist.

Jeder Agent bekommt einen bestimmen Wert v_{i}^{a} zugewiesen, welcher erniedrigt wird sobald dieser vor einem Objekt anhält. Die Verminderung des Wertes hängt dabei vom Objekt ab, welches der Agent gerade besucht und wird mit c_{i}^{o} festgehalten. Der Agent A kann dabei in der Welt zufällig herumwandern, folgt einem vordefinierten, oder evolvierten Schema. Das Ziel dabei ist alle Objekte mit einem v_{i}^{a} > 0 zu besuchen.

Die Agenten können dabei T Zeiteinheiten umherwandern und Objekte besuchen. Wir werden dies eine dynamische auf Generationen basierende Population nennen. Dynamisch deswegen, weil die Agenten die Welt jederzeit verlassen oder betreten können und auf Generationen basierend, weil nach T Zeiteinheiten eine andere Generation von Agenten die Welt bevölkert. Aktualisiert sollte die Simulation dabei synchron werden, z.B wenn eine Generation zum Zeitpunkt t gegeben ist hängt die Aktualiesierung füer den Zeitpunkt t + 1 nur vom Zeitunkt t ab. Alle Kollisionen mit anderen Agenten usw. werden basierend auf der jeweiligen Zeitstufe berechnet.

Abbildung 2.1: Objekt- und Agentenwelt

\underline{Beschreibung der Abbildung ??}:

Links ist das Schema der Objektwelt dargestellt. Es wird ein Raster über die Objektwelt gelegt. Schwarze Rasterfelder bedeuten, dass kein Objekt (=Entity) hier positioniert werden darf. Ein weißes Rasterfeld bedeutet, dass dieses Feld leer ist. Objekte können nur auf weiße Felder gestellt werden. Objekte können nur vom Agenten einen Wert bekommen,wenn dieser genau vor der Öffnung des Objektes steht. Rechts ist das Schema der Agentenwelt abgebildet. Agenten sind für uns Klassen. Die Umsetzung der Bewegungen der Agenten erfolgt am Anfang ganz einfach mit Hilfe eines Zufallsgenerators. Die Anzahl der Agenten wird immer konstant gehalten, d.h. wenn ein Agent die Agentenwelt verläßt wird ein anderer nachgeschickt.

Um genug Daten für den Optimierungsphase sammeln zu können, wird die Grundeinstellung der Objekte nach einem Durchlauf verändert.

2.1.2 Objektwelt

Im Grunde hat die Objektwelt die gleiche Größe wie die Agentenwelt, aber sie ist viel ungenauer. Das ist deshalb so, weil die Agenten in der Regel nicht soviel Raum wie unsere Objekte benötigen. Objekte besetzen eine Einheit in der Welt. Objekte werden einem bestimmten Typen zugeordnet und folglich werden ihnen bestimmte Kosten c_{i}^{o} zugewiesen, die dem Agenten von seinem Wert abgezogen werden, falls das Objekt vom Agenten besucht wurde. Das Objekt sammelt die reduzierten Werte des Agenten und nach einem Durchlauf hat das Objekt den Wert v_{i}^{o}.

Nach jedem Durchlauf wird die Grundeinstellung der Objekte solange verändert, bis genug Daten für den Optimierungsphase gesammelt wurden. Einige der Objekte können durch andere Objekte aus dem Objektvorrat ersetzt werden.

2.2 Initialisierungsphase

Diese Phase dient dazu, die für den Optimierungslauf notwendigen Daten zu ermitteln und zu sammeln. Hier werden über einen Zeitraum von p ∗ T Datensätze angelegt, wobei p z.B. 30 (Tage) und T z.B. 24 Stunden ∗ 60 Minuten sind. Es finden also insgesamt p Durchläufe statt, wobei vor jedem Durchlauf die Grundeinstellungen (Objekte, deren Verteilung, …) verändert werden. Nach jedem Durchlauf wird festgehalten welchen Wertevorrat die einzelnen Objekte an der bestimmten Postion haben. Durch die Veränderung der Grundeinstellungen vor jedem Experiment (=Durchlauf) entstehen genügend Vergleichsdaten für die Optimierungsphase.

Hierbei stellt sich jetzt die Frage, wie die einzelnen Agenten positioniert werden und nach welchem Schema sie sich bewegen. In unserem Fall wird dies zuerst ganz einfach mit Hilfe eines Zufallsgenerators realisert. Die Bewegung und die Postionierung sind Methoden, sodaß sie zu einem späteren Zeitpunkt einfach durch möglicherweise bessere ersetzt werden können.

Wichtig dabei ist auch, daß die Anzahl der Agenten konstant gehalten wird, d.h. daß wenn ein Agent die Welt betritt ein anderer sie verläßt und umgekehrt.

Eine weitere Frage ist, ob überwacht werden muß, daß die Objekte durch ihre Aufstellung die Agenten nicht behindern. Ein Beispiel wäre, daß etwa alle Objekte in einer Reihe stehen und kein Agent mehr zu einem Objekt kann, oder der Ein- oder Ausgang blockiert ist. Diese Problem müßte jedoch der GA lösen, da sich diese Aufstellung der Objekte als nicht sehr vorteilhaft klassifizieren müßte.

Wie ermittelt man welchen Fitnisswert ein Objekt hat wenn es zwei Einträge in der Liste gibt? z.B.: Objekt 1 hat am Platz 1 zuerst 50 Punkte und beim nächsten Mal 100 Punkte bekommen.

• Ermittelt man dies durch Zufall?

– Dies ist sehr schlecht, da der GA zuerst einen Fitnisswert bekommt und beim nächsten Mal einen anderen. Welcher gilt?

• Maximum?

• Durchschnitt?

Dies ist noch zu klären.

Am Ende der Initialisierungsphase werden die gesammelten Daten zu einem Datensatz zusammengefügt und stehen anschliessend dem Optimierungsalgorithmus als Ausgangsbasis zur Verfügung.

Datum  Objekt Wert
02.03.2000  1  1000
02.03.2000  2  3000
…  …  …

2.2.1 Datenstrukutr

2.3 Optimierungsphase

In dieser Phase wird versucht, aus den Daten, welche aus der Initialisierungsphase gewonnen wurden (können auch empirische Daten sein) eine optimale Postitionierung der Objekte zu finden. Ziel dabei ist es eine Aufstellung zu finden, bei welcher die Summe der Werte aller Objekte möglichst hoch ist. Realisiert wird diese Optimierung mit Hilfe eines GA’s.

2.3.1 Motivation warum ein GA verwendet wird

• Wahrscheinlich ist dieses Problem ein Assigment-Problem.

• Ein Assigment-Problem ist jedoch NP-Vollständig!

• Herkömlicher Lösungsansatz:

– Gegeben ist die Liste der Objekte, ihre Postion und ihrer Wertigkeit:

– z.B.:

Objekt Positon Wert
1  1  1000
1  2  300
2  1  900
2  2  100
…  …  …

– Nun sucht man einfach aus der Liste den Besten heraus (in unserem Fall Objekt 1 auf Postion 1) und positioniert ihn dort. Das Ergebnis ist in diesem Beispiel folgendes:

Objekt Positon 1  1  1000 2  2  100 …  …  … Dies ergibt ein Gesamtergebnis von 1100.

Besser wäre jedoch folgendes:

Objekt Positon 1  2  300 2  1  900 …  …  … Da das Gesamtergebnis hier 1200 ist!

Anhang A

Protokolle

A.1 Protokoll vom 15. März 2000

Leiter: DI Mag. Roland Schwaiger Protokollführer: Florian Angulanza Teilnehmer: Manfred Bernhard Mayr

Christian Osterrieder Markus Spitzlinger

Ort: Salzburg Zeit: 17^{30}

• Treffen wöchentlich, später weniger oft

• Was ist zu tun im Laufe des Praktikums:

– Paper erstellen (in L^{A}TEX)

– Objektbeschreibung in UML (Unified Modelling Language)

– Beherrschung von HTML

– Programmieren in Java

• Beschreibung als L^{A}TEX-file bis Mi 17^{30} als .TEX-Source • Beschreibung der Grafik im Paper:

Grafik besteht aus folgenden Elementen:

– Objekten (Entities)

∗ bewegen sich

∗ Werte werden gesammelt

– Agenten ∗ bewegen sich anders als Objekte

∗ kann nicht auf Objektfelder

– Schwarzen Flecken ∗ sind verbotene Zonen

– Ein- und Ausgängen

• OOP ist ein Multiagentensystem • Beschreibung des Diagramms im Paper:

1. Initialphase: z.B.: System 24 Stunden laufen lassen / mit einer Auflösung von 1 Minute Daten aufzeichnen → Tagesergebnis T ergibt sich aus 24 ∗ 60 Minuten. Dies wird wiederholt, z.B. 30 mal → 1 Monat → 30 Experimente. Immer zwischendurch an den Objekten Änderungen machen → Vergleichsdaten.

Datum  Objekt Value
02.03.2000  1  1000
02.03.2000  2  3000
…  …  …

2. Hauptphase: Gleiche Laufzeit (z.B. 1 Tag), Optimierung aufgrund von Daten aus der Initialphase → Genetischer Algorithmus für Optimierung, dann Agenten wieder laufen lassen.

• 1. Aufgabe:

– L^{A}TEX-file aus \underline{˜ rschwaig/out-dir/ppktII2000/gruppe2} holen und in eigenes Dokument kopieren

– Dokument ergänzen

– Fragen einbinden

• Nächster Termin: Mi, 22. März 2000

A.2 Protokoll vom 22. März 2000

Leiter: DI Mag. Roland Schwaiger Protokollführer: Markus Spitzlinger Teilnehmer: Manfred Bernhard Mayr

Christian Osterrieder Florian Angulanza

Ort: Salzburg Zeit: 17^{30}

• Was ist UML und wozu wird es verwendet?

– UML ist die Abkürzung für Unified Modelling Language.

– UML dient dazu die Entwicklung von Software zu dokumentieren und ist prinzipiell eine graphische Beschreibungssprache.

• UML in unserem Projekt:

– Ein Tool um Dokumentationen in UML zu erstellen ist ARGO-UML (auf der Hompage von DI Mag. Roland Schwaiger zu finden (XML-Parser von IBM ist notwendig!).

– Klassendiagramme und Benutzerfälle sollen mit UML-dargestellt werden.

• Wie werden die Agenten positioniert?

– Ein Agent ist in diesem Fall eine Klasse.

– Die Bewegung des Agenten wird zuerst ganz einfach mittels Zufallsgenerator realisiert (einfache Methode).

– Die Anzahl der Agenten wird immer konstant gehalten, d.h. wenn ein Agent die Agentenwelt verläßt wird ein anderer nachgeschickt.

• Motivation warum ein GA verwendet wird:

– Wahrscheinlich ist dieses Problem ein Assigment-Problem.

– Ein Assigment-Problem ist jedoch NP-Vollständig!

– Herkömlicher Lösungsansatz:

∗ Gegeben ist die Liste der Objekte, ihre Postion und ihrer Wertigkeit:

∗ z.B.:

Objekt Positon Wert
1  1  1000
1  2  300
2  1  900
2  2  100
…  …  …

∗ Nun sucht man einfach aus der Liste den Besten heraus (in unserem Fall Objekt 1 auf Postion 1) und positioniert ihn dort. Das Ergebnis ist in diesem Beispiel folgendes:

Objekt Positon 1  1  1000 2  2  100 …  …  … Dies ergibt ein Gesamtergebnis von 1100.

Besser wäre jedoch folgendes:

Objekt Positon 1  2  300 2  1  900 …  …  … Da das Gesamtergebnis hier 1200 ist!

• Wie wird überwacht, daß die Objekte die Agenten durch ihre Aufstellung nicht behindern, z.B. alle in einer

Reihe wodurch es möglich wäre, daß kein Agent mehr zu einem Objekt kann?

– Dies müßte der GA lösen, da die Objekte keine Punkte bekommen und somit als gute Lösung ausschei-

den.

• Wie ermittelt man welchen Fitnisswert ein Objekt hat wenn es zwei Einträge in der Liste gibt? z.B.: Objekt 1

hat am Platz 1 zuerst 50 Punkte und beim nächsten Mal 100 Punkte bekommen.

– Ermittelt man dies durch Zufall?

∗ Dies ist sehr schlecht, da der GA zuerst einen Fitnisswert bekommt und beim nächsten Mal einen

anderen. Welcher gilt?

– Maximum?

– Durchschnitt? Dies ist noch zu klären.

• Aufgabenstellung bis nächste Woche:

– Welche Datenstrukur wird verwendet?

– Welche Felder hat die Tabelle bzw. Datenbank?

– Motivation GA ins Dokument einbinden.

– Mit UML vertraut machen.

– Dokument erweitern.

Anhang B

Glossar

Blockung: Zusammenfassen bestimmter Gene zu einer Einheit, deren Teile bei der weiteren Vererbung bei einer

Inversion oder einem Crossover nicht mehr getrennt werden dürfen. Crossover: Teilen zweier Chromosomen und Vererbung des über Kreuz zusammengesetzten Chromosoms. Hierbei

muß man darauf achten, daß die Ergebnisse der Neukombination wieder gültige Chromosomen sind. Entblockung: Aufhebung einer Blockung. GA: Genetischer Algorithmus Algorithmus, der Strategien aus der Evolutionstheorie verwendet, um zu einem Pro-

blem eine möglichst gute Lösung zu finden. Inversion: Umdrehen eines Teilstücks eines Chromosoms und Vererbung des so modifizierten Chromosoms an die

nächste Population. Mutation: Ein oder mehrere Gene eines Chromosoms werden bei der Vererbung zufällig abgeändert. NP: Menge aller Sprachen, die von einer nichtdeterministischen Turingmaschine in polynomialer Laufzeit erkannt

werden können (Determinismus). Hinter dem Kürzel NP verbirgt sich eines der schwierigsten und für die Praxis bedeutsamsten Probleme der Informatik, nämlich die Frage, ob gewisse Aufgabenstellungen schnelle Lösungsverfahren besitzen oder nicht.

Reproduktion: Ein Chromosom wird unverändert an die nächste Population vererbt. Selektion: Die bzgl. der Bewertungsfunktion besten Chromosomen überleben.