遗传算法和蚂蚁算法求解TSPJava版.docx

遗传算法和蚂蚁算法求解TSPJava版.docx

《遗传算法和蚂蚁算法求解TSPJava版.docx》由会员分享，可在线阅读，更多相关《遗传算法和蚂蚁算法求解TSPJava版.docx（37页珍藏版）》请在冰点文库上搜索。

遗传算法和蚂蚁算法求解遗传算法和蚂蚁算法求解TSPJava版版河北工业大学人工智能课程实验实验报告题目：

使用遗传算法和蚂蚁算法解决TSP问题专业：

软件工程班级：

软件122班姓名：

姚陈堃学号：

122590完成日期：

2015.5.19目录一、实验内容1二、实验目的1三、实验原理1四、源代码7五、实验结果25六、实验分析29一、一、实验内容实验内容旅行商问题，即TSP问题（TravelingSalesmanProblem）是数学领域中著名问题之一。

假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。

路径的选择目标是要求得的路径路程为所有路径之中的最小值。

本次实验要求利用遗传算法和蚂蚁算法分别对TSP问题求解，并要求求解时间和求解结果均在可接受范围内。

二、二、实验目的实验目的掌握遗传算法和蚂蚁算法的基本思想，并能结合实际问题对算法进行相应调整，最终解决问题。

三、三、实验原理实验原理1.遗传算法遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。

每个个体实际上是染色体带有特征的实体。

染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。

因此，在一开始需要实现从表现型到基因型的映射即编码工作。

由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。

这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。

下面是简单遗传算法的求解结构：

需要指出的是，适应度函数、选择、交叉和变异操作均要根据实际问题进行灵活变更，并非固定模式。

针对本次实验的TSP问题，下面给出我在遗传算法中采用的方法。

（1）适应度函数该函数是算法的关键，通过它对这个繁衍出来的后代进行评估打分。

在TSP问题中，路径越短，分数越高，故而适应度函数可设置为，不同的计算方法会影响算法的收敛速度，直接影响结果和性能。

（2）选择操作利用轮盘赌的方式选出优秀的物种，进入下一代。

选择概率的计算公式为，其中i表示种群中的任一物种；选择过程示意如下图所示。

考虑到优化算法性能，我加入了“精英保留策略”，即并非所有物种均参与赌轮，而是事先选出适应度最高的物种，复制若干进入下一代后，再让剩余的物种参与赌轮，最终形成新种群。

这样避免了因为概率原因，使得优秀物种沧海遗珠的情况发生，但这样做也容易陷入局部最优。

（3）交叉操作物种基因的编码形式是以“城市编号”为元素的，在实现交叉操作时首先任选一个位置作为起点，交换两个物种的后半段基因。

但需考虑的是，交换后的基因可能与物种已有的基因重复，故而需要再加上冲突处理操作。

交叉操作示意如下图所示。

（4）变异操作“变异”是跳出局部最优解的一个重要法宝。

我采用的是随机两个位置，逆转其之间的城市编号，即随机产生1和n之间的两相异整数k和m，若km，则交换两者数值后实行之前同样的操作。

2.蚂蚁算法蚂蚁算法是一种用来在图中寻找优化路径的机率型算法。

它由MarcoDorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为，其示意图如下图所示。

蚂蚁算法的主要原理有以下几点：

（1）蚂蚁在寻找食物源时，能在其走过的路上释放一种特殊的分泌物信息素（随着时间的推移该物质会逐渐挥发）,后来的蚂蚁选择该路径的概率与当时这条路径上该物质的强度成正比。

（2）当一定路径上通过的蚂蚁越来越多时，其留下的信息素轨迹也越来越多，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度。

（3）强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制,通过这种正反馈机制，蚂蚁最终可以发现最短路径。

（4）特别地，当蚂蚁巢穴与食物源之间出现障碍物时，蚂蚁不仅可以绕过障碍物，而且通过蚁群信息素轨迹在不同路径上的变化，经过一段时间的正反馈，最终收敛到最短路径上。

蚂蚁算法的基本求解步骤如下图所示：

