基于模因演化算法的有限容量弧路径问题研究

发布时间：2017-03-19 10:03

  本文关键词：基于模因演化算法的有限容量弧路径问题研究，由笔耕文化传播整理发布。

【摘要】：有限容量弧路径问题(Capacitated Arc Routing Problem, CARP)是一个经典的带有约束条件的组合优化问题,在现实生活中有非常广泛的应用,如城市道路撒盐与洒水路径规划,垃圾回收线路规划,物流配送网络优化,输气、输电线路检修规划等等,因此也得到了许多研究者的关注。由于该问题是NP-hard问题,对于精确算法,要在可接受的时间内得到问题的最优解是非常困难的,并且计算成本非常之大。因此,本文旨在利用元启发式方法在给定时间内取得性能更优的次优解,为有限容量弧路径问题提供更加有效实用的解决方案。首先,本文以目前求解CARP较为领先的算法—基于扩展邻域搜索的模因演化算法(MAENS)为基础算法,提出了三种改进方法,即(1)使用锦标赛选择算子筛选父代(MAENS-T);(2)基于个体适应度的自适应搜索概率(MAENS-Pls);(3)基于动态参数的随机排序算法(MAENS-Pf)，结合三种改进方法,形成了本文所提出的基于自适应扩展邻域搜索的模因演化算法(MAENS-C)，，然后利用C语言编程实现算法,并采用研究领域内的通用测试集—Egl数据集中的三个实例对三种改进算法分别进行测试,证明了本文所设计算法的有效性。其次,针对设计的各版本算法中包含的参数,利用统计赛车技术(Racing Algorithm)与统计检验中的非参数检验方法对所有算法在全部的实验用例上(Egl数据集的八个实验用例)进行了参数优化,大大节省了参数优化的计算成本,最终得到了各算法的优化参数组合,为算法评价、应用奠定了基础。再次,基于改进算法与其相应的优化参数组合,利用平均总成本,收敛可靠性,全局寻优能力,鲁棒稳定性,以及时间复杂度五个评价指标,在Egl数据集的八个实例上进行了定量与定性的算法评价。本文主要从相同演化代数和相同时间复杂度水平两个角度进行了比较总结,得出了MAENS-Pls以及三种改进方法的结合算法MAENS-C显著的优于基础算法MAENS,并且发现了13个针对CARP问题的新型最优解,进一步验证了本文提出的算法能有效地对局部搜索频率与深度进行双重优化,证明了算法的优异性能。最后,将本文的理论研究成果应用于路径规划实例中,利用英国兰开夏郡Egl数据集的路径服务需求与地理信息,对兰开夏郡的路网进行了实例验证,为路径规划与车辆分配提供了优化的规划方案,并进行了优化解的可视化呈现,为交通领域内的路径规划提供了有效的解决方案。
【关键词】：有限容量弧路径问题 模因演化算法 扩展邻域搜索 自适应局部搜索频率与深度 动态随机排序算法 算法鲁棒性优化 解的可视化
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：U116
【目录】：

• 致谢5-6
• 摘要6-7
• ABSTRACT7-13
• 1 引言13-21
• 1.1 问题概述14
• 1.2 研究现状14-19
• 1.2.1 构造型启发式算法15-16
• 1.2.2 元启发式算法16-17
• 1.2.3 模因演化算法17-18
• 1.2.4 算法评估18-19
• 1.3 研究思路与论文结构19-21
• 2 有限容量弧路径问题模型与算法21-34
• 2.1 有限容量弧路径问题模型定义21-23
• 2.2 模因演化算法框架23-24
• 2.3 基于扩展邻域搜索的模因演化算法24-34
• 2.3.1 处理约束条件24-27
• 2.3.2 算法的搜索能力27-30
• 2.3.3 基于扩展邻域搜索的模因演化算法30-33
• 2.3.4 当前算法缺陷分析33-34
• 3 基于自适应扩展邻域搜索的模因演化算法设计34-43
• 3.1 基于锦标赛选择机制的父代选择算子34
• 3.2 基于个体适应度的自适应局部搜索概率34-36
• 3.2.1 递增式局部搜索概率34-35
• 3.2.2 递减式局部搜索概率35-36
• 3.3 基于动态参数的随机排序算法36-37
• 3.4 算法实现与测试37-38
• 3.5 结果与讨论38-43
• 4 基于统计赛车技术的参数优化43-52
• 4.1 参数优化方法论43-44
• 4.2 MAENS-PF的参数优化44-46
• 4.2.1 参数设定44-45
• 4.2.2 实验及结果分析45-46
• 4.3 MAENS-PLS的参数优化46-48
• 4.3.1 参数设定46-47
• 4.3.2 实验及结果分析47-48
• 4.4 MAENS-C的参数优化48-49
• 4.4.1 参数设定48-49
• 4.4.2 实验及结果分析49
• 4.5 MAENS的参数优化49-50
• 4.6 结果与讨论50-52
• 5 算法评价与比较52-62
• 5.1 实验分析52-56
• 5.2 统计方法分析56-58
• 5.3 结果与讨论58-62
• 6 算法求解路径优化方案实例62-68
• 6.1 英国兰开夏郡实例信息62-64
• 6.2 路径优化方案可视化64-67
• 6.3 分析与讨论67-68
• 7 总结与展望68-73
• 7.1 研究结论68-69
• 7.2 研究创新点69-70
• 7.3 研究局限性70-71
• 7.4 未来展望71-73
• 参考文献73-78
• 附录A78-80
• 附录B80-83
• 作者简历及攻读硕士学位期间取得的研究成果83-85
• 学位论文数据集85

