《粒子群算法解决TSP问题》由会员分享，可在线阅读，更多相关《粒子群算法解决TSP问题（15页珍藏版）》请在金锄头文库上搜索。
1、 河南理工大学 计算机科学与技术学院 课程设计报告 2014 2015 学年第一学期 课程名称 Java 语言程序设计 设计题目 利用粒子群算法解决 TSP 问题 姓 名 朱超琦 学 号 3613090102 专业班级 计科合 13 指导教师 刘 志 中 2015 年 1 月 2 日 精选 目录 一课程设计内容 . 2 (一)课程设计题目 . 2 (二)课程设计目的 . 2 (三)课程设计要求 . 2 二算法相关知识 . 2 (一) 粒子群算法简介 . 2 (二) 人工生命简介 . 3 (三) 粒子群算法的流程图及伪代码： . 4 三.算法的 JAVA 实现. 5 四. 课程设计的总结体会 .
2、 14 五参考文献 . 14 精选 一课程设计内容 (一)课程设计题目 应用粒子群算法(Particle Swarm Optimization) 求解 旅行商问题（TSP）； 旅行商问题： 即 TSP 问题（Travelling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访 n 个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值 (二)课程设计目的 1.训练应用算法求解实际问题； 2 训练应用 Java 语言实现具体问题的
3、求解算法； 3.到达理解 java 语言的应用特点以及熟练应用 java 语言的目标。 (三)课程设计要求 1.读懂算法，理解算法计算过程中每一步操作是如何实现的； 2.设计函数优化的编码格式； 3.采用 java 语言编程实现算法的求解过程； 4.掌握粒子群算法的基本原理 ,了解在 JAVA 环境中实现粒子群算法的过程。 二算法相关知识 (一) 粒子群算法简介 粒子群算法简称 PSO，它的基本思想是模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的
4、就是搜寻目前离食物最近的鸟的周围区域。 PSO 从这种模型中得到启示并用于解决优化问题。 PSO 中， 每个优化问题的解都是精选 搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitness value)， 每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。 PSO 初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次迭代中， 粒子通过跟踪两个极值来更新自己。 第一个就是粒子本身所找到的最优解，这个解叫做个体极值 pBest。另一个极值是整个种群目前找到的最优解，这个极值是全局极值 gBest。另外也
5、可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。 粒子公式：在找到这两个最优值时，粒子根据如下的公式来更新自己的速度和新的位置： vi = w * vi + c1 * rand() * (pbesti - presenti) + c2 * rand() * (gbest - presenti) presenti = presenti + vi 其中 vi代表第 i 个粒子的速度，w 代表惯性权值,c1 和 c2 表示学习参数，rand()表示在0-1 之间的随机数,pbesti代表第 i 个粒子搜索到的最优值,gbest 代表整个集群搜索到的最优值,pre
6、senti代表第 i 个粒子的当前位置。 (二) 人工生命简介 人工生命是来研究具有某些生命基本特征的人工系统。 两方面内容 1. 研究如何利用计算技术研究生物现象 2. 研究如何利用生物技术研究计算问题 我们现在关注的是第二部分的内容。 现在已经有很多源于生物现象的计算技巧. 例如,人工神经网络是简化的大脑模型。遗传算法是模拟基因进化过程的 . 社会系统。 现在我们讨论另一种生物系统- 社会系统。更确切的是, 在由简单个体组成的群落与环境以及个体之间的互动行为。 也可称做群智能(swarm intelligence). 这些模拟系统利用局部信息从而可能产生不可预测的群体行为 例如 floys
7、 和 birds 他们都用来模拟鱼群和鸟群的运动规律, 主要用于计算机视觉和计算机辅助设计。 在计算智能(computational intelligence)领域有两种基于群智能的算法.蚁群算 法 (ant colony optimization) 和PSO粒 子 群 算 法 (particle swarm optimization). 前者是对蚂蚁群落食物采集过程的模拟。 已经成功运用在很多离散优化问题上。 粒子群优化算法(PSO) 也是起源对简单社会系统的模拟。 最初设精选 想是模拟鸟群觅食的过程. 但后来发现 PSO 是一种很好的优化工具。 (三) 粒子群算法的流程图及伪代码： 1.流
8、程图： 2.伪代码： For each particle _Initialize particle END Do _For each particle _Calculate fitness value _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 gB
9、est _For each particle _Calculate particle velocity according equation (a) _Update particle position according equation (b) _End While maximum iterations or minimum error criteria is not attained 3.PSO 的参数设置： 从上面的例子我们可以看到应用 PSO 解决优化问题的过程中有两个重要的步骤: 问题解的编码和适应度函数。 PSO 的一个优势就是采用实数编码, 不需要像遗传算法一样是二进制编码(或者
10、采用针对实数的遗传操作。例如对于问题 f(x) = x12 + x22+x32 求解, 粒子可以直接编码为 精选 (x1, x2, x3), 而适应度函数就是 f(x)。 接着我们就可以利用前面的过程去寻优.这个寻优过程是一个叠代过程， 中止条件一般为设置为达到最大循环数或者最小错误 PSO 中并没有许多需要调节的参数， 下面列出了这些参数以及经验设置 粒子数: 一般取 20 40. 其实对于大部分的问题 10 个粒子已经足够可以取得好的结果, 不过对于比较难的问题或者特定类别的问题，粒子数可以取到 100 或 200 粒子的长度: 这是由优化问题决定, 就是问题解的长度 粒子的范围: 由优化
11、问题决定,每一维可是设定不同的范围 Vmax: 最大速度，决定粒子在一个循环中最大的移动距离,通常设定为粒子的范围宽度,例如上面的例子里,粒子 (x1, x2, x3) x1 属于 -10, 10, 那么 Vmax 的大小就是 20 学习因子: c1 和 c2 通常等于 2. 不过在文献中也有其他的取值. 但是一般 c1 等于 c2 并且范围在 0 和 4 之间。 中止条件: 最大循环数以及最小错误要求. 例如, 在上面的神经网络训练例子中, 最小错误可以设定为 1 个错误分类, 最大循环设定为 2000, 这个中止条件由具体的问题确定. 全局 PSO 和局部 PSO: 我们介绍了两种版本的粒
12、子群优化算法: 全局版和局部版. 前者速度快不过有时会陷入局部最优. 后者收敛速度慢一点不过很难陷入局部最优. 在实际应用中, 可以先用全局 PSO 找到大致的结果,再有局部 PSO 进行搜索. 三.算法的 JAVA 实现 代码实现： package noah; public 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
13、() return y; public void setY(int y) this.y = y; public void print() 精选 System.out.println(x:+this.x+ y:+this.y); package noah; import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Ra
14、ndom; public class PSO private int bestNum; private float w; private int MAX_GEN;/ 迭代次数 private int scale;/ 种群规模 private int cityNum; / 城市数量，编码长度 private int t;/ 当前代数 private int distance; / 距离矩阵 private int oPopulation;/ 粒子群 private ArrayListArrayList listV;/ 每科粒子的初始交换序列 private int Pd;/ 一颗粒子历代中出现最
15、好的解， private int vPd;/ 解的评价值 private int Pgd;/ 整个粒子群经历过的的最好的解，每个粒子都能记住自己搜索到的最好解 private int 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
16、 = s; this.w = w; * 初始化 PSO 算法类 * param filename 数据文件名，该文件存储所有城市节点坐标数据 精选 * throws IOException */ private void init(String filename) throws IOException / 读取数据 int x; int y; String strbuff; BufferedReader data = new BufferedReader(new InputStreamReader( new FileInputStream(filename); distance = new i
17、ntcityNumcityNum; x = new intcityNum; y = new intcityNum; for (int i = 0; i cityNum; i+) / 读取一行数据，数据格式 1 6734 1453 strbuff = data.readLine(); / 字符分割 String strcol = strbuff.split( ); xi = Integer.valueOf(strcol1);/ x 坐标 yi = Integer.valueOf(strcol2);/ y 坐标 / 计算距离矩阵 / ，针对具体问题，距离计算方法也不一样，此处用的是 att48 作
18、为案例，它有 48 个城市，距离计算方法为伪欧氏距离，最优值为 10628 for (int i = 0; i cityNum - 1; i+) distanceii = 0; / 对角线为 0 for (int j = i + 1; j cityNum; 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
19、= distanceij; else distanceij = tij; distanceji = distanceij; distancecityNum - 1cityNum - 1 = 0; 精选 oPopulation = new intscalecityNum; fitness = new intscale; Pd = new intscalecityNum; vPd = new intscale; Pgd = new intcityNum; vPgd = Integer.MAX_VALUE; bestT = 0; t = 0; random = new Random(System.c
20、urrentTimeMillis(); / 初始化种群，多种随机生成办法 void initGroup() int i, j, k; for (k = 0; k scale; k+) oPopulationk0 = random.nextInt(65535) % cityNum; for (i = 1; i cityNum;) oPopulationki = random.nextInt(65535) % cityNum; for (j = 0; j i; j+) if (oPopulationki = oPopulationkj) break; if (j = i) i+; void ini
21、tListV() int ra; int raA; int raB; listV = new ArrayListArrayList(); for (int i = 0; i scale; i+) ArrayList list = new ArrayList(); ra = random.nextInt(65535) % cityNum; for (int j = 0; j ra; j+) raA = random.nextInt(65535) % cityNum; raB = random.nextInt(65535) % cityNum; while (raA = raB) 精选 raB =
22、 random.nextInt(65535) % cityNum; / raA 与 raB 不一样 SO s = new SO(raA, raB); list.add(s); listV.add(list); public int evaluate(int chr) / 0123 int len = 0; / 编码，起始城市,城市 1,城市 2.城市 n for (int i = 1; i cityNum; i+) len += distancechri - 1chri; / 城市 n,起始城市 len += distancechrcityNum - 1chr0; return len; /
23、求一个基本交换序列作用于编码 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() = arrs.getY(); arrs.getY() = temp; / 求两个编码的基本交换序列，如 A-B=SS public ArrayList minus(int a, int b) int temp = b.clone(); /* * int tem
24、p=new intL; for(int i=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相同数值的下标 index index = findNum(temp, ai); / 在 temp 中交换下标 i 与下标 index 的值 changeIndex(temp, i, index); / 记住交换子 s = new SO(i, ind
25、ex); / 保存交换子 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; / 将数组 arr 下标 index1 与下标 index2 的值交换 public void changeIndex(int arr, int index1, int index2) int tem
26、p = 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 copyarrayNum(int from, int to) for (int i = 0; i cityNum; i+) toi = fromi; public void evolution
27、() 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(); /System.out.println(-); / 更新速度 / Vii=wVi+ra(Pid-Xid)+rb(Pgd-Xid) Vi = listV.get(i); / wVi+表示获取 Vi 中 size*w 取整个交换序列 le
28、n = (int) (Vi.size() * w); /越界判断 /if(lencityNum) len=cityNum; /System.out.println(w:+w+ 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; j+) Vii.add(a.get(j
29、); 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; copyarrayNum
30、(oPopulationk, Pdk); bestNum=k; if (vPgd vPdk) System.out.println( 最 佳 长 度 +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) vP
31、gd = vPdk; copyarrayNum(Pdk, Pgd); bestNum=k; / 打印 System.out.println(初始粒子群.); for (k = 0; k scale; k+) for (i = 0; i cityNum; i+) System.out.print(oPopulationki + ,); System.out.println(); System.out.println(- + fitnessk); / 进化 evolution(); / 打印 System.out.println(最后粒子群.); for (k = 0; k scale; k+)
32、for (i = 0; i cityNum; i+) System.out.print(oPopulationki + ,); System.out.println(); System.out.println(- + fitnessk); System.out.println(最佳长度出现代数：); System.out.println(bestT); System.out.println(最佳长度); System.out.println(vPgd); System.out.println(最佳路径：); for (i = 0; i cityNum; i+) System.out.print
33、(Pgdi + ,); public static void main(String args) throws IOException System.out.println(Start.); PSO pso = new PSO(48, 5000, 30, 0.5f); pso.init(c:/data.txt); 精选 pso.solve(); (二)运行结果 四. 课程设计的总结体会 通过这次的课程设计，我的能力的到了很大提升，也学到了很多东西。课程设计中遇到的一系列问题，都通过讨论或请教老师得到了解决，这次课程设计收货很多，学会很多 五参考文献 1离散粒子群优化算法及其应用郭文忠 陈国龙，清华大学出版社 2JAVA 基础入门传智博客，清华大学出版社