四、四、源代码源代码根据伪代码及流程图，采用Java语言，在eclipse平台上分别编程实现利用遗传算法和蚂蚁算法解决TSP问题的程序。

1.遗传算法采用面向对象思想实现，分别建立了GeneticAlgorithm遗传算法类，SpeciesList种群链表类，SpeciesNode物种结点类，Constant常量类，Main主类，。

（1）GeneticAlgorithm遗传算法类publicclassGeneticAlgorithm（/开始遗传SpeciesNoderun（SpeciesListlist）（/创建初始种群createBeginningSpecies（list）;for（inti=1;i=Constant.DEVELOP_NUM;i+）（/选择select（list）;/交叉crossover（list）;/变异mutate（list）;returngetBest（list）;/创建初始种群voidcreateBeginningSpecies（SpeciesListlist）（/100%随机intrandomNum=（int）（Constant.SPECIES_NUM）;for（inti=1;ipoint.distance）（talentDis=point.distance;talentSpecies=point;point=point.next;/将最大适应度物种复制talentNum个SpeciesListnewSpeciesList=newSpeciesList（）;inttalentNum=（int）（list.speciesNum/4）;for（inti=1;i=talentNum;i+）（/复制物种至新表SpeciesNodenewSpecies=talentSpecies.clone（）;newSpeciesList.add（newSpecies）;/轮盘赌list.speciesNum-talentNum次introundNum=list.speciesNum-talentNum;for（inti=1;i=roundNum;i+）（/产生0-1的概率floatrate=（float）Math.random（）;SpeciesNodeoldPoint=list.head.next;/游标while（oldPoint!

=null&oldPoint!

=talentSpecies）/寻找表尾结点（if（rateConstant.pcl&rateConstant.pch）（SpeciesNodepoint=list.head.next;/游标Randomrand=newRandom（）;intfind=rand.nextInt（list.speciesNum）;while（point!

=null&find!

=0）/寻找表尾结点（point=point.next;find-;if（point.next!

=null）（intbegin=rand.nextInt（Constant.CITY_NUM）;/取point和point.next进行交叉，形成新的两个染色体for（inti=begin;iConstant.CITY_NUM;i+）（/找出point.genes中与point.next.genesi相等的位置fir/找出point.next.genes中与point.genesi相等的位置secintfir,sec;for（fir=0;!

point.genesfir.equals（point.next.genesi）;fir+）;for（sec=0;!

point.next.genessec.equals（point.genesi）;sec+）;/两个基因互换Stringtmp;tmp=point.genesi;point.genesi=point.next.genesi;point.next.genesi=tmp;/消去互换后重复的那个基因point.genesfir=point.next.genesi;point.next.genessec=point.genesi;/变异操作voidmutate（SpeciesListlist）（/每一物种均有变异的机会,以概率pm进行SpeciesNodepoint=list.head.next;while（point!

=null）（floatrate=（float）Math.random（）;if（rateright）（inttmp;tmp=left;left=right;right=tmp;/逆转left-right下标元素while（leftpoint.distance）（bestSpecies=point;distance=point.distance;point=point.next;returnbestSpecies;

（2）SpeciesNode物种结点publicclassSpeciesNode（Stringgenes;/基因序列floatdistance;/路程floatfitness;/适应度SpeciesNodenext;floatrate;SpeciesNode（）（/初始化this.genes=newStringConstant.CITY_NUM;this.fitness=0.0f;this.distance=0.0f;this.next=null;rate=0.0f;/初始物种基因（随机）voidcreateByRandomGenes（）（/初始化基因为1-CITY_NUM序列for（inti=0;igenes.length;i+）（genesi=Integer.toString（i+1）;/获取随机种子Randomrand=newRandom（）;for（intj=0;jgenes.length;j+）（intnum=j+rand.nextInt（genes.length-j）;/交换Stringtmp;tmp=genesnum;genesnum=genesj;genesj=tmp;/初始物种基因（贪婪）voidcreateByGreedyGenes（）（Randomrand=newRandom（）;inti=rand.nextInt（Constant.CITY_NUM）;/随机产生一个城市作为起点genes0=Integer.toString（i+1）;intj;/终点intcityNum=0;do（cityNum+;/选出单源最短城市floatminDis=Integer.MAX_VALUE;intminCity=0;for（j=0;jConstant.CITY_NUM;j+）（if（j!

