Kriging and Constraint Handling for Multi-Objective Simulation Optimization(I)

[[abstract]]近年來，演化式演算法已經成為求解多目標最佳化問題相當有效的方法，但是如果目標函數是經由模擬實驗所估算，由於模擬的運算耗時以及隨機誤差的干擾，演化式演算法可能會因速度緩慢或不夠精確而失去實用性。因此，模擬最佳化的主要挑戰是在於如何兼顧模擬實驗的準確度以及演算法的搜尋過程。目前相關的研究集中於單目標的模擬最佳化問題，本人目前執行的計畫已發展出一個注重效率的雙目標演化式演算法，主要特色為產生子代後可運用篩選機制略過缺乏潛力的解而不進行模擬，另一個重點在於實施兩階段的模擬實驗過程，演算法比較第一階段的模擬結果並淘汰明顯較差的解，只模擬存活的較佳解以節省運算時間。現有的實驗結果顯示以上做法確實可在不犧牲求解品質的前提下加速求解過程。本計畫將延續現有研究的方向，並且將改進下列幾點。首先是以距離為基礎的篩選機制可能在中高維度空間或是離散決策變數時無法有效運用。其次，兩階段的模擬實驗雖然改善了收斂性，卻無法兼顧多元性。最後，可嘗試運用部分違反績效限制的解來引導演算法的搜尋方向。因此，本計畫擬定下列研究項目。第一、運用克利金(Kriging)方法與現有數據建構預測模式，對產生的子代解進行預測，以便篩選出較具潛力的解來進行模擬評估。第二、根據競賽方式發展出適用於模擬最佳化問題之限制式處理方法(constraint handling)，使演算法能產生更接近效率邊緣的子代解。第三、修改兩階段模擬實驗，兼顧子代解的品質與多元性。上述的研究構想更可以與其他型態的最佳化演算法結合。本計畫若能順利完成，將能協助解決模擬最佳化的一大障礙，使模擬成為更有力之應用工具。[[abstract]]Evolutionary algorithms have been extensively tested and display quite effective results in solving multi-objective optimization algorithms. However, applying evolutionary algorithms to simulation optimization problems is difficult because it can be very expensive or time-consuming to perform thousands of functional evaluations via simulation runs. What makes optimization via simulation challenging is how to allocate the simulation time used in estimating the objective function and the computational effort used for searching promising solutions. Most studies focus on single objective simulation optimization. Our current research has developed a bi-objective algorithm which uses a filtering mechanism to screen out less promising offspring solutions before they are evaluated via simulation runs. The algorithm also employs a two-stage procedure for simulation evaluation. Uncompetitive solutions are screened out after the first stage to save computation time. Experimental results suggest that these features can speed up the algorithm significantly without compromising quality of solutions. This project will continue our current research. Based on the feedback we have received in the conferences, we recognize that the performance of the algorithm can be improved in several ways. First of all, the filtering based on shortest distance to current non-dominance set may be less reliable for higher dimensional spaces or discrete decision variables. Secondly, the two-stage procedure improves the convergence but not the diversity of the Pareto set. Last but not least, we feel that solutions that violate performance constraints can be utilized to guide the search direction to improve the performance of the algorithm. Therefore, this project proposes (1) to develop a new filtering mechanism based on Kriging which is a prediction model based on observations currently available, (2) to develop a constraint handling method based on tournament approach to select and utilize solutions that slightly violate performance constraints to generate offspring solutions closer to the efficiency frontier, and (3) to revise the two-stage simulation procedure to maintain the balance between proximity and diversity so that the algorithm can converge faster with more diverse Pareto solutions. These features can be implemented in other types of optimization algorithms. We hope that completion of this project can help overcoming a big obstacle of multi-objective simulation optimization[[note]]NSC98-2221-E327-02