java基于蚁群算法路由选择可视化动态模拟

PAGE本科毕业论文基于蚁群算法路由选择可视化动态模拟VisulSimulationofRoutingSelsectbasedonAntColonyAlgorithms学院名称：计算机学院专业班级：学生姓名：指导教师姓名：指导教师职称：年6月PAGE摘要路由选择是一种基于网络层的协议，而所有流行的网络层路由选择协议都是基于以下两种典型的分布式算法之一：距离向量路由算法和链路状态路由算法。组合优化问题是人们在工程技术、科学研究和经济管理等众多领域经常遇到的问题，其中许多问题如旅行商问题、0-1背包问题、图着色问题、装箱问题等，都被证明为NP-困难问题。用确定性的优化算法求NP完全问题的最优解，其计算时间使人难以忍受或因问题的高难度而使其计算时间随问题规模的增加以指数速度延长。用近似算法如启发式算法求解得到的近似解不能保证其可行性和最优性，甚至无法知道所得解同最优解的近似程度。因而在求解大规模组合优化问题时，传统的优化算法就显得无能为力了。在过去的10多年，蚁群算法（ACO）的研究和应用取得了很大的进展，大量结果证明了算法的有效性和在某些领域的优势。蚁群算法是一种新型的模拟进化算法,研究表明该算法具有并行性,鲁棒性等优良性质。本文阐述了蚁群算法的原理,详细的说明了蚂蚁算法中各个功能模块，并介绍了该算法在理论和实际问题中的应用,并对其前景进行了展望。关键词:蚁群算法信息素仿真AbstractWhetheritisonebasedonInternetagreementforroutenottochoose,andallInternetroutethatprevailchooseagreementonthebasisofthefollowingtwotypicaldistributedalgorithmoneof.Isitoptimizeproblempeopleinengineering,scientificresearch,economicmanagementnumerousproblemthatfieldrunintooftentomakeup,amongthemalotofquestionifknapsackissue,issueofbusinessmaninthetravelindustryandofTSP,pursuepaintedquestion,caseissue,etc.,provedas6WFdifficultproblem.AskthesolvingoptimumlyofJSPcompleteproblemwiththedeterministicoptimizationalgorithm,calculationitstimemakepeopletobeinsufferablemakingtheircalculationtimeuptoincrease,issueofscalelengthensoastoindexspeedbecausethequestionishighlydifficult.Ifheuristicalgorithmisitsolvereceiveapproximatesolutioncantheassurancefeasibilityandgettingoptimumtheirtoaskwithalgorithmofsimilartoing,itisevenunabletoknowincomesandsolveandsolveoptimumlytobesimilartothedegree.Thereforewhileaskingandsolvingandmakingthequestionofoptimizinguponalargescale,thetraditionaloptimizationalgorithmseemspowerless.Fromvectorialroutealgorithm,algorithmofrouteandstateofchainTheresearchesandapplicationsonACOalgorithmhavemadegreatprogressesinthepastmorethantenyears.Anumberofresultsprovethevalidityofthealgorithmanditsadvantagesinsomefields.ACOalgorithmwhetheronenew-typesimulationevolvethealgorithm,studieshaveshownthisalgorithmhaswalkingabreastnature,finenaturesuchasbeingstupidandexcellent.Thistexthasexplainant'sprincipleofonegroupofalgorithms,hasintroducedthisapplicationinthetheoryandpracticalproblemofalgorithm,andhaslookedforwardtoitsprospect.Keyword:AntColonyOptimizationalgorithmPheromoneSimulation -PAGEii-目录TOC\o"1-3"\h\z前言 1第1章绪论 21.1路由选择的意义 21.1.1路由选择技术的组成 21.1.2路由算法设计目标 31.1.3路由算法的分类 41.1.4路由算法衡量的标准 41.2.目前常用的路由算法 51.2.1最短路径算法 5第2章蚁群算法的基本原理 72.1蚂蚁算法的产生 72.2蚂蚁算法的算法思想 72.3蚁群算法原理 82.4蚁群算法的应用 122.4.1蚂蚁算法在电信网动态路由优化中的应用 122.4.2蚂蚁算法在组合优化中的应用 122.5蚂蚁算法的未来发展 122.5.1MMAS(Max2Minantsystem)最大最小蚁群算法 122.5.2具有变异特征的蚁群算法 122.5.3自适应蚁群算法 132.5.4大规模集成电路综合布线 132.5.5电信网络路由 13第3章开发工具 143.1软件环境 143.2其他资料 143.3Java的简单介绍 143.3.1网络时代的需要 143.3.2Internet的普及 143.3.3跨平台可移植性的要求 143.4Java的主要特点 153.4.1简单性 153.4.2安全性 153.4.3面向对象性 153.4.4可靠性 16第4章具体的功能结构 174.1系统的结构总框图 174.2蚂蚁算法的主要步骤 18第5章系统的实现 255.1蚁群算法的实现结果 25第6章 算法的不足和改进 296.1算法的不足 296.2算法的改进 306.2.1信息素更新参数微调 306.2.2全局调整 316.2.3信息素值微调 316.3一种先进的蚂蚁算法——智能蚂蚁算法 316.3.1取消外激素 316.3.2自动调节选择最优路径的比例 325.6.3选择目标城市的依据 326.3.4引入扰动 326.4蚂蚁算法的展望 33结束语 34参考文献 35 -PAGE39-前言蚁群算法是一种新生的算法，具有很强的通用性。从提出到现在，仅短短10余年的时间，但是在离散型组合优化问题中。表现很突出，所以一起人们的关注。目前蚁群算法的研究者主要集中在比利时、意大利、德国等国家，美国和日本在近几年也开始了对蚁群算法的研究。国内的研究开始于1998年末。主要在上海、北京、东北少数几个学校和研究所开展了此项工作，主要围绕TSP及相关问题的实验仿真，少数涉及通信网络的路由选择、负载平衡、电力系统的故障检测以及蚁群算法在连续系统应用，如函数逼近等方面应用的尝试。在国外，蚁群算法已经在集成电路布线、网络路由选择、机器人线路规划等方面得到了应用。自1998年，第一届蚂蚁优化国际研讨会召开以来，已经是第三届了，大大推动了蚁群算法的发展。蚁群算法已经引起越来越多的关注，尽管还缺乏完善的理论分析，对它的有效性也没有出严格的数学解释，但是回顾模糊控制的发展历史，理论的不完善并不妨碍应用，有时应用是超前于理论的，并推动理论的研究。我们相信蚁群算法必将得到广泛的应用。第1章绪论1.1路由选择的意义路由(Route)的概念出现于本世纪70年代,当时的网络结构较简单,因此直至80年代中期出现了大规模的网络结构后,路由技术才得到了广泛的应用。在ISO/OSI体系结构中,路由技术是第三层(网络层)的功能,路由选择(Routing)是分组交换系统中的一个重要概念,是指在互联网络中选择将信包(Package)从信源机(SourceHost)传往信宿机(DestinationHost)的传输路径的过程。实际的网络协议(如IP协议),其本身并不涉及具体的路由选择细节,它只说明路由选择的一般原理和规则,具体的路由选择是指路由表的建立与刷新机制,由一组独立的路由选择协议(RoutingProtocol)描述。路由选择的过程是由路由算法来完成的,路由算法可以运行在网络主机上,也可运行在专用的路由设备上,如路由器是一种网络互联设备,其主要功能就是进行路由选择。1.1.1路由选择技术的组成路由选择技术涉及两方面内容:最佳路径的选择及信包在网络上的传递。信包的传递也可称为交换(Switching),交换过程相对简单,而路径的选择过程比较复杂。最佳路径选择最佳路径依赖于不同的衡量标准,例如可使用路径长度作为衡量标准。在确定最佳路径的路由算法中,路由表(RoutingTables)是一个重要的数据结构,其中包含了网络的路由信息,算法通过建立和维护路由表进行最佳路径的确定。路由算法根据算法要求在路由表中填写各种路由信息,其中最基本的是目标/驿站(Hop)信息(见表1)。这一组信息告诉路由器,在信包发往信宿机的过程中,最佳选择是将信息转发至下一驿站(NextHop)所代表的节点。当路由器接收到一个输入信息时,首先检查信包的目标地址,然后尝试找出与此目标地址相匹配的下一驿站,若匹配成功则进行信包转发,否则放弃该信包。除了目标/驿站信息外,根据不同的路由算法,路由表中还包含有其它内容,例如最佳路径的衡量标准等信息。在路由器之间传输的各种信息中,有关路由选择的信息称为路由刷新报文(RoutingUpdateMessage)。路由刷新报文通常是全部或部分路由表内容。通过对所有路由信息的分析,路由器可建立一个详细的网络拓扑图。例如,用于链接-状态路由算法的链接-状态广播报文通知其它路由器有关自身的链接状态,通过这些信息,路由器可建立一个完整的网络拓扑图,通过拓扑图便可确定到达目标的最佳路径。1.1.2路由算法设计目标路由算法往往具有下列一种或多种目标:最佳性、简单性、稳定性、快速收敛性及适应性等目标。(1)最佳性目标要求算法具有寻找最佳路径的能力,最佳路径依赖于算法所采用的衡量标准。通常路由选择协议严格定义了计算时所采用的衡量标准。(2)简单性目标要求算法尽可能简单,即用尽可能小的软件开销提供有效的功能。当算法运行在低档设备上时效率尤为重要。(3)稳定性目标算法必须是稳定可靠的。在遇到特殊情况(如硬件故障、过载、误操作等)时,算法能够稳定地运行。由于路由器位于互联网络的连接点上,有着相当重要的地位,若算法不稳定将造成严重的后果。优秀的路由算法经得起时间的检验并且在任何情况下都能稳定地工作。(4)快速收敛性目标路由算法要求能够快速收敛。这里所指的收敛是指最佳路径能迅速被网上所有路由器所接受。若发生网络故障导致线路断开或恢复,相应路由器向网络发出路由刷新报文,促使其它路由器重新计算最佳路径,更新路由表,同时又向网络发送刷新报文,直至所有路由器都相互认可这些最佳路径。收敛慢的算法将导致路由环问题及网络损耗。(5)适应性目标路由算法必须具有较强的适应能力,即能够迅速准确地适应各种网络环境的变化。例如,如果发现某一网段出现故障,能迅速为所有经过该网段的路径选择另一条最佳路径。另外,还必须能适应网络带宽、路由器队列大小、网络延迟或其它变化。1.1.3路由算法的分类(1)静态或动态路由算法静态路由是由管理员在路由使用前建立的,只有管理员才能对路由表进行修改。静态路由算法的设计简单,在可预知网络的通信量且网络结构简单的情况下使用静态路由算法。静态路由算法不能适应网络情况的变化,因此不适用于目前的大规模及变化频繁的网络结构,90年代占主导地位的路由算法是动态路由算法。动态路由算法通过分析路由刷新报文,能够进行实时调整以适应网络的变化。当网络发生变化时,根据路由刷新信息,路由软件重新计算最佳路径并将变化信息向网络上发送。这些信息在网络上使得网络上的其它路由器也相应运行路由算法刷新其路由表。(2)单重路径或多重路径算法单重路径算法对同一信宿机提供一条最佳路径,多重路径算法对同一信宿机提供多条路径以供选择,允许在复杂的线路上进行多重通信。多重路径算法不仅提高了通信量而且提高了通信的可靠性。(3)单层或多层结构算法单层结构中,网络上所有的路由器是对等的,而在多层结构中,存在主干路由器与分支路由器。信包从分支路由器转发至主干路由器,再传送至信宿机所在区域的主干路由器,再从这一位置通过一个或多个分支路由器最终到达信宿机。路由系统将一组逻辑节点称为域或自治系统。在层次结构中,有些路由器只能在自治系统内相互通信,位于自治系统顶层的路由器可与其它自治系统的顶层路由器进行通信。层次结构的主要优点在于模仿了公司的组织结构,因为网络的大部分通信量存在于分公司内部(自治系统),自治系统内的路由器只需清楚系统内其它路由器的情况。因此系统内的路由算法可进行简化,相应减少了路由刷新时产生的通信量。(4)向量-距离算法或链接-状态算法这两种算法是两类基本的自动路径广播算法,在此基础上相应有多种协议,典型的有GGP和SPF协议。1.1.4路由算法衡量的标准路由信息表中包含了交换所需的如何确定最佳路径的要求,即确定最佳路径的标准,路由算法根据这些标准进行计算。复杂的算法往往综合多种标准,常用的衡量标准有:(1)路径长度路径长度是使用最普遍的标准,一些协议许可网络管理员对网络的线路赋予一定的代价值,在此类情况下,最佳路径就是所经过的每条线路的代价总和。有些协议定义驿站数量为标准,即路径上所经过的网络设备(如路由器)的数量。(2)可靠性在路由算法中,可靠性是指每个网络连接的可靠性,通常用每位的错误率表示。有些网络连接可能经常发生故障,而发生故障时,有些网络连接能很快或很容易恢复。可靠性可通过对网络连接赋予相应的数值来确定。(3)延迟延迟是指将信包从信源机发送到信宿机所经过的时间,延迟受很多因素影响,例如:网络带宽、路由器端口队列数量、网络负荷以及实际传输的距离等。(4)带宽带宽是指网络连接的通信能力,虽然带宽代表了网络连接所能达到的最高的通信速率,但往往宽带连接意味着网络更繁忙,传送一个信包所需要实际时间可能更长,因此宽带连接并不一定能提供更好的路由能力。(5)负载负载是指网络设备(如路由器)的繁忙程度。负载有多种计算方式,如CPU利用率、每秒处理的信包数量等,对这些参数的监控过程本身也是网络的一种负载。1.2.目前常用的路由算法1.2.1最短路径算法寻找两顶点间的最短路径的算法很多目前公认最好的算法是Dijkstra在1959年提出的它不仅求出从始点到终点的最短路径而且最后所得到的实际上是始点到各顶点的最短路径对Dijkstra算法进行补充得出的步骤如下：第一步：初始化V={12N}S={F}D[I]=L[FI]Y[I]=F其中I=1，2，…N。F表示路径的始点I表示某一顶点N表示网络中所有顶点的数目V是所有顶点的集合L[FI]表示从F点到I点的距离S是顶点的集合D为N个元素的数组用来存储顶点F到其它顶点的最短距离Y为N个元素的数组用来存储最短路径中在顶点I之前经过的最近顶点第二步：从VS集合中找一个顶点T使得D[T]是最小值并将T加入到S集合中如果VS是空集合则结束运算第三步：调整YD数组中的值在VS集合中对于顶点T的邻接各顶点I如果D[I]>D[T]+L[IT]那么令Y[I]=TD[I]=D[T]+L[IT]继续执行第二步最短路径算法的不足Dijkstra算法所采用的数据结构及其实现方法总体上说是比较复杂的其缺点也是明显的难以应付公交线路的网络拓扑中的复杂性主要表现如下：（1）数据结构复杂网络在教学和计算领域被抽象为图所以其基础是图的存储表示一般而言无向图可以用邻接矩阵和十字链表表示公交线路网络拓扑很难用现有的数据结构加以完整的表示如果采用现有的最短路径算法分析其建立的公交线路网络图的数据结构模型将非常复杂（2）算法时间长以Dijkstra算法来计算公交路线最短路径在大数据量的情况下计算速度会慢得让人难以忍受系统设计中要求公交转车的查询必须在较短的时间内完成Dijkstra算法难以实现（3）Dijkstra最短路径算法对于网络拓扑图要求简捷对于复杂的广州公交网络拓扑必须对其进行复杂的抽象合并成简捷的网络拓扑图这无疑增加了程序的复杂性而蚁群算法是一种新型的模拟进化算法，自从1991年M.Dorigo等人首先提出蚁群算法以来,有许多研究人员对该算法进行研究,并成功地应用于解决复杂组合优化问题.在研究该算法的过程中,研究人员提出一些改进的算法,研究表明该算法具有很好的通用性和鲁棒性,在离散的组合优化问题中实验,取得了良好的效果。下章节就着重介绍一下蚂蚁算法。第2章蚁群算法的基本原理2.1蚂蚁算法的产生蚂蚁是自然界中常见的一种生物，人们对蚂蚁的关注大都是因为“蚂蚁搬家，天要下雨”之类的民谚。然而随着近代仿生学的发展，这种似乎微不足道的小东西越来越多地受到学者们的关注。1991年M·Dorigo等人首先提出了蚁群算法（AntColonyAlgorithms）。人们开始了对蚁群的研究：相对弱小，功能并不强大的个体是如何完成复杂的工作的（如寻找到食物的最佳路径并返回等）。在此基础上一种很好的优化算法逐渐发展起来。2.2蚂蚁算法的算法思想蚁群算法是受到对真实的蚁群行为的研究的启发而提出的.为了说明人工蚁群系统的原理,先从蚁群搜索食物的过程谈起.象蚂蚁、蜜蜂、飞蛾等群居昆虫,虽然单个昆虫的行为极其简单,但由单个简单的个体所组成的群体却表现出极其复杂的行为,原因是什么呢?仿生学家经过大量细致观察研究发现,蚂蚁个体之间是通过一种称之为外激素(pheromone)的物质进行信息传递的.蚂蚁在运动过程中,能够在它所经过的路径上留下该种物质,而且蚂蚁在运动过程中能够感知这种物质,并以此指导自己的运动方向,因此,由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大.蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。蚂蚁个体之间的信息交换是一个正反馈过程。说了这么多，蚂蚁究竟是怎么找到食物的呢？

