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

An Enhanced Hybrid Genetic Algorithm for the Capacitated Arc Routing Problem

为了在可接受的时间里求解具有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.