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

An Enhanced Hybrid Genetic Algorithm for the Capacitated Arc Routing Problem

作　　者：刘天堂[1] 江志斌[1] 胡鸿韬[1] 刘冉[1] 

机构地区：[1]上海交通大学机械与动力工程学院,上海200240

出　　处：《上海交通大学学报》2013年第4期619-625,共7页Journal of Shanghai Jiaotong University

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

摘　　要：为了在可接受的时间里求解具有NP-hard性质的能力约束弧路径问题(CARP),提出了加强的混合遗传算法(EHGA).该算法是在遗传算法框架里嵌入加强的局域搜索算子来强化搜索,充分发挥了遗传算法的全局搜索能力和加强的局域搜索算子的局域搜索能力.同时,在进行种群替代时,二元锦标赛替代被提出,并使用了种群管理来保持种群的多样性.测试了标准CARP算例,并给出了算法效果比较.结果表明,加强的混合遗传算法胜出一般的Memetic算法,是有效的求解CARP的方法.In order to solve the NP-hard capacitated arc routing problem （CARP） in acceptable time, an en hance 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 popula tion 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.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]