Stochastische mikroskopische Simulationsmodelle zur Optimierung von Zielgrößen

Abstract

Schon lange steht fest, dass die Optimierung ein fundamentales Gebiet in der Mathematik ist, sowohl in Theorie als auch in Praxis. Wie einst Leonhard Euler schrieb: „Was immer in der Welt passiert, in seinem Inneren hat es die Bedeutung von Maximum oder Minimum. Somit ist kein Zweifel, dass alle Naturphänomene über die Methode des Maximierens oder Minimierens erklärt werden können.“ Nicht immer ist die mathematische Optimierung der beste Ansatz, gerade bei sehr komplexen Systemen kann es passieren, dass kein Optimum analytisch oder numerisch bestimmbar ist. Eine äußerst hilfreiche Option bietet daher die Modellbildung dieser Systeme, um durch Veränderung von Input Parametern den Output der Simulation zu optimieren. Diese Arbeit diskutiert und erläutert die wichtigsten Methoden der „Simulation Optimization“,darunter gradientenbasierte Suchmethoden, stochastische Approximierungs Algorithmen wie den Kiefer-Wolfowitz Algorithmus, welcher mit finiten Differenzen den Gradienten der Zielfunktion schätzt um, ähnlich wie beim Gradientenverfahren, entlang des steilsten Abstiegs eine Minimalstelle zu suchen, Response Surface Methodology, die mit Hilfe von linearer und quadratischer Regression Metamodelle erzeugt und damit versucht eine optimale Lösung zu finden, heuristische Methoden wie genetische Algorithmen, Random Search und Simulated Annealing und letztendlich statistische Methoden wie Ranking and Selection, welche sich für diskrete, endliche Lösungsräume eignen. Insbesondere achten wir auf die Tauglichkeit für stochastische mikroskopische Modelle mit langer Rechenzeit. Wir fordern von den Methoden, mit möglichst wenigen Durchläufen von Simulationen auszukommen, um die bestmögliche Kombination an Input Parametern für das Modell zu finden. Das ist ein entscheidender Faktor, da Simulationsdurchläufe sehr teuer im Sinne von langer Rechenlaufzeit sein können und es de facto unmöglich wäre, in einem beschränkten Zeitraum alle Möglichkeiten auszuwerten, um die beste zu finden. Die Arbeit setzt mit der Beschreibung von drei Fallstudien fort, einem Optimierungsproblem für ein stochastisches, agentenbasiertes Simulationsmodell eines U-Bahn Netzes, der Anpassung einer Epidemiologischen Kurve eines COVID-19 SIR Modells und schließlich einem Optimierungsproblem für Policies mit Hilfe eines komplexen Modells, das entwickelt wurde, um agentenbasierte Simulation für die Evaluierung von Contact-Tracing Policies gegen die Ausbreitung des SARS-CoV-2 durchführen zu können und in der realen Entscheidungsunterstützung zum Einsatz kommt. Die Parameteroptimierung für das U-Bahn Modell sieht den Algorithmus von Kiefer und Wolfowitz als beste Methode, während Random-Search am wenigsten effizient funktioniert. Bei der Anpassung einer epidemiologischen Kurve von neu bestätigten Covid-19 Fällen an gegebene Echtdaten versagt der Kiefer-Wolfowitz Algorithmus allerdings, da dieser im Allgemeinen nur lokale Minimalstellen findet. In dieser zweiten Fallstudie zeigte sich der Simulated Annealing Algorithmus als sehr verlässlich, weshalb dieser auch für die Optimierungen verschiedener Szenarien im agentenbasierten COVID Modell verwendet wird. Abschließend wird mit geeigneten Optimierungen geklärt, mit welchen Szenarien die Effekte von verschiedenen Policies gegen die Ausbreitung von SARS-CoV-2 vergleichbar gemacht werden können. Die Frage ob Kreuzeffekte durch den Einsatz mehrerer Policies in der gleichen Simulation entstehen können wird auch in der Arbeit behandelt und kann letztendlich mit „Ja“ beantwortet werden.

It has long been established that optimization is a fundamental area in mathematics, both in theory and in practice. As Leonhard Euler once wrote: „Nothing takes place in the world whose meaning is not that of some maximum or minimum.“ Mathematical optimization is not always the best approach, especially with extraordinarily complex systems it can happen that no optimum can be determined in an analytical or numerical way. Modeling these systems therefore offers an extremely helpful option to optimize the simulation output by changing input parameters. The purpose of this thesis is to provide an overview over the most relevant approaches for simulation optimization. To begin with we look at gradient based search methods and stochastic approximation algorithms like the algorithm introduced from Kiefer and Wolfowitz, that is an iterative scheme based on gradient estimation. Secondly, we consider response surface methodology, that is a procedure for fitting a series of regression models to the output variable of a simulation model and optimizing the regression function with the steepest descent search method. Furthermore, we inspect heuristic methods like genetic algorithms, random search and simulated annealing and to conclude, we consider statistical methods like ranking and selection. We especially investigate the suitability for stochastic microscopic simulation models with long computing times. Simulation optimization can be defined as the process of finding optimal performance with the right choice of input variable values from among all possibilities without having to evaluate each possibility. We require from the considered methods to find this right choice with as few simulation runs as possible. This is crucial, since simulation runs can be expensive in terms of long computing times and it would be impossible to evaluate all possibilities in a limited period of time in order to find the best combination. Moreover, we will compare these algorithms using three case studies. Initially, we explore a stochastic, agent-based simulation model of a subway line. Afterwards, we go into the process of fitting an epidemiological curve of a COVID-19 SIR model to real data and, ultimately, we consider an optimization problem for a complex agent-based model that not only validly depicts the spread of SARS-CoV-2, but allowsfor exploratory analysis of containment policies. This agent-based model was developed to quantify the benefits of tracing and similar policies and to help the decision making process of the government of Austria. For optimizing the parameters in the subway model, the Kiefer-Wolfowitz algorithm was the most economical method for finding the best decision variables, while random search is not that efficient. In the second case study, the process of fitting the epidemiological curve fails in using the Kiefer-Wolfowitz algorithm since this method only seeks for local optima in general. In both case studies, the simulated annealing algorithm turned out to find the right choice of input variable values exceptionally reliable. So, the choice was made to use this method to optimize various scenarios in the agent-based COVID model.Finally, we are interested in how to find the right scenarios which can be used to compare the effects of different policies against the spread of SARS-CoV-2. In this thesis we show how to achieve that with suitable optimizations and, furthermore, we ascertain that cross effects can arise using several policies in the same simulation.