毕业设计（论文）-基于蚁群算法的网络多节点路由优化

《毕业设计（论文）-基于蚁群算法的网络多节点路由优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中北大学2011届毕业设计说明书1绪论通信网络的迅速发展，新业务的不断出现，使多点通信成为网络必须支持的功能。传统网络中使用一对一的通信协议支持多点协议，数据需要做多个拷贝，分别传送，极大的浪费了网络资源。未来的多媒体通信，将带来大量的多点通信，使用点对点协议将造成网络效率的低下；另外，多媒体通信的业务通常需要达成一定的同步关系，使用点对点协议完成多点通信不再有效；而复用技术的发展使组播在共同的链路上共享带宽成为可能。由于上述原因必须考虑多点路由问题。由于网络是动态变化的，网络拓扑结构的变化的不可预测性和变化的频繁性和不确定性是

2、网络多点路由问题与其他常见的组合优化问题的根本不同之处，网络流量的随机性和偶然性也是网络动态变化的主要因素。有效快捷的网络路由算法是网路发展的重要问题。而蚁群算法的出现和广泛应用，提供了多点路由优化设计的新的思想。蚁群算法是一种模拟进化算法，它是在对自然界中真实蚁群的集体行为研究的基础上，由意大利学者M.Dorigo等人首先提出的。M.Dorigo等人充分利用了蚁群搜索食物的过程与著名的旅行商问题（TSP）之间的相似性，通过人工模拟蚂蚁搜索食物的过程（即通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径）来求解TS

3、P问题。仿生学家通过大量细致观察研究发现，蚂蚁个体之间是通过一种被称为外激素的物质进行信息传送，从而能相互协作，完成复杂的任务。蚂蚁在运动过程中，能在它所经过的路径上留下该物质，而且蚂蚁在运动过程中能够感知这种物质的存在及其强度，并以此指导自己的运动方向，蚂蚁倾向于朝着这种物质强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。蚁群算法是一种随机搜索算法，与其它模拟进化算法一样，通过候选解

4、组成的群体的进化过程来寻求最优解，该过程包含两个基本阶段：适应阶段和协作阶段。在适应阶段，各候选解根据所积累的信息不断调整自身结构；在协作阶段，候选解间通过信息交流，以期产生性能更好的解。第33页共33页中北大学2011届毕业设计说明书蚁群算法之所以能引起相关领域研究者的注意，是因为这种求解模式能将问题求解的快速性、全局优化特征以及有限时间内答案的合理性结合起来。其中，寻优的快速性是通过正反馈式的信息传递和积累来保证的。而算法的早熟性收敛又可以通过其分布式计算特征加以避免，同时，具有贪婪启发式搜索特征的蚁群系统又能在搜索过程的早

5、期找到可以接受的问题解答。这种优越的问题分布式求解模式经过相关领域研究者的关注和努力，已经在最初的算法模型基础上得到了很大的改进和拓展。基于蚁群算法的以上特点，将蚁群算法用于OSPF协议的网络中，根据不同网络的需要寻找最优路径（可以是时延、中间路由器个数或者费用等参数最优化），将是一个非常值得我们去研究的课题。1.1本设计研究的目的意义人们生活的现代社会是一个由计算机信息网络、电话通信网络、运输服务网络、能源和物流分配网络等各种网络组成的复杂的网络系统。网络优化的目的就是研究如何有效地计划、控制和管理这个网络系统，使之发挥最大的

6、社会效益和经济效益。网络优化是运筹学的是一个经典和重要的分支，所研究的问题涉及诸多领域，一方面是如何最大限度的节省资源，如最短路径、最小费用等；另一方面是在网络资源有限的情况下如何发挥其最大效益，如最大物流问题、最优资源配置问题等。网络优化问题是一类特殊的组合优化问题，属于NP难问题。对于此类NP问题，传统运筹学的优化方法显得无能为力，寻找、研究、应用启发式智能化的优化方法显得尤为重要。蚂蚁算法就是其中一种有效的启发式智能优化算法。本设计就是要在掌握蚁群算法的基础上，将其用于网络路由优化问题，根据不同网络的特点和需求，对算法进行

7、相应修改，编写出优化软件。由于这种求解模式能将问题求解的快速性、全局优化特征以及有限时间内答案的合理性结合起来，因而能适应网络各种因素随机变化的的特性，将其用于OSPF协议的工作过程中，可以快速有效的找出其所需的最优路径。最终，实现网络资源的合理利用和高效的数据传输，提高网络的运行速度，这对于互联网今后的快速发展起着重要的促进作用。1.2本设计的研究现状第33页共33页中北大学2011届毕业设计说明书蚁群算法诞生于1991年，是一类新颖而前沿的问题求解算法。在算法改进与理论问题的应用领域，这种算法很快就得到了国内外学者们的关注。

8、在国外，学者们提出了不同版本的蚁群算法，进一步地提高算法的性能；同时，他们也把蚁群算法应用到众多复杂的经典理论问题中，包括旅行商、车辆路由、二次指派、工序调度、背包问题、群组规划等等。在某些具体问题中，蚁群算法的性能更是达到乃至超越了用于该问题的其它经典的求解算