基于改进萤火虫算法的TSP问题

胡 楠,徐晓光

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



基于改进萤火虫算法的TSP问题

胡 楠,徐晓光∗

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

摘要:针对旅行商问题,提出了一种改进的萤火虫算法．首先,重新定义萤火虫个体距离、位置更新公式．其次,为了增加萤火虫群的多样性、避免过早陷入局部最优、减少算法运行时间,引入了遗传算法．最后,通过仿真实验表明,改进后的算法能在迭代次数较少的情况下更快收敛到最优解,证明了所提方法的可行性和有效性．

关 键 词:旅行商问题;改进的萤火虫算法;遗传算法

旅行商问题(Travel Salesman Problem,TSP)是最基本的路线问题,其探索单一旅行者由起点出发,并通过所有给定点后,再回到起点的最小路径成本问题[1]．求解TSP一直是组合优化领域研究的热点和难点问题之一[2]．目前,为解决TSP问题引入了各种智能算法,如遗传算法、PSO算法、蚁群算法等[3-5],然而这些方法存在计算存储量大、运行时间长、求解城市规模太小等不足．萤火虫算法(Firefly Algorithm, FA)是近年来提出的一种新型群智能算法,已经在很多领域得到了应用[6-8],通过模拟自然界中萤火虫的发光特性发展而来,同蚁群算法、鱼群算法一样,也是一种高级启发式算法[9]．针对TSP问题,在标准萤火虫算法的基础上,提出了一种改进的萤火虫算法,对萤火虫个体距离、位置更新公式进行了重新定义．为了提高萤火虫算法求解TSP问题时的收敛速度,使其找到全局最优解,在标准萤火虫算法中引入了遗传算法的交叉、变异、逆转操作．

1 标准萤火虫算法

1．1 标准萤火虫算法基本概念

萤火虫算法通过萤火虫个体之间的相互吸引达到寻优的目的,具体来说,就是由于萤火虫亮度的不同,在一定范围内,亮度小的萤火虫会被亮度大的萤火虫吸引,从而逐渐向其移动．萤火虫的亮度与目标函数有关,所以在萤火虫移动的过程结束后,萤火虫会聚集在亮度最大的萤火虫位置,即最优解,这就是萤火虫算法的寻优过程[9]．

1．2 标准萤火虫算法的数学描述与分析

萤火虫根据亮度不同进行选择移动．亮度分为绝对亮度和相对亮度[9]．绝对亮度,即萤火虫i在r＝0处的光强度,记为Ii,绝对亮度由目标函数直接决定,代表解的优劣程度;相对亮度,即萤火虫i在萤火虫j处的光强度,记为Iij,表达为[10]:

式中,γ为光吸收系数,设为常数;rij为萤火虫i到萤火虫j的距离．

每个萤火虫都遵循吸引规则,即绝对亮度小的萤火虫被绝对亮度大的萤火虫吸引,吸引力与亮度成比例,萤火虫i对萤火虫j的吸引力βij(rij)为[10]:

式中,β0为最大吸引力,即在光源处(r＝0处)萤火虫的吸引力．

假设萤火虫j被萤火虫i吸引,向其移动,移动后的新位置可根据位置更新公式计算,表达为[6-7]:

式中,t为迭代次数;→xi、→xj为萤火虫的空间位置;α为常数,一般可取α∈[0,1];→εj是由高斯分布、均匀分布或者其他分布得到的随机数向量．

2 萤火虫算法TSP实现

2．1 编码

根据萤火虫算法的思想,每个萤火虫可代表一组解,假设城市的编号为:cities＝{1,2,3,…,n},那么每个萤火虫代表n个城市的任意排列,即Path＝{p1,p2,p3,…,pi,…,pn},pi代表途经的第i个城市．

2．2 绝对亮度

即目标函数的值越小,路线长度越短．绝对亮度由目标函数直接决定,代表解的优劣程度,所以,绝对亮度的公式可设置为:

即路线长度越短,萤火虫的绝对亮度值越大．

2．3 萤火虫个体间距公式

