求解双层CARP优化问题的知识型遗传算法  

Knowledge-based genetic algorithm to the double layer capacitated arc routing problems

作　　者：姚锋[1] 邢立宁[1] 李菊芳[1] 贺仁杰[1] 陈英武[1] 

机构地区：[1]国防科技大学信息系统与管理学院管理系,长沙410073

出　　处：《系统工程理论与实践》2014年第1期239-247,共9页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金重点项目(71031007);国家自然科学基金(71101150;70971131;71071156;70901074)

摘　　要：双层CARP优化问题首先考虑物流系统的宏观配置问题,然后考虑相关服务的完成问题.提出了一种求解双层CARP优化问题的知识型遗传算法:采用两种扩展启发式方法来辅助生成初始种群;基于算子绩效知识为每次选择、交叉和变异操作选择合适的操作算子;基于弧段顺序知识为每次交叉和变异操作选择合适的断点位置;采用局部替换程序不断向当前种群中注入新个体.实验结果表明,知识型遗传算法在优化性能方面优于其他几种方法.In double-layer capacitated arc routing problems （DCARP）, both the high-level configura- tion problem and the low-level service problem are considered. In the proposed knowledge-based genetic algorithm （KGA）, two extended heuristic approaches are applied to produce initial individuals, the perfor- mance knowledge of operators is applied to determine an appropriate operator for each selection, crossover and mutation, the arc priority knowledge is employed to decide a suitable broken position for operations of crossover and mutation, and the partial replacement procedure is implemented to maintain population diversity. Experimental results suggest that KGA outperforms other methods.

关 键 词：组合优化 弧段顺序知识 算子绩效知识 宏观配置优化 遗传算法 

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