- 學位論文
基因演算法應用在離散型模擬最佳化問題上
Genetic Algorithms for Discrete Simulation Optimization Problems
摘要
在最佳化問題中，有許多問題的目標函數值是很難被求取的，但其可經由模擬的過程來加以估計，稱其為模擬最佳化問題。而目標函數值得經由系統參數來決定，不同系統參數的決定更關係到整個系統執行的成本。所以在本研究中，我們針對離散型模擬最佳化問題，提出一個新的演算法GADRA，來求取最佳的系統參數。 離散型模擬最佳化問題包括網路問題、供應鏈問題、排程問題、存貨系統…等等。例如:在（s，S）存貨系統中，若存貨水準高於s時均不提出訂購，若存貨水準低於s，即提出訂購，而以S與當時之存貨水準之差額為該次之訂購數量，而決策者決定s和S的數值來使得系統總成本(包括持有成本、訂購成本…等等)最小化。此系統中決策變數為（s，S），目標函數值為系統總成本，且此系統的決策變數組合為{0, 1,..., smax}x{0, 1,..., Smax}，其中smax和Smax為s及S的最大可能值。 GADRA 運算法則結合相依回朔近似法(DRA: Dependent Retrospective Approximation)和基因演算法(GA: Genetic Algorithms)。GADRA 使用 DRA 的架構藉由增加樣本的數量反覆地解決一系列的樣本路徑問題，並由GA搜尋每一個樣本路徑的最佳化。其中當增加到無限大的樣本數時，此樣本路徑即等同於真實的目標函數。 本研究將針對以下二點作分析：（1)演算法參數的靈敏度分析，（2)與不同的演算法做比較。在本研究中，演算法績效指標的衡量採取以下二種MSEf 和 CP。MSEf 為目標函數值的均方差(mean square error)；CP為收斂到最佳解的實驗次數。由此可知對較佳演算法而言，其擁有就小的MSEf及較大的CP值。在本研究結果顯示出GADRA收斂的速度表現的比其他演算法更加優異。
並列摘要
We propose the GADRA algorithm to solve the simulation optimization problem---finding the optimal point (in a discrete set) that minimizes the objective function, where the function value is difficult to compute but can be estimated via simulation experiments. Such problems occur in the design of stochastic systems. The decision variables are controllable system parameters to be determined. The objective function is the associate system cost. Applications of the discrete simulation optimization problem include the network design, supply chains design, scheduling, and inventory control. For example, in an (s, S) inventory control system, the inventory ordering policy is to order up to S units if the inventory level falls below s units. The system designer wants to decide the values of s and S such that the mean system cost (including holding, ordering, and backlogging costs) is minimized. In this example, the decision variables are (s, S), the objective function is the associate mean system cost, and the discrete set is {0, 1,..., s_max}x{0, 1,..., S_max}, where s_max and S_max are the biggest possible values of s and S. The GADRA algorithm combines the dependent retrospective approximation (DRA) procedure and genetic algorithms (GA). GADRA uses the framework of DRA to iteratively solve a sequence of sample-path problems with increasing sample sizes, where each sample-path problem is solved by GA. Eventually GA solves the real objective function because when the sample size goes to infinity, the sample-path objective function goes to the real objective function. Two empirical studies are conducted: (1) sensitivity analysis of the algorithm parameters, and (2) comparison of GADRA to four existing algorithms. 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. Our simulation results show that a small mutation rate usually performs better and the population size should increases from one sample path to the next. The simulation results also show that GADRA converges faster than the four existing algorithm.
參考文獻
延伸閱讀
- 廖薏琳（2020）。基因演算法於工程最佳化問題之研究〔博士論文，中原大學〕。華藝線上圖書館。https://doi.org/10.6840/cycu202000850
- 翁昭榮（2003）。基因演算法應用於動態可靠度之研究〔碩士論文，元智大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0009-0112200611311122
- 黃崑濱（1997）。基因演算法應用於管制圖經濟模式最佳參數設計之研究〔碩士論文，元智大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0009-0112200611335481
- Lin, Y. C. (2011). 基因演算法應用於二階多變數內建模式控制之研究. 崇仁學報, (5), 102-118. https://doi.org/10.6485/JCJJCNHSM.201112.0013
- 紅名鴻（2002）。On the Use of Genetic Algorithms to Solve the Dynamic Location Problem〔碩士論文，元智大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0009-0112200611300756