基于粒子群与人工鱼群混合算法的TSP求解模型

彭凯， 黄宜庆， 邵寿琛

(安徽工程大学电气工程学院， 安徽芜湖241000)

基于粒子群与人工鱼群混合算法的TSP求解模型

彭凯， 黄宜庆， 邵寿琛

(安徽工程大学电气工程学院， 安徽芜湖241000)

传统的群智能算法不断被优化和改进，但由于传统单纯算法的固有缺陷和局限性很难从根本上去除，因此衍生出许多群智能混合算法。针对人工鱼群算法(AFSA)收敛速度慢及粒子群算法(PSO)全局收敛性差的缺陷，提出了一种新的粒子群与人工鱼群的混合算法。算法以人工鱼群算法为基础，将粒子群算法的线性递减惯性权重策略引入到人工鱼群算法中，对人工鱼进行编码处理以及动态改变人工鱼个体的视野，使之形成新的粒子群人工鱼群混合算法(PSO-AFSA)。完成算法融合并将混合算法应用于旅行商(TSP)问题。仿真结果表明：与传统的人工鱼群算法和粒子群算法相比，该混合算法全局收敛性效果更好，收敛速度更快。

旅行商问题；人工鱼群算法；粒子群算法；混合算法

引言

近年来，各种群智能混合算法不断被提出和优化，并应用于解决TSP(Traveling Salesman Problem，TSP)等各种问题，如免疫蚁群混合算法[1]，遗传蚁群混合算法[2]，粒子群和蜂群混合算法[3]，遗传算法与人工鱼群的混合算法[4]等，各种混合算法[5-8]的提出，是对群智能算法的进一步发展，弥补了传统单一算法的固有缺陷，扬长避短地结合其他算法的优势，较好地解决了TSP等问题。

在解决TSP问题上，各种方法层出不穷。文献[9]提出了具有嗅觉特征的人工鱼群算法去解决TSP问题，但存在搜索时间较长，收敛速度较慢的缺点；文献[10]采用随机密钥的表达式来进行编码来改进人工鱼群算法，并应用于解决TSP问题，改进后的算法优化速度虽然提高，但易陷入局部最优；文献[11]将伊藤算法中的漂移和波动算子作为粒子群算法中的学习因子，将牛顿力学中的加速度因子映射粒子群算法的惯性权重，但改进后的算法处理规模较大的城市群时收敛速度较慢，全局收敛性较差。文献[12]将蚁群划分成多个蚂蚁子群，通过把蚂蚁子群的参数作为粒子来优化蚂蚁子群的参数，并引入信息素交换的思想到蚂蚁子群中，但没有很好地克服粒子群的缺陷，容易陷入局部最优解。文献[13]将自适应的惯性权重粒子群算法引入模拟退火法的思想，解决了基本粒子群算法容易陷入局部最优的问题，但是前期的搜索时间过长，稳定性较差。

在粒子群和人工鱼群混合算法的融合方面，也有一些研究出现。文献[14]将粒子的飞行速度和惯性权重与鱼群算法融合，一定程度上改善了算法的收敛速度，但鱼群的视野固定，容易陷入局部最优，后期收敛速度很慢。文献[15]将种群分为两部分，分别用PSO和AFSA进化，两种算法共享种群极值信息，文献增加了计算的复杂性，没有从根本上克服两种算法的固有缺陷。文献[16]利用粒子群算法特性，为人工鱼引入记忆、交流行为模式，并定义一个参数来动态限定人工鱼的视野和步长。算法单纯限定人工鱼的视野和步长，没有更好地利用视野的线性递减惯性权重来寻优，容易在后期收敛陷入局部最优。

利用粒子群算法对人工鱼群算法中的视野加以改进，引入粒子群算法的惯性权重，并采用线性递减惯性权重策略对鱼群进行编码和视野动态变化，可以加快算法的收敛速度的同时提高算法的全局搜索能力。最后通过TSP问题仿真实验表明，所提出的算法具有良好的性能。

1 TSP问题的描述

TSP问题是指已知n个城市，以及每个城市间的距离，求得从一个城市出发遍访每一个城市且每个城市只能访问一次，最后再次回到出发城市的最短总路程。

2 基本算法

2.1 人工鱼群算法[4]

(1) 觅食行为