在没有蚂蚁找到食物的时候，环境没有有用的信息素，那么蚂蚁为什么会相对有效的找到食物呢？这要归功于蚂蚁的移动规则，尤其是在没有信息素时候的移动规则。首先，它要能尽量保持某种惯性，这样使得蚂蚁尽量向前方移动（开始，这个前方是随机固定的一个方向），而不是原地无谓的打转或者震动；其次，蚂蚁要有一定的随机性，虽然有了固定的方向，但它也不能像粒子一样直线运动下去，而是有一个随机的干扰。这样就使得蚂蚁运动起来具有了一定的目的性，尽量保持原来的方向，但又有新的试探，尤其当碰到障碍物的时候它会立即改变方向，这可以看成一种选择的过程，也就是环境的障碍物让蚂蚁的某个方向正确，而其他方向则不对。这就解释了为什么单个蚂蚁在复杂的诸如迷宫的地图中仍然能找到隐蔽得很好的食物。

当然，在有一只蚂蚁找到了食物的时候，其他蚂蚁会沿着信息素很快找到食物的。

蚂蚁如何找到最短路径的？这一是要归功于信息素，另外要归功于环境，具体说是计算机时钟。信息素多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多（或者较长的路上蚂蚁多，这也无关紧要）。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素……；而长的路正相反，因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就近似找到了。也许有人会问局部最短路径和全局最短路的问题，实际上蚂蚁逐渐接近全局最短路的，为什么呢？这源于蚂蚁会犯错误，也就是它会按照一定的概率不往信息素高的地方走而另辟蹊径，这可以理解为一种创新，这种创新如果能缩短路途，那么根据刚才叙述的原理，更多的蚂蚁会被吸引过来。2.3蚁群算法原理蚁群算法是一种由于受自然界生物的行为启发而产生的“自然”算法。它是从对蚁群行为的研究中产生的。正如M·Dorigo等人在关于蚁群算法的第1篇文章中指出的：蚁群中的蚂蚁以“外激素”（Stigmergy）为媒介的间接的异步的联系方式是蚁群算法的最大的特点。蚂蚁在行动（寻找食物或者寻找回巢的路径）中，会在它们经过的地方留下一些化学物质（我们称之为“外激素”）。这些物质能被同一蚁群中后来的蚂蚁感受到，并作为一种信号影响后到者的行动（具体表现在后到的蚂蚁选择有这些物质的路径的可能性，比选择没有这些物质的路径的可能性大得多），而后到者留下的外激素会对原有的外激素进行加强，并如此循环下去。这样，经过蚂蚁越多的路径，在后到蚂蚁的选择中被选中的可能性就越大（因为残留的外激素浓度较大的缘故）。由于在一定的时间内，越短的路径会被越多的蚂蚁访问，因而积累的外激素也就越多，在下一个时间内被其他的蚂蚁选中的可能性也就越大。这个过程会一直持续到所有的蚂蚁都走最短的那一条路径为止。（如图）图1中有一条蚂蚁经过的路径，我们假设a点是食物，而e点是蚂蚁的巢穴，如图1a）所示。在某一个时刻忽然有一个障碍物出现在蚂蚁经过的路径中，原有的路径被切断，从a点到e点的蚂蚁就必须在b点决定应该往左还是往右走。而从a点到e点的蚂蚁也必须在d点决定选择哪条路径。这种决定会受到各条路径上以往蚂蚁留下的外激素浓度（即残留信息浓度）的影响。如果向右的路径上的外激素浓度比较大，那么向右的路径被蚂蚁选中的可能性也就比较大一些。但是对障碍出现后第一个到达b点或d点的蚂蚁而言，因为没有外激素的影响，所以它们选择向左或者向右的可能性是一样的，如图1b）所示。若以从a点到e点的蚂蚁为例进行说明，对于从e点到a点的蚂蚁而言过程基本是一样的。由于路径bhd比路径bed要短，因此选择bhd路径的第一只蚂蚁要比选择bed的第一只蚂蚁早到达d点。此时，从d点向b点看，指向路径dhb的外激素浓度要比指向路径deb的外激素浓度大。因此从下一时刻开始,从e点经d点达到a点的蚂蚁选择dhb路径比选择dcb路径的可能性要大得多。从而使路径bhd（或dhb）上外激素浓度与路径bed（或deb）上外激素浓度的差变大。而外激素浓度差变大的结果是选择路径bhd（或dhb）路径的蚂蚁进一步增加，这又导致外激素浓度差进一步加大。设想，如果我们要为蚂蚁设计一个人工智能的程序，那么这个程序要多么复杂呢？首先，你要让蚂蚁能够避开障碍物，就必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物，其次，要让蚂蚁找到食物，就需要让他们遍历空间上的所有点；再次，如果要让蚂蚁找到最短的路径，那么需要计算所有可能的路径并且比较它们的大小，而且更重要的是，你要小心翼翼的编程，因为程序的错误也许会让你前功尽弃。这是多么不可思议的程序，太复杂了，恐怕没人能够完成这样繁琐冗余的程序。

