java基于蚁群算法路由选择可视化动态模拟
蚁群算法是一种新生的算法，具有很强的通用性。从提出到现在，仅短短10余年的时间，但是在离散型组合优化问题中。表现很突出，所以一起人们的关注。目前蚁群算法的研究者主要集中在比利时、意大利、德国等国家，美国和日本在近几年也开始了对蚁群算法的研究。国内的研究开始于1998年末。主要在上海、北京、东北少数几个学校和研究所开展了此项工作，主要围绕TSP及相关问题的实验仿真，少数涉及通信网络的路由选择、负载平衡、电力系统的故障检测以及蚁群算法在连续系统应用，如函数逼近等方面应用的尝试。在国外，蚁群算法已经在集成电路布线、网络路由选择、机器人线路规划等方面得到了应用。自1998年，第一届蚂蚁优化国际研讨会召开以来，已经是第三届了，大大推动了蚁群算法的发展。蚁群算法已经引起越来越多的关注，尽管还缺乏完善的理论分析，对它的有效性也没有出严格的数学解释，但是回顾模糊控制的发展历史，理论的不完善并不妨碍应用，有时应用是超前于理论的，并推动理论的研究。我们相信蚁群算法必将得到广泛的应用。
2.1蚂蚁算法的产生
蚂蚁是自然界中常见的一种生物，人们对蚂蚁的关注大都是因为“蚂蚁搬家，天要下雨”之类的民谚。然而随着近代仿生学的发展，这种似乎微不足道的小东西越来越多地受到学者们的关注。1991年M·Dorigo等人首先提出了蚁群算法（Ant Colony Algorithms）。人们开始了对蚁群的研究：相对弱小，功能并不强大的个体是如何完成复杂的工作的（如寻找到食物的最佳路径并返回等）。在此基础上一种很好的优化算法逐渐发展起来。
2.2 蚂蚁算法的算法思想
蚁群算法是受到对真实的蚁群行为的研究的启发而提出的.为了说明人工蚁群系统的原理,先从蚁群搜索食物的过程谈起.象蚂蚁、蜜蜂、飞蛾等群居昆虫,虽然单个昆虫的行为极其简单,但由单个简单的个体所组成的群体却表现出极其复杂的行为,原因是什么呢?仿生学家经过大量细致观察研究发现,蚂蚁个体之间是通过一种称之为外激素(pheromone)的物质进行信息传递的.蚂蚁在运动过程中,能够在它所经过的路径上留下该种物质,而且蚂蚁在运动过程中能够感知这种物质,并以此指导自己的运动方向,因此,由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大.蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。蚂蚁个体之间的信息交换是一个正反馈过程。
说了这么多，蚂蚁究竟是怎么找到食物的呢？
在没有蚂蚁找到食物的时候，环境没有有用的信息素，那么蚂蚁为什么会相对有效的找到食物呢？这要归功于蚂蚁的移动规则，尤其是在没有信息素时候的移动规则。首先，它要能尽量保持某种惯性，这样使得蚂蚁尽量向前方移动（开始，这个前方是随机固定的一个方向），而不是原地无谓的打转或者震动；其次，蚂蚁要有一定的随机性，虽然有了固定的方向，但它也不能像粒子一样直线运动下去，而是有一个随机的干扰。这样就使得蚂蚁运动起来具有了一定的目的性，尽量保持原来的方向，但又有新的试探，尤其当碰到障碍物的时候它会立即改变方向，这可以看成一种选择的过程，也就是环境的障碍物让蚂蚁的某个方向正确，而其他方向则不对。这就解释了为什么单个蚂蚁在复杂的诸如迷宫的地图中仍然能找到隐蔽得很好的食物。
当然，在有一只蚂蚁找到了食物的时候，其他蚂蚁会沿着信息素很快找到食物的。
蚂蚁如何找到最短路径的？这一是要归功于信息素，另外要归功于环境，具体说是计算机时钟。信息素多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多（或者较长的路上蚂蚁多，这也无关紧要）。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素……；而长的路正相反，因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就近似找到了。也许有人会问局部最短路径和全局最短路的问题，实际上蚂蚁逐渐接近全局最短路的，为什么呢？这源于蚂蚁会犯错误，也就是它会按照一定的概率不往信息素高的地方走而另辟蹊径，这可以理解为一种创新，这种创新如果能缩短路途，那么根据刚才叙述的原理，更多的蚂蚁会被吸引过来。
2.3蚁群算法原理
蚁群算法是一种由于受自然界生物的行为启发而产生的“自然”算法。它是从对蚁群行为的研究中产生的。正如M·Dorigo等人在关于蚁群算法的第1 篇文章中指出的：蚁群中的蚂蚁以“外激素”（Stigmergy）为媒介的间接的异步的联系方式是蚁群算法的最大的特点。蚂蚁在行动（寻找食物或者寻找回巢的路径）中，会在它们经过的地方留下一些化学物质（我们称之为“外激素”）。这些物质能被同一蚁群中后来的蚂蚁感受到，并作为一种信号影响后到者的行动（具体表现在后到的蚂蚁选择有这些物质的路径的可能性，比选择没有这些物质的路径的可能性大得多），而后到者留下的外激素会对原有的外激素进行加强，并如此循环下去。这样，经过蚂蚁越多的路径，在后到蚂蚁的选择中被选中的可能性就越大（因为残留的外激素浓度较大的缘故）。由于在一定的时间内，越短的路径会被越多的蚂蚁访问，因而积累的外激素也就越多，在下一个时间内被其他的蚂蚁选中的可能性也就越大。这个过程会一直持续到所有的蚂蚁都走最短的那一条路径为止。（如图）
图1中有一条蚂蚁经过的路径，我们假设a点是食物，而e点是蚂蚁的巢穴，如图1 a）所示。在某一个时刻忽然有一个障碍物出现在蚂蚁经过的路径中，原有的路径被切断，从a点到e点的蚂蚁就必须在b点决定应该往左还是往右走。而从a点到e点的蚂蚁也必须在d点决定选择哪条路径。这种决定会受到各条路径上以往蚂蚁留下的外激素浓度（即残留信息浓度）的影响。如果向右的路径上的外激素浓度比较大，那么向右的路径被蚂蚁选中的可能性也就比较大一些。但是对障碍出现后第一个到达b点或d点的蚂蚁而言，因为没有外激素的影响，所以它们选择向左或者向右的可能性是一样的，如图1 b）所示。若以从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.1 MMAS ( Max2Min ant system) 最大最小蚁群算法
其基本思想是:只让最佳路径的外激素增加,加快收敛速度;为了避免算法过早收敛于非全局最优解,将各条路径可能的外激素浓度限于[τ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路径的最小费用值。然后周期性地释放蚂蚁来进行路由。并修改相应的信息素的值。无论呼叫是均匀分布还是集分布，利用蚁群算法所得呼叫拒绝率和平均路径长度均小于最小负载法结果:在呼叫符合集中分布时，蚁群算法所得呼叫拒绝率低于最短路径法。
4.1 系统的结构总框图
4.2 蚂蚁算法的主要步骤
第一步：判断蚂蚁是否已经找到目标点（在蚂蚁没有找到食物之前，目标点是事物，找到食物后，目标点则换成蚂蚁的窝）；
实现代码：
if(Judged==false){
if(JudgeEnd()){
//判断目前蚂蚁是否已经到了目标点，，如果找到了目标点那么就退出该程序
Judged=true;
return;
}
}
第二步：计算蚂蚁的主方向，也就是让蚂蚁的爬动有一个惯性，当没有信息素做指导的时候蚂蚁就按照主方向运动；
实现代码：
private double SelectDirect(){
//选择方向，最后选择的方向为主方向加一个随机扰动
double direct,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点附近的概率大，两边小
double re=Math.random();
double re1=Math.random();
direct+=Math.PI*(re*re-re1*re1)/2;
if(re<0.02){
//以小一定的概率0.02改变主方向的值，主方向的选取为从蚂蚁记住的点中随机选一个点，计算当前点和这个点之间的方向角。
int size=(int)(re1*memory)+1;
if(HistoryPoint.size()>size){
Point pt=(Point)(HistoryPoint.elementAt(HistoryPoint.size()-size));
if(pt.x!=nowPt.x||pt.y!=nowPt.y){
Main_direct=GetDirection(pt,nowPt);
}
}
}
return direct;
第三步：开始搜索自己周围的空间信息，包括有多少信息素，是否有障碍物；
实现代码：
//开始搜索环境，搜索的空间是以当前点为中心，VR为半径的四方形内，即VR/2*VR/2的正方形
for(int x=-VR;x<=VR;x++){
for(int y=-VR;y<=VR;y++)
{
if(x!=0||y!=0){
if(maxphe<phe){
//如果当前点的信息素是0，则表示蚂蚁还在窝里，如果是1，就要根据随机数
//以mistake来决定蚂蚁犯错误的概率，即如果犯错误，它就不按信息素最大的方向走
double ra=Math.random();
if(here==0||ra>mistake){
boolean found=false;
//查一下内存最近走过的的点数，从而避免当地转圈
int size=HistoryPoint.size();
int minsize=memory;
if(size<memory)minsize=size;
for(int i=size-1;i>=size-minsize;i--){
Point pt=(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;
}
}//end here==0||ra>0.001
}//end maxphe<here
}//end if x!=0
}//end for y
}//end for x
Point pt;
第四步：根据信息素的大小决定蚂蚁的移动方向；
实现代码：
//根据获得的信息的来的位移量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;
//决定释放信息素的种类
int kind=FoundTimes%2;
//获得当前点环境已有信息素的值
int Phec=local_colony.Pheromone_grid[kind][lastPt.x][lastPt.y];
boolean ofound=false;
if(Phec!=0){
//如果当前点已经有信息素了在信息素向量中查找该点的信息
for(int i=0;i<local_colony.phe.size();i++){
Pheromone ph=(Pheromone)(local_colony.phe.elementAt(i));
if(lastPt.x==ph.x&&lastPt.y==ph.y&&ph.kind==kind){
//找到了，则看看蚂蚁所在的位置是否是刚刚走过的，如果不是才撒信息素
int size=HistoryPoint.size();
//如果在表中找到信息素，则用ofound记录。
ofound=true;
boolean found=false;
if(size>4){
for(int j=size-4;j<size-1;j++){
Point pt=(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){
//如果当前环境没有信息素，或者当前环境的信息素来自窝或者食物，则新建一个信息素元素放到列表中
Pheromone ph=new Pheromone(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;
}
未完待续。。。