A Multi-Objective Evolutionary Algorithm for Simulation Optimization of Production and Inventory Control Problems

[[abstract]]隨著資訊科技的進步，系統模擬已經成為各領域廣泛使用的分析工具，但是 傳統的看法認為模擬適用於比較數個系統的優劣，無法像數學規劃一樣進行系統 最佳化。近年來，不少學者倡議結合模擬與最佳化演算法，也有軟體公司推出最 佳化軟體如OptQuest，提供完整的研究工具。雖然現有文獻已針對確定性 (deterministic)問題發展出各種多目標最佳化的演算法，但是極少有研究探討如何 應用模擬求解多目標的最佳化問題。因為利用模擬最佳化，需要大量的運算時間， 加上模擬實驗的結果具有隨機誤差，造成評比多個績效指標的困難度，甚至影響 求解的品質與效率，這是確定性的多目標最佳化問題不會遭遇的問題。 本研究發展能快速收斂且適合模擬實驗的多目標演算法，鑑於演化式演算法 可以同時建構多個解，並可一次獲得多個非凌駕解，因此成為本研究的主要架構。 演算法採用隨機或Latin-Hypercube Sampling (LHS)的方式選取起始解集合，參考 數種多目標演化式演算法(VEGA, NSGA-II)的優點，簡化運算步驟，同時達成快 速收歛。演算法並採用scatter search 的交配方式以保持解的多元性，判定非凌駕 解與比較各個解的優劣時，也考慮到模擬結果的隨機誤差。實驗結果發現本演算 法應用在不同類型的數學式與模擬問題都可以快速收歛；使用Diversity reference set 可以解決找不出某些端點或分部不均勻的情形並提升召回率與正確率；在誤差 幅度變大時，不影響搜尋非凌駕解的收斂情形。[[abstract]]As the technology of computer hardware and software advances, simulation becomes a powerful tool for performance evaluation, but not suitable for optimization. In recent years, researchers have attempted to combine simulation and optimization procedures to provide a complete solution. Some commercial software provides built-in optimization packages based on these research ideas, but none is capable of handling multi-objective problems. Although there is abundant literature on deterministic optimization, simulation optimization is quite different because the computation is time-consuming and the estimation is still subject to random errors. This research proposes an evolutionary algorithm for multi-objective optimization based on simulation experiment. The algorithm uses random search or Latin-Hypercube Sampling to select the initial population, generates a mating pool for each objective, uses interpolation and extrapolation operators to create the offspring population, and updates the non-dominance set iteratively to estimate the Pareto-optimal front of the multi-objective optimization problem. Some of its properties are adapted from well-known algorithms such as VEGA, NSGA-II, and scatter search. The final results found the algorithm speed up the convergence of Pareto-optimal set and accommodate random errors of simulation experiment. Using diversity reference set improves to search the extreme solutions and gets higher recall rate and precision rate than without using diversity reference set