=i）（/判是否和已有重复booleanrepeat=false;for（intn=0;ncityNum;n+）（if（Integer.parseInt（genesn）=j+1）（repeat=true;/重了break;if（repeat=false）/没重（/判长度if（Constant.disMapijminDis）（minDis=Constant.disMapij;minCity=j;/加入到染色体genescityNum=Integer.toString（minCity+1）;i=minCity;while（cityNumConstant.CITY_NUM-1）;/计算物种适应度voidcalFitness（）（floattotalDis=0.0f;for（inti=0;iConstant.CITY_NUM;i+）（intcurCity=Integer.parseInt（this.genesi）-1;intnextCity=Integer.parseInt（this.genes（i+1）%Constant.CITY_NUM）-1;totalDis+=Constant.disMapcurCitynextCity;this.distance=totalDis;this.fitness=1.0f/totalDis;/深拷贝publicSpeciesNodeclone（）（SpeciesNodespecies=newSpeciesNode（）;/复制值for（inti=0;ithis.genes.length;i+）species.genesi=this.genesi;species.distance=this.distance;species.fitness=this.fitness;returnspecies;/打印路径voidprintRoute（）（System.out.print（最短路线：

）;for（inti=0;i）;System.out.print（genes0+n）;System.out.print（最短长度：

+distance）;（3）SpeciesList种群链表类publicclassSpeciesList（SpeciesNodehead;/头结点intspeciesNum;/物种数量SpeciesList（）（head=newSpeciesNode（）;speciesNum=Constant.SPECIES_NUM;/添加物种voidadd（SpeciesNodespecies）（SpeciesNodepoint=head;/游标while（point.next!

=null）/寻找表尾结点point=point.next;point.next=species;（4）Constant常量类publicclassConstant（staticintCITY_NUM;/城市数staticfinalintSPECIES_NUM=2000;/种群数staticfinalintDEVELOP_NUM=100;/进化代数staticfinalfloatpcl=0.6f,pch=0.95f;/交叉概率staticfinalfloatpm=0.4f;/变异概率staticfinalfloatdisMap;/地图数据static（/intcityPosition=（/（0,0,（12,32,（5,25,（8,45,（33,17,/（25,7,（15,15,（15,25,（25,15,（41,12;/10个城市（最优解:

147）/intcityPosition=（/（60,200,（180,200,（80,180,（140,180,/（20,160,（100,160,（200,160,（140,140,/（40,120,（100,120,（180,100,（60,80,/（120,80,（180,60,（20,40,（100,40,/（200,40,（20,20,（60,20,（160,20;/20个城市（最优解:

870）/城市坐标集合intcityPosition=（1304,2312,（3639,1315,（4177,2244,（3712,1399,（3488,1535,（3326,1556,（3238,1229,（4196,1004,（4312,790,（4386,570,（3007,1970,（2562,1756,（2788,1491,（2381,1676,（1332,695,（3715,1678,（3918,2179,（4061,2370,（3780,2212,（3676,2578,（4029,2838,（4263,2931,（3429,1908,（3507,2367,（3394,2643,（3439,3201,（2935,3240,（3140,3550,（2545,2357,（2778,2826,（2370,2975;/31个城市（最优解:

14700）/路径集合CITY_NUM=cityPosition.length;disMap=newfloatCITY_NUMCITY_NUM;for（inti=0;iCITY_NUM;i+）（for（intj=i;jCITY_NUM;j+）（floatdis=（float）Math.sqrt（Math.pow（cityPositioni0-cityPositionj0）,2）+Math.pow（cityPositioni1-cityPositionj1）,2）;disMapij=dis;disMapji=disMapij;（5）Main主类publicclassMain（publicstaticvoidmain（Stringargs）（/创建遗传算法驱动对象GeneticAlgorithmGA=newGeneticAlgorithm（）;/创建初始种群SpeciesListspeciesList=newSpeciesList（）;/开始遗传算法（选择算子、交叉算子、变异算子）SpeciesNodebestRate=GA.run（speciesList）;/打印路径与最短距离bestRate.printRoute（）;2.蚂蚁算法同样采用面向对象思想实现，分别建立了AntAlgorithm蚂蚁算法类，Ant蚂蚁类，CanReachCity候选结点类，Constant常量类，Main主类，Route路径类。

