透過您的圖書館登入
IP:54.211.203.45
  • 學位論文

禁忌搜尋法應用在離散型模擬最佳化問題上

Tabu Search for Discrete Simulation Optimization Problems

指導教授 : 陳慧芬
若您是本文的作者,可授權文章由華藝線上圖書館中協助推廣。

摘要


在最佳化問題中,可因決策變數分為連續型與離散型的問題,而目標函數值的複雜度可分模擬問題與解析問題,而在本論文中,主要在探討離散型最佳化的問題。針對此類問題是只能利用其目標函數值的估計去求得,然而這類型的問題大多都發生在系統設計上伴隨著模擬應用。因此目標函數的決策變數是可控制和改變的系統參數並且使得目標函數的系統成本是達到最佳進而求得其最佳的決策變數。且由於隨機系統是過於複雜的,所以此問題的目標函數值是不能被分析或是計算的,但是卻能夠透過模擬實驗去估計其目標值。例如:生產問題,當產品的到達率或是服務時間不是服從指數分配(Exponential Distribution)時,而是服從任意某一種分配時,則其等候長度或等候時間很難用數學模式推導,這時就可利用模擬的方法,去有效率地得到一組可行解。 本論文提出TSDRA 運算法,是結合回溯近似法(DRA: Dependent Retrospective Approximation)和禁忌搜尋法 (TS:Tabu Search) 來解離散型模擬最佳化的問題。TSDRA是依附回溯近似法(DRA: Dependent Retrospective Approximation)的架構藉由增加樣本的數量反覆地解決一系列的樣本路徑問題(sample-path),並由TS搜尋每一個樣本路徑的最佳化。當樣本到達無限大時,此樣本路徑即等同於真實的目標函數。 本研究考慮兩個績效指標一個是均方差(MSEf mean square error),另一個為收斂到最佳解的實驗次數(CP convergent path)。並與現有的六種演算法做比較(Random Search Algorithms,SADRA,GADRA)。在本研究中,計算出較小的MSEf及較大的CP值,就可得知此演算法為較佳的演算法。在本研究中使用的例子包含了M/M/1 系統與多項式單一解的例子來討論TSDRA是否會達到最佳解,並與其他的方法比較探討。在M/M/1 系統的例子中,因為決策變數只有一個,針對禁忌搜尋法而言,只要禁忌搜尋法搜尋的次數夠多,就可以達到最佳的解。在多項式單一解的例子中,有兩個決策變數,易陷入區域最佳解,實驗的結果顯示MSEf的收斂速度比SADRA和GADRA還要優異,若看CP值TSDRA就會比SADRA(N(x2))的CP差。

並列摘要


The optimization problems can be categorized into two types: continuous and discrete, base on the decision variables. We also discuss the simulation and numerical analysis. Now we consider mainly discrete simulation optimization problems. The simulation 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 objective function is the associate system cost to be minimized. Due to the complexity in the simulation system, the objective function values can not be computed numerically but can be estimated through simulation experiments. We propose the TSDRA algorithm for solving discrete simulation optimization problems. This algorithm combines the Dependent Retrospective Approximation (DRA) procedure and Tabu Search (TS). The main idea of DRA algorithm is to iteratively solve a sequence of sample-path problems with increasing sample size. Each sample-path problem is then solved by the heuristic tabu search (TS). We consider two performance indexes in this research: first is sensitivity analysis of the algorithm parameters, second is comparison of TSDRA to six existing algorithms --- MSSA, SRS, MSSR, MSSC, GADRA and SADRA---. Both studies use MSEf and CP as algorithm performance measures, where MSEf is the mean square error in the function value and CP is the number of convergent paths out of replications (a convergent path is one that terminates with the true optimal point). Algorithms with small MSEf and big CP are preferred. The simulation results also show that M/M/1 system is one dimension. In tabu search, long as search it from the large iterations, can reach best solution. Uni-model system is two dimensions, so that it will produce the cycle. TSDRA will get small MSEf than SADRA and GADRA, But SADRA ( ) get a good CP value.

參考文獻


VI. REFERENCES
【1】 Alrefaei, M. H. and S. Andrad´ottir (2001).” A Modification of the Stochastic Ruler Method for Discrete Stochastic Optimization.” European Journal of Operation Research 133, 160—182.
【2】 Andrad´ottir, S. (1996). “A Global Search Method for Discrete Stochastic Optimization.” SIAM journal on Optimization 6, 513—530.
【3】 Armentano, V.S., and Ronconi, D.P.(1999). “Tabu search for total tardiness minimization in flow shop scheduling problems.” Computers and Operations Research 26, 219-235
【5】 Brooks, S. H. (1958). “Discussion of random methods for locating surface maxima.” Operations Research 6, 244—251.

延伸閱讀