Hauptinhalt

Simulationsbasierte Optimierung (Seminar)

Seminar WS 14/15 (2 SWS, Nr. 041407)

Simulationsbasierte Optimierung

 

Veranstalter: Peter Buchholz (Tel.: (0231) 755 4746),

Email: peter.buchholz@udo.edu

Sprechstunde: Donnerstag 10:00-11.30 und n.V.

 

Das Seminar findet als Kompaktseminar im Februar 2015, nach der Vorlesungszeit im Wintersemester statt.

Anmeldung zum Seminar bitte bis Anfang Dezember 2014 per E-Mail an

Die inhaltliche Beschreibung wird im Laufe des Semesters ergänzt und erweitert.

 

Inhalt

Viele technische Systeme werden heute modellbasiert per Simulation analysiert. Dabei kommen oft ereignisdiskrete stochastische Simulationsmodelle zum Einsatz. In der Praxis sollen Systeme aber nicht nur analysiert, sondern verbessert oder sogar optimiert werden. Idealerweise geschieht dies ebenfalls auf Basis der bereits erstellten Simulationsmodelle. Damit müssen Optimierungsverfahren mit Simulationsmodellen kombiniert werden. Man spricht dann oft von simulationsbasierter Optimierung. Die Optimierung von Simulationsmodellen ist ein schwieriges Problem, da die Ausgaben der Simulationsmodelle stochastischen Schwankungen unterliegen, Simulation generell einen hohen Aufwand erfordert, keine oder kaum Strukturinformationen vorliegen, so dass die Modelle als so genannte black boxes betrachetet werden müssen und damit klassische matehmatische Optimierungsverfahren nicht oder nur sehr eingeschränkt einsetzbar sind. Im Wesentlichen werden deshalb heuristische Verfahren zur Optimierung genutzt, mit denen man zwar nicht zwangsläufig ein Optimum findet, man kann oft nicht einmal garantieren, dass das Optimum, sofern es existiert, mit einer gewissen vorgegebenen Qualität approximiert wird, die aber in der Praxis in fast allen Fällen gute Ergebnisse liefern.

Im Rahmen des Seminars wollen wir eine Übersicht über die Vielzahl der vorhandenen Ansätze zur simulationsbasierten Optimierung erlangen, indem wir die vorhandenen Algorithmen klassifizieren und die wesentlichen Ansätze etwas detaillierter vorstellen.

 

Themen