由式(1)可知,相对亮度与绝对亮度Ii、光吸收系数γ和两萤火虫之间的距离rij有关．然而在TSP问题中,每只萤火虫代表一组经过n个城市的随机序列,所以,在这重新定义萤火虫个体间的距离．假设萤火虫i的解为Path(i)＝{pi1,pi2,pi3,…,pin},萤火虫j的解为Path(j)＝{pj1,pj2,pj3,…,pjn},rij则:

相对亮度公式和吸引力公式不变,仍沿用式(1)、式(2)．

2．4 位置更新公式

根据TSP问题解的特点,每次位置更新并不能像式(3)一样,即不能采用一只萤火虫向另一只萤火虫所在位置逐步移动这种方式,而是在满足移动时直接移动到另一只萤火虫的位置,即把另一只萤火虫的解直接赋值给当前的萤火虫．表示为:

3 改进的萤火虫算法求解TSP问题

为了提高萤火虫算法求解TSP问题时的收敛速度,使其找到全局最优解,对萤火虫算法进行改进,即引入遗传算法中的交叉、变异、逆转操作．

3．1 引入交叉、变异、进化逆转操作

萤火虫算法容易陷入局部最优的情况,针对这一缺点,将遗传算法中的交叉、变异、进化逆转操作引入到萤火虫算法,这样增加了TSP问题解的可能性,可以避免陷入局部最优．

(1)交叉操作．交叉操作即将每代的解,两个分为一组,设置交叉概率Pc,交叉区间为[r1,r2],区间内数据进行交换,如有重复数据,则进行部分映射消除冲突[1]．假设城市数为12,r1＝5,r2＝8,{6,2,7,9,3, 10,1,5,11,4,8,12},{7,1,8,11,2,12,4,5,10,3,6,9},交叉后,{6,1,7,9,2,12,4,5,11,3,8,10},{7,2, 8,11,3,10,1,5,4,12,6,9}．

(2)变异操作．变异操作即任意选取两点,将其对换位置[1]．假设城市数为12,r1＝5,r2＝8,变异概率为Pm,如下一组数据{6,2,7,9,3,10,1,5,11,4,8,12},变异后,{6,2,7,9,5,10,1,3,11,4,8,12}．

(3)进化逆转操作．进化逆转操作与变异操作都是任意选取两点,将其对换位置,区别在于进化逆转操作结束后数据优于原来的可保留,否则数据不变[1]．

交叉概率Pc,变异概率Pm,在这里应取很小的值,因为问题的寻优主要依靠萤火虫算法的思想,而加入交叉、变异操作主要为了增加解的随机性,使得TSP问题的解具有多样性,这样可以避免陷入局部最优,使算法找到全局最优解的概率增加．

3．2 算法步骤

用改进的萤火虫算法求解TSP问题,可按以下步骤执行:

(1)设定算法参数,包括最大迭代次数G、萤火虫数量、光吸收系数γ等;

(2)初始化萤火虫位置,即随机产生N组解;

(3)初始化萤火虫亮度,萤火虫绝对亮度由目标函数直接决定,按照式(5)计算;

(4)判断是否满足程序终止条件,即是否进行了G次迭代,若满足条件,程序终止,执行第8步,否则继续执行下一步;

(5)更新萤火虫位置,首先按式(6)计算萤火虫个体间距,由于萤火虫会向绝对亮度比本身大且个体间距较小的萤火虫移动,通过轮盘赌法进行位置选择,并按式(7)进行位置更新;

(6)更新萤火虫亮度,计算位置更新后的萤火虫亮度;

(7)当萤火虫算法迭代到一定次数后,可能已达到最优化,如果有最优解在G/5次运算后结果仍保持不变,则提前结束算法,执行第8步,否则回到第4步;

(8)输出遍历城市顺序,绘出最优解路线图．

4 仿真实验

仿真实验通过对标准萤火虫算法与改进的萤火虫算法的比较,验证改进算法的可行性．假设TSP问题的城市数为14,萤火虫个数为80,最大迭代次数为200,光吸收系数γ取1．5,在Matlab中进行仿真实验,每种算法分别进行50次,来验证实验的普遍性,仿真结果如表1所示．由表1可知,将标准萤火虫算法与改进萤火虫算法的50次运行结果的最优值和平均值进行比较发现,虽然标准萤火虫算法与改进萤火虫算法所得最优值相同,但标准萤火虫算法的最优值出现次数较少,且有最差值的出现,平均值的结果较大;而改进萤火虫算法50次运行结果都为最优值,且平均值更优．

