基于改进遗传算法的最短路径路由优化算法的设计与实现

摘要

最短路径问题是图论研究中的一个经典的算法问题，也是网络优化中路由优化算法领域研究的热点问题之一，其旨在寻找图(由结点和路径组成的)中结点间的最短路径。
　　 随着Internet的迅猛发展，人们对计算机网络的伸缩性、稳定性、安全性和快速收敛性等提出了更高的要求，对网络性能进行优化便显得十分的必要。
　　 求解最短路径问题的自适应路由算法很多，广为人知的有Dijkstra算法和Floyd算法，这两种算法在解决最短路经问题的路由优化问题中都有自己特定的优势，Dijkstra算法适合于求解确定起点的最短路径路由问题(即已知起始结点，求从该结点开始至图中其余任意结点的最短路径的问题)，而Floyd算法更适合于求解全局最短路径路由问题(求图中所有的结点对间的最短路径)，但是随着网络中结点数目的增加，这些算法的复杂度便会呈现几何级数的增长，显然对于较大型网络，这些算法是不能很好的去适应。
　　 近年来，遗传算法(Genetic Algorithm，GA)以其较强的自适应性、全局优化性和较强的并行性，在解决复杂优化问题中体现出很强的解决问题的能力，其卓越的性能引起了人们的广泛关注。对于自适应路由算法，GA是较为有效的方法之一。相对于传统的算法，遗传算法的快速收敛性以及较低的算法复杂度使得其在路由算法的研究中具有一定的优势。
　　 本文研究了一般传统路由算法在最短路径问题中的应用，使用C++语言编写了相应的程序实现，开发了可视化的软件仿真界面模拟网络路由选择的过程，将路由过程使用图形和表格形式直观的表示了出来，并对比了两个经典算法(Dijkstra和Floyd)和本文改进的遗传算法在解决最短路径问题方面的收敛速度和算法复杂度。

目录

文摘

英文文摘

声明

第一章绪论

1.1研究背景及意义

1.1.1研究背景

1.1.2研究意义

1.2最短路径路由优化算法国内外研究现状

1.2.1 Dijkstra算法

1.2.2 Floyd算法

1.2.3其他路由查找算法

1.2.4最短路径路由优化算法的国内外研究现状

本文的主要创新点

本文的组织

第二章遗传算法的基本理论

2.1遗传算法概述

2.1.1遗传算法的发展

2.1.2遗传算法的基本步骤及求解过程

2.1.3遗传算法的特点及应用

2.2本章小结

第三章求最短路径优化问题的改进遗传算法的设计与实现

3.1求解最短路径路由问题的自适应路由选择的遗传优化算法

3.1.1求解SP路由问题的数学网络模型

3.1.2算法编码的设计

3.1.3算法种群的初始化

3.1.4算法适应度函数的设计

3.1.5算法的选择操作

3.1.6算法的交叉与变异

3.2求最短路径优化问题的改进遗传优化算法的实现

3.3本章小结

第四章仿真实验和结果分析

4.1仿真实验描述

4.2实验结果和分析

4.3本章小结

第五章结束语与下一步工作展望

5.1结束语

5.2下一步工作展望

参考文献

致谢

攻读学位期间发表的学术论文和参加的研究项目