Estudio y simulación de eventos raros mediante el método de aceleración RESTART

Abstract

En este trabajo fin de máster se tratará el estudio de sucesos raros en redes de colas. Concretamente, aquellos sucesos con una probabilidad tan baja que no resulta viable hacer una simulación del sistema lo suficientemente completa como para asegurar la precisión de los resultados. El objetivo es el análisis del método RESTART, que permite acelerar la simulación forzando la aparición del evento de estudio. RESTART divide el espacio en regiones según la probabilidad de que ocurra el evento raro. El algoritmo lanza un número determinado de nuevos procesos cada vez que alcanza una región con una probabilidad más alta que la actual, con el objetivo de que alguno de ellos alcance la siguiente región y así sucesivamente hasta provocar el evento raro.
Para dicho análisis se ha desarrollado un simulador con una interfaz simple que permite modelar una red y aplicar el algoritmo RESTART, así como observar su comportamiento durante la misma. La adaptación gráfica del algoritmo permite ajustar los parámetros del método en tiempo real con el objetivo de maximizar la eficiencia de la simulación. La herramienta puede ajustar varios parámetros mediante varias simulaciones piloto donde el evento de estudio no es tan raro. Finalmente, se realizan varios experimentos, cuyos resultados podemos calcular de forma analítica.---ABSTRACT---This work deals with the study of rare events in queuing networks. Specifically, those events with a so low probability that it is not possible to make a simulation of the system complete enough to ensure the accuracy of the results. The aim is the analysis of the RESTART method, which allows to accelerate the simulation forcing the occurrence of the study event. RESTART divides the space into regions according to the probability of the rare event occurring. The algorithm launches some new processes each time it reaches a region with a higher probability than the current one, so that some of them reach the next region and so on until the rare event is triggered.
For this analysis a simulator with a simple interface has been developed, which allows to create networks and to apply the RESTART algorithm as well as to observe its behavior during the simulation. The graphical adaptation of the algorithm allows to adjust the method parameters during the execution so that we can maximize the efficiency of the simulation. The tool can adjust the parameters with several pilot simulations where the event is not so rare. Finally, we made some experiments with the tool, which results can be calculated applying the known formulas.