表1 标准萤火虫算法与改进萤火虫算法结果比较

在参数相同的情况下,标准萤火虫算法下得到的仿真结果如图1、图2所示．由图1、图2可知,在同样条件下,标准萤火虫算法得到的最优路线结果并不稳定,每次运行的结果都可能不同,也表明了标准萤火虫算法更易陷入局部最优解,而错过最优路线．改进萤火虫算法下得到的路线仿真结果如图3所示．由图3可知,结果相对较为稳定．两种算法的优化过程对比如图4所示．由图4可以看出,改进萤火虫算法最优值结果更好,且时间更少．

图1 标准萤火虫算法路线

图2 标准萤火虫算法路线

图3 改进萤火虫算法路线

5 结论

提出了一种改进的萤火虫算法在TSP求解上的具体实现．该算法针对TSP问题,在标准萤火虫算法基础上,对萤火虫个体距离、位置更新公式进行了重新定义,并加入了交叉、变异、逆转操作,避免寻优过程出现早熟现象,提高了算法效率．通过仿真实验表明,改进后的萤火虫算法在更少代数内能够找到最优解,不仅大大提高了效率,也使优化结果更好、更稳定,证明了改进萤火虫算法的可行性与有效性．

参考文献:

[1] 史峰,王辉,郁磊,等．MATLAB智能算法30个案例分析[M]．北京:北京航空航天大学出版社,2011．

[2] 周永权,黄正新．求解TSP的人工萤火虫群优化算法[J]．控制与决策,2012,27(12):1 816-1 821．

[3] 王宇平,李英华．求解TSP的量子遗传算法[J]．计算机学报,2007,30(5):748-755．

[4] 范会联,李献礼．基于近邻关系求解TSP的离散PSO算法[J]．计算机应用研究,2011,28(2):511-513,544．

[5] 吴华峰,陈信强,毛奇凰,等．基于自然选择策略的蚁群算法求解TSP问题[J]．通信学报,2013,34(4):165-170．

[6] K N Krishnand,D Ghose．Glowworm swarm based optimization algorithm for multimodal functions with collective robotics applications[J]．Multiagent and Grid System,2006,2(3):209-222．

[7] R Dutta,R Ganguli,V Mani．Exploring isospectral spring-mass systems with firefly algorithm[J]．Proceedings of the Royal Society of London A,2011(467):1-20．

[8] T Mauder,C Sandera,J Stetina,et al．Optimization of the quality of continuously cast steel slabs using the firefly algorithm[J]．Materials and Technology,2011,45(4):347-350．

[9] 董静．萤火虫算法研究及其在水下潜器路径规划中的应用[D]．哈尔滨:哈尔滨工程大学,2013．

[10]于宏涛,高立群,韩希昌．求解旅行商问题的离散人工萤火虫算法[J]．华南理工大学学报:自然科学版,2015,43(1): 126-131,139．

Travel salesman problem based on improved firefly algorithm

HU Nan,XU Xiao-guang∗
(College of Electrical Engineering,Anhui Polytechnic University,Wuhu 241000,China)

Abstract:According to the characteristics of travel salesman problem,an improved firefly algorithm is proposed．Firstly,a new distance formula are location update formula is redefined．Secondly,in order to increase the diversity of firefly swarms,avoid quick convergence to local optimal solution and save time, genetic algorithm is introduced．Finally,simulation experiments show that the improved algorithm can find the global optimal solution with less evolving time,and the proposed method is feasible and effective．

Key words:travel salesman problem;improved firefly algorithm;genetic algorithm

中图分类号:TP391．9

文献标识码:A

收稿日期:2015-10-15

基金项目:安徽省高等学校省级自然科学研究项目(KJ2014A024)

作者简介:胡 楠(1991-),女,安徽淮南人,硕士研究生．

通讯作者:徐晓光(1972-),男,安徽明光人,副教授,硕导．