（1）AntAlgorithm蚂蚁算法类publicclassAntAlgorithm（privateintNC=1000;/迭代次数privateintantNum=100;/蚂蚁数量privateAntants;/蚁群privatefloatQ=1000.0f;privatefloatp=0.5f;/蒸发率floatminLength=Float.MAX_VALUE;/当前最短距离intminRoute;/当前最短路线AntAlgorithm（）（ants=newAntantNum;for（inti=0;iantNum;i+）antsi=newAnt（）;minRoute=newintConstant.CITY_NUM;voidrun（）（for（intnc=1;nc=NC;nc+）/迭代次数（/初始化for（intk=0;kants.length;k+）/蚂蚁数据antsk.init（）;/遍历所有城市for（intlook=1;lookConstant.CITY_NUM;look+）（for（intk=0;kants.length;k+）/每只蚂蚁（intnextCity=select（antsk）;/选择下一个城市antsk.reachNextCity（nextCity）;/到达下一个城市/返回起点城市并计算最优路径for（intk=0;kantsk.passedLength）（minLength=antsk.passedLength;/记录最短距离copyRoute（antsk.passed）;/记录最短路线/对routes进行信息素更新for（inti=0;iConstant.CITY_NUM;i+）for（intj=0;jConstant.CITY_NUM;j+）（for（intk=0;kants.length;k+）（/信息素增量floatdp=Q/antsk.passedLength;for（intn=0;nConstant.CITY_NUM;n+）（intcurCity=antsk.passedn-1;intnextCity=antsk.passed（n+1）%Constant.CITY_NUM-1;if（curCity=i&nextCity=j）/出现过这段路径（Constant.routesij.dp+=dp;break;for（inti=0;iConstant.CITY_NUM;i+）for（intj=0;jConstant.CITY_NUM;j+）（Constant.routesij.pheromone+=p*Constant.routesij.pheromone+Constant.routesij.dp;Constant.routesij.dp=0.0f;/计算选择概率+轮赌intselect（Antant）（floattotalVAP=0.0f;ListcanSelectedCityList=newLinkedList（）;for（intnextCity=0;nextCityConstant.CITY_NUM;nextCity+）（if（!

ant.isPassedCity（nextCity+1）/可选择城市（doublevisibility=1.0f/Constant.routesant.curCitynextCity.distance;/能见度visibility=Math.pow（visibility,5）;doublepheromone=Constant.routesant.curCitynextCity.pheromone;pheromone=Math.pow（pheromone,2）;floatVAP=（float）visibility*（float）pheromone;totalVAP+=VAP;/累加VAPCanReachCityrCity=newCanReachCity（nextCity,VAP）;canSelectedCityList.add（rCity）;/添加/计算每个城市被选中的概率ListIteratoriterator=canSelectedCityList.listIterator（）;/获取pelList对应的迭代器头结点while（iterator.hasNext（）（/取城市CanReachCityrCity=iterator.next（）;/计算概率rCity.rate=rCity.VAP/totalVAP;/赌轮选择其中一个城市floatrate=（float）Math.random（）;iterator=canSelectedCityList.listIterator（）;/获取pelList对应的迭代器头结点while（iterator.hasNext（）（CanReachCityrCity=iterator.next（）;if（rate=rCity.rate）returnrCity.id;elserate=rate-rCity.rate;/精度所致，人为返回最后一个城市iterator=canSelectedCityList.listIterator（）;/获取pelList对应的迭代器头结点while（iterator.hasNext（）（CanReachCityrCity=iterator.next（）;if（iterator.hasNext（）=false）/最后一个元素了returnrCity.id;return