Upload
godehard-hennies
View
107
Download
1
Embed Size (px)
Citation preview
3. März 2000 LS VI Workshop: Kalibrierung und Optimierung 1/20
Kalibrierung und Optimierung in simulierten Multiagentensystemen
Christoph Oechslein
Kalibrierung und Optimierung in simulierten Multiagentensystemen
Christoph Oechslein
3. März 2000 LS VI Workshop: Kalibrierung und Optimierung 2/20
BegriffsbestimmungBegriffsbestimmung
• Kalibrierung: Anpassen von Ein-/Ausgabeverhaltens eines Systems.
• Optimierung: Maximierung eines Modells bzgl. einer Bewertungsfunktion
• Optimierung beinhaltet Kalibrierung:Bei Kalibrierung ist Optimum gegeben.
3. März 2000 LS VI Workshop: Kalibrierung und Optimierung 3/20
O ptim ierungs-ko m po nente
S im u latio nslau f(n ich tdeterm in istisch :
m ehrere)
W ertv erläu fe
Bew
ertu
ng
Bew ertungsfunktio n
S im u latio nsm o dell
Optimierung von SimulationenStandardansatz
Optimierung von SimulationenStandardansatz
3. März 2000 LS VI Workshop: Kalibrierung und Optimierung 4/20
O ptim ierungs-ko m po nente
S im u latio nslau f(n ich tdeterm in istisch :
m ehrere)
Param etersatz
W ertv erläu fe
Bew
ertu
ng
Bew ertungsfunktio n
S im u latio nsm o dell Simulationsmodell
Optimierung von SimulationenStandardansatz (Forts.)
Optimierung von SimulationenStandardansatz (Forts.)
• Optimierer kann • dabei beliebiger Suchalgorithmus sein (Tabusearch, SA, ...)• beliebiges OR-Verfahren ((nicht-)lineare Programmierung, ...)• populationsbasierte Verfahren (GA, ES, Scatter Search, ...)
• möglichst wenige Parameterevaluationen, da extrem kostspielig
3. März 2000 LS VI Workshop: Kalibrierung und Optimierung 5/20
Kommerzielle LösungenKommerzielle Lösungen
AutoStat AutoMod, AutoSched ES
OPTIMIZ SIMUL8 NN
SimRunner2 MedModel, ProModel ES, GA
OptQuestArena, QUEST, Micro Saint
SS, TS, NN
WITNESS Optimizer
WITNESS SA, TS
Quelle: Simulation Modelling and Analysis; Law, Kelton; 3rd Edition
3. März 2000 LS VI Workshop: Kalibrierung und Optimierung 6/20
Problem:Parameterevaluationskosten
Standardlösungen
Problem:Parameterevaluationskosten
Standardlösungen
• Heuristik für• Parameterauswahl• Parameterbewertung• Parameterrekombination
• Lernen des Ein-/Ausgabeverhalten (response-surface) • des Simulationsmodells bzw. • der Bewertungsfunktion
3. März 2000 LS VI Workshop: Kalibrierung und Optimierung 7/20
Beobachtung:
Folgerung:
Neue Ansätze INeue Ansätze I
Aus mehreren Simulationsläufen (mit gleichen Parameter) nur eine Bewertung
Ausnutzen des Simulationslaufs, um Parameter zu optimieren:• auf Populationsebene (Multi-Agenten-
System)• auf Individuenebene (Lernen)
3. März 2000 LS VI Workshop: Kalibrierung und Optimierung 8/20
Modellbauer erzeugt oft sehr viele Parameter, bedingt auch durch Aktionsselektionsarchitektur
Teile des Modells abstrakter definieren:• durch Erweiterung des Modells um
Constraintnetz der Parameterabhängigkeiten• durch was soll geschehen und nicht wie.
( Lernen, Reinforcement Learning)
Beobachtung:
Folgerung:
Neue Ansätze IINeue Ansätze II
3. März 2000 LS VI Workshop: Kalibrierung und Optimierung 9/20
Alle AnsätzeAlle Ansätze
• Standardansatz:Simulationslauf als parametrisierte Funktion, die optimiert wird
• Optimierung während Simulationslauf• populationsbasiert• individuenbasiert (Lernen)
• Dimensionseinschränkung durch abstrakteres Modell
3. März 2000 LS VI Workshop: Kalibrierung und Optimierung 10/20
• Bewertungsfunktion eines Simulationslaufes• Test, ob Parameterwerte sinnvoll sind • Funktion, um Parameterwerte sinnvoll zu
machen (Reparatur) oder Funktion zur Konstruktion von sinnvollen Parameterwerten
• Funktion zur Rekombination von Parameterwerten
• Populationsbasiert oder suchbasiert• Lernen der Response-Surface durch statistische
Methoden, NN, Radial Basis Function
Zusätzliches Wissen:
Algorithmus:
StandardansatzAnforderungenStandardansatzAnforderungen
3. März 2000 LS VI Workshop: Kalibrierung und Optimierung 11/20
• Bewertungsfunktion für Individuum oder ‚survival of the fittest‘
• Test, ob Parameterwerte von Individuum sinnvoll sind • Funktion, um Parameterwerte sinnvoll zu machen
(Reparatur) oder Konstruktion von Werten
• Evolutionäre Strategie zur Parameteradaption bzw. –rekombination
• Genetisches Programmieren zur Verhaltensneubildung
Zusätzliches Wissen:
Algorithmus:
Optimierung während Simulationslauf auf Populationsebene
Anforderungen
Optimierung während Simulationslauf auf Populationsebene
Anforderungen
3. März 2000 LS VI Workshop: Kalibrierung und Optimierung 12/20
Nachbildung biologischer Evolution
Nachbildung biologischer Evolution
• Mit Populationsoptimierungskomponente lassen sich biologische Fragestellungen lösen, z.B.• das Problem der Evolution staatenbildender Insekten
oder• die Auswahl verschiedener Erklärungsmodelle
• Biologische Evolution möglichste genau Nachbilden, z.B. diploid/haploid
Alexanders Diplomarbeit (Abschlussvortrag) Projekt mit Biologie
3. März 2000 LS VI Workshop: Kalibrierung und Optimierung 13/20
Zusätzliches Wissen:
Algorithmus:
Optimierung auf Modellebene Anforderungen
Optimierung auf Modellebene Anforderungen
• Wissen über Parameterabhängigkeiten (Constraintnetz)Z.B.: Parameter A Parameter B
• Constraintsatisfaction
Möglichkeiten gute Startparameterwerte zu finden und
Überprüfungen der Parameter zur Laufzeit siehe Standardansatz bzw. Optimierung auf
Populationsebene
3. März 2000 LS VI Workshop: Kalibrierung und Optimierung 14/20
Ak tiv itä t 1
Ak tiv itä t 2
Ak tiv itä t 3
Optimierung während Simulationslauf auf Individuenebene
Optimierung während Simulationslauf auf Individuenebene
Ak tiv itä t 1
Ak tiv itä t 2
Ak tiv itä t 3
Black-Box
3. März 2000 LS VI Workshop: Kalibrierung und Optimierung 15/20
Reinforcem ent Rein forcementw issen
Umw elt
Senso rinpu t
Rein forcementupdate
Aktions- oderAktivitätsausw ah l
Zustandsaktions-abb ildung
M ög licheAktionen bzw .
Aktivitäten
3. März 2000 LS VI Workshop: Kalibrierung und Optimierung 16/20
Zusätzliches Wissen:
Algorithmus:
Optimierung während Simulationslauf auf IndividuenebeneAnforderungen
Optimierung während Simulationslauf auf IndividuenebeneAnforderungen
• Reinforcement-Wissen, d.h. was muss man wie verändert, falls Reinforcement R auftritt.
• Wie wird Reinforcement R aus Sensorinput errechnet.
• Möglichst nur für Teilbereiche des Modells definieren.
• Reinforcement-Learning
3. März 2000 LS VI Workshop: Kalibrierung und Optimierung 17/20
Zusammenfassung:Zusätzliches WissenZusammenfassung:Zusätzliches Wissen
a) Bewertungsfunktion eines Simulationslaufesb) Bewertungsfunktion für Individuum oder
‚survival of the fittest‘c) Wissen über Parameterabhängigkeiten
(Constraintnetz):a) Test, ob Parameterwerte von Individuum sinnvoll sind b) Funktion, um Parameterwerte sinnvoll zu machen
(Reparatur) oder Funktion zur Konstruktion von sinnvollen Parameterwerten
d) Reinforcement-WissenStandardansatz
Populationseben
Individuenebene
Modellebene
a) bzw. b), c) b), c) d) c)
3. März 2000 LS VI Workshop: Kalibrierung und Optimierung 18/20
Zusammenfassung:Zusätzliche Algorithmen
Zusammenfassung:Zusätzliche Algorithmen
a) Suchalgorithmus (uninformiert?)b) Evolutionäre Strategie zur
Parameteradaption bzw. –rekombination
c) Constraintsatisfactiond) Reinforcement-Learning
Standardansatz
Populationseben
Individuenebene
Modellebene
a), c) b), c) d) c)
3. März 2000 LS VI Workshop: Kalibrierung und Optimierung 19/20
‚Zeitplan‘‚Zeitplan‘
1) Optimierung auf Individuenebene Projekt mit Biologie
2) Optimierung auf Modellebene3) Standardansatz4) Optimierung auf Individuenebene
Lernen, Baldwin-Effekt
3. März 2000 LS VI Workshop: Kalibrierung und Optimierung 20/20