然而，事实并没有你想得那么复杂，上面这个程序每个蚂蚁的核心程序编码都不是很长。为什么这么简单的程序会让蚂蚁干这样复杂的事情？答案是：简单规则的涌现。事实上，每只蚂蚁并不是像我们想象的需要知道整个世界的信息，他们其实只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律。那么，这些简单规则是什么呢？下面详细说明：

1、范围：

蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径VR（一般是3），那么它能观察到的范围就是VR*VR个方格世界，并且能移动的距离也在这个范围之内。

2、环境：

蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。

3、觅食规则：

在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。

4、移动规则：

每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。

5、避障规则：

如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。

7、播撒信息素规则：

每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。

根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。2.4蚁群算法的应用2.4.1蚂蚁算法在电信网动态路由优化中的应用针对我国电信网的具体情况，提出借助蚂蚁算法，用分散控制的方式实现电信网动态路由优化的一种方案，目的是提高网络资源的利用率、网络运行的效率和可靠性。2.4.2蚂蚁算法在组合优化中的应用蚂蚁算法是近年来新出现的一种随机型搜索寻优算法,自从在TSP等著名问题中得到富有成效的应用之后,已引起越来越多的关注和重视.本文进一步将这种新型的生物优化思想扩展到其他一些组合优化难题,包括目前尚缺乏有效求解手段的多目标组合优化问题,从实验上探索了蚂蚁算法的优化能力,获得了满意的效果。2.5蚂蚁算法的未来发展自从1991年M.Dorigo等人首先提出蚁群算法以来,有许多研究人员对该算法进行研究,并成功地应用于解决复杂组合优化问题.在研究该算法的过程中,研究人员提出一些改进的算法。2.5.1MMAS(Max2Minantsystem)最大最小蚁群算法其基本思想是:只让最佳路径的外激素增加,加快收敛速度;为了避免算法过早收敛于非全局最优解,将各条路径可能的外激素浓度限于[τmin,τmax],超出这个范围的值被强制设为τmin或τmax,可以有效地避免某条路径上的信息量远大于其余路径,使蚂蚁都集中到同一条路径上,这样使算法不再扩散;将各条路径上外激素的起始浓度设为τmax,这样便可以更加充分地进行寻优。2.5.2具有变异特征的蚁群算法当群体的规模较大时,需要较长时间才能搜索到最佳路径.为了克服此缺点,受遗传算法中的变异算子的启发,提出具有变异特征的蚁群算法.算法中使用逆转变异方式,即设某个体走的路径是:i0i1i2⋯i(n-1),(i0,i1,⋯i(n-1)∈{0,1,2,⋯,n-1})如果满足其中s1,s2∈{0,1,⋯,(n-1)},%表示整除.将s1+1和s2这一段颠倒过来.此算法引入变异算子,经较少的进化代数就可以找到较好的解。2.5.3自适应蚁群算法在此算法中采用确定性选择和随机选择相结合的选择策略,并在搜索过程中动态调整确定性选择的概率.当进化到一定代数后,进化方向已经基本确定,对路径上的信息量进行动态调整,缩小最好和最差路径上的信息量的差距,并适当加大随机选择的概率,以利于对空间的完全搜索,可有效地克服基本蚁群算法进化速度慢及易陷入局部最优解的缺陷。2.5.4大规模集成电路综合布线大规模集成电路中的综合布线可以采用蚁群算法的思想来进行(在布线过程中，各个引脚对蚂蚁的引力可根据引力函数来计算。各个线网Agent根据启发策略，象蚁群一样在开关盒网格上爬行，所经之处便布上一条金属线，历经一个线网的所有引脚之后，线网便布通了。给定一个开关盒布线问题，问题的计算量是固定不变的。主要由算法的迭代次数决定，而迭代次数由Agent的智能和开关盒问题本身的性质确定蚁群算法本身的并行法，使之比较适合于解决布线问题。2.5.5电信网络路由电信网络中的路由是通过路由表进行的。在每个节点的路由表中!对每个目的节点都列出了与该节点相连的节点，当有数据包到达时，通过查询路由表可知道下一个将要到达的节点，首先对路由表中的信息素强度进行初始化。在节点Xi以节点i为目的地址，邻节点为J处的信息素强度为从X经节点J到节点i路径的最小费用值。然后周期性地释放蚂蚁来进行路由。并修改相应的信息素的值。无论呼叫是均匀分布还是集分布，利用蚁群算法所得呼叫拒绝率和平均路径长度均小于最小负载法结果:在呼叫符合集中分布时，蚁群算法所得呼叫拒绝率低于最短路径法。第3章开发工具3.1软件环境装有JDK的JAVA环境的计算机，由于蚂蚁算法演示是用JAVA做的一个小程序，所以在装有JAVA环境的机子上都能够运行。3.2其他资料JAVA工具书，软件工程工具书。面向对象工具书。3.3Java的简单介绍3.3.1网络时代的需要1995年在美国举办的一年一度的COMDEX展览会上,IBM公司总裁Gerstner作为第一个受邀请的发言人向全世界宣布人类已进入计算机技术发展的新时代——网络时代。在信息极度膨胀、爆炸的网络时代下,网络技术的发展为以网络为中心的计算提供了现实的可能和基础。这样,用户便不必关心自己计算机的性能和操作系统及应用软件如何,只要在网络上掌握更高一级的计算能力即可。这样,就势必要求有Java或类似的网络操作语言出现。3.3.2Internet的普及网络时代最突出的体现莫过于Internet(互连网)的广泛使用和迅速普及了。诞生十余年的Internet如今依然是应用开发的热点,并有广泛的市场和灿烂的前景。资料表明:这种开放式的计算机网络已覆盖了160多个国家和地区,连接的网络高达6万多个,终端用户超过3300万个。但是,目前的Internet依旧是个静态的媒介,几乎不比电话更具有交互性,它仅仅对用户的需求发送图片和文本,它所缺少的正是软件。这样便为Java或类似语言创造了广阔的市场。3.3.3跨平台可移植性的要求目前的计算机行业的现状使其工作难度变得越来越大。广大软件开发人员不仅需要在各种不兼容的软件平台、硬件平台和操作系统下工作,进行开发,而且还需要在各种不同的软件或硬件平台上使用互不相容的图形用户界面(GUI),所以人们手头现有的软件开发工具已远远不能满足网络时代的要求,开发一种网络上畅通无阻的编程语言势在必行,于是Java便应运而生。事实上,Java的前身Oak是一个最初为消费类电子产品开发的、险些夭折的产品,随着WWW的盛行,Sun公司发现其主要开发方向——平台无关性、系统安全性与可靠性一旦与WWW结构相结合将有广阔的市场。在经过一番努力和改后,Java才于1995年5月正式推出。3.4Java的主要特点3.4.1简单性简单性是Java语言设计的最基本的出发点,为了使程序员很容易进行编程并便于广大C++编程人员掌握,Java在设计上很大部分继承了C++的风格,并从以下几个方面使其更为简化:(1)摒弃了C++的不足之处和一些极少用到的功能,如操作符过载、多级继承性和各种自动强制性等;(2)增加了自动垃圾搜集功能,使程序员在开发过程中不必考虑存储器管理方面的问题,有利于减少编程错误的发生率;(3)减小了程序规模,使编程更为简单,用Java编写的应用程序Applets(小苹果)能完成某项特定任务,但其规模却不超过10kB。3.4.2安全性对于网络操作而言,最重要的莫不过是安全性了。针对此,Java提供了一种分布式编程环境。在其运行时间系统中,内置了防病毒和损害文件系统的保护机制,对于用户来说,即使是从Internet上卸载或者修改Java的应用程序,也是非常安全的。并且,在网络环境中,用户终端机上的应用程序是经过Java一级一级传译的,禁止其他未授权的代码对其进行干涉,更加保证了程序的安全性。3.4.3面向对象性Java具有许多面向对象的功能特性,如代码重用、代码扩展及动态应用等优点,基本上与C++相同。但它摒弃了C++的复杂性,扩展了对象模型,并对C++作了功能扩充,以提供更多的动态解决方法。事实上,在Java语言中,除了原始数据类型外,其余的成分均属Java的对象。3.4.4可靠性Java为了保证编写的软件的可靠性,对可能存在的问题采取了早期(编程期)和后期(运行期)两级动态检查的措施。此外,为减少开发人员的出错机会,Java还摒弃了C语言不易掌握、常常引起系统崩溃的指针操作功能,并增加了自动内存管理功能,从而排除了导致Java应用程序运行不稳定的一个重要因素。3.4.5解释性Java是一种解释执行语言,其运行环境是在Java虚拟机上的,而虚拟机又是独立于各种硬件平台上的,所以Java解释程序可以在任何机器上直接执行Java字节代码。而且Java应用程序在编译期产生的各种信息作为字节码流的一部分,在运行期间仍可使用,因而Java应用软件也更易于调试。除上述优点以外,Java还具有多线程动态性、系统结构中立性和可移植性等特点。正因如此,Java的出现给Internet带来了新的希望和无限生机。迄今,计算机行业内除了DEC以外的,诸如Oracle、IBM、Microsoft、SGI等所有的大公司都宣布支持Java。第4章具体的功能结构4.1系统的结构总框图、蚂蚁算法蚂蚁算法程序算法Ant.java画图操作程序Antcolony.java初始化图形界面初始化蚂蚁类面版设置Config.java地图库程序map.java建立蚂蚁对象图形化蚂蚁蚂蚁决策主程序画障碍物处理动画过程信息素释放程序Pheromone.java蚂蚁属性程序设计SetInt.java地图编辑MapPad.java动画运行过程蚂蚁之间的信息交流程序初始化蚂蚁属性蚂蚁属性面版设置初始化信息素增加该点的信息素消散信息素画布程序初始化地图编辑器控制面版程序画图地图库信息画边框画分形图各点地图坐标读出数据更改记录数据更新蚂蚁属性初始化蚂蚁属性4.2蚂蚁算法的主要步骤第一步：判断蚂蚁是否已经找到目标点（在蚂蚁没有找到食物之前，目标点是事物，找到食物后，目标点则换成蚂蚁的窝）；实现代码：if(Judged==false){if(JudgeEnd()){//判断目前蚂蚁是否已经到了目标点，，如果找到了目标点那么就退出该程序Judged=true;return;}}第二步：计算蚂蚁的主方向，也就是让蚂蚁的爬动有一个惯性，当没有信息素做指导的时候蚂蚁就按照主方向运动；实现代码：privatedoubleSelectDirect(){//选择方向，最后选择的方向为主方向加一个随机扰动doubledirect,e=0;if(Main_direct<0){//如果目前还没有主方向角，就随机的选择一个 e=2*Math.PI*Math.random();Main_direct=e;}//选择主方向角direct=Main_direct;//做一个随机模型，产生两个随机数，x,y都是[0,1]内的，这样x^2-y^2就是一个[-1，1]的随机数，并且在0点附近的概率大，两边小doublere=Math.random();doublere1=Math.random();direct+=Math.PI*(re*re-re1*re1)/2;if(re<0.02){//以小一定的概率0.02改变主方向的值，主方向的选取为从蚂蚁记住的点中随机选一个点，计算当前点和这个点之间的方向角。intsize=(int)(re1*memory)+1;if(HistoryPoint.size()>size){Pointpt=(Point)(HistoryPoint.elementAt(HistoryPoint.size()-size));if(pt.x!=nowPt.x||pt.y!=nowPt.y){Main_direct=GetDirection(pt,nowPt);}}}returndirect;第三步：开始搜索自己周围的空间信息，包括有多少信息素，是否有障碍物；实现代码：//开始搜索环境，搜索的空间是以当前点为中心，VR为半径的四方形内，即VR/2*VR/2的正方形for(intx=-VR;x<=VR;x++){for(inty=-VR;y<=VR;y++){if(x!=0||y!=0){if(maxphe<phe){//如果当前点的信息素是0，则表示蚂蚁还在窝里，如果是1，就要根据随机数//以mistake来决定蚂蚁犯错误的概率，即如果犯错误，它就不按信息素最大的方向走doublera=Math.random();if(here==0||ra>mistake){booleanfound=false;//查一下内存最近走过的的点数，从而避免当地转圈intsize=HistoryPoint.size();intminsize=memory;if(size<memory)minsize=size;for(inti=size-1;i>=size-minsize;i--){Pointpt=(Point)(HistoryPoint.elementAt(i));if(pt.x==xx&&pt.y==yy){found=true;break;}}if(!found){//如果没有原地转圈，那么记录信息素。maxphe=local_colony.Pheromone_grid[1-kind][xx][yy];deltx=x;delty=y;}}//endhere==0||ra>0.001}//endmaxphe<here}//endifx!=0}//endfory}//endforxPointpt;第四步：根据信息素的大小决定蚂蚁的移动方向；实现代码：//根据获得的信息的来的位移量deltx,delty，来具体的进行移位pt=Evade_obs(deltx,delty);第五步：根据决策的目标进行移动，其中包括遇见障碍的躲避和洒下自己的信息素。（1）躲避障碍物如果遇到障碍物，就根据主方向来确定位移，如果主方向也有障碍物了，那蚂蚁就会随机变换自己的主方向。实现代码：if(pt.x==nowPt.x&&pt.y==nowPt.y){pt=Evade_obs(deltx1,delty1);}（2）洒下自己的信息素在本程序中，蚂蚁洒下信息素的功能是通过一个子程序实现的，实现代码：if(Pheromone_count<=0)return;//决定释放信息素的种类intkind=FoundTimes%2;//获得当前点环境已有信息素的值intPhec=local_colony.Pheromone_grid[kind][lastPt.x][lastPt.y];booleanofound=false;if(Phec!=0){//如果当前点已经有信息素了在信息素向量中查找该点的信息for(inti=0;i<local_colony.phe.size();i++){Pheromoneph=(Pheromone)(local_colony.phe.elementAt(i));if(lastPt.x==ph.x&&lastPt.y==ph.y&&ph.kind==kind){//找到了，则看看蚂蚁所在的位置是否是刚刚走过的，如果不是才撒信息素intsize=HistoryPoint.size();//如果在表中找到信息素，则用ofound记录。ofound=true;booleanfound=false;if(size>4){for(intj=size-4;j<size-1;j++){Pointpt=(Point)(HistoryPoint.elementAt(j));if(pt.x==lastPt.x&&pt.y==lastPt.y){//如果当前点重复了以前走过的路，就不释放found=true;break;}}}if(!found){//如果当前点不重复，则开始撒ph.Add(Phe);local_colony.Pheromone_grid[kind][lastPt.x][lastPt.y]+=Phe;//让还剩下的信息素总量减少Pheromone_count-=Phe;}break;}}}if(Phec==0||!ofound){//如果当前环境没有信息素，或者当前环境的信息素来自窝或者食物，则新建一个信息素元素放到列表中Pheromoneph=newPheromone(lastPt.x,lastPt.y,local_colony.phe.size(),local_colony.Delimiter,id,local_colony,Phec,kind);ph.Add(Phe);local_colony.Pheromone_grid[kind][lastPt.x][lastPt.y]+=Phe;local_colony.phe.addElement(ph);//让还剩下的信息素总量减少Pheromone_count-=Phe;}//根据还剩下信息素的量调整释放信息素的数值Phe，//把剩余信息量看成数组count(n)，count(n)以几何级数的速度递减，这样，蚂蚁刚走出的地方信息素远远高于后走的地方Phe=(int)(0.005*Pheromone_count);//如果剩余信息素已经太小了，则按照等差数列递减if(Phe<=10)Phe=10;}第5章系统的实现5.1蚁群算法的实现结果程序执行后的到的结果如图：程序运行说明：浅蓝色的点表示食物，黄色的点表示窝，雾状的点表示蚂蚁留下的信息素，红色的点表示障碍物，白色的动点就是蚂蚁了（此图中还没有开始执行，所以暂时没有白色的点）。按设置按钮你可以更改一些环境变量，也可以更改单个蚂蚁的属性。在设置参数窗口中显示了整个蚂蚁群中找到的从它的窝到食物的最短路径。预期的结果：

各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种信息素，吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物！有些蚂蚁并没有象其它蚂蚁一样总重复同样的路，他们会另辟蹊径，如果令开辟的道路比原来的其他道路更短，那么，渐渐，更多的蚂蚁被吸引到这条较短的路上来。最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复着。下面是程序运行的连续截图：上图是刚开是执行时，白色的蚂蚁从黄色的窝中出来，是按随机的方向出发，所以看上去基本上是个圆。上图中是一只蚂蚁找到了左下角的事物，随即将窝作为目标点，向窝移动，并在一边向窝移动的过程中一边留下信息素（蓝色的轨迹），其他的蚂蚁仍在寻路中。从上图中我们可以看到，其他蚂蚁找到了食物，在回窝的过程中，它根据以前的蚂蚁留下的信息素找到了路径。看上图，一只蚂蚁在找到事物回窝的过程中，遇到了障碍（图中圆圈标记处），此时周围也没有其他的信息素，所以就根据主方向来确定位移，如果主方向也有障碍物了，那蚂蚁就会随机变换自己的主方向。在此图中我们追踪刚才遇见障碍的那只蚂蚁（图中圆圈标记处），由于在它在移动过程中又遇到了其他蚂蚁留下的信息素，所以它后面的路径就会沿着以前的蚂蚁的路径。上图是在程序执行了比较长一段时间后的截图，由图中我们可以看出越来越多的蚂蚁集中到一条比较短的路径上，在这条路径上留下的信息素也比较多，其他的路径由于不是最优解，走过的蚂蚁比较少，留下的信息素也就比较少，信息素的保留有一定的时间的，如此循环最终该路径就没有蚂蚁路过，该路径就淘汰。算法的不足和改进6.1算法的不足虽然蚁群算法已经被证明是一种有效的解决组合优化问题的方法，但是由于问世的时间比较短，还存在如下不足：1.限于局部最友解。从算法的性质而言，蚁群算法也是在寻找一个比较好的局部最优解，而不是强求是全局最优解。2.工作过程的中间停滞问题。和算法开始时收敛速度一样，在算法工作过程当中，迭代到一定次数后，蚂蚁也可能在某个或些局部最优解邻域附近发生停滞。3.较长的搜索时间。尽管和其他算法相比，蚁群算法在迭代次数和解的质量上都有一定的优势，但是对于目前计算机网络的实际情况，还是需要较长的搜索时间。虽然计算机计算速度的提高和蚁群算法的并行性在一定程度上可以缓解这一问题，但是对于大规模复杂的计算机网络，这还是一个很大的障碍。4蚂蚁的数量影响算法的性能实验前提:其他的参数值都不变图1蚂蚁的数量为10的结果图2蚂蚁的数量为50的结果由实验结果可知,算法的性能随着蚁群数量的增加有很大提高,但是运行时间也延长了不少。所以,选择蚁群数量取决于应用场合对算法的要求。蚁群算法存在很多有待改进的地方。文中只是对通过实验发现的不稳定因素做了简要的分析,因为实验是有偶然性的,所以发现的问题和对问题的分析只是一种探讨性的研究。蚁群算法中如何调整信息素将是一个难题,同时也是以后研究的重点。6.2算法的改进6.2.1信息素更新参数微调如何在计算过程中跟踪并调整DiscountDown和DiscountUp值呢？可以参照每只蚂蚁在某一时刻的遍历次数来决定。算法如下:(1)求t时刻所有蚂蚁运行次数的平均值EV(t):（6-2-1）(2)统计运行次数大于EV(t)α1倍的蚂蚁个数β1(t),其中α1是自定义的。β1(t)的初始值为0,遍历所有的ant(i,t):（6-2-2）统计运行次数小于EV(t)α2倍的蚂蚁个数β2(t),其中α2是自定义的。β2(t)的初始值为0,遍历所有的ant(i,t):（6-2-3）(3)分别计算比率（6-2-4）(4)如果γ1大于设定的上限值,则说明部分路径上的信息素偏高,为了均衡信息素,需要缓减信息素削弱速度,将DiscountDown和DiscountUp值减小。如果γ2小于设定的下限值,则说明信息素在路径上的分布过于均衡,应该加大差距,增加削弱速度,需要将DiscountDown和DiscountUp值增大。需要注意的是,这种改进方式是有时段限制的,特别适用于所有蚂蚁自由选择完路径之后到有近三分之一的蚂蚁找到相同路径这段时间内调整。因为再往后调整将严重影响收敛效率。6.2.2全局调整类似于MDorigo信息素更新算法中的全局调整。设置一个变量recordShort,记录所有蚂蚁到目前为止所能找到的最短路径。自定义时间序列t[i]。recordShort是随时更新的,每当一个蚂蚁找到路径时,就和recordShort比较,若更小,则更新recordShort值,同时根据时间序列t[i],在相应时间点加强recordShort所记录路径的信息素。实验表明,这种方式能够提高蚁群算法的正确性。6.2.3信息素值微调蚁群算法中一个常见的问题是容易产生早熟现象。即在某些时刻,部分路径上的信息素值与其他路径上的信息素值偏差太大,会影响结果的正确性。因此对偏差太大的值进行调整是必要的,比较著名的方法是设置MAX和MIN值,超过上下限值的信息素都被强制限制为MAX和MIN值,算法如下:(1)求所有路径(信息素≠0)上的信息素的平均值EV;(2)将所有大于EVa倍的信息素相对于EV减半(其中a是自定义的)。（6-2-1）这样做的优点是偏差最大的值调整幅度最大。6.3一种先进的蚂蚁算法——智能蚂蚁算法6.3.1取消外激素外激素是蚁群算法中蚂蚁实现通信的媒介,指导蚂蚁的前进方向。但是,由于蚂蚁的每一步运动都要更新外激素,要占用大量的CPU时间。通过对蚁群算法的考察可以发现,由于局部更新的作用,除最优路径外的所有边,其外激素水平相差无几。而最优路径与其它路径的外激素水平则差异巨大。这在搜索的后期尤其明显。因此,如果取消外激素,即以q0的比例选择最优路径,以1-q0的比例选择其它路径,可以大量减少计算,同时搜索的性能不会有太大的变化。实际上,在智能蚂蚁系统中,有两个比例参数和,分别代表选择全局最优路径和上次迭代搜索中最优路径的比例(+<1)。通过引进,蚂蚁的搜索范围不局限于全局最优路径的周围,这样,可以避免重复搜索,也就达到了蚁群算法中局部更新的目的。6.3.2自动调节选择最优路径的比例相对距离,给定两条周游路线t1,t2,t1相对t2的距离为