粒子群算法解决TSP问题

河南理工大学 计算机科学与技术学院 课程设计报告 2014 2015 学年第一学期 课程名称 Java 语言程序设计 设计题目 利用粒子群算法解决 TSP 问题 姓 名 朱超琦 学 号 3613090102 专业班级 计科合 13 指导教师 刘 志 中 2015 年 1 月 2 日 1 目录 一 课程设计内容 2 一 课程设计题目 2 二 课程设计目的 2 三 课程设计要求 2 二 算法相关知识 2 一 粒子群算法简介 2 二 人工生命简介 3 三 粒子群算法的流程图及伪代码 4 三 算法的 JAVA 实现 5 四 课程设计的总结体会 14 五 参考文献 14 2 一 课程设计内容一 课程设计内容 一一 课程设计题目课程设计题目 应用粒子群算法 Particle Swarm Optimization 求解 旅行商问题 TSP 旅行商问题 即 TSP 问题 Travelling Salesman Problem 又译为旅行推销员问题 货郎担问题 是数学领域中著名问题之一 假设有一个旅行商人要拜访 n 个 城市 他必须选择所要走的路径 路径的限制是每个城市只能拜访一次 而 且最后要回到原来出发的城市 路径的选择目标是要求得的路径路程为所有 路径之中的最小值 二二 课程设计目的课程设计目的 1 训练应用算法求解实际问题 2 训练应用 Java 语言实现具体问题的求解算法 3 到达理解 java 语言的应用特点以及熟练应用 java 语言的目标 三三 课程设计要求课程设计要求 1 读懂算法 理解算法计算过程中每一步操作是如何实现的 2 设计函数优化的编码格式 3 采用 java 语言编程实现算法的求解过程 4 掌握粒子群算法的基本原理 了解在 JAVA 环境中实现粒子群算法的过程 二 算法相关知识二 算法相关知识 一一 粒子群算法简介粒子群算法简介 粒子群算法简称 PSO 它的基本思想是模拟鸟群的捕食行为 设想这样一个 场景 一群鸟在随机搜索食物 在这个区域里只有一块食物 所有的鸟都不知道 食物在那里 但是他们知道当前的位置离食物还有多远 那么找到食物的最优策 略是什么呢 最简单有效的就是搜寻目前离食物最近的鸟的周围区域 PSO 从这种模型中得到启示并用于解决优化问题 PSO 中 每个优化问题的解都 3 是搜索空间中的一只鸟 我们称之为 粒子 所有的粒子都有一个由被优化的 函数决定的适应值 fitness value 每个粒子还有一个速度决定他们飞翔的方 向和距离 然后粒子们就追随当前的最优粒子在解空间中搜索 PSO 初始化为一群随机粒子 随机解 然后通过迭代找到最优解 在每一次迭代 中 粒子通过跟踪两个 极值 来更新自己 第一个就是粒子本身所找到的最优解 这个解叫做个体极值 pBest 另一个极值是整个种群目前找到的最优解 这个极 值是全局极值 gBest 另外也可以不用整个种群而只是用其中一部分作为粒子的 邻居 那么在所有邻居中的极值就是局部极值 粒子公式 在找到这两个最优值时 粒子根据如下的公式来更新自己的速度和新 的位置 v i v i w w v i v i c1c1 rand rand pbest i pbest i present i present i c2c2 rand rand gbest gbest present i present i present i present i present i present i v i v i 其中 v i v i 代表第 i i 个粒子的速度 w w 代表惯性权值 c1c1 和 c2c2 表示学习参数 rand rand 表示在 0 10 1 之间的随机数 pbest i pbest i 代表第 i i 个粒子搜索到的最优值 gbestgbest 代表整个集群搜索到的 最优值 present i present i 代表第 i i 个粒子的当前位置 二二 人工生命简介人工生命简介 人工生命 是来研究具有某些生命基本特征的人工系统 两方面内容 1 研究如何利用计算技术研究生物现象 2 研究如何利用生物技术研究计算问题 我们现在关注的是第二部分的内容 现在已经有很多源于生物现象的计算技巧 例如 人工神经网络是简化的大脑模型 遗传算法是模拟基因进化过程的 社会系统 现在我们讨论另一种生物系统 社会系统 更确切的是 在由简单个体组成的群 落与环境以及个体之间的互动行为 也可称做 群智能 swarm intelligence 这些模拟系统利用局部信息从而可能产生不可预测的群体行为 例如 floys 和 birds 他们都用来模拟鱼群和鸟群的运动规律 主要用于计算机 视觉和计算机辅助设计 在计算智能 computational intelligence 领域有两种基于群智能的算法 蚁群 算法 ant colony optimization 和 PSO 粒子群算法 particle swarm optimization 前者是对蚂蚁群落食物采集过程的模拟 已经成功运用在很多 离散优化问题上 粒子群优化算法 PSO 也是起源对简单社会系统的模拟 最 4 初设想是模拟鸟群觅食的过程 但后来发现 PSO 是一种很好的优化工具 三三 粒子群算法的流程粒子群算法的流程图及伪代码图及伪代码 1 流程图 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 gBest For each particle Calculate particle velocity according equation a Update particle position according equation b End 5 While maximum iterations or minimum error criteria is not attained 3 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 实现实现 代码实现代码实现 packagepackage noah noah publicpublic classclass SOSO privateprivate intint x x privateprivate intint y y publicpublic SO intSO int x intx int y y this x x this x x this y y this y y publicpublic intint getX getX returnreturn x x publicpublic voidvoid setX intsetX int x x this xthis x x x 6 publicpublic intint getY getY returnreturn y y publicpublic voidvoid setY intsetY int y y this ythis y y y publicpublic voidvoid print print System out println x this x System out println x this x y this y y this y packagepackage noah noah importimport java io BufferedReader java io BufferedReader importimport java io FileInputStream java io FileInputStream importimport java io IOException java io IOException importimport java io InputStreamReader java io InputStreamReader importimport java util ArrayList java util ArrayList importimport java util Random java util Random publicpublic classclass PSOPSO privateprivate intint bestNum bestNum privateprivate floatfloat w w privateprivate intint MAX GEN MAX GEN 迭代次数迭代次数 privateprivate intint scale scale 种群规模种群规模 privateprivate intint cityNum cityNum 城市数量 编码长度城市数量 编码长度 privateprivate intint t t 当前代数当前代数 privateprivate int int distance distance 距离矩阵距离矩阵 privateprivate int int oPopulation oPopulation 粒子群粒子群 privateprivate ArrayList ArrayList ArrayList ArrayList listV listV 每科粒子的初始交换序每科粒子的初始交换序 列列 privateprivate int int Pd Pd 一颗粒子历代中出现最好的解 一颗粒子历代中出现最好的解 privateprivate int int vPd vPd 解的评价值解的评价值 privateprivate int int Pgd Pgd 整个粒子群经历过的的最好的解 每个粒子都能整个粒子群经历过的的最好的解 每个粒子都能 记住自己搜索到的最好解记住自己搜索到的最好解 privateprivate intint vPgd vPgd 最好的解的评价值最好的解的评价值 privateprivate intint bestT bestT 最佳出现代数最佳出现代数 privateprivate int int fitness fitness 种群适应度 表示种群中各个个体的适应度种群适应度 表示种群中各个个体的适应度 privateprivate RandomRandom random random publicpublic PSO PSO publicpublic PSO intPSO int n n intint g g intint s s floatfloat w w 7 this cityNumthis cityNum n n this MAX GENthis MAX GEN g g this scalethis scale s s this wthis w w w 初始化初始化 PSOPSO 算法类算法类 param param filenamefilename 数据文件名 该文件存储所有城市节点坐标数据数据文件名 该文件存储所有城市节点坐标数据 throws throws IOExceptionIOException privateprivate voidvoid init Stringinit String filename filename throwsthrows IOExceptionIOException 读取数据读取数据 int int x x int int y y StringString strbuff strbuff BufferedReaderBufferedReader datadata newnew BufferedReader newBufferedReader new InputStreamReader InputStreamReader newnew FileInputStream filename FileInputStream filename distancedistance newnew int cityNum cityNum int cityNum cityNum x x newnew int cityNum int cityNum y y newnew int cityNum int cityNum forfor int int i i 0 0 i i cityNum cityNum i i 读取一行数据 数据格式读取一行数据 数据格式 1 1 67346734 14531453 strbuffstrbuff data readLine data readLine 字符分割字符分割 String String strcolstrcol strbuff split strbuff split x i x i Integer valueOf strcol 1 Integer valueOf strcol 1 x x 坐标坐标 y i y i Integer valueOf strcol 2 Integer valueOf strcol 2 y y 坐标坐标 计算距离矩阵计算距离矩阵 针对具体问题 距离计算方法也不一样 此处用的是 针对具体问题 距离计算方法也不一样 此处用的是 att48att48 作作 为案例 它有为案例 它有 4848 个城市 距离计算方法为伪欧氏距离 最优值为个城市 距离计算方法为伪欧氏距离 最优值为 1062810628 forfor int int i i 0 0 i i cityNumcityNum 1 1 i i distance i i distance i i 0 0 对角线为对角线为 0 0 forfor int int j j i i 1 1 j j cityNum cityNum j j doubledouble rijrij MathMath sqrt x i sqrt x i x j x j x i x i x j x j y i y i y j y j y i y i y j y j 10 0 10 0 四舍五入 取整四舍五入 取整 intint tijtij int int Math round rij Math round rij ifif tij tij rij rij distance i j distance i j tijtij 1 1 distance j i distance j i distance i j distance i j 8 elseelse distance i j distance i j tij tij distance j i distance j i distance i j distance i j distance cityNumdistance cityNum 1 cityNum1 cityNum 1 1 0 0 oPopulationoPopulation newnew int scale cityNum int scale cityNum fitnessfitness newnew int scale int scale PdPd newnew int scale cityNum int scale cityNum vPdvPd newnew int scale int scale PgdPgd newnew int cityNum int cityNum vPgdvPgd Integer MAX VALUE Integer MAX VALUE bestTbestT 0 0 t t 0 0 randomrandom newnew Random System currentTimeMillis Random System currentTimeMillis 初始化种群 多种随机生成办法初始化种群 多种随机生成办法 voidvoid initGroup initGroup intint i i j j k k forfor k k 0 0 k k scale scale k k oPopulation k 0 oPopulation k 0 random nextInt 65535 random nextInt 65535 cityNum cityNum forfor i i 1 1 i i cityNum cityNum oPopulation k i oPopulation k i random nextInt 65535 random nextInt 65535 cityNum cityNum forfor j j 0 0 j j i i j j ifif oPopulation k i oPopulation k i oPopulation k j oPopulation k j break break ifif j j i i i i voidvoid initListV initListV intint ra ra intint raA raA intint raB raB listVlistV newnew ArrayList ArrayList ArrayList ArrayList 9 forfor int int i i 0 0 i i scale scale i i ArrayListArrayList listlist newnew ArrayList ArrayList rara random nextInt 65535 random nextInt 65535 cityNum cityNum forfor int int j j 0 0 j j ra ra j j raAraA random nextInt 65535 random nextInt 65535 cityNum cityNum raBraB random nextInt 65535 random nextInt 65535 cityNum cityNum whilewhile raA raA raB raB raBraB random nextInt 65535 random nextInt 65535 cityNum cityNum raAraA 与与 raBraB 不一样不一样 SOSO s s newnew SO raA SO raA raB raB list add s list add s listV add list listV add list publicpublic intint evaluate int evaluate int chr chr 01230123 intint lenlen 0 0 编码 起始城市编码 起始城市 城市城市 1 1 城市城市 2 2 城市城市 n n forfor int int i i 1 1 i i cityNum cityNum i i lenlen distance chr idistance chr i 1 chr i 1 chr i 城市城市 n n 起始城市起始城市 lenlen distance chr cityNumdistance chr cityNum 1 chr 0 1 chr 0 returnreturn len len 求一个基本交换序列作用于编码求一个基本交换序列作用于编码 arrarr 后的编码后的编码 publicpublic voidvoid add int add int arr arr ArrayListArrayList list list intint temptemp 1 1 SOSO s s forfor int int i i 0 0 i i list size list size i i s s list get i list get i temptemp arr s getX arr s getX arr s getX arr s getX arr s getY arr s getY arr s getY arr s getY temp temp 求两个编码的基本交换序列 如求两个编码的基本交换序列 如 A B SSA B SS 10 publicpublic ArrayListArrayList minus int minus int a a int int b b int int temptemp b clone b clone int int temp newtemp new int L int L for intfor int i 0 i L i i 0 i L i temp i b i temp i b i intint index index 交换子交换子 SOSO s s 交换序列交换序列 ArrayListArrayList listlist newnew ArrayList ArrayList forfor int int i i 0 0 i i cityNum cityNum i i ifif a i a i temp i temp i 在在 temptemp 中找出与中找出与 a i a i 相同数值的下标相同数值的下标 indexindex indexindex findNum temp findNum temp a i a i 在在 temptemp 中交换下标中交换下标 i i 与下标与下标 indexindex 的值的值 changeIndex temp changeIndex temp i i index index 记住交换子记住交换子 s s newnew SO i SO i index index 保存交换子保存交换子 list add s list add s returnreturn list list 在在 arrarr 数组中查找数组中查找 numnum 返回 返回 numnum 的下标的下标 publicpublic intint findNum int findNum int arr arr intint num num intint indexindex 1 1 forfor int int i i 0 0 i i cityNum cityNum i i ifif arr i arr i num num indexindex i i break break returnreturn index index 将数组将数组 arrarr 下标下标 index1index1 与下标与下标 index2index2 的值交换的值交换 publicpublic voidvoid changeIndex int changeIndex int arr arr intint index1 index1 intint index2 index2 intint temptemp arr index1 arr index1 arr index1 arr index1 arr index2 arr index2 arr index2 arr index2 temp temp 11 二维数组拷贝二维数组拷贝 publicpublic voidvoid copyarray int copyarray int from from int int to to forfor int int i i 0 0 i i scale scale i i forfor int int j j 0 0 j j cityNum cityNum j j to i j to i j from i j from i j 一维数组拷贝一维数组拷贝 publicpublic voidvoid copyarrayNum int copyarrayNum int from from int int to to forfor int int i i 0 0 i i cityNum cityNum i i to i to i from i from i publicpublic voidvoid evolution evolution intint i i j j k k intint lenlen 0 0 floatfloat rara 0f 0f ArrayListArrayList Vi Vi 迭代一次迭代一次 forfor t t 0 0 t t MAX GEN MAX GEN t t 对于每颗粒子对于每颗粒子 forfor i i 0 0 i i scale scale i i if i bestNum if i bestNum continue continue ArrayListArrayList ViiVii newnew ArrayList ArrayList System out println System out println 更新速度更新速度 Vii wVi ra Pid Xid rb Pgd Xid Vii wVi ra Pid Xid rb Pgd Xid ViVi listV get i listV get i wVi wVi 表示获取表示获取 ViVi 中中 size wsize w 取整个交换序列取整个交换序列 lenlen int int Vi size Vi size w w 越界判断越界判断 if len cityNum if len cityNum len cityNum len cityNum System out println w w System out println w w len len len len Vi size Vi size Vi size Vi size forfor j j 0 0 j j len len j j Vii add Vi get j Vii add Vi get j ArrayListArrayList a a minus Pd i minus Pd i oPopulation i oPopulation i rara random nextFloat random nextFloat 12 lenlen int int a size a size ra ra 越界判断越界判断 forfor j j 0 0 j j len len j j Vii add a get j Vii add a get j ArrayListArrayList b b minus Pgd minus Pgd oPopulation i oPopulation i rara random nextFloat random nextFloat ra Pid Xid ra Pid Xid lenlen int int b size b size ra ra 越界判断越界判断 forfor j j 0 0 j j len len j j SOSO tt tt b get j b get j Vii add tt Vii add tt listV add i listV add i Vii Vii add oPopulation i add oPopulation i Vii Vii 计算新粒子群适应度 计算新粒子群适应度 Fitness max Fitness max 选出最好的解选出最好的解 forfor k k 0 0 k k fitness k fitness k vPd k vPd k fitness k fitness k copyarrayNum oPopulation k copyarrayNum oPopulation k Pd k Pd k bestNum k bestNum k ifif vPgd vPgd vPd k vPd k System out println System out println 最佳长度最佳长度 vPgd vPgd 代数 代数 bestT bestT bestTbestT t t vPgdvPgd vPd k vPd k copyarrayNum Pd k copyarrayNum Pd k Pgd Pgd publicpublic voidvoid solve solve intint i i intint k k initGroup initGroup 13 initListV initListV 每颗粒子记住自己最好的解每颗粒子记住自己最好的解 copyarray oPopulation copyarray oPopulation Pd Pd 计算初始化种群适应度 计算初始化种群适应度 Fitness max Fitness max 选出最好的解选出最好的解 forfor k k 0 0 k k vPd k vPd k vPgdvPgd vPd k vPd k copyarrayNum Pd k copyarrayNum Pd k Pgd Pgd bestNum k bestNum k 打印打印 System out println System out