上海交通大学学报

上海交通大学学报（自然版） ›› 2013, Vol. 47 ›› Issue (04): 619-625.

• 自动化技术、计算机技术 • 上一篇    下一篇

加强的混合遗传算法求解能力约束弧路径问题

 刘天堂, 江志斌, 胡鸿韬, 刘冉   

  1. (上海交通大学 机械与动力工程学院, 上海 200240)  
  • 收稿日期:2011-12-07 出版日期:2013-04-28 发布日期:2013-04-28
  • 基金资助:

    国家自然科学基金资助项目(70872077),国家自然科学基金国际(地区)合作交流项目(70831160527)

     

An Enhanced Hybrid Genetic Algorithm for the Capacitated Arc Routing Problem  

 LIU  Tian-Tang, JIANG  Zhi-Bin, HU  Hong-Tao, LIU  Ran   

  1. (School of Mechanical Engineering, Shanghai Jiaotong University, Shanghai 200240, China)
  • Received:2011-12-07 Online:2013-04-28 Published:2013-04-28

摘要： 为了在可接受的时间里求解具有NP-hard性质的能力约束弧路径问题(CARP)，提出了加强的混合遗传算法(EHGA). 该算法是在遗传算法框架里嵌入加强的局域搜索算子来强化搜索，充分发挥了遗传算法的全局搜索能力和加强的局域搜索算子的局域搜索能力. 同时，在进行种群替代时，二元锦标赛替代被提出，并使用了种群管理来保持种群的多样性.测试了标准CARP算例，并给出了算法效果比较. 结果表明，加强的混合遗传算法胜出一般的Memetic算法，是有效的求解CARP的方法.   

关键词: 能力约束弧路径问题, 元启发式算法, 混合遗传算法, 二元锦标赛替代

Abstract: In order to solve the NP-hard capacitated arc routing problem (CARP) in acceptable time, an enhance hybrid genetic algorithm (EHGA) was proposed. The enhanced local search (ELS) was used within a genetic algorithm (GA) framework to intensify the search. Binary tournament replacement and population management strategy were proposed when population was updated. The CARP benchmark instances were tested. The results show that EHGA outperforms memetic algorithm (MA), and is effective to solve the CARP.  

Key words: capacitated arc routing problem (CARP), metaheuristic; , hybrid genetic algorithm, binary tournament replacement

中图分类号: