《1　前言》

1　前言

粒子群算法（particle swarm optimizer，PSO）是根据鸟类捕食原理提出的[1]，是一种基于群体智能的随机优化算法。PSO 与其他类似遗传算法的进化方法相比，易于实现，计算量小，易于在工程中应用，广泛应用于函数优化、模式分类、优化调度、神经网络训练、模糊系统控制等领域[2,3]，并显示出很强的全局优化能力。

旅行商问题（TSP）在工程科学中是一种具有重要意义的组合优化问题。近年来仿生学优化理论的发展，提出了采用模拟自然进化过程求解 TSP 问题的一系列方法。意大利学者 M .Dorigo 于 20 世纪 90 年代初开始提出蚁群算法[4]，设计人工蚂蚁，模仿自然界蚂蚁在觅食过程中留下信息素的行为，用于解决复杂的组合优化问题，取得了很好的效果。蚁群算法利用了信息素的正反馈机制搜索组合优化问题的解，因此信息素的更新在求解过程中起至关重要的作用。但蚁群算法也存在着收敛速度慢、容易过早停滞陷入局部最小等问题。

笔者结合蚁群算法的信息素机制，实现粒子群方法在 TSP 问题上应用。对基本粒子群算法进行了改进，针对多样性下降导致的局部最优问题，设计一种自动调节机制，根据群体适应值的差异计算多样性，并在群体多样性下降到一定程度时，随机退化部分适应值较高的粒子，增强群体的多样性。

《2　TSP 问题与蚁群算法中信息素机制》

2　TSP 问题与蚁群算法中信息素机制

图 G = （ U，E）代表 n 个城市的分布，ui，uj ∈ U，ui，uj  分别表示第 i，j 个城市，边 eij  ∈ E 上有非负权值 w（eij  ） = d（i，j），d（i，j）代表 2 个城市之间的距离。寻找 G 的一个最小 Hamilton 圈 C，使得 C 的总权值

最小，则该问题称为旅行商问题。当 d（i，j） = d（j，i）时，称为对称旅行商（STSP）问题，否则称为非对称旅行商（ATSP）问题。

蚁群算法求解 TSP 问题的主要步骤如下 ：共有 m 只蚂蚁，每只蚂蚁都要经过每个城市一次。蚂蚁对于下一个城市的选择主要考虑到该城市的路径上信息浓度和到该城市的距离。如果 i 表示蚂蚁当前的位置，则蚂蚁到城市 j 的概率表示为

τij （t）是 i 到 j 的信息素浓度，ηij （t） = 1/d（i，j）为启发式信息。α 表明留在每个结点上信息量受重视的程度，β 表明启发式信息受重视的程度。tabu 为禁忌列表，是蚂蚁已经经过的城市集合。初始时刻，所有城市之间的信息素浓度相同。随着时间的推移，城市路径上的信息素会挥发一部分，同时每只蚂蚁在它经过的路径上会增加部分信息素。因此，蚁群算法在每次所有蚂蚁遍历一遍后更新城市之间路径上的信息素，较短路径有较大的机会增加信息素，并在下一轮遍历中吸引更多的蚂蚁。

可以看到，信息素是蚁群算法中信息交流的唯一途径。蚁群在寻找路径过程中获得的信息表现为信息素更新的形式，信息素的更新进一步指导蚁群下一次的寻找路径过程，最终整个蚁群的路径朝一个局部或全局最优的路径收敛。但是由于蚂蚁总是依赖于其他蚂蚁的反馈信息来强化学习，导致经过初始时刻的快速收敛后，某条局部最优路径上会积累较多信息素，而信息素的正反馈机制会使得该局部最优路径上信息素更快增加，最终导致无法跳出局部最小，产生早熟。笔者试图借鉴蚁群算法中的信息素机制结合一种改进的粒子群实现求解 TSP 问题的一种新的方法 ： 基于信息素的粒子群方法（pheromone based particle swarm optimizer，PPSO）。

《3　粒子群求解 TSP 问题》

3　粒子群求解 TSP 问题

《3.1　个体的表示》

3.1　个体的表示

在粒子群算法中，每个优化问题的解都是搜索空间中的一只鸟，称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值 （fitness value），每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子就追随当前最优粒子在解空间中搜索。

个体采用实数编码，计算中无须解码过程，以节省计算时间。编码如图 1 所示，个体编码中的每一位 τij  代表了 i 到 j 的信息素浓度，因此一个粒子个体就是蚁群中的一张信息素表，则第 i 个粒子个体表示为 Xi = ｛｝，Xi  同时也代表了在粒子群更新时粒子的值。

《图1》

图1　个体编码示意

Fig.1　Code structure sample of particles

《3.2　适应度函数的确定》

3.2　适应度函数的确定

适应度函数的计算通过对每个个体求解 TSP 的结果获得。计算方法如下 ：

1）初始时刻 t = 0，t 时刻所处的城市位置记为 s（t），s（0） = 1。

2）设当前所处城市位置为 s（t） = j，则下一个时刻城市位置为

tabu 为已经过城市的禁忌列表，。重复式（3）直到 t = n - 1。

3）通过

计算个体的适应度 f，适应度值越低的个体性能越好。

《3.3　粒子群更新》

3.3　粒子群更新

式（3）的状态转移完全是最大概率选择，因此由一个粒子个体可以决定 TSP 问题的一个解，通过对粒子群个体值的更新，以寻求最优粒子个体。

