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

西安工业大学毕业设计(论文)

根据以上对粒子群算法的重新定义，可以把公式（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】 。 …… 此处隐藏：37字，全部文档内容请下载后查看。喜欢就下载吧 ……