西安工业大学毕业设计(论文)
gbest?(pg1,pg2,?,pgD)
在找到这两个最优值时，粒子根据如下的公式(1)和(2)来更新自己的速度和位置[12]：
vid?w?vid?c1r1?pid?xid??c2r2(pgd?xid) (2.2.1)
xid?xid?vid (2.2.2)
其中?为惯性权重，c1,c2为学习因子，r1,r2为0到1之间均匀分布的随机数。 粒子群算法的性能很大程度上取决于算法参数的选择，选取较好的参数，不仅能
缩短算法执行的时间，而且可以提高解决问题的准确性。这其中决定算法性能的参数有：粒子数、惯性权重、学习因子、等，各个参数的选择一般情况下可以参考如下： ? 粒子数：粒子数的多少选择一般是根据问题的复杂性决定的。对于一般优化问题
取20到40个粒子完全可以得到很好的结果。
? 粒子的维度：这是由优化问题决定，就是问题解的维度。
? 学习因子：学习因子使粒子具有自我总结和向群体中优秀个体的学习能力，一般
取值范围为0到4。
? 惯性权重：决定了粒子对当前速度继承多少，合适的选择可以使粒子具有均衡的
探索能力和开发能力。惯性权重越大粒子的全局搜索能力越强，反之惯性权重越小粒子的局部搜索能力越强。
2.3 算法的流程和流程图
算法的流程如下：
步骤1：初始化粒子群，包括群体规模N，每个粒子的位置xi和速度Vi； 步骤2：计算每个粒子的适应度值，并将当前微粒的位置和适应值存储在pbest中，将所有粒子的pbest中适应值最好的个体存储在gbest中； 步骤3：根据公式(2.2.1),(2.2.2)更新粒子的速度vi和位置xi；
（i）步骤4：每个粒子，用它的适应度值Fit[i]和个体极值pbest比较出较优为新pbest（i）；
步骤5：所有粒子的新的pbest选出最优的，为新的gbest；
5
西安工业大学毕业设计(论文)
步骤6：如果满足结束条件(通常为预设的计算精度或到达最大循环次数)退出，否则返回步骤3。
6
西安工业大学毕业设计(论文)
算法的流程图如下：
开始 初始化每个粒子的速度和位置 计算每个粒子的适应值 求出每个粒子的个体最优 求出整个群体的全局最优值 根据方程(2.2.1)对粒子的速度进行进化 根据方程(2.2.2)对粒子的位置进行进化 否 是否满足条件
是
输出结果
7
西安工业大学毕业设计(论文)
总结：对于这种连续性的问题,用粒子群算法求解,只要随着粒子数和迭代步数的增加,求解的结果会不断趋近最优解。
2.4 算法的优缺点分析
粒子群算法的优点：粒子群优化算法(PSO)是模拟鸟群觅食过程中的行为提出的一种基于群体智能的演化计算方法。该算法易于描述，在求解过程中只有非常少的参数需要调整并且无集中控制约束，不会因个体的故障影响整个问题的求解，确保了系统具备很强的鲁棒性，相比其它演化算法，只需要较少的函数计算次数就可达到收敛，因此能以较大概率找到问题的全局最优解。最后该算法最大的优势也在于编程简单，易实现。
粒子群算法的缺点：在求解全局最优解的过程中对于有多个局部极值点的函数，容易陷入到局部极值点中，得不到正确的结果。此外，由于粒子群算法问世时间不长在搜索纠结过程中缺乏精密搜索方法的配合，导致使用粒子群算法这种方法往往不能得到精确的结果。再则，PSO方法提供了全局搜索的可能，但并不能严格证明它在全局最优点上的收敛性。因此，PSO一般适用于存在多个局部极值点而并不需要得到很高精度的优化问题。对于本文而言，基本粒子群算法有一个致命的的缺点，它速度更新和位置更新都是由特定的连续函数决定的，所以它只能解决连续性优化问题，对于求解离散问题存在困难。
8
3 旅行商问题 3 旅行商问题
3.1 TSP问题介绍
旅行商问题(Traveling Salesman Problem,简称TSP)是一个典型的NP问题也是一个典型的组合优化问题。旅行商问题描述如下：给定n个城市及两两城市之间的距离，求一条经过各城市一次且仅一次的最短路线。对于n个城市的TSP问题，存在着（n-1）! /2条可能的路径，随着城市数目n的增长，可能路径的数目以n的指数倍增加。如果使用穷举法搜索，需要考虑所有可能的情况，并两两比较，找出最优解，那么可搜索的路径及距离之和的计算量将正比于n! /2，算法的复杂度呈指数增长，要求出旅行商问题的最优化解是很困难的，这也是该问题被认为是NP问题的原因。同样不幸的是，旅行商问题为离散问题，使得可以解决该问题的方法更少。因此，任何可以求解旅行商问题的方法都应被高度关注。
在生产生活中许多问题都可以转化为旅行商这类问题的模型，因此旅行商问题具有很高的实际应用价值，例如：城市管道铺设优化、物流行业中的车辆调度优化、制造业中的切割路径优化以及电力系统配电网络重构等现实生活中的很多优化问题都可以归结为旅行商模型来求解，目前旅行商问题应用的一个非常重要方面就是无人飞机的航路设计问题，即事先针对敌方防御区内的威胁部署和目标的分布情况，对无人作战飞机的飞行航路进行整体规划设计，可以综合减小被敌方发现和反击的可能性降低耗油量，从而显著提高UCAV（无人战斗机）执行对地攻击（或侦察）任务的成功率。
3.2 TSP问题定义
设n为城市数目D?[dij]为n*n阶距离矩阵，dij代表从城市i到城市j的距离，
i?1,2,...,n，j?1,2,...,n。问题是要找出访问每个城市且每个城市恰好只访问一次的
一条Hamilton回路，且其路径的总长度是最短的。
这条Hamilton回路可以表示为(1,2,...,n)的所有循环排列的集合，即S?[Sij]
9