基于粒子群算法的TSP问题研究 - 图文(8)

步骤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