河池学院2012届本科毕业论文（设计）
小结
“没有免费午餐”的理论认为：不包含领域知识的算法不一定有效，但包含过多的问题领域知识也会因此导致算法对其它问题的脆弱性。从上面可以发现，当前已经有多种对PSO 算法的改进，然而正如“没有免费午餐”的理论所认为的，这些改进算法需要针对具体问题的特点，根据领域知识对算法参数进行设置，在提高某种性能的同时也为此付出相应代价。粒子群算法容易陷入局部最小，因此，如何实现全局搜索能力和局部搜索能力的平衡是改进的重点。
4 TSP问题概述
TSP是运筹学、图论和组合优化中的NP难问题。问题的具体如下：给定N个城市及两两城市之间的距离，求一条经过各城市一次且仅一次的最短路线。其图论描述为：给定图G=（V，A），其中V为顶点集，A为各顶点相互连接组成的弧集，已知各顶点间连接距离，要求确定一条长度最短的Hamilton回路，即遍历所有顶点一次且仅一次的最短回路。设
dij为城市i与j 之间的距离，即弧(i,j)的长度。引入决策变量：
(4.1)
??1 若旅行商访问城市i 后访问城市j
=?
0 否则??
MinZ?则TSP的目标函数为
i,j?1?Xnijdij (4.2)
TSP 问题描述非常简单，但最优化求解很困难，若用穷举法搜索，则要考虑所有可能情况，并两两对比，找出最优,其算法复杂性呈指数增长, 即所谓的“组合爆炸”。所以，寻求和研究TSP 的有效启发式算法,是问题的关键。
5 球隙迁移算法
5.1球隙迁移算法的定义
球隙：设ｎ维空间中由ｋ个点围成的一个唯一确定的超球G，这ｋ个点都在球面上，则称球G为一个球型的空隙（空心球），简称球隙。
从极值域 中一点B出发做贪心搜索，轨迹必趋向极点Ａ，称B－A为起－极对。
10
河池学院2012届本科毕业论文（设计）
极值域12球隙17球隙3极值域3极值域456球隙2
图5-1 球隙、极值域示意图
5.2球隙迁移算法的原理
球隙迁移法包括贪心搜索和球隙转移两个过程。贪心搜索为单一的开采，球隙转移为纯粹的勘探。
把每一个局部极小点A都看成一个吸引子，A所在的极值域称作其吸引域，在搜索得到极小点A之后如何摆脱它就成为最大的难点。解决策略是在搜索得到A点之后，为了摆脱它的吸引，应将接下来的搜索转移到其吸引域之外，且不能是原来老的吸引域，并转移到新的极值域进行搜索，发现新的极值，不断地找到新极值，这样就成功克服了局部最小，并有效地回避历史上已经发现的多个局部极小，避免重复搜索。当所有极值都发现了，从中选取最好的则为全局极值。
启发式策略1：离已找到的极小点越远越不容易落入其极值域。
启发式策略2：离已使用过的转移点越远越不容易落入老极值域 老转移点表明该区域已被开采过。
启发式策略3：如果形成球隙G的点都是起－极对 则G的大小应当减半考虑。 其中关键的一步是求下一个转移点，设已知当前k个点形成球隙序列，新增加第k+1个点 判断新点落入的那个Voronoi多边形体内，同时修改该Voronoi多边形体及相应
11
河池学院2012届本科毕业论文（设计）
Voronoi多边形体的边与顶点。如新球隙符合启发式策略3 还需对新球隙的大小进行修正，于是得到新的球隙序列。此处Voronoi法不是用于逼近目标函数ｆ的极小点，反而是远离之。
5.3基于球隙转移的改进措施
基本粒子群算法的速度进化方程由认识和社会两部分组成，如何实现全局搜索能力与局部搜索能力的平衡是一个重要的研究方向。PSO算法极易陷入局部极值，如何保证其在陷入局部最优时，能够及时“跳出”，继续进行全局搜索，对于提高其寻优性能有着至关重要的影响。球隙迁移算法中，发现局部极小（开采）和克服局部极小（勘探）这两个过程互不影响，并能防止其陷入已经发现的局部极小，这样就避免了不必要的重复探索，提高了性能。在解决TSP问题时，基于球隙迁移的策略克服了易陷入局部最优的缺陷，它不但能保证及时的“跳出”，同时，还能有效地回避历史上已经发现的多个局部极小。 5.4算法主要流程
Step1：用贪婪算法产生两个初始种群A群和B群，随机产生两个基本交换序作为两个种群的初始速度，设定惯性权重w及
，
； 和全局极值
；
Step2：计算粒子适应度，确定个体极值
Step3：利用球隙迁移算法对粒子的历史最优解进行分析，确定每个粒子的球隙序列，并在极值域内进行贪心搜索；
Step4：对搜索到的每个粒子，比较它的适应度值和邻域局部最优位置的适应度值，如果更好，更新；
Step5：对搜索到的每个粒子，比较它的适应度值和种群的最好位置的适应度值，如果更好，更新；
Step6：利用球隙迁移算法进行球隙转移，在新的极值域进行贪心搜索，发现新的局部极小值点，并确定下一个转移点，继续进行搜索；
Step7：如未满足终止条件（连续多次没有发现新的极小点），则返回Step2。 改进算法的流程图如图5-1所示：
12
河池学院2012届本科毕业论文（设计）
开始贪心算法产生两个初始种群计算粒子的适应度利用球隙算法确定球隙序列NO更新下一代粒子的速度和位置确定下一个转移点满足结束条件YES结束 图5-1 改进算法的流程图
初始种群的产生借鉴贪心算法（Greedy Algorithm）的思想，每一步都取局部最优。由于旅行商问题为一个循环回路，所以可以选择任意一个城市作为起始城市。采用贪心算法的思想，随机选择一个城市作为出发城市，并始终选择距离当前城市最近的城市作为下一个遍历城市，直到所有城市均被遍历后直接连接到出发城市即可。可以利用这个贪心算法得到近似最优循环序列，产生一定规模的初始种群。
6改进的粒子群算法求解TSP问题
6.2概念更新
TSP问题为离散问题，用PSO求解TSP问题需要对基本PSO算法中粒子的位置、速度以及操作进行重新定义： （1）粒子的位置
粒子的位置可以定义为一个具有所有节点的哈密尔顿圈，设所有与存在，粒子的位置可表示为序列空间。
（2）粒子的速度
速度定义为粒子位置的变换集，表示一组置换序列的有序列表。可以表示为：
13
之间的弧，E为状态
,其中
河池学院2012届本科毕业论文（设计）
,
其中，然后交换
、
表示该速度所含交换的数目，式(3.1)表示先交换粒子中的位置，依此类推。
、
的位置，
（3）粒子位置与速度的加法操作
该操作表示将一组置换序列依次作用于某个粒子位置，其结果为一个新的位 置，即一个新的节点的排列。例如：位置为X={l，5，2，4，3，l}，速度为V={(1，3)，(2，4)},则其相加X+V后结果为X={2，4，1,5,3,2}。 （4）粒子位置与位置的减法操作
粒子位置与位置相减后结果为一组置换序列，即速度。例如X={2，4，1，5，3，2}，Y={1，5，2，4，3，1}，由于X(1)=Y(3)=2,)=2，所以第一个交换为
，因此第二个交换为，作用到粒子的位置X1后得
，所以位置X
与位置Y相减后得到一组置换序列，即X-Y={(1,3),(2,4)}。 （5）粒子速度与速度的加法操作
粒子速度与速度的加法操作为两个置换序列的合并，结果为一个新的置换序列，即一个新的速度。例如：速度
。
6.3公式更新
粒子的速度、位置及其各种操作重新定义后，离散粒子群算法的速度更新公式表示如下：
= w =
⊕ +
（
-）⊕
（
-） （6.1）
,相加后得
（6.2）
其中，、仍为加速常数，在0～2之间取值，r1、r2为（0，1）上均匀分布的两个相互独立的随机数；?为两交换序的合并算子，表示速度与速度的加法操作；－表示粒子位置与
位置的减法操作；＋表示粒子位置与速度的加法操作。
7 实验结果与分析
7.1实验结果
表6-1 14 节点的 TSP 标准问题
14