西安工业大学毕业设计(论文)
为(1,2,...,n)的排列，Sij 表示访问第i个城市后访问第j个城市。
目标函数（在粒子群算法中也可以叫做适应值函数）：城市Hamilton回路总长度为：
mind??D[s(k),s(k?1)] (3.2.1)
n?1k?1引入决策变量：
?1xij???0若旅行商访问城市i后访问城市j (3.2.2)
否则旅行商问题定义虽然非常简单，使用穷举法可以让旅行商得到确定的最优解，但随着需要访问城市数目的增加，会出现所谓的组合爆炸现象。所以，城市数目比较多的时候使用穷举搜索策略几乎是不可能做到的。
10
4 改进的粒子群算法去解决TSP问题 4 改进的粒子群算法求解TSP问题
4.1 改进的粒子群算法简介
由第二章的基本粒子群算法介绍，我们可以看出基本的粒子群算法对适应度函
数是有连续的要求。因此，基本粒子群算法在很多连续优化问题中得到成功应用，但粒子群算法不能直接应用到离散问题中，那么，如果非要用它解决离散问题，就必须对算法进行改进。我们需要对方程(2.2.1)和方程(2.2.2)进行改写并且重新定义方程中加法和乘法的含义。下面我将介绍几种改进的粒子群算法，这些算法可以比较好的解决旅行商这种离散型问题。
王翠茹，张江维，王 等[13][14]对粒子群优化算法进行了改进后，粒子不仅根据自身和同伴中最好的个体调整自己的飞行速度，而且按照一定的概率向其他个体学习，这种强化后的学习行为更符合自然界生物的学习规律，更有利于粒子发现问题的全局最优解。同时借鉴单点调整算法思想，提出了调整因子和调整序概念用以重构粒子群算法。傅 刚[15]认为，用粒子群算法解决旅行商问题时，调整因子的先后顺序决定下一代种子的优劣，以及能否很快地收敛到最优值，如何恰当地解决惯性权重个体间的协作和个体历史最优以及群体最优对个体的影响是快速高效解决这一问题的关键。
旁巍，王康平，周春光等[16]通过引入模糊矩阵提出了一种改进的粒子群优化算法，采用模糊矩阵来表示粒子的位置和速度，并重新定义速度和位置更新公式中的各种运算符号，这种改进的粒子群算法给求解旅行商问题提供了一种新思路。基于这种思路下文将会介绍详细的实现过程。
郭文忠等[17]在介绍目前已经有多种针对惯性权值的研究的基础上，提出引入模 糊技术，并提出了佳粒子距的概念，并给出了一种惯性权值的模糊自适应调整模型及其相应的粒子群优化算法，使用不同的惯性权值更新同一代种群，用于TSP问题的求解。实验结果表明改进后的算法不仅在求解组合优化问题中的有效性，而且同时提高了算法的性能，加快了收敛速度。
2012年中国学者易云飞，陈国鸿[18]提出了基于k-means的改进粒子群算法求解旅行商问题。也是一种基本粒子群算法进行了改进，每一步都借鉴贪心算法的思想取局
11
西安工业大学毕业设计(论文)
部最优，这样产生的初始种群全局最优值已经比较接近问题的解，可以节省搜索时间,提高算法收敛速度。针对粒子群算法易陷入局部最优的缺陷，采取了适合于求解旅行商问题的基于k-means的改进策略,对粒子群进行聚类分析，实现了粒子之间的信息交换,扩大了粒子的搜索空间。两个种群同时寻优,种群内部独立进行粒子群算法进化，种群个体最优之间以一定概率进行交叉，两个种群同时寻优可以减小算法陷入局部最优的概率，种群间个体最优的交叉能够增强两种群间以及粒子间的信息共享，及时传递最优值信息，提高粒子向更好解进化的速度。实验结果表明这种改进粒子群算法是有效的。
西南大学计算机与信息科学学院的教授王文峰，刘光远，温万惠[19]共同进行了求解旅行商问题的自逃逸混合离散粒子群算法研究。这种算法是结合自然界中种群密度过大时，个体自动寻找栖息地的习性，提出了一种自逃逸思想：从候选边集合中吸收新边，给陷入局部区域的粒子一个变异，使其跳出局部区域。自逃逸思想提高了粒子群算法的全局搜索能力，成功地克服了早熟的缺陷。实验结果表明，自逃逸的粒子群算法比混合蚁群算法具有更好的效率和收敛速度, 尤其在较大规模的实例上更具优势。
4.2 引入模糊矩阵的粒子群算法求解TSP问题
4.2.1旅行商问题的解用模糊矩阵表示
在用模糊矩阵[16]表示旅行问题的解前，我们首先引入以下几个定义：
定义1：一个城市为n的旅行商问题，设集合s为旅行商问题的一个解序列，s可以表示为S?{s1,s2,s3,...sn}，其中si(i?1,2,...n)表示旅行商问题的解即Hamilton回路中第i个结点。
定义2：一个城市为n的旅行商问题，设集合M是旅行商问题的结点集合，M可以表示为：M?{m1,m2,m3,...mn}，那么mi(i?1,2,3...n)表示旅行商问题中编号为i的具体结点。
对上述的定义1和定义2，进行解释：集合S中的每个元素，si表示旅行商问题可行解中按照访问的先后次序的第i个结点，即已访问了i-1个结点，即将访问第i
12
西安工业大学毕业设计(论文)
个结点，还有n-i个结点需要访问；对于集合M中的元素mi(i?1,2,...n)表示的是旅行商问题中编号为i的结点(这个结点的顺序不发生改变)。则整个状态空间可以表示为S和M的笛卡尔积：
SS?S?M?{(si,mi)si?S,mi?N} S与M的模糊关系R有如下意义：
ri,j??R(si,mj),(0?ri,j?1) (4.2.1) ?R是隶属度函数，表示在一个可行解中第 i 个要访问的点选择编号为j的结点的隶属度。
显然，如果我们有了这个隶属度函数?R，那么我就可以确定一个模糊矩阵。下面介绍旅行商问题的解是怎样用模糊矩阵表示的。
在上文定义中已经分别提到了集合S?{s1,s2,s3,...sn}和集合M?{m1,m2,m3,...mn} 它们的模糊关系可以用模糊矩阵来表示，因此，从S到M的模糊关系可以写成：
R?(rij)n*n?r11?r1n?? (4.2.2) ?????????rn1?rnn??其中rij?[0,1]，它表示集合S中第i个元素si与集合M中第j个元素mj对于关系R的隶属程度。
4.2.2引入模糊矩阵的粒子群算法重新定义
基于上面提出的用模糊矩阵表示旅行商问题的解, 进而提出了一种改进的粒子群算法。首先重新定义速度和位置的更新公式(2.2.1)、(2.2.2)中的符号与操作符。
粒子的位置是要用来表示旅行商问题的解，因此定义为公式（4.2.2）这种形式：
?r11?r1n?? X?????（4.2.3） ????rn1?rnn?? 粒子的速度重新定义为：
13
西安工业大学毕业设计(论文)
?v11?v1n?? （4.2.4）V????? ????vn1?vnn??操作符“乘法”的重新定义: 我们使用符号“?”表示新的乘法, 设a 是一个实数, 则：
?v11?v1n??a*v11?a*v1n????? a?V?a*???????（4.2.5） ??????vn1?vnn????a*vn1?a*vnn??操作符“减法”的重新定义: 我们使用符号“?”表示新的减法,则：
?a11V?V1?V2??????an1?a11?b11????????an1?bn1?
?a1n??b11?b1n??????????????ann????bn1?bnn?? （4.2.6）
a1n?n1n????ann?bnn??操作符“加法”的重新定义: 我们使用符号“?”表示新的加法,加法可以是速度之间的加法也可以是位置和速度之间的加法则分别表示为：
?a11V?V1?V2??????an1?a11?b11????????an1?bn1?
?a1n??b11?b1n??????????????ann????bn1?bnn?? （4.2.7）
a1n?n1n????ann?bnn???a11?a1n??b11?b1n????????X??X?V????????? （4.2.8）
????a?ab?bnn?nn??n1?n1 14