基于回溯和分解的Memetic算法求解限量弧路由问题

作     者：都炳琪 

作者单位：西安电子科技大学 

学位级别：硕士

导师姓名：尚荣华

授予年度：2017年

学科分类：08[工学] 081104[工学-模式识别与智能系统] 0811[工学-控制科学与工程] 

主      题：回溯法 分解策略 蚁群算法 回路调整 扩展搜索 

摘      要：限量弧路由问题（Capacitated Arc Routing Problem,CARP）是组合优化领域中一个经典的NP难问题,由于其在生活中有着广泛的应用,近年来得到了很多学者的持续关注。现实生活中的街道垃圾收集,运输路径规划,能源线路的检查,输油通路的检查和更换等,都是在有容量约束的前提下寻找总消耗最小的最优路径,都属于限量弧路由问题。近年来,很多研究方法都被提出用来解决该组合优化问题,但是随着大数据时代的到来,问题的规模都变得很大,很多针对中小规模的算法都不再适应,本文采用问题分解的策略,将大规模问题分解为很多小规模问题,将多目标问题分解成一系列单目标问题从而进行求解。然后,现有算法对问题初始解的要求比较高,从而影响了算法的稳定性。蚁群算法具有鲁棒性强,对初始解的要求不高的特点,有较强的全局搜索能力,比较适用于图中的路径搜索优化问题。另外,本文还设计了适合该问题的回路调整算子,扩展搜索算子以及精英保存策略来提高算法寻优质量。本文主要工作如下:（1）对于单目标大规模CARP,有学者最近提出了基于路线距离分组的协同进化算法（RDG-MAENS）并极具竞争性,但是该算法在问题分解上不合理,使得搜索资源分配不均,容易陷入局部最优。同时,在对子问题进行求解的过程中,RDG-MAENS采用随机选择算子挑选种群中的个体作为父代,从而产生新的子代个体,虽然在一定程度上保持了解的多样性,但是收敛速度很慢。对此,本文提出了基于路由距离分组和回溯的分解策略（RBD-MANES）,实验结果表明:与RDG-MANES相比RBD-MAENS算法具有一定的竞争性。（2）针对RDG-MAENS对初始解要求过高从而导致的算法稳定性差以及寻优质量不高的问题,本文提出了一种基于排序蚁群算法的分解策略用于求解大规模限量弧路由问题（RDAC）。在本文中,利用基于排序的蚁群算法对限量弧路由问题进行求解,同时对求解过程中的信息素更新方式进行了改进,从而产生质量较高的初始解,减少了RDAC对初始解的依赖性,增强了算法的稳定性。其次,本文将分解策略引入进来,通过把问题分解成几个规模更小的子问题并且实现子问题间的信息交流,从而在巨大的解空间中实现更有效的搜索,提高了算法的搜索效率并使之适用于求解大规模问题。最后,本文在局部搜索中加入了一种回路调整算子来对解的质量进行进一步的改善,从而提高了算法的寻优能力。（3）对于多目标大规模CARP,本文提出了一种基于扩展搜索和问题分解的Memetic算法（ED-MAENS）。首先,通过加权和的方法将多目标问题分解为多个单目标问题。然后,为每个单目标子问题分配代表解,为保证每个子问题都能分配得到一个比较合适的代表解,本文引入了等级的概念,对所有候选解根据两个目标函数值进行优先级的排序。之后,对每个子问题,结合其邻域子问题的信息,利用MAENS算法进行全局和局部搜索。最后,本文还加入一种扩展搜索算子,扩大对多目标解空间的搜索来提高解的质量。实验证明,与对比算法相比,ED-MAENS十分适合求解MO-CARP。