蚁群优化算法的JAVA实现

1蚁群优化算法的JAVA实现一、蚁群算法简介蚁群算法是群智能算法的一种，所谓的群智能是一种由无智能或简单智能的个体通过任何形式的聚集协同而表现出智能行为，它为在没有集中控制且不提供全局模型的前提下寻找复杂的分布式问题求解方案提供了基础，比如常见的蚂蚁觅食，大雁南飞等行为。蚁群算法是模拟自然界中蚂蚁觅食的一种随机搜索算法，由Dorigo等人于1991年在第一届欧洲人工生命会议上提出[1]。二、蚁群算法的生物原理通过观察发现，蚁群在觅食的时候，总能找到一条从蚁巢到食物之间的一条最短的路径。这个现象引起了生物学家的注意，根据研究，原来是蚂蚁在行进的过程中，会分泌一种化学物质——信息素，而蚂蚁在行进时，总是倾向于选择信息素浓度比较高的路线。这样，在蚁巢和食物之间假如有多条路径，初始的时候，每条路径上都会有蚂蚁爬过，但是随着时间的推迟，单位时间内最短的那条路上爬过的蚂蚁数量会比较多，释放的信息素就相对来说比较多，那么以后蚂蚁选择的时候会大部分都选择信息素比较多的路径，从而会把最短路径找出来。蚁群算法正是模拟这种蚁群觅食的原理，构造人工蚂蚁，用来求解许多组合优化问题。有关蚁群算法的详细信息，可参考[2]——[5]。三、蚁群算法的JAVA实现我个人认为利用JAVA编写一些计算密集型的算法不是一个好的选择。本身一些算法是要要求高效率的，但是我感觉JAVA语言的性能不够，所以编写算法最好用c，其次也可以用c++。当然，这仅是一家之言，欢迎拍砖。四、算法说明算法以求解TSP问题为例，用来演示ACO的框架。算法设定了两个类，一个是ACO，用来处理文件信息的读入，信息素的更新，路径的计算等；另一个是ant，即蚂蚁的信息。算法中用到的数据，可以从TSPLib上面下载，使用的是对称TSP数据，为了简化算法的代码，下载下来的数据需要做一个简单处理，即把TSP文件中除去城市节点信息部分之外的内容都删除掉，然后在文件首插入一行，写入此文件包含的城市的数目，以att48.tsp为例，下载下来的文件内容如下：2NAME:att48COMMENT:48capitalsoftheUS(Padberg/Rinaldi)TYPE:TSPDIMENSION:48EDGE_WEIGHT_TYPE:ATTNODE_COORD_SECTION1673414532223310355301424440184153082164467608445877573371687265126896898188510111220491154682606125989287313470626741446122035156347268316610766917761151841874623590197732472320590035612144833369226101111023519921822416332809254307232226675100627755548192875413981293177756307352450631754528013232453305336426317334460811983523221636724837793777624595387392224433934842829406271213541498514042191615694372804899447509323945102676466807299347518532584830231942EOF修改之后，内容变为如下：481673414532223310355301424440184153082164467608445877573371687265126896898188510111220491154682606125989287313470626741446122035156347268316610766917761151841874623590197732472320590035612144833369226101111023519921822416332809254307232226675100627755548194287541398129317775630735245063175452801323245330533642631733446081198352322163672483779377762459538739222443934842829406271213541498514042191615694372804899447509323945102676466807299347518532584830231942这么做仅是为了方便处理，也可以根据TSPLib给出的文件格式而自己写代码读取。算法流程图此处实现的算法应该是AS（AntSystem），其算法流程如下：算法代码[java]viewplaincopypackagetspsolver;5importjava.util.Random;/***蚂蚁类*@authorFashionXu*/publicclassant{/***蚂蚁获得的路径*/publicint[]tour;//unvisitedcity取值是0或1，//1表示没有访问过，0表示访问过int[]unvisitedcity;/***蚂蚁获得的路径长度*/publicinttourlength;intcitys;/***随机分配蚂蚁到某个城市中*同时完成蚂蚁包含字段的初始化工作*@paramcitycount总的城市数量*/publicvoidRandomSelectCity(intcitycount){citys=citycount;unvisitedcity=newint[citycount];tour=newint[citycount+1];tourlength=0;for(inti=0;icitycount;i++){tour[i]=-1;unvisitedcity[i]=1;}longr1=System.currentTimeMillis();Randomrnd=newRandom(r1);intfirstcity=rnd.nextInt(citycount);unvisitedcity[firstcity]=0;tour[0]=firstcity;}/***选择下一个城市*@paramindex需要选择第index个城市了*@paramtao全局的信息素信息*@paramdistance全局的距离矩阵信息*/6publicvoidSelectNextCity(intindex,double[][]tao,int[][]distance){double[]p;p=newdouble[citys];doublealpha=1.0;doublebeta=2.0;doublesum=0;intcurrentcity=tour[index-1];//计算公式中的分母部分for(inti=0;icitys;i++){if(unvisitedcity[i]==1)sum+=(Math.pow(tao[currentcity][i],alpha)*Math.pow(1.0/distance[currentcity][i],beta));}//计算每个城市被选中的概率for(inti=0;icitys;i++){if(unvisitedcity[i]==0)p[i]=0.0;else{p[i]=(Math.pow(tao[currentcity][i],alpha)*Math.pow(1.0/distance[currentcity][i],beta))/sum;}}longr1=System.currentTimeMillis();Randomrnd=newRandom(r1);doubleselectp=rnd.nextDouble();//轮盘赌选择一个城市；doublesumselect=0;intselectcity=-1;for(inti=0;icitys;i++){sumselect+=p[i];if(sumselect=selectp){selectcity=i;break;}}if(selectcity==-1)System.out.println();tour[index]=selectcity;unvisitedcity[selectcity]=0;}/***计算蚂蚁获得的路径的长度*@paramdistance全局的距离矩阵信息*/7publicvoidCalTourLength(int[][]distance){tourlength=0;tour[citys]=tour[0];for(inti=0;icitys;i++){tourlength+=distance[tour[i]][tour[i+1]];}}}[java]viewplaincopypackagetspsolver;importjava.io.*;/***蚁群优化算法，用来求解TSP问题*@authorFashionXu*/publicclassACO{//定义蚂蚁群ant[]ants;intantcount;//蚂蚁的数量int[][]distance;//表示城市间距离double[][]tao;//信息素矩阵intcitycount;//城市数量int[]besttour;//求解的最佳路径intbestlength;//求的最优解的长度/**初始化函数*@paramfilenametsp数据文件*@paramantnum系统用到蚂蚁的数量*@throws如果文件不存在则抛出异常*/publicvoidinit(Stringfilename,intantnum)throwsFileNotFoundException,IOException{antcount=antnum;ants=newant[antcount];//读取数据int[]x;int[]y;Stringstrbuff;BufferedReadertspdata=newBufferedReader(newInputStreamReader(newFileInputStream(filename)));strbuff=tspdata.readLine();citycount=Integer.valueOf(strbuff);distance=newint[citycount][citycount];x=newint[citycount];y=newint[citycount];for(intcitys=0;cityscitycount;citys++){8strbuff=tspdata.readLine();String[]strcol=strbuff.split();x[citys]=Integer.valueOf(strcol[1]);y[citys]=Integer.valueOf(strcol[2]);}//计算距离矩阵for(intcity1=0;city1citycount-1;city1++){distance[city1][city1]=0;for(intcity2=city1+1;city2citycount;city2++){distance[city1][city2]=(int)(Math.sqrt((x[city1]-x[city2])*(x[city1]-x[city2])+(y[city1]-y[city2])*(y[city1]-y[city2]))+0.5);distance[city2][city1]=distance[city1][city2];}}distance[citycount-1][citycount-1]=0;//初始化信息素矩阵tao=newdouble[citycount][citycount];for(inti=0;icitycount;i++){for(intj=0;jcitycount;j++){tao[i][j]=0.1;}}bestlength=Inte