結合差分進化演算法與最佳計算資源分配於大規模隨機問題最佳化之研究

An Improved Differential Evolution Algorithm with Optimal Computing Budget Allocation to Efficiently Solve Large Stochasitc Optimization Problems

王弘道(Hung-Dow Wang)

指導教授 ： 任恒毅

元智大學/工程學院/工業工程與管理學系/碩士(2012年)

https://doi.org/10.6838/YZU.2012.00286

摘要

差分進化演算法(Differential Evolution, DE)屬於啟發式演算法之一類，具備結構簡單以及所需設定參數較少等特性，並被廣泛地應用於求解最佳化問題。DE在求解大規模隨機問題，如大型投資組合最佳化問題，仍有弱點，如目標函數有雜訊時，收斂情形的不穩定，以及需要使用大量的迭代以找到近似最佳解，這導致差分演算法之效能與效率有所限制。最佳計算資源分配 (Optimal Computing Budget Allocation, OCBA)則是一種可以在給定計算資源條件(如時間)下，找到最佳的計算資源分配方法，使得正確選擇最佳方案的機率最大化。OCBA動態分配較多部分的計算資源分配於較佳的設計方案。如此可以在同樣的精度要求下有效地減少模擬的次數。本研究以DE為基礎，結合最佳計算資源分配 (Optimal Computing Budget Allocation, OCBA)，透過設計一個整合OCBA與DE的演算法，擷取個別算法的優點，彼此互補，能夠快速有效率地處理大規模隨機型問題，並找出近似最佳解。將所開發之新演算法，透過一簡單之實例與一大型投資組合最佳化案例問題，就所得出結果與DE進行效率與效能之比較與分析。本研究經數值測試，發現不論在簡單實例或是大型投資組合案例問題，每一個世代的個體若先進行DE，再進行OCBA的結合方式，相較於傳統DE，能夠以更少的迭代數，更有效率的找出近似最佳解。

關鍵字

差分進化演算法 ； 最佳計算資源分配 ； 大型投資組合最佳化

並列摘要

Differential Evolution (DE) is one of optimization heuristics developed in recent years. DE is widely used in solving optimization problems because DE has simple structure as well as only needs to configure fewer parameters. However, when using DE to solve large-scale stochastic problems, i.e. large asset portfolio optimization problems, it has unstable convergence when the noise is high; and it requires large iterations to approximate optimal solutions. Thus the effectiveness and efficiency of DE is limited. Optimal Computing Budget Allocation (OCBA) is a smart method to allocate finite resources to find promising designs/solutions with high probability of correct selection. OCBA dynamically allocate more resources to currently better designs/solutions and less resourse to inferior ones. Thus total simulation replications can be reduced while at the same time the required precision of better designs can be achieved. This study tried to improve DE by using OCBA in its iterations to effectively improve the population quality and to find near optimal solutions more efficiently. The DE improvement scheme was then tested with one simple case and a large asset portfolio optimization problem given by DEoptim package. The numerical experiments showed that performing first DE steps then OCBA can achieve almost equal results with fewer iterations, therefore a better efficiency.

並列關鍵字

DE ； OCBA ； Large complex problems ； Optimization

參考文獻

李維平, 江長育, et al. (2011). "搭配擾動策略之差分演化演算法." 資訊科技國際期刊 5(1): 24-39.

Bechhofer, R. E., T. J. Santner, et al. (1995). Design and analysis of experiments for statistical selection, screening, and multiple comparisons, Wiley New York, NY.

Boudt, K., P. Carl, et al. (2010). "Portfolio optimization with conditional value-at-risk budgets." Status: published.

Chen, C. and L. H. Lee (2010). Stochastic simulation optimization: an optimal computing budget allocation, World Scientific Pub Co Inc.

Chen, C. H. (1996). "A lower bound for the correct subset-selection probability and its application to discrete-event system simulations." Automatic Control, IEEE Transactions on 41(8): 1227-1231.