Skip to content. | Skip to navigation

Personal tools

Sections
You are here: Home / Publikationen / Informatik / Theorie und Praxis der automatischen Stundenplanerstellung / Diplomarbeit / html / Erste Versuche einer Implementierung

Erste Versuche einer Implementierung

next up previous contents
Next: Zusammenfassung Up: Verfahren 2: Handels - Previous: Ablauf der Auktion und

Erste Versuche einer Implementierung

Allgemeine Anmerkung zu Simulationen
Eine Simulation nach der obigen Beschreibung weist keine weiteren Besonderheiten auf. Da sie keinen Zeitvorgaben unterworfen ist, treten die bei Simulation anderer reeller Vorgänge zu beachtenden Synchronisationsprobleme nicht auf. Des weiteren kann momentan kein Vorteil darin erkannt werden, die Handelsvorgänge in einer besonderen Reihenfolge ablaufen zu lassen, so daß hier jeweils eine beliebige gewählt wurde, um Symmetrien vorzubeugen. Wie auch bei der Tabusuche war es notwendig, auf die Zielfunktionen ein leichtes Rauschen aufzumodellieren, so daß sich nicht alle Händler, denen alle Zeitstunden recht wären, unnötig lange um die gleiche Stunde bemühen. Das Ganze wurde so implementiert, daß die Handelsstrategien unabhängig von der Auktion modifiziert werden können.

Der erste Versuch
Zunächst wurde ein Verfahren implementiert, bei dem jeder Händler in jeder Handelsrunde seine Wunschobjekte vollständig neu nach dem besten Preis-Leistungs-Verhältnis bestimmen kann und sein Geld einfach jeweils zu gleichen Teilen verteilt. Die bestehenden Besitzstände wurden nur insofern berücksichtigt, als der jeweilige Händler wußte, daß er diese kostenlos erhalten könnte. Auf einem kleinen Testfall gestartet, zeigte dieses Modell ein konvergentes Verhalten, bei dem das Handeln häufig schon nach einigen hundert Iterationen zum Stillstand kam. Die Qualität der gefundenen Lösungen zeigte sich aber unabhängig davon hochgradig sensitiv gegenüber kleinsten Parameterveränderungen.

Der zweite Versuch
Als nächstes wurde versucht, die Bestimmung der neuen Zeitstunden durch vollständiges Durchsuchen vorzunehmen, da es erträglich schien, alle drei oder vierelementigen Teilmengen der ca. 30 Zeitstunden zu betrachten. Da aber wegen der dynamischen Ressourcen zu jeder Überprüfung ein Neubestimmen der Ressourcenmenge notwendig ist, erwies sich dies doch als wesentlich zu langwierig, und das Verfahren konnte in einigen Testläufen nie in annehmbarer Zeit die erste Iteration abschließen.

Eine fortgeschrittenere Implementierung
In einem dritten Versuch wurde das fluktuationsbeschränkte Modell der Strategiebestimmung verwandt und auch die zusätzliche Tabuliste implementiert. Dem Geld wurde ein Wert zugewiesen, der in Abhängigkeit davon, ob ein Händler seine Bedürfnisse befriedigen konnte, gehoben oder gesenkt wird: Besitzt ein Händler zu viele Objekte, wird seine Wertschätzung des Geldes solange angehoben, bis er den Überschuß verkauft hat. Bei zu wenigen Objekten sinkt sein Geldwert, allerdings nur bis zu einer bestimmten unteren Grenze, damit die Bedingungen von GALE eingehalten werden. Da das Ganze trotz dieser Vereinfachungen immer noch zu langsam wäre, wurde jeder Händler\ zusätzlich noch in ein Frontend und ein Backend aufgespalten. Das Backend übernimmt dabei die eigentliche Strategiebestimmung und wird nur jeweils nach einer vollständigen Handelsrunde, die aus je einer Second-Price-Auktion für jedes Objekt besteht, aufgerufen. Das Frontend wird nach jedem Handelsvorgang, an dem der betreffende Händler beteiligt ist, aktiviert und paßt bei konstant gehaltenen Objektwünschen, die einzelnen Angebote der veränderten Geldsituation durch einfaches Skalieren an. Da hierbei jedesmal mehrere Objekte gehandelt werden, an denen der Händler interessiert ist, kann dabei natürlich die langfristige Strategie verfehlt werden, so daß die entsprechenden Objekte in der nächsten Runde möglicherweise mit Verlust wieder abgestoßen werden müssen. Dieses Verfahren setzte immerhin schon tex2html_wrap_inline7114 der Schulstunden,wobei die Probleme in erster Linie darin bestanden, daß die Händler am Ende manchmal nicht zusammenpassende Objekte besaßen, und teilweise der Geldwert noch zu langsam sank, so daß keine Objekte erworben wurden.

Beide Implementierungen haben damit noch nicht den Stand erreicht, der es erlauben würde, auswertbare Ergebnisse zu erzeugen. Beim ersten Versuch war dies von vorneherein nicht beabsichtigt; er diente lediglich dazu, einen Teil der Schwierigkeiten, die normalerweise nur im Rahmen einer praktischen Umsetzung erkannt werden können, sichtbar werden zu lassen. Hier fiel besonders das Problem der fehlenden Preisbildung auf.

Das zweite Verfahren stellt vermutlich bereits einen zu großen Sprung gegenüber dem ersten dar. Obwohl die erwähnte Möglichkeit, Anteile zu erwerben, noch nicht integriert wurde, erwies sich die Abstimmung der Parameter insbesondere auch auf wechselnde Problemgrößen als zu aufwendig, um in der diesen Versuchen von mir zugebilligten Zeit erfolgreich durchgeführt werden zu können. Andererseits ist aber auch fraglich, ob ein Test, der nicht dem vollen Modell entspricht, erfolgreich verlaufen kann, da doch eine sehr hohe Interaktion der einzelnen Bestandteile notwendig ist. Das in [Bin92] beschriebene Prinzip der Bounded Rationality, d.h. der Tatsache, daß relativ einfach konstruierte Spieler in einer Simulation zum Equilibrium gelangen können, das ein Vorgehen nach dem Prototyping-System nahelegte, scheint hier doch nicht so weit zu reichen.


next up previous contents
Next: Zusammenfassung Up: Verfahren 2: Handels - Previous: Ablauf der Auktion und

(c) Martin Loehnertz 1999