用多种群自适应混合遗传算法求解车辆路径问题

摘要

人工智能(Artificial Intelligence)一直以来是计算机科学中的重要的研究方向,而智能规划(Intelligent Planning)领域又是人工智能研究中的重要分支.智能规划研究的是如何利用计算机高速度高性能的计算来优化规划问题中经常出现的冗余现象,由此节约大量的人力和物力.在智能规划领域中存在的一个重要问题是车辆路径问题(Vehicle Routing Problems,VRP),即研究如何利用有限的运输资源来完成一定量的运输任务,并且使得运输成本最低.如果在此基础上加上时间窗的限制,问题就演变成了有时间窗的车辆路径问题(Vehicle RoutingProblems with Time Windows,VRPTW).有时间窗的车辆路径问题由于其巨大的经济效益,所以从它被提出以来一直就是计算机学者和管理者研究的重要课题,并且在过去的40多年间得到了突飞猛进的发展.各种方法,包括:线性规划方法、非线性规划方法、动态规划方法、组合优化方法、启发式方法、分枝界定法、爬山法、贪婪法等,都被应用于问题的求解,并且取得了不错的求解效果.然而,以往的这些方法都不可避免地存在各自的缺点,例如求解时间过长,容易陷入局部最优,系统资源消耗过大等.该文在以往方法研究的基础上,对传统的遗传算法进行改进,提出了多种群自适应混合遗传算法(Multiplepopulation AdaptiveHybrid Genetic Algorithms),并设计开发出了基于改进遗传算法的有时间窗的车辆路径问题求解系统.实验结果表明,经过改进的遗传算法比一般算法收敛速度更快,求解质量更为优良.

目录

文摘

英文文摘

第一章引言

1.1课题的背景和意义

1.2本文的研究重点

1.3本文的结构框架

第二章遗传算法概述

2.1遗传算法理论基础

2.1.1遗传算法的生物遗传学基础

2.1.2遗传算法的基本概念

2.1.3标准遗传算法

2.1.4遗传算法的特点

2.2遗传算法的描述与设计

2.2.1编码表示

2.2.2种群的初始化

2.2.3适应度

2.2.4选择算子

2.2.5交叉算子

2.2.6变异算子

2.3遗传算法的数学基础

2.3.1模式定理和积木块假设

2.3.2收敛性分析

2.3.3欺骗性问题

2.3.4隐式并行性

2.4算法实现的关键问题：如何防止“早熟”现象

2.4.1适应度伸拉法

2.4.2多种群交叉法

2.4.3 Boltzmann生存机制

2.5遗传算法的研究现状

2.5.1算法自身的改进

2.5.2参数的动态自适应

2.5.3基于小生境技术的遗传算法

2.5.4混合遗传算法

2.5.5并行遗传算法

2.6遗传算法的应用

第三章车辆路径问题及研究状况

3.1车辆路径问题定义

3.2车辆路径问题和旅行商问题的区别与关联

3.3车辆路径问题的研究现状及常用算法

3.3.1 λ交换的局部搜索法

3.3.2模拟退火算法

3.3.3禁忌搜索算法

3.4用遗传算法求解车辆路径问题的研究现状

第四章用多种群自适应混合遗传算法求解车辆路径问题

4.1多种群自适应混合遗传算法思想

4.2问题模型的建立

4.3系统的设计方案

4.3.1系统实现过程

4.3.2系统流程

4.3.3重要模块

4.4算法的改进机制

4.4.1编码机制/解码机制

4.4.2好坏种群

4.4.3精英种群

4.4.4二次遗传

4.4.5混合算法：爬山法和模拟退火机制

4.4.6遗传算子改进：交叉，变异

4.4.7算法的自适应性

4.5改进算法的复杂性和收敛性分析

4.5.1复杂性分析

4.5.2收敛性分析

4.6系统关键细节实现的伪码表示

4.6.1数据结构设计

4.6.2系统实现的重要函数

4.7实验结果比较分析

4.7.1算法的自身改进机制的比较分析

4.7.2不同算法的实验结果比较分析

第五章问题的总结与展望

5.1问题总结

5.2研究展望

参考文献

致谢

论文原创性声明