1、J I A N G S U U N I V E R S I T Y本 科 毕 业 论 文基于蚁群算法路由选择可视化动态模拟Visul Simulation of Routing Selsect based on Ant Colony Algorithms 摘 要路由选择是一种基于网络层的协议，而所有流行的网络层路由选择协议都是基于以下两种典型的分布式算法之一：距离向量路由算法和链路状态路由算法。组合优化问题是人们在工程技术、科学研究和经济管理等众多领域经常遇到的问题，其中许多问题如旅行商问题、0-1背包问题、图着色问题、装箱问题等，都被证明为NP-困难问题。用确定性的优化算法求NP完全问题的最
2、优解，其计算时间使人难以忍受或因问题的高难度而使其计算时间随问题规模的增加以指数速度延长。用近似算法如启发式算法求解得到的近似解不能保证其可行性和最优性，甚至无法知道所得解同最优解的近似程度。因而在求解大规模组合优化问题时，传统的优化算法就显得无能为力了。在过去的10多年，蚁群算法（ACO ）的研究和应用取得了很大的进展，大量结果证明了算法的有效性和在某些领域的优势。蚁群算法是一种新型的模拟进化算法, 研究表明该算法具有并行性, 鲁棒性等优良性质。本文阐述了蚁群算法的原理,详细的说明了蚂蚁算法中各个功能模块，并介绍了该算法在理论和实际问题中的应用, 并对其前景进行了展望。关键词: 蚁群算法 信
3、息素 仿真AbstractWhether it is one based on Internet agreement for route not to choose, and all Internet route that prevail choose agreement on the basis of the following two typical distributed algorithm one of. Is it optimize problem people in engineering , scientific research , economic management nu
4、merous problem that field run into often to make up, among them a lot of question if knapsack issue , issue of businessman in the travel industry and of TSP , pursue painted question , case issue ,etc., proved as 6WF difficult problem. Ask the solving optimumly of JSP complete problem with the deter
5、ministic optimization algorithm, calculation its time make people to be insufferable making their calculation time up to increase , issue of scale lengthen so as to index speed because the question is highly difficult. If heuristic algorithm is it solve receive approximate solution can the assurance
6、 feasibility and getting optimum their to ask with algorithm of similar toing, it is even unable to know incomes and solve and solve optimumly to be similar to the degree. Therefore while asking and solving and making the question of optimizing up on a large scale, the traditional optimization algor
7、ithm seems powerless . From vectorial route algorithm, algorithm of route and state of chain The researches and applications on ACO algorithm have made great progresses in the past more than ten years. A number of results prove the validity of the algorithm and its advantages in some fields. ACO alg
8、orithm whether one new-type simulation evolve the algorithm , studies have shown this algorithm has walking abreast nature, fine nature such as being stupid and excellent. This text has explain ants principle of one group of algorithms, has introduced this application in the theory and practical pro
9、blem of algorithm, and has looked forward to its prospect .Keyword: Ant Colony Optimization algorithm Pheromone Simulation- i -目 录前 言 .1第 1 章 绪 论 .21.1 路 由 选 择 的 意 义 .21.1.1 路 由 选 择 技 术 的 组 成 .21.1.2 路 由 算 法 设 计 目 标 .31.1.3 路 由 算 法 的 分 类 .41.1.4 路 由 算 法 衡 量 的 标 准 .41.2.目 前 常 用 的 路 由 算 法 .51.2.1 最 短
10、路 径 算 法 .5第 2 章 蚁 群 算 法 的 基 本 原 理 .72.1 蚂 蚁 算 法 的 产 生 .72.2 蚂 蚁 算 法 的 算 法 思 想 .72.3 蚁 群 算 法 原 理 .82.4 蚁 群 算 法 的 应 用 .122.4.1 蚂 蚁 算 法 在 电 信 网 动 态 路 由 优 化 中 的 应 用 .122.4.2 蚂 蚁 算 法 在 组 合 优 化 中 的 应 用 .122.5 蚂 蚁 算 法 的 未 来 发 展 .122.5.1 MMAS ( Max2Min ant system) 最 大 最 小 蚁 群 算 法 .122.5.2 具 有 变 异 特 征 的 蚁 群
11、算 法 .122.5.3 自 适 应 蚁 群 算 法 .132.5.4 大 规 模 集 成 电 路 综 合 布 线 .132.5.5 电 信 网 络 路 由 .13第 3 章 开 发 工 具 .143.1 软 件 环 境 .143.2 其 他 资 料 .143.3 Java 的 简 单 介 绍 .143.3.1 网 络 时 代 的 需 要 .143.3.2 Internet 的 普 及 .143.3.3 跨 平 台 可 移 植 性 的 要 求 .143.4 Java 的 主 要 特 点 .153.4.1 简 单 性 .153.4.2 安 全 性 .153.4.3 面 向 对 象 性 .153.
12、4.4 可 靠 性 .16第 4 章 具 体 的 功 能 结 构 .174.1 系 统 的 结 构 总 框 图 .174.2 蚂 蚁 算 法 的 主 要 步 骤 .18第 5 章 系 统 的 实 现 .255.1 蚁 群 算 法 的 实 现 结 果 .25第 6 章 算 法 的 不 足 和 改 进 .296.1 算 法 的 不 足 .29- ii -6.2 算 法 的 改 进 .306.2.1 信 息 素 更 新 参 数 微 调 .306.2.2 全 局 调 整 .316.2.3 信 息 素 值 微 调 .316.3 一 种 先 进 的 蚂 蚁 算 法 智 能 蚂 蚁 算 法 .316.3.1
13、 取 消 外 激 素 .316.3.2 自 动 调 节 选 择 最 优 路 径 的 比 例 .325.6.3 选 择 目 标 城 市 的 依 据 .326.3.4 引 入 扰 动 .326.4 蚂 蚁 算 法 的 展 望 .33结 束 语 .34参 考 文 献 .35- 1 -前言蚁群算法是一种新生的算法，具有很强的通用性。从提出到现在，仅短短10余年的时间，但是在离散型组合优化问题中。表现很突出，所以一起人们的关注。目前蚁群算法的研究者主要集中在比利时、意大利、德国等国家，美国和日本在近几年也开始了对蚁群算法的研究。国内的研究开始于 1998年末。主要在上海、北京、东北少数几个学校和研究所开
14、展了此项工作，主要围绕 TSP及相关问题的实验仿真，少数涉及通信网络的路由选择、负载平衡、电力系统的故障检测以及蚁群算法在连续系统应用，如函数逼近等方面应用的尝试。在国外，蚁群算法已经在集成电路布线、网络路由选择、机器人线路规划等方面得到了应用。自 1998年，第一届蚂蚁优化国际研讨会召开以来，已经是第三届了，大大推动了蚁群算法的发展。蚁群算法已经引起越来越多的关注，尽管还缺乏完善的理论分析，对它的有效性也没有出严格的数学解释，但是回顾模糊控制的发展历史，理论的不完善并不妨碍应用，有时应用是超前于理论的，并推动理论的研究。我们相信蚁群算法必将得到广泛的应用。- 2 -第 1章 绪论1.1 路由
15、选择的意义 路由(Route) 的概念出现于本世纪70 年代,当时的网络结构较简单,因此直至80 年代中期出现了大规模的网络结构后,路由技术才得到了广泛的应用。在ISO/ OSI 体系结构中,路由技术是第三层(网络层) 的功能,路由选择(Routing)是分组交换系统中的一个重要概念,是指在互联网络中选择将信包(Package) 从信源机(Source Host) 传往信宿机(Destination Host) 的传输路径的过程。实际的网络协议(如IP协议) ,其本身并不涉及具体的路由选择细节,它只说明路由选择的一般原理和规则,具体的路由选择是指路由表的建立与刷新机制,由一组独立的路由选择协议
16、(RoutingProtocol) 描述。路由选择的过程是由路由算法来完成的,路由算法可以运行在网络主机上,也可运行在专用的路由设备上,如路由器是一种网络互联设备,其主要功能就是进行路由选择。1.1.1 路由选择技术的组成路由选择技术涉及两方面内容:最佳路径的选择及信包在网络上的传递。信包的传递也可称为交换(Switching) , 交换过程相对简单,而路径的选择过程比较复杂。最佳路径选择最佳路径依赖于不同的衡量标准,例如可使用路径长度作为衡量标准。在确定最佳路径的路由算法中,路由表(Routing Tables) 是一个重要的数据结构,其中包含了网络的路由信息,算法通过建立和维护路由表进行最
17、佳路径的确定。路由算法根据算法要求在路由表中填写各种路由信息,其中最基本的是目标/ 驿站(Hop) 信息(见表1) 。这一组信息告诉路由器,在信包发往信宿机的过程中,最佳选择是将信息转发至下一驿站(Next Hop) 所代表的节点。当路由器接收到一个输入信息时,首先检查信包的目标地址,然后尝试找出与此目标地址相匹配的下一驿站,若匹配成功则进行信包转发,否则放弃该信包。除了目标/ 驿站信息外,根据不同的路由算法,路由表中还包含有其它内容,例如最佳路径的衡量标准- 3 -等信息。在路由器之间传输的各种信息中,有关路由选择的信息称为路由刷新报文(Routing Update Message) 。路由
18、刷新报文通常是全部或部分路由表内容。通过对所有路由信息的分析,路由器可建立一个详细的网络拓扑图。例如,用于链接-状态路由算法的链接- 状态广播报文通知其它路由器有关自身的链接状态,通过这些信息,路由器可建立一个完整的网络拓扑图,通过拓扑图便可确定到达目标的最佳路径。1.1.2 路由算法设计目标路由算法往往具有下列一种或多种目标: 最佳性、简单性、稳定性、快速收敛性及适应性等目标。(1) 最佳性目标要求算法具有寻找最佳路径的能力,最佳路径依赖于算法所采用的衡量标准。通常路由选择协议严格定义了计算时所采用的衡量标准。(2) 简单性目标要求算法尽可能简单,即用尽可能小的软件开销提供有效的功能。当算法
19、运行在低档设备上时效率尤为重要。(3) 稳定性目标算法必须是稳定可靠的。在遇到特殊情况(如硬件故障、过载、误操作等) 时,算法能够稳定地运行。由于路由器位于互联网络的连接点上, 有着相当重要的地位, 若算法不稳定将造成严重的后果。优秀的路由算法经得起时间的检验并且在任何情况下都能稳定地工作。(4) 快速收敛性目标路由算法要求能够快速收敛。这里所指的收敛是指最佳路径能迅速被网上所有路由器所接受。若发生网络故障导致线路断开或恢复, 相应路由器向网络发出路由刷新报文,促使其它路由器重新计算最佳路径,更新路由表,同时又向网络发送刷新报文,直至所有路由器都相互认可这些最佳路径。收敛慢的算法将导致路由环问
20、题及网络损耗。(5) 适应性目标路由算法必须具有较强的适应能力,即能够迅速准确地适应各种网络环境的变化。例如,如果发现某一网段出现故障,能迅速为所有经过该网段的路径选择另一条最佳路径。另外,还必须能适应网络带宽、路由器队列大小、网络延迟或其它变化。- 4 -1.1.3 路由算法的分类(1) 静态或动态路由算法静态路由是由管理员在路由使用前建立的,只有管理员才能对路由表进行修改。静态路由算法的设计简单,在可预知网络的通信量且网络结构简单的情况下使用静态路由算法。静态路由算法不能适应网络情况的变化,因此不适用于目前的大规模及变化频繁的网络结构, 90 年代占主导地位的路由算法是动态路由算法。动态路
21、由算法通过分析路由刷新报文,能够进行实时调整以适应网络的变化。当网络发生变化时,根据路由刷新信息, 路由软件重新计算最佳路径并将变化信息向网络上发送。这些信息在网络上使得网络上的其它路由器也相应运行路由算法刷新其路由表。(2) 单重路径或多重路径算法单重路径算法对同一信宿机提供一条最佳路径,多重路径算法对同一信宿机提供多条路径以供选择,允许在复杂的线路上进行多重通信。多重路径算法不仅提高了通信量而且提高了通信的可靠性。(3) 单层或多层结构算法单层结构中,网络上所有的路由器是对等的,而在多层结构中,存在主干路由器与分支路由器。信包从分支路由器转发至主干路由器,再传送至信宿机所在区域的主干路由器
22、,再从这一位置通过一个或多个分支路由器最终到达信宿机。路由系统将一组逻辑节点称为域或自治系统。在层次结构中,有些路由器只能在自治系统内相互通信,位于自治系统顶层的路由器可与其它自治系统的顶层路由器进行通信。层次结构的主要优点在于模仿了公司的组织结构,因为网络的大部分通信量存在于分公司内部(自治系统) ,自治系统内的路由器只需清楚系统内其它路由器的情况。因此系统内的路由算法可进行简化,相应减少了路由刷新时产生的通信量。(4) 向量- 距离算法或链接- 状态算法这两种算法是两类基本的自动路径广播算法,在此基础上相应有多种协议,典型的有GGP 和SPF 协议。1.1.4 路由算法衡量的标准路由信息表
23、中包含了交换所需的如何确定最佳路径的要求, 即确定最佳路径- 5 -的标准, 路由算法根据这些标准进行计算。复杂的算法往往综合多种标准,常用的衡量标准有:(1) 路径长度路径长度是使用最普遍的标准,一些协议许可网络管理员对网络的线路赋予一定的代价值,在此类情况下,最佳路径就是所经过的每条线路的代价总和。有些协议定义驿站数量为标准,即路径上所经过的网络设备(如路由器) 的数量。(2) 可靠性在路由算法中, 可靠性是指每个网络连接的可靠性, 通常用每位的错误率表示。有些网络连接可能经常发生故障,而发生故障时,有些网络连接能很快或很容易恢复。可靠性可通过对网络连接赋予相应的数值来确定。(3) 延迟延
24、迟是指将信包从信源机发送到信宿机所经过的时间,延迟受很多因素影响, 例如: 网络带宽、路由器端口队列数量、网络负荷以及实际传输的距离等。(4) 带宽带宽是指网络连接的通信能力,虽然带宽代表了网络连接所能达到的最高的通信速率,但往往宽带连接意味着网络更繁忙, 传送一个信包所需要实际时间可能更长, 因此宽带连接并不一定能提供更好的路由能力。(5) 负载负载是指网络设备(如路由器) 的繁忙程度。负载有多种计算方式, 如CPU利用率、每秒处理的信包数量等, 对这些参数的监控过程本身也是网络的一种负载。1.2.目前常用的路由算法1.2.1 最短路径算法寻找两顶点间的最短路径的算法很多目前公认最好的算法是Dijkstra在1959 年提出的它不仅求出从始点到终点的最短路径而且最后所得到的实际上是始点到各顶点的最短路径对Dijkstra 算法进行补充得出的步骤如下：第一步：初始化 V=1 2 N S = F D I = LF I Y I = F 其中I=1，2 ， N 。 F 表示路径的始点 I 表示某一顶点 N 表示网络中所有顶点的数目 V 是所有顶点的集合 LF I表示从 F 点到 I 点的
