基于降阶和定向进化的限量弧路由问题研究

摘要

限量弧路由问题(CARP)是经典的组合优化问题之一，在实际生活中有非常广泛的应用，例如：城市垃圾清理，冬季撒盐除雪、校车调度和信件投递等。因此，很多研究学者越来越关注该类实际应用问题。针对中小规模的限量弧路由问题，相关研究学者目前已经提出了一些算法进行有效地解决。但随着21世纪信息网络的不断扩大，对中小规模问题的研究远远不能满足我们实际的需要，研究学者开始把目光转移到大规模限量弧路由问题的研究上。然而，大规模限量弧路由有更高的复杂度，现有的算法很难在有限的时间内找到全局最优解。基于对这种情况的考虑，我们解决大规模优化问题的核心思想是降阶，从而降低问题的复杂度，且免疫克隆算法等是高度进化的并行算法，因此，我们考虑利用基于降阶和定向进化的算法用于求解大规模限量弧路由问题。本文的主要工作如下：
　　1)针对单目标的大规模限量弧路由问题，梅一等最近提出了基于回路距离分组的合作协同进化算法(RDG-MAENS)并取得了很好的结果，但在产生子种群的变异机制和后代解的更新替换两方面仍有不足。首先，RDG-MAENS算法采用了小概率0.2进行变异操作来改变搜索区域，以利于跳出局部最优进行广度搜索。而对于大规模CARP，小概率变异很容易使问题陷入局部最优。其次，RDG-MAENS算法是选择迭代前种群中的个体为父代然后进行交叉变异得到子种群的，不能保证种群的多样性，容易陷入局部最优解。改进后算法IRDG-MAENS针对以上两点不足进行了改进，实验结果表明，改进后算法较RDG-MAENS有更好的结果。
　　2)针对多目标的大规模限量弧路由问题，我们提出了基于定向进化的免疫克隆算法(DE-ICA)。该算法整体应用了免疫克隆的算法框架，并在初始化过程中扩大了种群的规模，以利于提高解的质量从而找到更优的非支配解。其次，DE-ICA算法在免疫基因操作过程中结合了分解策略以利于种群邻域之间信息的共享，使算法快速收敛到理想解。最后，DE-ICA算法利用一种全新的对比算子按照一定原则来选出优秀个体并将这些个体作为进行下一次进化迭代的候选初始解，使算法一直按照选择设定的方向不断优化，从而收敛到更优的非支配解。实验结果表明，DE-ICA算法在大规模测试集EGL-G的全部实例上获得的解都可以支配其它算法获得的解集。
　　3)针对多目标的大规模限量弧路由问题，我们提出了基于降阶和分解的遗传算法(RDGA)。RDGA算法首先借鉴了RDG-MAENS中的协同进化算法作为降阶算子，根据回路距离相近的原则将大规模的MO-CARP问题分解为几个小规模的MO-CARP，从而降低求解问题的规模和复杂度。其次，针对每个小规模的MO-CARP子问题，RDGA采用了基于问题分解的策略，根据一定的规则将每个多目标的子问题分解为多个单目标的子问题，再利用遗传算法来求解每个单目标子问题从而求得整个子问题的解。再次，RDGA采用了一种多保留策略来保存进化过程中的解以保持解的多样性并防止优质解的丢失。实验结果表明，针对大规模的多目标限量弧路由问题，RDGA在获得优质解方面较其它算法有强大的竞争力。

目录

封面

声明

中文摘要

英文摘要

插图索引

表格索引

符号对照表

缩略语对照表

目录

第一章 绪论

1.1限量弧路由问题概述

1.2限量弧路由问题的研究现状

1.3论文内容和安排

第二章 改进的RDG-MAENS算法用于求解单目标大规模限量弧路由问题

2.1引言

2.2单目标限量弧路由问题的数学模型

2.3 RDG-MAENS算法简介

2.4改进的RDG-MAENS算法用于求解大规模限量弧路由问题

2.5实验结果及分析

2.6本章小结

第三章 基于定向进化的免疫克隆算法用于求解多目标大规模限量弧路由问题

3.1引言

3.2多目标限量弧路由问题

3.3基于定向进化的免疫克隆算法用于求解多目标大规模限量弧路由问题

3.4实验结果及分析

3.5本章小结

第四章 基于降阶和分解的遗传算法用于求解多目标大规模限量弧路由问题

4.1引言

4.2基于降阶和分解的遗传算法用于求解多目标大规模限量弧路由问题

4.3实验结果及分析

4.4本章小结

第五章 总结与展望

5.1本文总结

5.2课题展望

参考文献

致谢

作者简介