以梯度為基礎的隨機最佳化演算法 --回顧與比較

Gradient-Based Simulation Optimization Algorithms -- Review and Comparison

李國英(Kuo-Ying Lee)

指導教授 ： 陳慧芬

中原大學/工學院/工業工程研究所/碩士(2005年)

https://doi.org/10.6840/cycu200500395

摘要

本論文將分成兩個主題來探討，一是將焦點擺在模擬最佳化演算法的文獻回顧上，藉由文獻資料的整理與分析後，可對於目前在求解隨機最佳化問題方法，有著簡明的了解與認知。另一是著重在最佳化演算法的比較上，利用一個簡單但可解析的例子，提供作為比較的平台，讓我們對最佳化演算法的求解能力與速度，有著更深一層的認識。
在演算法的回獻的方面，我們是針對求解連續型參數的最佳化演算法做為回獻重點，而這類型的演算法是以隨機近似演算法 (Stochastic Approximation algorithm) 最被廣泛使用。另外，隨機近似演算法的重要部分為梯度估計，使用不同的梯度估計技巧，可讓隨機近似演算法應用在許多的模擬模式類型，我們主要討論的梯度估計技巧有四種，分別為perturbation analysis (PA), likelihood ratios (LR), finite difference (FD) and simultaneous perturbation (SP)。
不同的梯度估計技巧除了有著不同的估計方式外，所得的梯度估計量也將分為有偏與不偏的估計量，而將之套用在隨機近似演算法(SA)裏，也將形成不同類型的演算法，一類是以直接梯度估計(不偏的估計量)為基礎的演算法，包括PASA， LRSA等二種，另一類為以梯度近似估計(有偏的估計量)為基礎的演算法， 則FDSA及SPSA屬於這一類型。不同類型的演算法也將有著不同的收歛速度，在做比較的同時，是必須分開的。而我們利用這四種不同的最佳化演算法來求解同一個隨機最佳化的問題時，除了在求解的精確度方面有不同之處外，也收歛速率的不同也將影響求解的時間與解的品質。
為了提供一可比較的平台，我們採用的範例是簡明易懂且是可解析的，以便於我們的實驗結果可與真正最佳值核對後進行比較。因此，我們使用一簡明易懂但常被運用的例子, M/M/1 queue, 做為四種演算法的比較平台;經由模擬實驗後所得到的實驗結果顯示，PASA是最有效率的演算法，但我們並不能說是PASA絕對最好的，因為不同類型的演算法有著不同的收歛速度，只是在相對上來說，針對這個簡單例子，PASA的表現是相當不錯的。

關鍵字

模擬最佳化演算法 ； 梯度估計技巧 ； 有偏與不偏估計量 ； 模擬實驗 ； 隨機最佳化問題 ； 收歛速率 ； 隨機近似演算法

並列摘要

In this thesis, our main interests are 1) to have a clear idea of how to solve stochastic optimization problem and 2) to present comparison of solutions by applying algorithms incorporated with different gradient estimation techniques. In order to have better understanding of solving stochastic optimization problem, we present some famous research references on simulation optimization algorithms and then conduct some general analysis on these research references. On the other hand, we focus on the comparison of the merits (such as the ability and speed of solving problem) of major algorithms embedded with different gradient estimation techniques. To derive the practical result and thus have better understanding, we use an analytical sample problem as our comparison platform.
With regard to the references review of algorithms, we focus more on continuous parameter optimization algorithms, of which Stochastic Approximation algorithm is the most widely adopted. For SA algorithm, the most essential part is the gradient estimation. By using various gradient estimation techniques, we can have SA be applied in a number of types of simulation models. In our research, we present four gradient estimation techniques, containing PA (Perturbation Analysis), LR (Likelihood Ratios), FD (Finite Difference) and SP (Simultaneous Perturbation).
Each gradient estimation technique has distinct estimator and the derived gradient estimates are either biased or unbiased. Therefore, when applying them in SA algorithms, we will obtain two different types of algorithms. One type of algorithms are based on direct (or unbiased) gradient estimate, including PSAS, and LRSA. The others are algorithms based on gradient approximation (or biased estimate), such as FDSA and SPSA. Different types of algorithms have different convergence speed; we have to compare the algorithms with same type (compare different types of algorithms separately). When applying these four optimization algorithms to solve same stochastic optimization problem, we derive not only different precision of the solutions but also varied convergence rate. Convergence rate further influences the time required to solve the problem and have impact on the quality of solutions.
To provide a comparable platform, we use a simple problem, which is analytical and easy to understand. By doing so, we can compare the simulation experimental results with the true optimized values. Here, the so-called easy and analytical example is M/M/1 queue. After conducting the simulation experiment, we learn PASA is the most efficient algorithm among the four discussed. This, however, doesn't mean PASA is the best because different algorithms have different convergence rate. What we can draw from our research is that for this simple problem (M/M/1), PASA's performance is pretty good.

並列關鍵字

simulation experimental results. ； stochastic approximation algorithm ； simulation optimization algorithm ； stochastic optimization problem ； gradient estimation techniques

參考文獻

List of Reference

Asmussen, S. 1991. Performance Evaluation for the Score Function Method in Sensitivity Analysis and Stochastic Optimization. Manuscript, Chalmers University of Technique, Goteborg, Sweden.

Andradottir, S. 1995a. A stochastic approximation algorithm with varying bounds. Operations Research, Vol. 43, pp. 1037-1048.

Andradottir, S. 1996b. Optimization of the transient and steady-state behavior of discrete event systems. Management Science, Vol. 42, pp. 717-737.

Benveniste, A., M. Metivier, and P. Priouret. 1990. Adaptive algorithms and stochastic approximations. Berlin: Springer-Verlag.