【相似文献】

中国期刊全文数据库 前10条

1 郭振宇;程博;叶敏;康龙云;曹秉刚;;一种并行混沌差异演化算法[J];西安交通大学学报;2007年03期

2 卢青波;张学良;温淑花;兰国生;刘丽琴;;多种群协作差异演化算法及其应用[J];现代制造工程;2012年02期

3 熊银键,嵇启春;演化算法在非线性参数估计中的应用[J];西安建筑科技大学学报(自然科学版);1999年01期

4 刘明广;李高扬;;差异演化算法在机械优化设计中的应用[J];机床与液压;2006年05期

5 戴福祥;胡晓林;;基于邻域探索的多目标演化算法[J];武汉理工大学学报;2009年09期

6 兰国生;张学良;卢青波;温淑花;刘丽琴;;简单差异演化算法及其在装配公差优化中的应用[J];机械设计与制造;2011年05期

7 王志刚;夏慧明;;基于差异演化算法的化学方程式配平研究[J];哈尔滨商业大学学报(自然科学版);2012年04期

8 韩珂;杨俊鹏;;求解旅行商问题的分布式演化算法[J];华北水利水电学院学报;2013年04期

9 胡中波;苏清华;;求解混合变量优化问题的自适应差分演化算法[J];武汉理工大学学报;2010年03期

10 兰国生;张学良;卢青波;温淑花;;增强差异演化算法及其应用[J];工程设计学报;2010年04期

中国重要会议论文全文数据库 前3条

1 冯珊;李锋;周凯波;;面向演化算法应用的智能体系统建模与仿真研究[A];西部开发与系统工程——中国系统工程学会第12届年会论文集[C];2002年

2 张文俊;谢晓锋;马君;;并行演化算法在半导体器件综合中的应用[A];2006年全国开放式分布与并行计算学术会议论文集（二）[C];2006年

3 谢柏桥;戴光明;郑蔚;王剑文;;有指导的多目标演化算法在区域星座设计中的应用[A];中国宇航学会深空探测技术专业委员会第四届学术年会论文集[C];2007年

中国博士学位论文全文数据库 前10条

1 彭晟;演化算法的静电场论模型[D];武汉大学;2011年

2 陈明;演化算法渐近行为的若干问题研究[D];武汉大学;2012年

3 彭飞;实值演化算法投资组合研究[D];中国科学技术大学;2011年

4 万书振;动态环境下差分演化算法研究与应用[D];武汉理工大学;2012年

5 魏波;交互式与自适应演化算法研究[D];武汉大学;2013年

6 赖鑫生;演化算法与混合算法的性能研究[D];华南理工大学;2014年

7 武志峰;差异演化算法及其应用研究[D];北京交通大学;2009年

8 陈天石;演化算法的计算复杂性研究[D];中国科学技术大学;2010年

9 龚文引;差分演化算法的改进及其在聚类分析中的应用研究[D];中国地质大学;2010年

10 吴志健;演化优化及其在微分方程反问题中的应用[D];武汉大学;2004年

中国硕士学位论文全文数据库 前10条

1 杨颖;一种多差分向量的自适应差分演化算法[D];浙江大学;2015年

2 陈伟;队伍演化算法及其在微波电路设计中的应用[D];杭州电子科技大学;2015年

3 吴昊;多群体并行演化算法的研究[D];南京邮电大学;2015年

4 要婷婷;基于模因演化算法的有限容量弧路径问题研究[D];北京交通大学;2016年

5 戴志晃;一种基于熵量守恒的改进演化算法的研究[D];江西理工大学;2010年

6 潘伟丰;一种基于平均矢量偏差的仿生演化算法[D];江西理工大学;2008年

7 胡中波;差分演化算法及其在函数优化中的应用研究[D];武汉理工大学;2006年

8 李程俊;组合优化问题的并行演化算法研究[D];武汉理工大学;2003年

9 赵永翔;多目标差分演化算法的构造及其应用[D];武汉理工大学;2007年

10 张鑫;协同演化算法及其在组合投资中的研究与应用[D];哈尔滨工程大学;2011年

  本文关键词：基于模因演化算法的有限容量弧路径问题研究，由笔耕文化传播整理发布。

本文编号：255865