设粒子总数为 N，个体速度表示为 Vi = ｛ ｝，1 ≤ i ≤ N，1 ≤ j ≤ n，1 ≤ k ≤ n。允许粒子个体最大值 Xmax = ｛ τjkmax ｝，允许粒子个体最小值 Xmin =｛ τjkmin ｝，允许速度最大值 Vmax = ｛ vjkmin ｝，最大进化代数 max gen。

1）计算所有粒子的适应度 ；

2）确定个体历史最好值 Xpbest 和全局最好个体

X gbest，并保存最好个体的适应度 fmax ；

3）线性权值按[5,6]

计算，其中，gen 为当前的进化代数 ；wmax 与 wmin 为 w 的最大值和最小值。

4）按照下列方法对粒子群每个个体更新[1]。

速度更新 ：

式中，c1，c2 为固定参数 ；rand（ ）为介于（0，1）之间的随机数。

粒子个体更新 ：

《3.4　多样性函数设计》

3.4　多样性函数设计

记 P 为当前代群体，其中，第 i 个个体定义为 Xi，i = 1，2，…，N ； N 为种群规模 ；gen 为当前的进化代数。

定义 1　种群适应度均值和方差

定义 2　种群最大方差

定义 3　多样性函数为

由于所有粒子都有朝全局最优粒子移动的趋势，用平均适应值与最大适应值的比值来度量种群多样性。div ∈ [0，1]，div 越大，认为群体多样性越好，div 越小，认为群体多样性越差，当 div = 0 时表明所有粒子的适应度都一样，都处于搜索空间的同一点，此时的多样性最差。

《3.5　排序》

3.5　排序

按照适应度的高低对粒子群进行排序。

《3.6　多样性调节》

3.6　多样性调节

定义 4　粒子调节因子为

当 2/3 ＜ div ＜ 1 时，则认为群体多样性较好，不需要进行调节。

当 div ＜ 2/3 时，对适应度前（1 - div）N 的粒子作如下调节 ：

1）计算粒子调节因子 μ（Xi ） ；

2）生成（0，1）间随机数 μ0 = rand （0，1） ；

3）如果 μ0 ＜ μ（pi ），重新初始化粒子 Xi，否则保留该粒子。

《4　实验结果》

4　实验结果

实验参数为 α = 1，β = 3，c1 = 2.0，c2 = 2.0，wmax = 0.9，wmin = 0.4，N = 50。实验选择的TSP 问题来自 TSPLIB，分别是 eil 51 和 ry 48，其中 ry 48 为非对称 TSP 问题。图 2（a）中为初始随机解，即根据随机初始化的信息素表获得的路径，图 2（b）为最终优化结果，可以看到提出的 PPSO 方法可以获得 TSP 问题的最优解。图 3 为最优路径长度与平均路径长度收敛曲线，随着最优个体路径度的收敛，所有个体路径长度的平均值能够保持在某个值上下浮动，表明随着进化的过程，种群的多样性能够较好地保持，多样性函数在进化过程中起了作用。

《图2》

图2　eil 51 问题的一次典型的结果

Fig.2　A classic result for eil 51

《图3》

图3　最优路径长度与平均路径长度收敛曲线

Fig.3　Convergence curve of best result and average result of the swarm

表 1 中给出 PPSO 算法在 eil 51 上的统计结果。独立重复实验 25 次，每次运行最大迭代次数为 5 000，25 次实验中获得最优解的概率为 56 %。表 2中给出了 PPSO 算法与 ACS[7]，MMAS[8]和 AS 的实验结果对比。ACS，MMAS，AS elite 最大运行次数都是 10 000 次，采用 51 只蚂蚁。表 3 给出在 ry 48 上的实验结果对比。PPSO 算法最大迭代次数 10 000，ACS，MMAS，AS 为 20 000。其中用 σ 代表 25 次实验的均方差。

《表1》

表1　PPSO算法在 eil 51 上运行 25 次的统计结果

Table 1　Solution quality for PPSO on eil 51 based on 25 independent runs

从表 2、表 3 可见，PPSO 算法获得的解明显优于 ASelite，ACS 与 MMAS，从图 3 收敛曲线可见，粒子群在收敛到全局最优解的过程中，平均路径长度并未收敛，说明尽管最优个体适应值快速收敛了，但平均适应值没有随之收敛，表明 PPSO 算法中多样性函数起了作用，有助于克服早熟，使算法具有逃离局部最优解的能力。

《表2》

表2　PPSO与 ASelite，ACS，MMAS在 eil 51 上的结果比较

Table 2　Comparison of PPSO with ASelite，ACS，MMAS for eil 51

《表3》

表3　PPSO 与 ASelite，ACS，MMAS在 ry 48 上的结果比较

Table 3　Comparison of PPSO with ASelite，ACS，MMAS for ry 48

《5　结语》

5　结语

分析了信息素机制在蚁群算法中的作用，利用粒子群算法操作简单、易于实现、计算量小的特点，结合信息素机制，提出一种新的解决 TSP 问题的PPSO 方法。针对智能优化算法普遍存在的局部收敛问题，对基本粒子群进行了改进，设计一种根据多样性函数和调节因子的多样性调解机制，以克服陷入局部最小而导致收敛过早的停滞问题。从实验中可以看到，算法在避免停滞现象的同时具有搜索较好解的能力，验证了 PPSO 方法的改进是有效的。同时，与蚁群算法的对比实验也证明了 PPSO 方法在求解 TSP 问题的有效性。