粒子群算法解决TSP问题

《粒子群算法解决TSP问题》由会员分享，可在线阅读，更多相关《粒子群算法解决TSP问题（16页珍藏版）》请在装配图网上搜索。

1、河南理工大学计算机科学与技术学院课程设计报告2014 2015 学年第一学期课程名称Java 语言程序设计设计题目利用粒子群算法解决TSP 问题姓名朱超琦学号3613090102专业班级计科合 13指导教师刘 志 中2015年1月2日目录一课程设计内容2(一 )课程设计题目2(二 )课程设计目的2(三 )课程设计要求2二算法相关知识2(一 ) 粒子群算法简介2(二 ) 人工生命简介3(三 ) 粒子群算法的流程图及伪代码：4三 .算法的 JAVA 实现5四 . 课程设计的总结体会14五参考文献14一课程设计内容(一)课程设计题目应用粒子群算法 (Particle Swarm Optimizati

2、on) 求解 旅行商问题（ TSP）；旅行商问题：即 TSP问题（ Travelling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n 个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值( 二) 课程设计目的1. 训练应用算法求解实际问题；2 训练应用 Java 语言实现具体问题的求解算法；3. 到达理解 java 语言的应用特点以及熟练应用 java 语言的目标。( 三) 课程设计要求1. 读懂算法，理解算法计算过程中

3、每一步操作是如何实现的；2. 设计函数优化的编码格式；3. 采用 java 语言编程实现算法的求解过程；4. 掌握粒子群算法的基本原理 , 了解在 JAVA 环境中实现粒子群算法的过程。二算法相关知识( 一)粒子群算法简介粒子群算法简称 PSO，它的基本思想是模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为

4、“粒子”。所有的粒子都有一个由被优化的函数决定的适应值 (fitness value) ，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。PSO 初始化为一群随机粒子 ( 随机解 ) 。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个 极值 来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值 pBest 。另一个极值是整个种群目前找到的最优解，这个极值是全局极值 gBest 。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。粒子公式：在找到这两个最优值时，粒子根据如下的公式来更新自己的

5、速度和新的位置：vi = w * vi + c1 * rand() * (pbesti - presenti) + c2 * rand() * (gbest - presenti)presenti = presenti + vi其中 vi代表第0-1 之间的随机数最优值 , presentii个粒子的速度，w 代表惯性权值 , c1 和, pbesti代表第i个粒子搜索到的最优值代表第 i 个粒子的当前位置。c2表示学习参数，rand() 表示在, gbest代表整个集群搜索到的(二) 人工生命简介 人工生命 是来研究具有某些生命基本特征的人工系统。两方面内容1. 研究如何利用计算技术研究生物

6、现象2. 研究如何利用生物技术研究计算问题我们现在关注的是第二部分的内容。现在已经有很多源于生物现象的计算技巧.例如 , 人工神经网络是简化的大脑模型。遗传算法是模拟基因进化过程的.社会系统。现在我们讨论另一种生物系统 - 社会系统。更确切的是 , 在由简单个体组成的群落与环境以及个体之间的互动行为。 也可称做 群智能 (swarm intelligence). 这些模拟系统利用局部信息从而可能产生不可预测的群体行为例如 floys和 birds他们都用来模拟鱼群和鸟群的运动规律,主要用于计算机视觉和计算机辅助设计。在计算智能 (computational intelligence)算 法 (

7、antcolonyoptimization)和领域有两种基于群智能的算法PSO 粒 子 群 算 法 (particle. 蚁群swarmoptimization). 前者是对蚂蚁群落食物采集过程的模拟。 已经成功运用在很多离散优化问题上。粒子群优化算法 (PSO) 也是起源对简单社会系统的模拟。 最初设想是模拟鸟群觅食的过程.但后来发现 PSO是一种很好的优化工具。(三) 粒子群算法的流程图及伪代码：1. 流程图：2.伪代码：For each particle_Initialize particleENDDo_For each particle_Calculate fitness value_

8、If the fitness value is better than the best fitness value (pBest) in history_set current value as the new pBest_End_Choose the particle with the best fitness value of all the particles as the gBest_For each particle_Calculate particle velocity according equation (a)_Update particle position accordi