设人工鱼的当前状态为xp，在其视野范围随机选择一个状态xq，在求极大值问题时，若(Yp

(2) 聚群行为

设人工鱼当前状态为xp，探测当前领域内(dpqYp，表示中心位置附近不太拥挤且食物浓度较高，则进一步向中心位置移动，否则执行觅食行为。

(3) 追尾行为

设人工鱼的当前状态为xp，搜索人工鱼所在视野范围内(dpqYp，表明伙伴xq处有较高的食物浓度且周围不太拥挤，则向着xq方向前进一步，否则执行觅食行为。

(4) 随机行为

随机行作为觅食行为的一个缺省行为，即人工鱼在其视野范围内随机选择一个状态，并向该方向移动。

(5) 公告板

记录人工鱼在寻优过程中最优个体的状态。

2.2 粒子群算法

粒子群算法(PSO)[5]是由Kennedy和Eberhart在1995年提出的一种基于种群的随机优化技术。粒子群算法源于对鸟群觅食行为的研究，通过对鸟群群体行为的研究，人们发现生物群体中存在着一种社会信息共享机制，这种机制为鸟群群体的进化提供了一种优势，这也是粒子群算法形成的基础。同遗传算法和蚁群算法相比，PSO有着算法简单、容易实现，并且可调整参数少等特点,因此被广泛应用于结构设计、电磁场和任务调度等工程优化问题中。

基本的粒子群算由n个基本粒子构成，每个粒子的位置表示所需优化问题在D维空间潜在的解。每个基本粒子根据它所处的位置，通过优化函数计算出一个适应值，通过速度来决定其飞行距离和方向。粒子根据如下式子进行速度和位置的更新：

(1)

(2)

3 粒子群与人工鱼群混合算法

3.1 线性递减惯性权重策略

本算法将线性递减惯性权重策略的粒子群算法与人工鱼群算法进行融合，形成新的人工鱼群粒子群混合算法(PSO-AFSA)，算法中引入一个惯性权重ω到公式(1)，更新后的公式如下：

(3)

式中，ω为非负数，称为惯性因子，惯性权重，是控制速度的权重，其计算公式如下：

(4)

式中，ωmax和ωmin分别表示权重的最大及最小值，kn为当前迭代次数，kmax表示最大迭代次数。

将线性递减的惯性权重策略用于更新粒子位置并对鱼群进行重编码，使其视野随着迭代次数的增加线性递减，Visual=ω*Visual0，ω的变化参照公式(4)，变化范围为0.09～0.04线性递减。

ω的大小决定粒子的速度变化，而ω的线性递减使得混合算法在开始时探索较大的区域，能够以较快的速度定位到最优解的大致位置，并且随着ω的减小，粒子寻优速度减慢，此时粒子开始精准的局部搜索。

ω的大小采用线性递减惯性权重策略，在算法优化初期时，人工鱼随机分布，此时人工鱼个体之间距离较大，人工鱼个体视野也较大，能有效地克服局部极值的影响，并且快速收敛。随着算法迭代，人工鱼逐渐聚集，此时人工鱼之间的距离逐渐变小，视野也随着ω的变化而变小，提高了算法的准确性、可以实现全局最优。

3.2 算法流程图

算法的流程如图1 所示。

图1 算法流程图

3.3PSO-AFSA实现步骤

Step1：读取城市坐标数据，从而获得城市的距离矩阵。获取人工鱼的群体规模N、最大迭代次数NC、视野范围Visual、最大移动步长step、尝试次数Try_number等数据，同理获取粒子群数据。

Step2：参数初始化：生成n个粒子群，并初始化参数。生成N个人工鱼个体，形成初始人工鱼群，当前迭代次数Passed_times=0。

Step3：线性递减计算惯性权重，对鱼群进行排序编码，并开始迭代，更新粒子速度和位置，计算目标函数并更新粒子群全局最优和个体最优。

Step4：惯性权重改变人工鱼视野，各人工鱼按照算法的行为准则，模拟执行追尾行为、觅食行为和聚群行为，选择最优行为执行，缺省行为为觅食行为。如果依然得不到最优值，则进行随机行为。

Step5：人工鱼每行动一次后，进行检查自身状态，并与公告牌状态对比，若优于公告牌状态，则以自身状态取代公告牌状态。

Step6：判断是否满足终止条件，判断Passed_times是否达到最大迭代次数值NC，若大于则输出公告牌值即为计算结果，否则跳转Step3。

4 仿真实验

为了验证混合算法的有效性，将传统的AFSA、PSO和PSO-AFSA分别应用于城市数分别为30、40和50的三类TSP问题的求解。

图2 ～图4 为三种算法对应不同城市的优化曲线对比图。从图中可以明显看出PSO-AFSA混合算法前期收敛速度更快，且容易摆脱局部最优的缺陷，有着更好的寻优精度。

图2 30城市TSP优化曲线

图3 40城市TSP优化曲线

图4 50城市TSP优化曲线

图5 ～图7 为三种算法迭代180次时所对应30个城市路径优化图。将图5 ～图7 与图2 对比发现，在城市数为30个的TSP问题求解过程中，PSO和AFSA算法在迭代180次之后仍不能找到最优解，而PSO-AFSA可以达到最优路线。

图5 AFSA30城市路径优化

图6 PSO30城市路径优化

图7 PSO-AFSA30城市路径优化

图8 ～图10 为三种算法迭代500次时所对应40个城市路径优化图。将图8 ～图10 与图3 对比发现，AFSA算法达不到最优解，PSO陷入局部最优，而PSO-AFSA可以较快地找到最优解。

图8 AFSA40城市路径优化

图9 PSO40个城市路径优化

图10 PSO-AFSA40城市路径优化

图11 ～图13 为三种算法迭代500次时所对应50个城市路径优化图。从图11 ～图13 与图4 对比看出，AFSA算法陷入局部最优，PSO算法可以找到较短路径，但是仍不是最优解，PSO-AFSA的效果更好。

图11 AFSA50城市路径优化

图12 PSO50城市路径优化

图13 PSO-AFSA50城市路径优化

5 结束语

基于惯性权重线性递减策略，给出了一种粒子群与人工鱼群的混合算法。利用粒子群算法中的线性递减惯性权重策略实现了对人工鱼群算法的编码和视野的动态变化，增大了人工鱼的视野范围，使算法得到了较好的收敛速度和全局搜索能力。通过TSP求解模型的仿真实验验证了混合算法的优良性能。

[1]刘勇,刘念,刘孙俊.一种基于免疫蚁群混合算法的TSP求解模型.四川大学学报:工程科学版,2010,42(3):121-126.

[2]黄明,王聪,梁旭.改进型遗传蚁群混合算法求解旅行商问题.大连交通大学学报,2011,32(2):86-88.

[3]史小露.粒子群和人工蜂群混合算法的研究与应用.南昌:南昌航空大学,2013.

[4]姜山,季业飞.改进的人工鱼群混合算法在交通分配中的应用.计算机仿真,2011,28(6):326-329.

[5]罗德相,周永权,黄华娟.粒子群和人工鱼群混合优化算法.计算机与应用化学,2009,26(10):1257-1261.

[6]NIKNAM T,AMIRI B.An efficient hybrid approach based on PSO,ACO and k-means for cluster analysis.Applied Soft Computing,2010,10(1):183-197.

[7]SenT,Mathur H D.A new approach to solve economic dispatch problem using a Hybrid ACO-ABC-HS optimization algorithm.International Journal of Electrical Power & Energy Systems,2016,78:735-744.

[8]张小琼,秦亮曦.基于混合变异的萤火虫群优化算法.计算机应用与软件,2016,33(2):272-275.

[9]李跃松,樊金生,张巧迪.用改进的人工鱼群算法求解TSP问题.石家庄铁道大学学报:自然科学版,2011,24(2):103-110.

[10]Zhu M H,She X Y.Improved artificial fish school algorithm to solve traveling salesman problem.Application Research of Computers,2010,27(10):3734-3736.

[11]易云飞,林晓东,蔡永乐.求解旅行商问题的改进粒子群算法.计算机工程与设计,2016,37(8):2195-2199.

[12]孙凯,吴红星,王浩,等.蚁群与粒子群混合算法求解TSP问题.计算机工程与应用,2012,48(34):60-63.[13]于桂芹,李刘东,袁永峰.一种结合自适应惯性权重的混合粒子群算法.哈尔滨理工大学学报,2016,21(3):49-53.

[14]梁毓明,裴兴环.粒子群优化人工鱼群算法.计算机仿真,2016,33(6):213-217.

[15]王联国,施秋红,洪毅.PSO和AFSA混合优化算法.计算机工程,2010,36(5):176-178.

[16]段其昌,唐若笠,徐宏英,等.粒子群优化鱼群算法仿真分析.控制与决策,2013,28(9):1436-1440.

Solving Model Based on Particle Swarm Optimization and Artificial Fish Swarm Algorithm

PENGKai,HUANGYiqing,SHAOShouchen

(College of Electrical Engineering, Anhui Polytechnic University, Wuhu 241000, China)

The traditional group intelligent algorithms are optimized and improved. However, the inherent shortcomings and limitations of the traditional simple algorithm is difficult to fundamentally removed, resulting in many groups of intelligent hybrid algorithm. A new hybrid algorithm of particle swarm and artificial fish swarm is proposed to overcome the shortcomings of artificial fish swarm algorithm (AFSA) convergence and the poor global convergence of particle swarm optimization algorithm(PSO). Based on the artificial fish swarm algorithm, the linear decreasing inertia weight strategy of particle swarm optimization algorithm is introduced into the artificial fish swarm algorithm. Artificial fish processing is encoded and the field of view of the individual artificial fish is changed dynamically, so that the new particle swarm and artificial fish swarm hybrid algorithm (PSO-AFSA) is formed. And the hybrid algorithm is applied to Traveling Salesman Problem (TSP). The simulation results show that the hybrid algorithm has better global convergence performance and faster convergence speed than the traditional artificial fish swarm algorithm and particle swarm optimization algorithm.

traveling salesman problem; artificial fish swarm algorithm; particle swarm optimization; hybrid algorithm

2016-10-13

国家自然科学基金项目(61304127);安徽省自然科学基金项目(1408085QF132)

彭 凯(1991-),男,安徽宿州人,硕士生,主要从事运动控制系统的分析与设计研究方面的研究,(E-mail)61445966@qq.com

1673-1549(2017)01-0027-06

TB115

A