| 【中文题名】 | 车辆路径问题的改进遗传算法 |
| 【英文题名】 | The Improved Genetic Algorithm for VRP |
| 【学科专业】 | 计算机软件与理论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-10-25 |
| 【中关键词】 | 遗传算法,车辆路径问题,早熟收敛,双种群,交叉算子, |
| 【英关键词】 | Genetic Algorithm,Vehicle Routing Problem,Early Convergence,Double Populations,Crossover Operator, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 |
在计算机飞速发展的今天,车辆路径问题(Vehicle Routing Problems,简称VRP)一直以来是众多计算机学者研究的焦点。如何针对车辆路径问题的特点,构造运算简单、性能优异的启发式算法,对物流系统及许多可以转化为车辆路径问题的组合优化问题都有十分重要的意义。因此,本文针对传统遗传算法求解车辆路径问题所存在的不足,将《作物育种学》中的理论分别应用于目前遗传算法求解车辆路径问题的两种最典型的算法:即广泛使用的单种群遗传算法和寻优效率较高的双种群遗传算法,并通过仿真实验验证了本文所设计的算法的性能。本文研究内容及成果如下:
①针对传统遗传算法在求解车辆路径问题中存在的“早熟收敛”、易陷入局部极值点等不足,本文提出了将作物育种学中的差异性原理应用于遗传算法求解车辆路径问题的算法设计中的改进思路。我们将该原理应用到单种群遗传算法交叉前的父染色体选择过程,以及双种群遗传算法的种群交叉过程,通过模拟自然界中的进化规律来提高遗传算法的优化性能。
②基于上述改进思路,本文设计了一种改进的单种群遗传算法。该算法通过采用新的父染色体选择策略以及新的交叉算子,能够保证一对适应值有一定差异的染色... |
| 【论文题纲】 |
|
摘要 |
3-5 |
|
ABSTRACT |
5-9 |
|
1 绪论 |
9-15 |
|
1.1 课题的背景及意义 |
9-10 |
|
1.2 国内外研究现状 |
10-12 |
|
1.3 本文研究的重点 |
12-13 |
|
1.4 本文组织结构 |
13-15 |
|
2 车辆路径问题概述 |
15-20 |
|
2.1 车辆路径问题简介 |
15-16 |
|
2.1.1 车辆路径问题的定义 |
15 |
|
2.1.2 车辆路径问题的研究现状 |
15-16 |
|
2.1.3 车辆路径问题的计算复杂性 |
16 |
|
2.2 车辆路径问题的数学模型 |
16-17 |
|
2.3 求解车辆路径问题的常用算法 |
17-18 |
|
2.4 本章小结 |
18-20 |
|
3 基于单种群遗传算法的车辆路径问题求解 |
20-37 |
|
3.1 遗传算法简介 |
20-27 |
|
3.1.1 遗传算法的基本概念 |
20-24 |
|
3.1.2 传统单种群遗传算法介绍 |
24-26 |
|
3.1.3 传统单种群遗传算法存在的不足 |
26-27 |
|
3.2 改进单种群遗传算法的设计方案 |
27-29 |
|
3.2.1 算法思想与流程 |
27-28 |
|
3.2.2 算法的主要步骤 |
28-29 |
|
3.3 改进单种群遗传算法设计 |
29-36 |
|
3.3.1 新的父染色体选择策略 |
29-33 |
|
3.3.2 新的交叉算子 |
33-35 |
|
3.3.3 改进算法优化性能分析 |
35-36 |
|
3.4 本章小结 |
36-37 |
|
4 基于双种群遗传算法的车辆路径问题求解 |
37-47 |
|
4.1 传统双种群遗传算法求解车辆路径问题 |
37-40 |
|
4.1.1 传统双种群遗传算法介绍 |
37-40 |
|
4.1.2 传统双种群遗传算法存在的不足 |
40 |
|
4.2 改进双种群遗传算法的设计方案 |
40-42 |
|
4.2.1 算法思想与流程 |
40-41 |
|
4.2.2 算法的主要步骤 |
41-42 |
|
4.3 改进双种群遗传算法设计 |
42-46 |
|
4.3.1 新的种群交叉策略 |
42-45 |
|
4.3.2 新的染色体交叉与变异策略 |
45 |
|
4.3.3 改进算法优化性能分析 |
45-46 |
|
4.4 本章小结 |
46-47 |
|
5 车辆路径问题的模拟系统设计及实验 |
47-59 |
|
5.1 车辆路径问题的模拟系统设计 |
47-48 |
|
5.1.1 系统功能 |
47 |
|
5.1.2 系统结构 |
47-48 |
|
5.1.3 遗传算法工作流程 |
48 |
|
5.2 基于单种群遗传算法的车辆路径问题实验 |
48-54 |
|
5.2.1 实验描述 |
48-49 |
|
5.2.2 实验内容及结果 |
49-54 |
|
5.2.3 实验小结 |
54 |
|
5.3 基于双种群遗传算法的车辆路径问题实验 |
54-58 |
|
5.3.1 实验描述 |
54-55 |
|
5.3.2 实验内容及结果 |
55-58 |
|
5.3.3 实验小结 |
58 |
|
5.4 本章小结 |
58-59 |
|
6 总结与展望 |
59-61 |
|
6.1 研究总结 |
59-60 |
|
6.2 研究展望 |
60-61 |
|
致谢 |
61-62 |
|
参考文献 |
62-65 |
|
附录 |
65 |
|
| 【DOI】 | LunWen.ID:2.2008.389053 |
