求解双层CARP优化问题的演化学习型遗传算法

Learnable genetic algorithm to double-layer CARP optimization problems

双层有能力约束的弧路径优化问题(capacitated arc routing problem,CARP)的研究对象通常是某个城市或地区,首先聚焦于该地物流系统的宏观配置,然后考虑相关服务的完成问题。针对双层CARP优化问题,提出了一种演化学习型遗传算法(learnable genetic algorithm,LGA)。建立了LGA的基本框架,设计了构件知识和算子知识等知识形式。在LGA中,采用扩展启发式方法辅助生成初始种群,使用算子知识为选择、交叉和变异选择操作算子,应用构件知识为交叉和变异操作选择断点位置,同时借助局部替换程序不断地向当前种群中注入新个体。LGA的框架为现有优化方法改进提供了一种有益借鉴。

In double-layer capacitated arc routing problems （CARP）, both the high-level configuration problem and the low-level service problem are considered as optimization objects. Aiming to the double-layer CARP problems, a learnable genetic algorithm （LGA） is proposed. The basic architecture of LGA is constructed, and two different forms of knowledge are designed to provide an important foundation for the LGA. In LGA, two extended heuristic approaches are employed to generate initial populations, the performance knowledge of operators is used to select a proper operator for the selection, crossover and mutation, the component knowledge is employed to select a proper breakpoint location for each crossover and mutation, and the partial replacement procedure is used to maintain population diversity. To validate the performance of LGA, 24 benchmark problems are solved by LGA and some extended heuristic methods. The LGA architecture will act as a helpful reference to the improvement of optimization approaches.