西安工业大学毕业设计(论文)
根据以上对粒子群算法的重新定义，可以把公式（2.2.1）、（2.2.2）分别改写。 速度更新公式为：
Vit?1???Vit?(C1*r1)?(pit?Xit)t?(C2*r2)?(pg?Xit) （4.2.9）
其中?为惯性权重，c1,c2为学习因子，r1,r2为0到1之间均匀分布的随机数，Vit表示第i个粒子第t次迭代后的速度，Xit表示第i个粒子第t次迭代后的位置，pit表
t示第i个粒子第t次迭代后的局部最好位置，pg表示第i个粒子第t次迭代后的全局
最好位置。
位置更新公式为：
Xit?1?Xit?Vit?1 （4.2.10）
4.2.3引入模糊矩阵的粒子群算法求解旅行商问题的具体操作
基本粒子群算法通过引入模糊矩阵把公式（2.2.1）、（2.2.2）分别改写为公式（4.2.9）、（4.2.10），为了确保改写后粒子群算法公式能够适用这种矩阵的变化，因此，在初始化时需要有许多特定的条件。下面先介绍这种改进的粒子群算法是如何初始化的。
初始化位置：
?r11?r1n?? X?????（4.2.11） ????rn1?rnn??矩阵中的元素是按照如下条件随机生成： a.
?rj?1nij?1,i?(1,2,...n) （4.2.12）
b. rij?(0,1) （4.2.13） 速度初始化：
?v11?v1n?? （4.2.14）V0????? ????vn1?vnn??
15
西安工业大学毕业设计(论文)
随机产生速度中元素必须也满足下面条件：
?vj?1nij?0（4.2.15） i?(1,2,...n)
下面引入几个引理，能很好的说明为何会有如此的条件限制初始位置和初始速度。
引理1：设a是一个实数, 如果速度V满足条件?vij?0,则a?V也满足条件
j?1n?vj?1nij?0。
nn引理2：如果位置 X满足?rij?1,i?(1,2,...n),并且位置V满足?vij?0, 则
j?1j?1X?V也满足?rij?1。
j?1n引理3：如果位置X1和X2满足
?rj?1nij?1,i?(1,2,...n),则X1?X2满足条件
?vj?1nij?0。
nn引理4：如果速度V1和速度V2满足?vij?0, 则V1?V2也满足?vij?0。
j?1j?1根据上述引理可以得到如下结论，在需要公式(4.2.9)和(4.2.10)进行更新的矩阵,若矩阵满足等式(4.2.13)和(4.2.15),则在以后的更新迭代中,更新后的速度将总是满足条件(4.2.15)，并且更新后的位置也将总是满足条件(4.2.13)。这个结论可以用数学归纳法进行证明，由于证明过程比较简单，所以在此我就不详细说明。
有了以上结论我们可以成功的把粒子群算法思想应用于离散的旅行商问题中。但这不能说粒子群算法已经可以解决旅行商问题了，这其中还存在有些问题需要解决。 这其中最主要的问题是:在每次迭代后，位置矩阵中的元素可能产生负值，这与条件（4.2.13）是不相符的。因此，在每次迭代后都应该对元素中是否出现负数进行检测。对于不符合条件的元素可以采用如下规范化进行操作：
首先将矩阵中所有为负数的元素清零, 然后将位置矩阵(4.2.3)在不违反
16
西安工业大学毕业设计(论文)
(4.2.12)的情况下进行如下的变化：
nn??r/r?r/r1n?1i??11?1ii?1i?1?????（4.2.16） ?? nn??r/r?r/rnn?ni??n1?nii?1i?1??算法流程描述：
在介绍算法流程前，首先介绍一个概念：非模糊化（也就是模糊化的一个逆过程）。非模糊化采用的方法为：“最大数法”，是非模糊化的常用方法, 在这种方法中, 用一个标志数组记录是否选择了矩阵中的列,并用一个路径数组来存储路径解。首先所有的列都标记为“未选择”,然后对于矩阵中的每一行,选择未被其他行选择过的并且具有最大值的那个元素,然后将这个元素所在的列标记为“选择”,并且该列的列号被记录在路径数组中,表示在本行中选择序号为该列号的节点。当所有的行都被处理完成后,就可以从路径数组中得到解路径以及解路径的费用值。采用这种方法,能够保证最终得到旅行商问题的可行解【16】 。
步骤1：初始化
步骤1-1：设置粒子群算法中粒子的个数，和最大迭代次数，对于解决旅行商问题的粒子算法中的迭代次数设置非常关键，因为迭代次数一般为算法终止条件，因此选择合适的迭代次数对算法的性能影响非常大。
步骤1-2：应用上述初始化过程，对粒子群算法中的每个粒子进行初始化得到一个随机的位置X，并且随机初始化得到一个随机速度V。最后让这些初始化的粒子位置为粒子的局部最优解pi，并在这些初始化后粒子群中选出全局最优解pg。
步骤2：计算粒子群算法中每个粒子的速度和位置。 步骤2-1：用公式（4.2.9）更新每个粒子的速度。 步骤2-2: 用公式（4.2.10）更新每个粒子的位置。
步骤2-3：对新位置矩阵进行非模糊化,计算新位置的费用。如果新位置的费用比当前局部最好解的费用还要小,则用新的位置更新当前的局部最好解。
步骤3：如果粒子群算法中粒子的局部最优解中存在优于当前的全局最优解时，则用此局部最优解来更新当前的全局最优解。
步骤4：判断当前的迭代次数是否达到预先设定的最大值，如果大于转步骤5，
17
西安工业大学毕业设计(论文)
否则转步骤2.
步骤5：输出最好路径和费用。
总结：这种改进的粒子群优化算法，其算法的流程和基本的粒子群算法的流程相似，只是在一些计算方面有些区别。该算法在解决旅行商这类离散型问题表现的不是那么高效，但它也是粒子群算法解决离散型问题的新尝试。值得注意的是,该算法不仅仅能够解决旅行商问题, 经过修改后也能够解决一般路由问题。由于旅行商问题的 特殊性,模糊矩阵的规模是n2,在一些简单的路由问题中,可以缩减矩阵的规模。另外, 能否寻找更好的非模糊化的方法, 也是今后的工作需要解决的问题[16]。
4.3 引入交换算子和交换序的粒子群算法求解TSP问题
4.3.1引入交换算子和交换序的粒子群算法定义和流程
黄岚等，王康平等[11]通过引入交换子和交换序的概念，并对基本公式中的符号赋予新的含义，构造了一种特殊的粒子群优化算法，这种改进的粒子群算法使得用粒子群算法思想解决离散问题成为可能。后来Clerc，M[12]重新定义了运算符号和规则，并用于求解离散问题，重新定义后的粒子群算法相比以前的算法有了很明显的改观。下文将会把这种改进的粒子群算法应用到解决旅行商问题中。
引入交换算子和交换序是另种一种改进的粒子群算法去解决旅行商这种离散型问题的方法。这种方法也是粒子群算法应用到离散型问题的第一次尝试的方法。此方法的问世，使得粒子群算法的应用领域反生巨大的改变。下面先介绍交换算子和交换序的概念。
交换算子：是用来交换一个有序序列中元素的位置，一个交换算子可以使这个有序序列中两个元素位置发生调换。具体到改变旅行商问题中，表示旅行商的可行解序列发生改变，改变后的结果仍是旅行商问题的可行解。用SO（i，j）表示一个交换子，i，j就表示序列中第i个元素和序列中第j个元素的位置发生调换。例：序列S=（1，2，3，4），交换算子SO（1，2），用?表示交换算子作用于序列S，即S?SO变化后得到S?=（2，1，3，4）这里的?被赋予特定含义。
交换序：一个或多个交换子的有序队列就是交换序。如交换算子SO，SOO,SOOO,SOOOO...组成交换序SS，那么SS=（SO，SOO，SOOO，SOOOO....）。当SS
18
西安工业大学毕业设计(论文)
作用一个序列就等于这个交换序中每个交换算子作用于这个序列。例：序列S=（1，2，3，4）交换序SS(SO,SOO),SO(1,2),SOO(3,4)，那么S?SS=S?SO?SOO=（2，1，4，3）。
在上边两个概念基础上再定义几个概念：
交换序的等价集：不同的交换序作用于同一解上可能产生相同的新解, 所有有相同效果的交换序的集合称为交换序的等价集。
基本交换序：在交换序等价集中, 拥有最少交换子的交换序称为该等价集的基本交换序。例：设给定两个解路径A =（1，2，3，4，5）和B=（4，3，2，1，5）,需要构造一个基本交换序 SS, 使得B?SS= A可以看出A（1）=B（4），A（2）=B（3），A（3）=B（2），A（4）=B（1），A（5）=B（5）可以看出第一个交换算子为SO（1，4，）第二个交换算子为SO（2，3），第三个交换算子为SO（3，2），第四个交换算子为SO（4，1），第五个交换算子为SO（5，5）那么SS=（（1，4），（2，3），（3，2），（4，1），（5，5）），即SS=B?A，这里的?和?被赋予新的含义。
在引入交换序和交换序列后基本的粒子群算法的公式（2.2.1）需要改写，计算符号的含义也需要改变。
粒子速度更新公式改写为：
t（4.3.1） Vit?1?Vit?r1(pit?Xit)?r2(pg?Xit)
这个公式的?和?的含义于上文概念介绍提到的含义相同；r1和r2为0到1之间的随机数，Vit表示第i个粒子第t次迭代后的速度，Xit表示第i个粒子第t次迭代后
t的位置，pit表示第i个粒子第t次迭代后的局部最好位置，pg表示第i个粒子第t次
迭代后的全局最好位置；r1(pit?Xit)表示基本交换序(pit?Xit)中的所有交换子以概率
tt?Xit)表示基本交换序(pg?Xit)中的所有交换子以概率 r2保留 ；r1保留 ；同理r2(pg可以看出r1和r2的值越大保留的交换子就越多。粒子群算法思想的向局部最好解和全局最好解学习，改变移动方向在这个速度更新公式中也得到体现。
粒子的位置更新公式保持原来的基本粒子群算法的公式（2.2.2），只是加法的含义发生改变，因此新位置更新公式可以改写为：
Xit?1?Xit?Vit?1 （4.3.2）
19