基于JAVA的路由选择网络层的协议开发课程设计.docx

上传人:b****5 文档编号:14845787 上传时间:2023-06-27 格式:DOCX 页数:33 大小:163.37KB
下载 相关 举报
基于JAVA的路由选择网络层的协议开发课程设计.docx_第1页
第1页 / 共33页
基于JAVA的路由选择网络层的协议开发课程设计.docx_第2页
第2页 / 共33页
基于JAVA的路由选择网络层的协议开发课程设计.docx_第3页
第3页 / 共33页
基于JAVA的路由选择网络层的协议开发课程设计.docx_第4页
第4页 / 共33页
基于JAVA的路由选择网络层的协议开发课程设计.docx_第5页
第5页 / 共33页
基于JAVA的路由选择网络层的协议开发课程设计.docx_第6页
第6页 / 共33页
基于JAVA的路由选择网络层的协议开发课程设计.docx_第7页
第7页 / 共33页
基于JAVA的路由选择网络层的协议开发课程设计.docx_第8页
第8页 / 共33页
基于JAVA的路由选择网络层的协议开发课程设计.docx_第9页
第9页 / 共33页
基于JAVA的路由选择网络层的协议开发课程设计.docx_第10页
第10页 / 共33页
基于JAVA的路由选择网络层的协议开发课程设计.docx_第11页
第11页 / 共33页
基于JAVA的路由选择网络层的协议开发课程设计.docx_第12页
第12页 / 共33页
基于JAVA的路由选择网络层的协议开发课程设计.docx_第13页
第13页 / 共33页
基于JAVA的路由选择网络层的协议开发课程设计.docx_第14页
第14页 / 共33页
基于JAVA的路由选择网络层的协议开发课程设计.docx_第15页
第15页 / 共33页
基于JAVA的路由选择网络层的协议开发课程设计.docx_第16页
第16页 / 共33页
基于JAVA的路由选择网络层的协议开发课程设计.docx_第17页
第17页 / 共33页
基于JAVA的路由选择网络层的协议开发课程设计.docx_第18页
第18页 / 共33页
基于JAVA的路由选择网络层的协议开发课程设计.docx_第19页
第19页 / 共33页
基于JAVA的路由选择网络层的协议开发课程设计.docx_第20页
第20页 / 共33页
亲,该文档总共33页,到这儿已超出免费预览范围,如果喜欢就下载吧!
下载资源
资源描述

基于JAVA的路由选择网络层的协议开发课程设计.docx

《基于JAVA的路由选择网络层的协议开发课程设计.docx》由会员分享,可在线阅读,更多相关《基于JAVA的路由选择网络层的协议开发课程设计.docx(33页珍藏版)》请在冰点文库上搜索。

基于JAVA的路由选择网络层的协议开发课程设计.docx

基于JAVA的路由选择网络层的协议开发课程设计

课程设计

 

题目:

基于JAVA的路由选择网络层的协议开发

 

简介:

组合优化问题是人们在工程技术、科学研究和经济管理等众多领域经常遇到的问题,其中许多问题如旅行商问题、0-1背包问题、图着色问题、装箱问题等,都被证明为NP-困难问题。

用确定性的优化算法求NP完全问题的最优解,其计算时间使人难以忍受或因问题的高难度而使其计算时间随问题规模的增加以指数速度延长。

用近似算法如启发式算法求解得到的近似解不能保证其可行性和最优性,甚至无法知道所得解同最优解的近似程度。

第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如今依然

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 农林牧渔 > 林学

copyright@ 2008-2023 冰点文库 网站版权所有

经营许可证编号:鄂ICP备19020893号-2