作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2011, Vol. 37 ›› Issue (14): 134-136. doi: 10.3969/j.issn.1000-3428.2011.14.044

• 人工智能及识别技术 • 上一篇    下一篇

一种求解RCPSP的协同进化分布估计算法

陈 旺,史彦军,滕弘飞   

  1. (大连理工大学机械工程学院,辽宁 大连 116023)
  • 收稿日期:2010-12-29 出版日期:2011-07-20 发布日期:2011-07-20
  • 作者简介:陈 旺(1983-),男,博士研究生,主研方向:智能优化算法,机械产品设计与流程规划;史彦军,讲师、博士;滕弘飞,教授、博士生导师
  • 基金资助:

    国家自然科学基金资助项目(60674078, 50975039)

Coevolutionary Estimation of Distribution Algorithm for Solving Resource-constrained Project Scheduling Problem

CHEN Wang, SHI Yan-jun, TENG Hong-fei   

  1. (School of Mechanical Engineering, Dalian University of Technology, Dalian 116023, China)
  • Received:2010-12-29 Online:2011-07-20 Published:2011-07-20

摘要:

针对大规模资源受限项目调度问题计算复杂的特点,提出一种合作式协同进化分布估计算法(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)

中图分类号: