系統模擬上的最佳化問題---回溯求解

Retrospective Approaches for Simulation Optimization Problems in System Design

黃彥登(Yen-Deng Huang)

指導教授 ： 陳慧芬

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

https://doi.org/10.6840/cycu200400310

摘要

本論文將分成兩個方向來探討，一是將重點擺在隨機最佳化方法論的文獻回顧上，藉由文獻的整理與分析後，對於目前在求解隨機最佳化問題，有著簡明的認知。另一方面是著重在隨機最佳化方法論的研究與發明上，我們提出有限差分回溯近似法(FDRA Algorithm)並利用兩個簡單但可解析的例子，提供已知的最佳解並與所求的近似解比較，然後並與其中一種隨機最佳化的方法論作比較，是由Jin(1998)所提出的回溯最佳化(RO Algorithm)，讓我們對隨機最佳化方法論的求解能力與速度，有著更深一層的認識。
首先，我們先考慮隨機最佳化問題，發現此問題的最佳解是只能利用其目標函數值的估計去求得，然而這類型的問題大多都發生在系統設計上伴隨著模擬應用。因此目標函數的決策變數是可控制和改變的系統參數並且使得目標函數的系統成本是達到最佳進而求得其最佳的決策變數。且由於隨機系統是過於複雜的，所以此問題的目標函數值是不能被分析或是計算的，但是卻能夠透過模擬實驗去估計其目標值。
在文獻回顧方面，我們是以求解連續型參數的隨機最佳化方法論作為重點，所以我們假設其目標函數式是單一型態、連續並且可微的，在這種情況下，找到這問題的最佳解(決策變數)相當於找到梯度函數為零的解並使其目標式達至最佳化，然而這類型的方法都以隨機近似法(SA algorithm)最為廣泛的被使用。儘管它的收斂性證明，然則若選擇不好的演算法參數值，隨機近似法的收斂速度也是會變得很緩慢。因此，隨機最佳化的方法論應用隨機近似法大多都是搭配梯度估計去求梯度函數為零，使用不同的梯度估計，可讓隨機近似法應用在許多不同的問題，我們主要討論的梯度估計技巧有四種，分別finite difference (FD)， simultaneous perturbation (SP)，perturbation analysis (PA) and likelihood ratios (LR)。
之後，我們提出有限差分回溯近似法(FDRA Algorithm)去解隨機最佳化問題並假設其目標函數式是單一型態、連續並且可微的。FDRA是使用這個 RA-Broyden的方法去解多維隨機求根的問題而不是隨機近似法，此多維隨機求根的問題相當於求解梯度函數為零的問題，而我們是用有限差分法去估計這個梯度。之後，我們使用兩個簡單問題去模擬實驗其演算法，然後判斷其演算法的收斂特性是否為堅固性並符合它的演算參數，最後再與回溯最佳化作比較。在我們的實驗結果中，FDRA收斂是迅速的並且是有堅固性符合它的演算參數。
關鍵詞：隨機最佳化演算法，隨機最佳化問題，回溯最佳化，隨機近似法，回溯近似法，梯度估計，有限差分法，收歛速率。

關鍵字

隨機近似法 ； 回溯最佳化 ； 有限差分法 ； 收歛速率 ； 隨機最佳化問題 ； 梯度估計 ； 回溯近似法 ； 隨機最佳化演算法

並列摘要

We consider stochastic optimization problems, finding the optimal point using only estimates of the function values. Such problems occur in system design with simulation applications. The
decision variables are controllable system parameters and the objective function is the associate system cost to be minimized. Due to the complexity in the stochastic system, the objective function values (for any choice of the decision variables) can not be computed numerically but can be estimated through simulation experiments.

We assume that the objective function is unimodal, continuous, and differentiable. In this case, finding the optimal point is equivalent to finding the zero of the gradient function. The literature of such problems focuses on stochastic approximation. Despite its convergence proof, stochastic approximation may converge slowly if the algorithm parameter
values are not well chosen.

We propose the FDRA algorithm to solve stochastic optimization problems. FDRA uses the RA-Broyden algorithm (a stochastic rootfinding algorithm) to find the zero of the gradient function, whereas the gradient is estimated by the finite-difference method. Using two test problems, werun simulation experiments to evaluate the robustness of FDRA corresponding to its algorithm parameters and compare FDRA with the non-gradient based retrospective optimization algorithm. In our empirical results, FDRA converges quickly and is robust to its algorithm parameters.

Keywords: Gradient Estimation, Finite Difference, Retrospective Approximation, Retrospective Optimization, Stochastic Optimization

並列關鍵字

Finite Difference ； Retrospective Approximation ； Gradient Estimation ； Retrospective Optimization ； Stochastic Optimization

參考文獻

LIST OF REFERENCES

[1] Andradottir, S. 1991. A Projected Stachastic Approximation Algorithm. Proceedings

Kelton, and G. M. Clark, 954-957. Institute of Electrical and Electronic Engineers,

[2] Andradottir, S. 1998. A Review of Simulation Optimization Techniques. Proceedings

of the 1998 Winter Simulation Conference, ed. D. J. Mederios, E. F.