標題: 運用OCBA法改善求解隨機性專案網路最佳化資源分配問題之研究
Solving the Optimal Resource Allocation Problem in Stochastic Activity Networks Using an Optimal Computing Budget Allocation Approach
作者: 朱怡樺
Chu, Yi-Hua
姚銘忠
林仁彥
Yao, Ming-Jong
Lin, Jen-Yen
運輸與物流管理學系
關鍵字: 專案網路;資源分配;基因演算法;蒙地卡羅模擬法;最佳模擬預算分配法;Activity networks;Resource Allocation;Genetic Algorithm;Monte Carlo Simulation;Optimal Computing Budget Allocation Approach
公開日期: 2010
摘要: 根據專案需求而做調整之複合性專案網路資源分配問題(Stochastic Adaptive Resource Allocation in Multimodal Activity networks Problem, SRAMAP) 多年來已被廣泛的研究。並且許多學者提出相當多不同的解法,例如:動態規劃法(dynamic programming, DP)、蒙地卡羅模擬法(Monte Carlo simulations, MCS)、基因演算法(genetic algorithm, GA)等。而蒙地卡羅模擬法為一種經常使用於搜尋評估候選解的方法,但由於其收斂速率相當慢且相當耗時,特別是針對大規模之專案網路問題時,MCS相當無效率且存在大量的計算負擔。在本研究中,我們建議並提出一套結合基因演算法、蒙地卡羅模擬法與最佳模擬預算分配法(Optimal Computing Budget Allocation, OCBA)之演算法,期望能改善求解SRAMAP問題之效率與效益。在演化過程中,根據所產生的染色體之評估適應值,我們使用OCBA法進行MCS最佳預算分配。根據本研究隨機產生之數值測試實驗,本研究證明結合基因演算法、蒙地卡羅模擬法與最佳模擬預算分配法之演算法比傳統的基因演算法或者是蒙地卡羅模擬法更具有效益。
The Stochastic Adaptive Resource Allocation in Multimodal Activity networks Problem (SRAMAP) has been studied for more than a decade. Researchers proposed different solution approaches, including dynamic programming, Monte Carlo simulations (MCS), genetic algorithm, etc., for solving the SRAMAP. Monte Carlo simulations (MCS), which are commonly employed for evaluating the obtained candidate solutions, make the solution approaches unattractive, especially for large-size problems because of its demanding computational load. In this study, we propose to a hybrid genetic algorithm (GA) with the Optimal Computing Budget Allocation (OCBA) Approach to improve for solving the SRAMAP. We utilize the OCBA approach for optimally allocating the computational budget for MCS as evaluating the fitness of the chromosomes in the evolutionary process. Based on our numerical experiments using randomly generated instances, we demonstrate the proposed GA with MCS and OCBA is more effective than the conventional GA or MCS .
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT079832534
http://hdl.handle.net/11536/47844
Appears in Collections:Thesis