1、河南理工大学计算机科学与技术学院课程设计报告2014 2015 学年第一学期课程名称 Java 语言程序设计 设计题目 利用粒子群算法解决 TSP 问题 姓 名 朱超琦 学 号 3613090102 专业班级 计科合 13 指导教师 刘 志 中 2015 年 1 月 2 日- 1 -目录一课程设计内容 .2(一)课程设计题目 .2(二)课程设计目的 .2(三)课程设计要求 .2二算法相关知识 .2(一) 粒子群算法简介 .2(二) 人工生命简介 .3(三) 粒子群算法的流程图及伪代码： .4三.算法的 JAVA 实现 .5四. 课程设计的总结体会 .14五参考文献 .142一课程设计内容(一)
2、 课程设计题目应用粒子群算法(Particle Swarm Optimization) 求解 旅行商问题（TSP）；旅行商问题：即 TSP 问题（Travelling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访 n 个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值(二)课程设计目的1.训练应用算法求解实际问题；2 训练应用 Java 语言实现具体问题的求解算法；3.到达理解 java 语言的应用特点以及熟练应用 jav
3、a 语言的目标。(三)课程设计要求1.读懂算法，理解算法计算过程中每一步操作是如何实现的；2.设计函数优化的编码格式；3.采用 java 语言编程实现算法的求解过程；4.掌握粒子群算法的基本原理 ,了解在 JAVA 环境中实现粒子群算法的过程。二算法相关知识(一) 粒子群算法简介粒子群算法简称 PSO，它的基本思想是模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO 从这种模型中得到启示并用于解决优化问题。
4、PSO 中，每个优化问题的解都3是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(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 代表整个集群搜索到的最优值,presenti代表第 i 个粒子的当前位置。(二) 人工生命简介“人工生命“是来研究具有某些生命基本特征的人
6、工系统。两方面内容1. 研究如何利用计算技术研究生物现象2. 研究如何利用生物技术研究计算问题我们现在关注的是第二部分的内容。 现在已经有很多源于生物现象的计算技巧. 例如,人工神经网络是简化的大脑模型。遗传算法是模拟基因进化过程的.社会系统。现在我们讨论另一种生物系统- 社会系统。更确切的是, 在由简单个体组成的群落与环境以及个体之间的互动行为。 也可称做“群智能“(swarm intelligence). 这些模拟系统利用局部信息从而可能产生不可预测的群体行为例如 floys 和 birds 他们都用来模拟鱼群和鸟群的运动规律, 主要用于计算机视觉和计算机辅助设计。在计算智能(comput
7、ational intelligence)领域有两种基于群智能的算法.蚁群算法(ant colony optimization)和 PSO 粒子群算法(particle swarm optimization). 前者是对蚂蚁群落食物采集过程的模拟。已经成功运用在很多离散优化问题上。粒子群优化算法(PSO) 也是起源对简单社会系统的模拟。 最4初设想是模拟鸟群觅食的过程. 但后来发现 PSO 是一种很好的优化工具。(三) 粒子群算法的流程图及伪代码：1.流程图：2.伪代码：For each particle_Initialize particleENDDo_For each particle_C
8、alculate 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 gBest_For each particle_Calculate particle velocity according equation (a)_Update pa
9、rticle position according equation (b)_End5While 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, 1
11、0, 那么 Vmax 的大小就是 20学习因子: c1 和 c2 通常等于 2. 不过在文献中也有其他的取值. 但是一般 c1 等于 c2 并且范围在 0 和 4 之间。中止条件: 最大循环数以及最小错误要求 . 例如, 在上面的神经网络训练例子中, 最小错误可以设定为 1 个错误分类, 最大循环设定为 2000, 这个中止条件由具体的问题确定.全局 PSO 和局部 PSO: 我们介绍了两种版本的粒子群优化算法: 全局版和局部版. 前者速度快不过有时会陷入局部最优. 后者收敛速度慢一点不过很难陷入局部最优. 在实际应用中, 可以先用全局 PSO 找到大致的结果,再有局部 PSO 进行搜索.三.
12、算法的 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; 6public int getY() return y; public void setY(int y) this.y = y; public void print() System.out.println(“x:“+this.x+“
13、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.Random;public class PSO private int bestNum;private float w;private int MAX_GEN;/ 迭代次数private int scale;/ 种群规
14、模private int cityNum; / 城市数量，编码长度private int t;/ 当前代数private int distance; / 距离矩阵private int oPopulation;/ 粒子群private ArrayList listV;/ 每科粒子的初始交换序列private int Pd;/ 一颗粒子历代中出现最好的解，private int vPd;/ 解的评价值private int Pgd;/ 整个粒子群经历过的的最好的解，每个粒子都能记住自己搜索到的最好解private int vPgd;/ 最好的解的评价值private int bestT;/ 最佳
15、出现代数private int fitness;/ 种群适应度，表示种群中各个个体的适应度private Random random;public PSO() public PSO(int n, int g, int s, float w) 7this.cityNum = n;this.MAX_GEN = g;this.scale = s;this.w = w;* 初始化 PSO 算法类* param filename 数据文件名，该文件存储所有城市节点坐标数据* throws IOException*/private void init(String filename) throws IOE
16、xception / 读取数据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 ();9for (int i = 0; i list = new ArrayList();ra = random.nextInt(65535) % cityNum;for (int j = 0; j 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