9、ng equation (b)_EndWhile maximum iterations or minimum error criteria is not attained3.PSO的参数设置：从上面的例子我们可以看到应用PSO 解决优化问题的过程中有两个重要的步骤:问题解的编码和适应度函数。PSO 的一个优势就是采用实数编码对实数的遗传操作。例如对于问题, 不需要像遗传算法一样是二进制编码(或者采用针f(x) = x12 + x22+x32求解 , 粒子可以直接编码为(x1, x2, x3), 而适应度函数就是f(x) 。接着我们就可以利用前面的过程去寻优.这个寻优过程是一个叠代过程，中止条件

10、一般为设置为达到最大循环数或者最小错误PSO 中并没有许多需要调节的参数，下面列出了这些参数以及经验设置粒子数 : 一般取 20 40. 其实对于大部分的问题10 个粒子已经足够可以取得好的结果 , 不过对于比较难的问题或者特定类别的问题，粒子数可以取到100或 200粒子的长度 :这是由优化问题决定, 就是问题解的长度粒子的范围 :由优化问题决定 ,每一维可是设定不同的范围Vmax: 最大速度，决定粒子在一个循环中最大的移动距离,通常设定为粒子的范围宽度 ,例如上面的例子里 ,粒子 (x1, x2, x3) x1属于 -10, 10,那么 Vmax 的大小就是20学习因子 : c1 和 c2

11、 通常等于2.不过在文献中也有其他的取值. 但是一般 c1等于 c2并且范围在 0 和 4 之间。中止条件 : 最大循环数以及最小错误要求. 例如,在上面的神经网络训练例子中, 最小错误可以设定为 1 个错误分类 , 最大循环设定为2000,这个中止条件由具体的问题确定 .全局 PSO 和局部 PSO: 我们介绍了两种版本的粒子群优化算法: 全局版和局部版 . 前者速度快不过有时会陷入局部最优. 后者收敛速度慢一点不过很难陷入局部最优.在实际应用中 , 可以先用全局 PSO 找到大致的结果 ,再有局部 PSO 进行搜索 .三 .算法的 JAVA 实现代码实现：package noah;publ

12、ic class SO private int x;private int y;public SO(int x,int y) this.x=x;this.y=y;public int getX() return x;public void setX(int x) this.x = x;public int getY() return y;public void setY(int y) this.y = y;public void print()package noah;public class PSO private int bestNum;private float w;private in

13、t MAX_GEN;/迭代次数private int scale;/种群规模private int cityNum; /城市数量，编码长度private int t;/当前代数private int distance; /距离矩阵private int oPopulation;/粒子群private ArrayListArrayList listV;/每科粒子的初始交换序列private int Pd;/private int vPd;/private int Pgd;/一颗粒子历代中出现最好的解，解的评价值整个粒子群经历过的的最好的解，每个粒子都能记住自己搜索到的最好解private int

14、 vPgd;/private int bestT;/private int fitness;/最好的解的评价值最佳出现代数种群适应度，表示种群中各个个体的适应度private Random random;public PSO() public PSO(int n, int g, int s, float w) this.cityNum = n;this.MAX_GEN = g;this.scale = s;this.w = w;* 初始化 PSO算法类* param filename 数据文件名，该文件存储所有城市节点坐标数据* throws IOException*/private void

15、 init(String filename) throws IOException / 读取数据 int x;int y;String strbuff;BufferedReader data = new BufferedReader(new InputStreamReader(new FileInputStream(filename);distance = new intcityNumcityNum;x = new intcityNum;y = new intcityNum;for (int i = 0; i cityNum; i+) / 读取一行数据，数据格式 1 6734 1453 str

16、buff = data.readLine();/ 字符分割String strcol = strbuff.split( );xi = Integer.valueOf(strcol1);/ xyi = Integer.valueOf(strcol2);/ y坐标坐标/ 计算距离矩阵/ ，针对具体问题，距离计算方法也不一样，此处用的是 att48 作为案例，它有 48 个城市，距离计算方法为伪欧氏距离，最优值为 10628for (int i = 0; i cityNum - 1; i+) distanceii = 0; /对角线为 0for (int j = i + 1; j cityNum;

17、j+) double rij = Math.sqrt(xi - xj) * (xi - xj) + (yi -yj)* (yi - yj) / 10.0);/ 四舍五入，取整int tij = (int) Math.round(rij);if (tij rij) distanceij = tij + 1;distanceji = distanceij; else distanceij = tij;distanceji = distanceij;distancecityNum - 1cityNum - 1 = 0;oPopulation = new intscalecityNum;fitness

18、 = new intscale;Pd = new intscalecityNum;vPd = new intscale;Pgd = new intcityNum;vPgd = Integer.MAX_VALUE;bestT = 0;t = 0;random = new Random(System.currentTimeMillis();/ 初始化种群，多种随机生成办法 void initGroup() int i, j, k;for (k = 0; k scale; k+)oPopulationk0 = random.nextInt(65535) % cityNum;for (i = 1; i

19、 cityNum;)oPopulationki = random.nextInt(65535) % cityNum; for (j = 0; j i; j+) if (oPopulationki = oPopulationkj) break;if (j = i) i+;void initListV() int ra;int raA;int raB;listV = new ArrayListArrayList();for (int i = 0; i scale; i+) ArrayList list = new ArrayList();ra = random.nextInt(65535) % c

20、ityNum;for (int j = 0; j ra; j+) raA = random.nextInt(65535) % cityNum;raB = random.nextInt(65535) % cityNum;while (raA = raB) raB = random.nextInt(65535) % cityNum;/ raA 与 raB 不一样 SO s = new SO(raA, raB); list.add(s);listV.add(list);public int evaluate(int chr) / 0123int len = 0;/ 编码，起始城市 , 城市 1, 城

21、市 2. 城市 nfor (int i = 1; i cityNum; i+) len += distancechri - 1chri;/ 城市 n, 起始城市len += distancechrcityNum - 1chr0;return len;/ 求一个基本交换序列作用于编码 arr 后的编码 public void add(int arr, ArrayList list) int temp = -1; SO s;for (int i = 0; i list.size(); i+) s = list.get(i);temp = arrs.getX(); arrs.getX() = arr

22、s.getY(); arrs.getY() = temp;/ 求两个编码的基本交换序列，如 A-B=SS public ArrayList minus(int a, int b) int temp = b.clone(); /*inttemp=newintL;for(inti=0;iL;i+) tempi=bi; */int index;/ 交换子SO s;/ 交换序列ArrayList list = new ArrayList();for (int i = 0; i cityNum; i+) if (ai != tempi) / 在 temp 中找出与 ai 相同数值的下标 indexind

23、ex = findNum(temp, ai);/ 在 temp 中交换下标 i 与下标 index 的值 changeIndex(temp, i, index);/ 记住交换子s = new SO(i, index);/ 保存交换子 list.add(s);return list;/ 在 arr 数组中查找 num，返回 num的下标public int findNum(int arr, int num) int index = -1;for (int i = 0; i cityNum; i+) if (arri = num) index = i;break;return index;/ 将数

24、组 arr 下标 index1 与下标 index2 的值交换 public void changeIndex(int arr, int index1, int index2) int temp = arrindex1; arrindex1 = arrindex2;arrindex2 = temp;/ 二维数组拷贝public void copyarray(int from, int to) for (int i = 0; i scale; i+) for (int j = 0; j cityNum; j+) toij = fromij;/ 一维数组拷贝public void copyarra

25、yNum(int from, int to) for (int i = 0; i cityNum; i+) toi = fromi;public void evolution() int i, j, k;int len = 0;float ra = 0f;ArrayList Vi;/ 迭代一次for (t = 0; t MAX_GEN; t+) / 对于每颗粒子for (i = 0; i scale; i+) if(i=bestNum) continue;ArrayList Vii = new ArrayList();/ 更新速度/ Vii=wVi+ra(Pid-Xid)+rb(Pgd-Xid

26、) Vi = listV.get(i);/ wVi+ 表示获取 Vi 中 size*w 取整个交换序列 len = (int) (Vi.size() * w);/ 越界判断/if(lencityNum) len=cityNum;len:+len+Vi.size():+Vi.size();for (j = 0; j len; j+) Vii.add(Vi.get(j);ArrayList a = minus(Pdi, oPopulationi);ra = random.nextFloat();len = (int) (a.size() * ra);/ 越界判断for (j = 0; j len;

27、 j+) Vii.add(a.get(j);ArrayList b = minus(Pgd, oPopulationi);ra = random.nextFloat();/ ra(Pid-Xid)+len = (int) (b.size() * ra);/ 越界判断for (j = 0; j len; j+) SO tt= b.get(j);Vii.add(tt);listV.add(i, Vii);add(oPopulationi, Vii);/ 计算新粒子群适应度， Fitnessmax, 选出最好的解 for (k = 0; k fitnessk) vPdk = fitnessk;cop

28、yarrayNum(oPopulationk, Pdk);bestNum=k;if (vPgd vPdk) 最 佳 长 度 +vPgd+代 数 ：+bestT);bestT = t;vPgd = vPdk;copyarrayNum(Pdk, Pgd);public void solve() int i;int k;initGroup();initListV();/ 每颗粒子记住自己最好的解 copyarray(oPopulation, Pd);/ 计算初始化种群适应度， Fitnessmax, 选出最好的解 for (k = 0; k vPdk) vPgd = vPdk;copyarrayNu

29、m(Pdk, Pgd);bestNum=k;/ 打印初始粒子群 .);for (k = 0; k scale; k+) for (i = 0; i cityNum; i+) / 进化evolution();/ 打印最后粒子群 .);for (k = 0; k scale; k+) for (i = 0; i cityNum; i+) 最佳长度出现代数： );最佳长度 );最佳路径： );for (i = 0; i cityNum; i+) PSO pso = new PSO(48, 5000, 30, 0.5f);pso.init(c:/data.txt);pso.solve();(二 )运行结果四 . 课程设计的总结体会通过这次的课程设计，我的能力的到了很大提升，也学到了很多东西。课程设计中遇到的一系列问题，都通过讨论或请教老师得到了解决，这次课程设计收货很多，学会很多五参考文献1 离散粒子群优化算法及其应用郭文忠陈国龙，清华大学出版社2 JAVA基础入门传智博客，清华大学出版社