Grundlagen

Der hier versuchte und bis zu einer ersten Testimplementierung gediehene Ansatz verwendet eine Kombination von Simulated Trading [BHM96], Negotiation [RW97] und Predictor-Korrektor Verfahren [AG82]. Der Kombination der letzten beiden entspricht in gewisser Weise das sogenannte Equilibrium Programming [ZG81]. Um das Zusammenwirken dieser Prinzipien zu verdeutlichen, soll hier eine kurze Beschreibung dieser Verfahren gegeben werden:

Predictor-Korrektor Verfahren

gehören zum Methodenrepertoire der nichtlinearen Optimierung. Die Grundidee besteht darin, daß man eine Homotopie von einer (stetigen) Funktion mit leicht bestimmbarem Minimum zur gewünschten (stetigen) Zielfunktion betrachtet, das heißt eine stetige Abbildung mit F(x,0)=g(x) und F(x,1)=f(x).
Nun spekuliert man darauf bzw. kann in bestimmten Fällen beweisen, daß die Menge aller Punkte an denen F den Wert 0 annimmt, einen stetigen Pfad in dem so entstandenen um eins höherdimensionalen Raum bildet [AG82].
Will man eine gegebene Optimierungsaufgabe mit Zielfunktion g=f' lösen, sucht man also jeweils einen optimalen Punkt, d.h. einen Nullpunkt der Ableitung. Dann erhöht man den Homotopiekoeffizienten um einen diskreten Wert. Differenzierbarkeit annehmend prognostiziert man, daß sich das Minimum entlang der letzten Tangente an den Pfad ein Stück weiterbewegt hat und sagt somit die ungefähre Position des neuen Minimums voraus (Predictor-Schritt). Danach wendet man lokale Suchverfahren, z.B, das Newtonverfahren, an, um sich dem tatsächlichen Minimalpunkt wieder zu nähern. Das Verhalten des Verfahrens kann über die Parameter Schrittweite des Predictor-Schritts und Zahl der nachfolgenden Korrektor-Schritte kontrolliert werden. Auf dem Predictor-Korrektor Verfahren basierten die ersten effizienten Algorithmen zum Lösen semidefiniter Programme ([VB96]). Wie PUZICHA, HOFMANN und BUHMANN [PHB99] zeigen, kann das Deterministische Annealing zu diesen Verfahren gezählt werden.

Negotiation:

Die Negotiation entstammt zu großen Teilen der künstlichen Intelligenz. Verschiedene Agenten sollen gemeinsam eine Aufgabe lösen, indem sie darüber eine Verhandlung (Negotiation) führen. Dies wird häufig bei verteilten Agentensystemen genutzt, um z.B. jedem Agenten eine Aufgabe zuzuordnen. Eine Variante dieser Methode wurde bereits von RAM und WARREN[RW97] im Timetabling-Bereich eingesetzt (vgl. Abschnitt 4.8).

Simulated Trading

ist eine lokale Simulation eines solchen Handelsvorgangs. Die Spieler teilen ihre Strategie einem Schiedsrichter mit, der unmittelbar das Ergebnis ermittelt, das nach k Handelsvorgängen, bei denen mehrere Spieler gleichzeitig handeln können, eine im Schnitt optimale Verbesserung darstellt. In der Terminologie von [BHM96]: Ein optimales Trading-Matching wird ermittelt (s.u.).

Equilibrium Programming

verbindet Negotiation und Predictor-Korrektor Verfahren. ZANGWILL und GARCIA [ZG81] zeigen, daß sich unter moderaten Voraussetzungen an Zielfunktion und Nebenbedingungen Probleme des wirtschaftlichen Gleichgewichts (Equilibriums) durch Einführung eines zusätzlichen Parameters so modifizieren lassen, daß die Punkte, die den jeweiligen Gleichgewichtszuständen entsprechen, eine Kurve im Parameterraum bilden. Diese läßt sich, analog zu den Prediktor-Korrektor-Verfahren, in der Form verfolgen, daß man die Schrittweite der Parameterveränderung ausreichend klein wählt und dann jeweils die Marktkräfte walten läßt, um das neue Equilibrium zu erreichen.

Im Prinzip beruht z.B. Simulated Annealing auf der gleichen Idee: Bei einer bestimmten Temperatur erreicht das System ein thermales Equilibrium. Dann wird die Temperatur geringfügig gesenkt und es besteht die Hoffnung, daß sich die alte und die neue stabile Verteilung soweit überlappen, daß nur wenige Schritte notwendig sind, um zwischen den beiden zu wechseln.

Das hier vorgestellte Verfahren wird im folgenden als Simulated Negotiation bezeichnet: Simulated, da ebenso wie bei BACHEM, nicht der Prozeß als solcher, sondern allein das Ergebnis interessiert. Die Agenten dienen also nur der besseren Veranschaulichung und könnten durch ein anderes System, das auf anderem Wege das spätere Verhandlungsergebnis bestimmt, ersetzt werden. Negotiation wird hier statt trading verwandt, da jeder Handelsprozeß sofort durchgeführt wird, also gewissermaßen nur das erste Level des Trading-Graphen betrachtet wird.