摘要:
针对大规模资源受限项目调度问题计算复杂的特点,提出一种合作式协同进化分布估计算法(CCEDA)。将合作式协同进化框架与分布估计算法相结合,将复杂问题分解为子问题,利用改进的分布估计算法对每个子问题进行协同优化求解。为提高分布估计算法的局部搜索能力,给出一种对解进行局部搜索的方法。将CCEDA用于求解标准问题库PSPLIB,并与GAPS、GA-DBH、GA-hybrid与GA-FBI算法进行比较,结果证明CCEDA拥有更好的求解性能。
关键词:
资源受限项目调度问题,
项目调度,
分解策略,
协同进化,
分布估计算法,
合作式协同进化分布估计算法
Abstract:
This paper presents Cooperative Coevolutionary Estimation of Distribution Algorithm(CCEDA) to solve Resource-constrained Project Scheduling Problem(RCPSP). It integrates the cooperative co-evolutionary framework and Estimation of Distribution Algorithm(EDA), decomposes RCPSP into several sub-problems, and then applies improved EDA to cooperatively solve these sub-problems. In order to enhance the local search ability of EDA, it gives a local search method for solutions. CCEDA is compared with GAPS, GA-DBH, GA-hybrid and GA-FBI, and experimental results on PSPLIB prove that CCEDA has better performance.
Key words:
Resource-constrained Project Scheduling Problem(RCPSP),
project scheduling,
decomposition strategy,
coevolutionary,
Estimation of Distribution Algorithm(EDA),
Cooperative Coevolutionary Estimation of Distribution Algorithm(CCEDA)
中图分类号:
陈旺, 史彦军, 滕弘飞. 一种求解RCPSP的协同进化分布估计算法[J]. 计算机工程, 2011, 37(14): 134-136.
CHEN Wang, SHI Pan-Jun, TENG Hong-Fei. Coevolutionary Estimation of Distribution Algorithm for Solving Resource-constrained Project Scheduling Problem[J]. Computer Engineering, 2011, 37(14): 134-136.