模擬最佳化演算法則的研擬與軟體製作(I)

Abstract

模擬最佳化(Simulation optimization)是最佳化方法領域中最新的發展，模擬最佳 化問題主要是指對任一個input variable setting 的objective function 的evaluation 都須利用模擬(simulation)的方法來求得，所以我們無法以傳統最佳化方法解決此類型的 的問題。此類問題涵蓋的範圍甚廣，如一些具有廣大輸入變數空間(huge input-variable space) 的隨機模擬最佳化問題(stochastic simulation optimization problem)，大型系 統中具有決策變數與discrete variable 的最佳化問題等等。 本計劃擬針對一些模擬最佳化問題加以歸類，並針對所歸納出的類型問題提出模擬最 佳化的演算法則，基本上在模擬最佳化問題中，其結構資訊(structural information)很 難用解析的方法萃取(extract)出來，所以我們所提出的模擬最佳化方法即以模擬 (simulation)做為萃取系統的結構資訊的手段，然後以所萃取的結構資訊作為縮小搜尋範 圍的依據。如此迭代進行，將可得到一個不錯的解。 我們將以序的最佳化理論(ordinal optimization theory)來證明我們所得的解是不 錯的解。 除此之外我們將以基因演算法(genetic algorithm)，模擬退火法(simulated annealing)，以及塔布搜尋法(tabu search)等常被用來解模擬最佳化問題的方法來解我們 所提出的類型的問題並比較所得的結果，以及所花費的計算時間及實用性。 演算法研擬完成且經完善的電腦模擬驗證後，我們將製作成軟體以提供更廣大的用途。