A stochastic simulation is a powerful tool for evaluating the performance of man-made complex systems, where the performance is evaluated by independent repeating simulations. The reverse simulation means finding optimal system designs satisfying given performance requirements of the system among various design alternatives, based on the stochastic simulation. If the number of design alternatives is small and limited, the ranking and selection (R&S) in statistics is an efficient approach for the reverse simulation. When computing resources available for repeating simulations are limited, the R&S aims to find optimal design accurately by distributing the limited resources to design alternatives effectively. Recently, with increasing complexity of the systems, computing resources per simulation run also increases rapidly; thus, a problem of increasing the efficiency of R&S for selecting optimal design accurately with minimized resources has been drawing attention. For this, three frameworks have been proposed: the optimal computing budget allocation (OCBA), the indifference-zone (IZ), and the expected opportunity cost (EVI), and many efficient algorithms for various R&S problems has been developed based on these frameworks. However, the previous frameworks have a disadvantage in that the efficiency decreases when simulation model has large stochastic noise.
This dissertation proposes an efficient R&S framework for efficient reverse simulation of the stochastic simulation model. To effectively allocate limited simulation resources, this dissertation defines a measurement named “uncertainty” based on the p-values of statistical hypothesis test and suggests a heuristic allocation policy of additional simulation resources for maximizing the accuracy based on the uncertainty. To use the limited resources more efficiently, the UE framework allocates the additional simulation resources step by step using the defined uncertainty and the policy, based on the sequential procedure. While the previous frameworks focus on only the sample mean and sample variance when allocating resources, the proposed framework considers the standard error additionally. This further consideration improves the efficiency of the framework in noisy situations by reducing wasted resources due to a poor value of sample mean. In this dissertation, based on the proposed framework, we propose efficient algorithms for solving various R&S problems. We demonstrate its improved efficiency and high robustness to noise by comparative experiments with the existing algorithms developed based on the previous frameworks. We also introduce several case studies in which the reverse simulation of the real system is efficiently performed through the proposed algorithm.
확률적 시뮬레이션은 복잡한 시스템의 성능을 측정하는데 유용하며 이 성능은 독립적 반복 시뮬레이션 출력의 기댓값으로 도출된다. 역 방향 시뮬레이션은 이러한 시뮬레이션을 통해서 주어진 성능 요구조건을 만족하는 시스템의 최적 설계들을 찾는 것을 의미한다. 순위 및 선택 방법은 가능한 설계의 개수가 작고 한정적일 경우에 이 역 방향 시뮬레이션을 효율적으로 활용할 수 있도록 하는 통계적 기법이다. 순위 및 선택 방법은 반복 시뮬레이션에 사용할 수 있는 컴퓨팅 자원이 한정되어 있을 때, 이를 효과적으로 각 설계에 분배하여 최적 설계를 정확하게 찾는 것을 목표로 한다. 최근 모의하는 시스템의 복잡도가 증가하고 시뮬레이션 수행에 필요한 컴퓨팅 자원이 증가함에 따라서 최소한의 자원으로 정확하게 최적 설계들을 찾을 수 있도록 순위 및 선택 방법의 효율성을 높이는 문제가 대두되고 있다. 이를 위하여 OCBA (Optimal computing budget allocation), IZ (Indifference-zone), EVI (Expected opportunity cost) 등 세 가지 프레임워크가 제안되었고, 이를 바탕으로 순위 및 선택의 다양한 문제를 해결하기 위한 효율적인 알고리즘들이 많이 제안되었다. 하지만 기존의 연구들은 시뮬레이션 출력의 높은 잡음(noise)으로 인해 정확하게 최적 설계들을 찾기 어려운 경우에 효율성이 급격하게 떨어지는 한계점이 있다.
본 학위논문에서는 확률적 시뮬레이션을 통한 역 방향 시뮬레이션을 효율적으로 활용하기 위한 순위 및 선택 프레임워크를 제안한다. 제안하는 프레임워크는 통계적 가설 검정의 p-value를 사용하여 불확실성이라는 평가 지표를 정의하고, 이 지표에 따라서 정확성을 최대화하기 위해 주어진 시뮬레이션 자원을 순차적으로 할당한다. 기존의 연구들이 자원을 할당할 때 관찰된 시뮬레이션 결과의 평균과 분산만을 고려하는데 반해서 제안하는 프레임워크는 표준 오차를 추가적으로 고려함으로써 높은 잡음이 존재할 때 효율성을 높인다. 본 학위 논문에서는 제안하는 프레임워크를 바탕으로 다양한 순위 및 선택의 문제들을 효율적으로 해결하기 위한 알고리즘들을 제시하고, 기존의 프레임워크를 바탕으로 개발된 알고리즘들과의 성능 비교 실험을 통해서 이 프레임워크의 높은 잡음에 대한 강인함과 향상된 효율성을 증명한다. 또한 제안하는 알고리즘을 통해서 실제 시스템에 대한 역 방향 시뮬레이션을 효율적으로 수행한 사례들을 소개한다.
