運用OCBA法改善求解隨機性專案網路最佳化資源分配問題之研究

Abstract

根據專案需求而做調整之複合性專案網路資源分配問題(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 .