粒子群算法解决TSP问题

河南理工大学计算机科学与技术学院课程设计报告2014—2015学年第一学期课程名称Java语言程序设计设计题目利用粒子群算法解决TSP问题姓名朱超琦学号3613090102专业班级计科合13指导教师刘志中2015年1月2日-1-目录一．课程设计内容..................................................................2(一)课程设计题目..............................................................................................2(二)课程设计目的............................................................................................2(三)课程设计要求............................................................................................2二．算法相关知识..................................................................2(一)粒子群算法简介......................................................................................2(二)人工生命简介..........................................................................................3(三)粒子群算法的流程图及伪代码：..........................................................4三.算法的JAVA实现..............................................................5四.课程设计的总结体会.....................................................14五．参考文献........................................................................142一．课程设计内容(一)课程设计题目应用粒子群算法(ParticleSwarmOptimization)求解旅行商问题（TSP）；旅行商问题：即TSP问题（TravellingSalesmanProblem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值(二)课程设计目的1.训练应用算法求解实际问题；2训练应用Java语言实现具体问题的求解算法；3.到达理解java语言的应用特点以及熟练应用java语言的目标。(三)课程设计要求1.读懂算法，理解算法计算过程中每一步操作是如何实现的；2.设计函数优化的编码格式；3.采用java语言编程实现算法的求解过程；4.掌握粒子群算法的基本原理,了解在JAVA环境中实现粒子群算法的过程。二．算法相关知识(一)粒子群算法简介粒子群算法简称PSO，它的基本思想是模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是3搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitnessvalue)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest。另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。粒子公式：在找到这两个最优值时，粒子根据如下的公式来更新自己的速度和新的位置：v[i]=w*v[i]+c1*rand()*(pbest[i]-present[i])+c2*rand()*(gbest-present[i])present[i]=present[i]+v[i]其中v[i]代表第i个粒子的速度，w代表惯性权值,c1和c2表示学习参数，rand()表示在0-1之间的随机数,pbest[i]代表第i个粒子搜索到的最优值,gbest代表整个集群搜索到的最优值,present[i]代表第i个粒子的当前位置。(二)人工生命简介人工生命是来研究具有某些生命基本特征的人工系统。两方面内容1.研究如何利用计算技术研究生物现象2.研究如何利用生物技术研究计算问题我们现在关注的是第二部分的内容。现在已经有很多源于生物现象的计算技巧.例如,人工神经网络是简化的大脑模型。遗传算法是模拟基因进化过程的.社会系统。现在我们讨论另一种生物系统-社会系统。更确切的是,在由简单个体组成的群落与环境以及个体之间的互动行为。也可称做群智能(swarmintelligence).这些模拟系统利用局部信息从而可能产生不可预测的群体行为例如floys和birds他们都用来模拟鱼群和鸟群的运动规律,主要用于计算机视觉和计算机辅助设计。在计算智能(computationalintelligence)领域有两种基于群智能的算法.蚁群算法(antcolonyoptimization)和PSO粒子群算法(particleswarmoptimization).前者是对蚂蚁群落食物采集过程的模拟。已经成功运用在很多离散优化问题上。粒子群优化算法(PSO)也是起源对简单社会系统的模拟。最初设4想是模拟鸟群觅食的过程.但后来发现PSO是一种很好的优化工具。(三)粒子群算法的流程图及伪代码：1.流程图：2.伪代码：Foreachparticle____InitializeparticleENDDo____Foreachparticle________Calculatefitnessvalue________Ifthefitnessvalueisbetterthanthebestfitnessvalue(pBest)inhistory____________setcurrentvalueasthenewpBest____End____ChoosetheparticlewiththebestfitnessvalueofalltheparticlesasthegBest____Foreachparticle________Calculateparticlevelocityaccordingequation(a)________Updateparticlepositionaccordingequation(b)____End5Whilemaximumiterationsorminimumerrorcriteriaisnotattained3.PSO的参数设置：从上面的例子我们可以看到应用PSO解决优化问题的过程中有两个重要的步骤:问题解的编码和适应度函数。PSO的一个优势就是采用实数编码,不需要像遗传算法一样是二进制编码(或者采用针对实数的遗传操作。例如对于问题f(x)=x1^2+x2^2+x3^2求解,粒子可以直接编码为(x1,x2,x3),而适应度函数就是f(x)。接着我们就可以利用前面的过程去寻优.这个寻优过程是一个叠代过程，中止条件一般为设置为达到最大循环数或者最小错误PSO中并没有许多需要调节的参数，下面列出了这些参数以及经验设置粒子数:一般取20–40.其实对于大部分的问题10个粒子已经足够可以取得好的结果,不过对于比较难的问题或者特定类别的问题，粒子数可以取到100或200粒子的长度:这是由优化问题决定,就是问题解的长度粒子的范围:由优化问题决定,每一维可是设定不同的范围Vmax:最大速度，决定粒子在一个循环中最大的移动距离,通常设定为粒子的范围宽度,例如上面的例子里,粒子(x1,x2,x3)x1属于[-10,10],那么Vmax的大小就是20学习因子:c1和c2通常等于2.不过在文献中也有其他的取值.但是一般c1等于c2并且范围在0和4之间。中止条件:最大循环数以及最小错误要求.例如,在上面的神经网络训练例子中,最小错误可以设定为1个错误分类,最大循环设定为2000,这个中止条件由具体的问题确定.全局PSO和局部PSO:我们介绍了两种版本的粒子群优化算法:全局版和局部版.前者速度快不过有时会陷入局部最优.后者收敛速度慢一点不过很难陷入局部最优.在实际应用中,可以先用全局PSO找到大致的结果,再有局部PSO进行搜索.三.算法的JAVA实现代码实现：packagenoah;publicclassSO{privateintx;privateinty;publicSO(intx,inty){this.x=x;this.y=y;}publicintgetX(){returnx;}publicvoidsetX(intx){this.x=x;}6publicintgetY(){returny;}publicvoidsetY(inty){this.y=y;}publicvoidprint(){System.out.println(x:+this.x+y:+this.y);}}packagenoah;importjava.io.BufferedReader;importjava.io.FileInputStream;importjava.io.IOException;importjava.io.InputStreamReader;importjava.util.ArrayList;importjava.util.Random;publicclassPSO{privateintbestNum;privatefloatw;privateintMAX_GEN;//迭代次数privateintscale;//种群规模privateintcityNum;//城市数量，编码长度privateintt;//当前代数privateint[][]distance;//距离矩阵privateint[][]oPopulation;//粒子群privateArrayListArrayListSOlistV;//每科粒子的初始交换序列privateint[][]Pd;//一颗粒子历代中出现最好的解，privateint[]vPd;//解的评价值privateint[]Pgd;//整个粒子群经历过的的最好的解，每个粒子都能记住自己搜索到的最好解privateintvPgd;//最好的解的评价值privateintbestT;//最佳出现代数privateint[]fitness;//种群适应度，表示种群中各个个体的适应度privateRandomrandom;publicPSO(){}publicPSO(intn,intg,ints,floatw){7this.cityNum=n;this.MAX_GEN=g;this.scale=s;this.w=w;}*初始化PSO算法类*@paramfilename数据文件名，该文件存储所有城市节点坐标数据*@throwsIOException*