Die Themen werden jeweils in Blöcke zusammengefasst. Ein Block umfasst mehrere Seminarthemen. Teilnehmerinnen und Teilnehmer sollten sich zuerst für einen Themenblock entscheiden, sich dort einarbeiten und anschließend ein konkretes Thema festlegen und bearbeiten.  Die angegebene Literatur dient zum Einstieg in das jeweilige Themengebiet. Das Weitersuchen  von Literatur und das Lesen weiterer Artikel ist erwünscht und meistens auch notwendig.

  1. Einführung die simulationsbasierte Optimierung (1 bis 2 Themen)
    Literatur:
    1. M. C. Fu. Optimization for Simulation: Theory vs. Practice. INFORMS Journal of Computing 14 (3) 2002,  192-215.
    2. G. Figueira, B.  Almada-Lobo. Hybrid simulation–optimization methods: A taxonomy and discussion. Simulation Modelling Practice and Theory 46, 2014, 118-134.
    3. L. F. Wang, Y.  Shi. Simulation Optimization: A Review on Theory and Applications. Acta Automatica Sinica 39 (11) 2013,  1957-1968.
  2. Methoden für diskrete Parameter mit garantierter Konvergenz
    1. Stochastische Suchverfahren mit garantierter Konvergenz (1 Thema)
      Literatur
      1.  S. Andradòttir. Simulation Optimization with Countably Infinite Feasible Regions: Efficiency and Convergence. ACM Transactions on Modeling and Computer Simulation 16 (4), 2006, 357–374.
      2.  S. Andradóttir, A. A. Prudius. Balanced Explorative and Exploitative Search with Estimation for Simulation Optimization. INFORMS Journal on Computing 21 (2), 2009, 193-208.
    2. Der COMPASS-Ansatz (1 Thema)
      Literatur
      1. L. J. Hong, B. L. Nelson. Discrete Optimization via Simulation Using COMPASS. Operations Research 54 (1), 2006, 115-129.
      2. J. Xu,  B. L. Nelson, L. J. Hong. Industrial Strength COMPASS: A Comprehensive Algorithm and Software for Optimization via Simulation. ACM Transactions on Modeling and Computer Simulation 20 (1), 2010, .
  3. Heuristiken und Metaheuristiken
    1. Übersicht über Metaheuristiken für die Optimierung stochastischer Simulationsmodelle (1 bis 2 Themen)
      Literatur

      1. L. Bianchi,  M. Dorigo, L.  M. Gambardella, W. J. Gutjahr. A survey on metaheuristics for stochastic combinatorial optimization. Natural Computing 8 (2009), 239-287.

      2. S. Ólafsson. Metaheuristics. In:  S.G. Henderson and B.L. Nelson (Eds.), Handbooks in Operations Research and Management Science, Vol. 13 (2006), 633-654.

    2. Deterministische Suchverfahren (1 bis 2 Themen)
      Literatur

      1. T. A. Sriver, J. W. Chrissis, M. A. Abramson. Pattern Search Ranking and Selection Algorithms for Mixed Variable Simulation-Based Optimization. European Journal of Operational Research, Vol. 198 (3), 2009, 878-890.

      2. K. H.  Chang. Stochastic Nelder-Mead Simplex Method-A New Globally Convergent Direct Search Method for Simulation Optimization. European Journal of Operational Research 220 (3), 2012, 684-694.

    3. Simulated Annealing (1 Thema)
      Literatur

      1. M. D A. Ahmed, T. M. Alkhamis, M. Hasan. OPTIMIZING DISCRETE STOCHASTIC SYSTEMS USING SIMULATED ANNEALING AND SIMULATION. Computers in Engng. 32 (4), 1997, 823-836.

      2. S. L. Rosen, C. M. Harmonosky. An improved simulated annealing simulation optimization method for discrete parameter stochastic systems. Computers and OR 32 (2005), 343-358.

  4. Metamodellbasierte Verfahren
    1. Übersicht über Metamodelle und ihr Einsatz in der Simulation (1 Thema)
      Literatur
      1. R. R. Barton, M. Meckesheimer. Metamodel-Based Simulation Optimization. In: S.G. Henderson and B.L. Nelson (Eds.), Handbooks in Operations Research and Management Science, Vol. 13 (2006), 535-574.
      2. Y.F. Li, S.H. Ng, M. Xie, T.N. Goh. A systematic comparison of metamodeling techniques for simulation optimization in Decision Support Systems. Applied Soft Computing 10 (4), 2010, 1257-1273.
    2. Response Surface Metamodelle (1 Thema)
      Literatur
      1. J. P.C. Kleijnen. Response Surface Methodology for Constrained Simulation Optimization: an Overview. Simulation Modelling Practice and Theory 16 (2008),
      2. K. H. Chang, L. J. Hong, H. Wan. Stochastic Trust-Region Response-Surface Method (STRONG)—A New Response-Surface Framework for Simulation Optimization. INFORMS Journal on Computing 25 (2), 2013, 230-243.
    3. Kriging Metamodelle (1 Thema)
      Literatur
      1. J. P.C. Kleijnen. Kriging metamodeling in simulation: A review. European Journal of Operational Research Vol 192 (3), 2009, 707-716.
      2. D. Huang, T. T. Allen, W. I. Notz,  N. Zeng. Global Optimization of Stochastic Black-Box Systems via Sequential Kriging Meta-Models. Journal Journal of Global Optimization 34 (2006), 441–466.
  5. Software zur simulationsbasierten Optimierung (1 bis 2 Themen)
    Literatur
    1. R. Pasupathy, S. G. Henderson. SIMOPT: A LIBRARY OF SIMULATION OPTIMIZATION PROBLEMS. In: S. Jain, R. R. Creasey, J. Himmelspach, K. P. White, and M. Fu (eds.), Proceedings of the 2011 Winter Simulation Conference, IEEE Press, 4075-4084.
    2. C. Almeder, M. Preusser. A TOOLBOX FOR SIMULATION-BASED OPTIMIZATION OF SUPPLY CHAINS. In: S. G. Henderson, B. Biller, M.-H. Hsieh, J. Shortle, J. D. Tew, and R. R. Barton (eds.), Proceedings of the 2007 Winter Simulation Conference, IEEE Press, 1932-1939.
    3. J. P.C. Kleijnen, J. Wan. Optimization of simulated systems: OptQuest and alternatives. Simulation Modelling Practice and Theory 15 (2007) 354–362.
    4. J. Boesel, B. L. Nelson, N. Ishi. A framework for simulation-optimization software. IIE Transactions 35, 2003, 221-229.
  6. Anwendungen
    1. Supply Chains (1 Thema)
      Literatur:
      1. X. W., Joseph F. Pekny, G. V. Reklaitis. Simulation-based optimization with surrogate models — Application to supply chain management. Computers and Chemical Engineering 29 (2005) 1317–1328.
      2. A. Nikolopoulou, M. G. Ierapetritou. Hybrid simulation based optimization approach for supply chain management. Computers and Chemical Engineering 47 (2012) 183– 193.
    2. Medizinische Notfallversorgung (1 Thema)
      Literatur:
      1. P. M. S. Silva, L. R. Pinto. EMERGENCY MEDICAL SYSTEMS ANALYSIS BY SIMULATION AND OPTIMIZATION. In: B. Johansson, S. Jain, J. Montoya-Torres, J. Hugan, and E. Yücesan (eds.), Proceedings of the 2010 Winter Simulation Conference.
      2. T. L. Chen. Decision Support System Based on Distributed Simulation Optimization for Medical Resource Allocation in Emergency Department. F.F.-H. Nah (Ed.): HCIB/HCII 2014, Springer LNCS 8527, pp. 15–24, 2014.

 

Organisatorisches

Für eine erfolgreiche Teilnahme am Seminar ist die Anwesenheit bei allen Vorträgen zwingend notwendig. Ferner muss ein ca. einstündiger Vortrag über ein Thema gehalten werden, die Diskussion zum Vortrag muss vorbereitet und geleitet werden und ein Ausarbeitung zum Thema im Umfang von ca. 15-20 Seiten ist zu erstellen. Ausarbeitungen sollen mit LaTeX unter Nutzung des llncs Stils erstellt werden und sollen mit pdflatex erzeugt werden können.