模擬退火法應用在離散型模擬最佳化問題上

在本論文中，主要研究探討離散型模擬最佳化的問題。所謂離散型模擬最佳化主要是在離散型之可行解空間中搜尋一滿足最小化目標函數的最佳解，但通常此目標函數不易去求算，但可藉由模擬實驗來估算。這類的問題通常發生在系統設計的情形下。此類系統最佳化問題之決策變數常見是系統的設定參數，如（s, S）存貨系統之安全存貨s 和最大存貨量S，而最佳化的問題便是尋找一組最佳績效指標的決策變數。在實務上，常見的問題如網路問題，供應鏈設計，排程或是存貨問題。很多方法論已經被發展來求解離散型模擬最佳化問題，若依據決策變數的數量來分類，可區分為兩大類：（1）無限大或是很多（2）有限多但數量很少。而本研究主要針對第一類來考量，有啟發式方法，如模擬退火法、禁忌搜尋法和基因演算法。隨機搜尋法，如單純隨機搜尋法、隨機尺度法和隨機比較法。而目前的演算法通常利用大量的模擬樣本來近四真實的目標函數圖形，因此會浪費大量的求算時間而降弟演算法的求解效率。本研究提出相依回溯近似模擬退火法（SADRA）來求解離散型模擬最佳化之問題。相依回溯近似模擬退火法利用相依回溯近似的觀念來迭代近似配合遞增模擬樣本求解一連串的樣本路徑（sample-path）問題。而每一個樣本路徑問題利用啟發式模擬退火演算法求解。本研究利用模擬實驗來驗證SADRA 之求解績效並與目前發展的演算法作比較。而實驗之績效指標是目標函數值的均方誤差MSEf 和收斂路徑（CP），所謂收斂路徑就是收斂的比例。因此較小的MSEf 和較大CP 值展現較佳的求解績效指標。並利用敏感度分析來研析方法論之參數對求解績效之影響。在模擬實驗中，當目標函數是平滑且只有一個最佳解時，SADRA 運用較小的鄰域會有較好的求解績效，但當目標函數有多個區域最佳解時，隨機型的鄰域參數會有較好的求解績效。

關鍵字

模擬退火法；回溯近似法；隨機搜尋法；隨機比較；離散型模擬最佳化

並列摘要

We consider the discrete 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 by simulation experiments. Such problems occur in system design. The decision variables are system parameter values to be determined and the objective function value is the associate system cost. The optimization problem is to find the system parameter values that minimize the system cost under certain constraints. Applications of discrete stochastic optimization include the network design, supply chains design, scheduling, and inventory control. Several methods have been developed for discrete simulation optimization problems. Depending on the number of decision variables, there are two branches: (i)infinite or many, and (ii) finite but a few. This research considers only the first branch. Available algorithms include heuristic methods (e.g., simulated annealing, tabu search, and genetic algorithm), random search methods (e.g., pure random search and stochastic ruler), and sample path methods. The existing methods usually use a big sample size to make the sample-path problem mimics the real problem. The disadvantage is that each function evaluation takes a long computation time and hence decreases the algorithm efficiency. We propose the SADRA algorithm for solving discrete simulation optimization problems. SADRA uses the DRA (dependent retrospective approximation) idea to iteratively solve a sequence of sample-path problems with increasing sample size. Each sample-path problem is then solved by the heuristic SA (simulated annealing) algorithm. Simulation experiments are run to evaluate the performance of SADRA and compare it to four existing algorithms. The algorithm performance measures used are the mean square error MSEf in function values and the convergent path (i.e., the percentage of replications that converge). A smaller MSEf and a big CP are preferred. Our simulation results show that SADRA converges and converges faster than the four existing algorithms. The sensitivity analysis is also conducted to study the influence of algorithm parameters to the algorithm performance. Simulation results show that a smaller neighborhood structure (for simulated annealing) works better when the objective function is smooth and has only one optimal point. A random neighborhood strategy works better when many local optima exist.

並列關鍵字

Discr ； Simulated Annealing ； Retrospective Approximation

參考文獻

Chung Li, 320, Taiwan.

LIST OF REFERENCES

[1] Alander, J. T. (1992). On optimal population size of genetic algorithms. Proc.

with Constant Temperature for Discrete Stochastic Optimization. Management

Ruler Method for Discrete Stochastic Optimization. European Journal of Operation

國際替代計量

模擬退火法應用在離散型模擬最佳化問題上

未授權

主題瀏覽