文档库 最新最全的文档下载
当前位置:文档库 › 具有分段和变异特性的蚁群算法求解TSP问题

具有分段和变异特性的蚁群算法求解TSP问题

具有分段和变异特性的蚁群算法求解TSP问题
具有分段和变异特性的蚁群算法求解TSP问题

收稿日期:2007-09-13

基金项目:安徽省自然科学基金资助项目(050420207)

作者简介:汪采萍(1970-),女,安徽无为人,副教授,硕士研究生,研究方向为数据挖掘与人工智能;胡学钢,博士,教授,硕士生导师,研究方向为数据挖掘与人工智能。

具有分段和变异特性的蚁群算法求解T SP 问题

汪采萍1,2,胡学钢1

(11合肥工业大学计算机与信息学院,安徽合肥230009;

2.安徽职业技术学院,安徽合肥230051)

摘 要:常规蚁群算法具有搜索时间较长,易于过早地收敛于非最优解的缺陷。为了提高蚂蚁一次周游的质量,采用具有轮盘赌方式的最大最小蚁群算法(MMAS +RW ),即在依据概率选择下一个城市时采用轮盘赌的方式。提出一种具有分段和变异特性的蚁群算法。该算法融合了分段的分而治之思想和遗传算法中的变异,有利于保持群体多样性的特性,是在采用轮盘赌方式的最大最小蚁群算法陷入局部最优解的情况下,引入随机分段和遗传算法的变异操作来优化当前最优解,改善解的质量,改进蚁群算法易于过早地收敛于非最优解的缺陷。仿真实验表明取得了较好的效果。关键词:TSP ;蚁群算法;最大最小蚁群算法;分段变异蚁群算法

中图分类号:TP30116 文献标识码:A 文章编号:1673-629X (2008)06-0090-04

A Subsection Mutation Ant System of Solving TSP

WAN G Cai 2ping 1,2,HU Xue 2gang 1

(11School of Computer Science and Information ,Hefei University of Technology ,Hefei 230009,China ;

2.Anhui Vocational and Technical College ,Hefei 230051,China )

Abstract :Typical ant system algorithms have the shortages of easily falling in local best solutions and long searching time.In order to im 2prove the ant touring quality ,adopt MAX -MIN ant system and introduce roulette wheel into MAX -MIN ant system (MMAS +RW ).Based on MAX -MIN ant system with roulette wheel (MMAS +RW ),a subsection mutation ant system (SMAS )of solving TSP is put forward.It combines ant colony algorithm with subsection and mutation of genetic algorithms.On the condition of falling in local best so 2lutions of ant colony algorithm ,it can improve the precision.The simulation results show that better effects are obtained.K ey w ords :TSP ;ant colony algorithm ;MMAS ;SMAS

0 引 言

意大利学者Dorigo M 等于1991年在法国巴黎召开的第一届欧洲人工生命会议(European Conference

on Artificial Life ,ECAL )上最早提出了蚁群算法的基

本模型,1992年,Dorigo M 又在其博士论文中进一步阐述蚁群算法的核心思想[1]。蚁群算法是一种新生算法,具有很强的通用性和鲁棒性。从提出到现在,仅短短十余年的时间,但其在离散型组合优化问题、Job -Shop 问题[2]、二次分配[3]、集成电路设计[4]、图着色问

题[5]、车辆调度[6]以及通信网络负载问题的处理中,表现得很突出,所以引起人们的关注。

虽然蚁群算法在离散型组合优化问题中表现突

出,但也存在着缺陷,如搜索时间较长,易于过早地收敛于非最优解。文中提出具有分段和变异特性的蚁群算法。该算法把小窗口、随机分段优化求解、遗传算法中的变异的思想引入蚁群算法。在蚁群算法出现停滞现象进而陷入局部最优解的情况下,把当前局部最优解分解成若干个子段,在各子段的小窗口范围内,引入变异来优化各子段的解,从而优化当前最优解,改善解的质量。

1 TSP 问题及蚁群算法

TSP 问题的描述为,已知n 个城市及各城市间的

距离,求一条经过各城市一次且仅一次的最短的回路。图论描述为,G =(V ,A ),V ={v 1,v 2,…,v n }是n 个城市的顶点集,A ={e ij |v i ,v j ∈V }是V 中各顶点相互连接组成的弧集,已知各城市间的距离d ij ,求一条最短的Hamilton 回路。文中选用的实例是对称

TSP 问题,即d ij =d ji 。以TSP 为例来说明常规蚁群算

第18卷 第6期2008年6月 计算机技术与发展COMPU TER TECHNOLO GY AND DEV ELOPMEN T

Vol.18 No.6J un. 2008

法(ant system,AS)。

设有n个城市(元素),m只蚂蚁,任意两城市i,j 之间的距离为d(i,j),τ(i,j)表示两个城市i,j之间信息素的浓度。初始时刻,各信息素的浓度相同。蚂蚁k从一个城市i转移到另一个城市j的转移概率的计算公式如(1)式。J(k)为蚂蚁k在城市i时,还没有访问的城市的集合。启发函数η(i,j)=1/d(i,j)。α,β,ρ为参数。

p k ij=

[τ(i,j)]α.[η(i,j)]β

∑[τ(i,j)]α.[η(i,j)]βs∈J(k)

0其它

(1)

τ(i,j)=ρτ(i,j)+△τ(i,j)(2)

信息素更新公式为(2)式,1-ρ(0<ρ<1)表示

信息素挥发程度。信息素的处理方式为:一代中仅对周游路径长度最小的蚂蚁所经过的路径进行信息素的修改增加,其余衰减,△τ(i,j)=Q/l mb,l mb为一代中m只蚂蚁所周游的最短路径长度,Q为参数。算法AS 描述如下:

①初始化。设定各参数的值,蚂蚁个数m,最大进化代数Nc,信息素初值τ(i,j)=1。

②每只蚂蚁独立地构造一个解。蚂蚁k根据概率公式(1)计算转移概率p k

ij

,按概率p k ij大者选择下一个城市j。若当前路径长度大于本代求得最短路径长度,结束此只蚂蚁的周游。否则,如此循环,直到蚂蚁k访问完所有的城市。

③若m只蚂蚁都构造完成各自的解,则转④,否则转②。

④根据周游路径长度最小的蚂蚁,按(2)式及信息素的处理方式进行全局信息素更新。

⑤若GEN>Nc或当前解已稳定,则输出最优解,否则GEN=GEN+1,转②。

文献[7]提到的MMAS算法在AS算法的基础上

作了三点改进:首先初始τ

ij

(t)=c设为最大值MAXTAO;其次一圈中只有路径最短的蚂蚁才修改

τ

ij

(t);最后将τij(t)限定在MAXTAO和MIN TAO之间。从实验结果可知,MMAS算法在防止算法过早停滞以及有效性方面对AS算法有较大改进[8]。另外,文中除采用蚁群算法MMAS,还对上述AS中的第②步

进行改进,将“按概率p k

ij

大者选择下一个城市j”,改进

为“根据概率p k

ij

,按轮盘赌(roulette wheel)的方式选择下一个城市j”,称为MMAS+RW。这样既兼顾概率的大小,又增加了搜索的随机性,以提高算法效率。

2 遗传算法

遗传算法是根据达尔文进化论的“物竞天择、适者生存”这一自然现象提出的,是一种随机搜索算法。20世纪70年代由美国密执根大学的Holland教授首先提出。

遗传算法的三个主要操作:选择、交配、变异。

a.选择是从群体中选择存活的染色体。可以有多种选择方式,其中经常使用的是一种被称为“轮盘赌”的方式。

b.交配发生在两个染色体之间,由两个被称之为双亲的父代染色体,经杂交以后,产生两个具有双亲的部分基因的新的染色体。

c.变异发生在染色体的某一个基因上,当以二进制编码时,变异的基因由0变成1或者由1变为0。如对于染色体x=11001,如果变异位发生在第三位,则变异后的染色体变成了y=11101。变异对于一个群体保持多样性具有好处。

对于TSP问题,有以下几种变异方法:

(1)基于位置的变异:该方法随机产生二个变异位,然后将第二个变异位上的基因移动到第一位变异之前。如假定二个随机产生的变异位分别为2和5,则对于TSP的一个可行解2136457,变异后的解则为: 2413657。

(2)基于次序的变异:该方法随机产生两个变异位,然后交换这两个变异位上的基因。如假定两个随机产生的变异位分别为2和5,则对于TSP的一个可行解2136457,变异后的解则为:2436157。

(3)打乱变异:该方法随机选取染色体上的一段,然后打乱在该段内的基因次序。如随机选取的段为染色体的第2到第5位,则对于TSP的一个可行解2136457,其可能的一种变异结果为:2436157[9]。

3 具有分段和变异特性的蚁群算法

3.1 分 段

常规蚁群易于过早地收敛于非最优解,在常规蚁群陷入局部最优解时,对此局部最优解进行分段,形成若干个子段,在各子段的小窗口范围内,引入变异来优化各子段的解,从而优化当前最优解,改善解的质量。

分段采用随机的方式进行。对局部最优解分成多少段是随机的,每段的起始位置也是随机的。即:先生成随机整数r,再生成r个随机整数(在0、n-1之间),从小到大放入随机队列,依此随机队列将局部最优解分成r个子段。分段使问题规模大大地缩小,有利于问题求解的效率和质量;分段的随机性可形成各种各样的子段,兼顾解空间的各种情况。

3.2 变 异

在生物进化的过程中,染色体的某些基因可能会

?

1

9

?

第6期 汪采萍等:具有分段和变异特性的蚁群算法求解TSP问题

发生变异,即表示染色体的编码发生了某些变化。一个群体的进化需要染色体的多样性,而变异对保持群体的多样性具有一定的作用。文中主要采用遗传算法的变异算子的打乱变异中的一特殊情况。介绍如下。

打乱变异方法是随机选取染色体上的一段,然后打乱在该段内的基因次序。若在这随机选取的一段中,采用逆序交换的方式产生一个状态的领域来打乱该段内的基因次序,生成一个新染色体,则可认为是打乱变异的一个特例,可称为逆序交换打乱变异。

对于TSP 问题,逆序交换方式:设i ,j 是选取的两个整数,i

[3]

设:S =(x 1,x 2,…,x i -1,x i ,x i +1,…,x j -1,x j ,

x j +1,…,x n )

则:S ’=(x 1,x 2,…,x i -1,x j ,x j -1,x j -2,…,x i +1,x j ,x j +1,…,x n )

图1 逆序交换方式示意图

3.3 具有分段和变异特性的蚁群算法

具有分段和变异特性的蚁群算法(subsection mu 2

tation ant system ,SMAS )是在蚁群算法(MMAS +RW )收敛于局部最优解,出现停滞现象的情况下,把

当前局部最优解分解成若干个子段,在各子段的小窗口范围内,利用变异保持解多样性的特性,经过充分的变异冲出当前局部最优解,优化各子段的解,从而优化当前最优解,改善解的质量。

设上述S 是当前解,指标函数F (S )定义为城市间路径长度之和,即当前解形成的Hamilton 回路的长度,如(3)式。若经逆序交换方式的打乱变异后产生新

解为S ’,定义指标函数之差为ΔF ,ΔF =F (S ’

)-F (S ),如(4)式所示。若ΔF <0,则接受新解,改善解

的质量。

F (S )=F (x 1,x 2,…,x n )=d (0,n )+

n

k =1

d (k ,

k +1)

(3)ΔF =F (S ’)-F (S )=(d (x i -1,x j )+d (x i +1,x i ))-(d (x i ,x i +1)+d (x j -1,x j ))

(4)

具有分段和变异特性的蚁群算法(SMAS )描述如下。

①蚁群算法MMAS +RW ,求得当前最优解S ;②生成随机整数r ,再生成r 个随机整数(在0、n

-1之间),从小到大放入随机队列,依此随机队列将当

前最优解S 分成r 个子段S 1,S 2,…,S r ;

③在子段S k 内,设i ,j 是随机选取的两个整数,i

计算指标函数之差为ΔF ,当ΔF <0时,用新解S k ’代替S k 。重复此过程,直到一定的次数(可取子段长的10倍)或当前解已稳定;

④若r 个子段都经过变异进行了优化,则转⑤,否则转③;

⑤若满足结束条件,则输出最优解,否则循环数加1,转②。结束条件为循环数达到定值或当前解已稳定。

从实验结果来看SMAS 算法的第⑤步的循环次数平均7次达到稳定,因而运行效率较高,不会增加太多的运行时间,在蚁群算法陷入局部最优解的情况下能较好地改进解的质量。

3.4 仿真实验结果

实验数据选用通用的

TSPL IB (http ://www.iwr.

uni -heidelberg.de/groups/comopt/software/TSPL IB 95/tsp/)中的实例eil51和ST70。实验首先采用蚁群

算法MMAS 及蚂蚁按轮盘赌(roulette wheel )的方式选择下一个元素的MMAS +RW 算法。然后采用具有分段和变异特性的蚁群算法SMAS ,并比较MMAS +

RW 和SMAS 的实验结果。实验比较结果见表1、表2。图2到图5是SMAS 求得eil51、st70的最优解及TSPL IB 提供的最佳路径的比较。

表1和表2中代数是解稳定时进化的代数,结果是解稳定时求得的最优值。从表1和表2可以看出分段变异平均迭代7次就达到了稳定,其进化的代数远远小于MMAS +RW 进化的代数,因而不会增加很多的运行时间,但却较好地改善了解的质量。

对ST70实例,SMAS 和MMAS +RW 求解结果比较为:最大改进30.7824,最小改进8.4248,平均改进

15.2859。TSPL IB 提供的最佳路径运算结果最优值为

?

29? 计算机技术与发展 第18卷

678.5974(如图2,但TSPL IB 提供的此最短路径取整

值为675),用SMAS 求得的最优值为677.1096(如图

3),解的质量改进1.4878。对eil51实例,SMAS 和MMAS +RW 求解结果比较为:最大改进19.2196,最

小改进10.7649,平均改进13.7566。TSPL IB 提供的最佳路径运算结果最优值为429.9833(如图4,但

TSPL IB 提供的此最短路径取整值为426),用SMAS

求得的最优值为428.8717(如图5),解的质量改进1.

1116。

表1 ST70实例MMAS +RW 与SMAS 算法的结果

参数ρMMAS +RW 代数MMAS +RW 结果SMAS 代数MMAS +RW 代数+

分段变异代数

SMAS 结果

解的改进值

0.91208711.9978208+10681.215430.78240.92283698.9672283+9679.369119.59810.93299699.0805299+8677.109621.97090.94401688.5337401+6679.36919.16460.95496691.1496496+7677.109614.040.96570686.8525570+7677.10969.74290.97716687.7939716+4679.36918.42480.98

1166

685.6735

1166+5

677.1096

8.5639

 注:α=1,β=1,τ(max )=1,τ(min )=0.000000001,Q =1

表2 eil51实例MMAS +RW 与SMAS 算法结果

MMAS +RW 代数MMAS +RW 结果SMAS 代数MMAS +RW 代数+分段变异代数

SMAS 结果解的改进值352441.0182352+9428.871712.1465367442.2427367+3431.477810.7649366441.0239366+5429.737111.2868356448.0913356+6428.871719.2196365447.1921365+7428.981618.2105342441.0182342+9428.871712.1465351442.7541351+7428.981613.7725321

442.2427

321+5

429.7371

12.5056

 注:α=1,β=2,ρ=0.95,τ(max )=1,

τ(min )=0.000000001,Q =1图2 TSPL IB 提供的St70的最优解(678.5974)

4 结束语

具有分段和变异特性的蚁群算法(SMAS )在蚁群算法中融合了分段的分而治之思想和遗传算法中的变异,有利于保持群体多样性的特性,有效地改善了蚁群算法易于过早地收敛于非最优解的缺陷。SMAS 把当前局部最优解分解成若干个子段,分段使问题规模大大地缩小,有利于问题求解的效率和质量;分段的随机性可形成各种各样的子段,兼顾解空间的各种情况。

SMAS 在各子段的小窗口范围内,利用变异保持解多

样性的特性,增加对解空间搜索的多样性,经过逆序打

(下转第170页)

?

39?第6期 汪采萍等:具有分段和变异特性的蚁群算法求解TSP 问题

选择,完全使用Java 开发的J -SIM 注定了开始拥有许多Java 的优越性,譬如跨平台,性能稳定,开发简单等。以实际的S -Mac 协议为例,在已有的模拟框架基础上实现了S -Mac 并进行了仿真,得到的试验结果既证明了J -SIM 仿真结果的正确性,又证明了J -SIM 在性能上优于NS2

图5 J -SIM 使用Mac IEEE802.11和S -Mac

参考文献:

[1] Tyan Hung -ying.Working With J -Sim[DB/OL ].2003-12-10.http ://www.j https://www.wendangku.net/doc/578235560.html,/tutorial/jsim -tutorial.

html.

[2] Y e W ,Heidemann J ,Estrin D.An ener gy -efficient mac

protocol for wireless sensor networks [C ]∥in Annual Joint Conference of the Computer and Communication Societies (INFOCOM ).New Y ork ,N Y ,USA :IEEE ,2002:1567-1576.

[3] Sobeih A ,Hou J C ,Kung Lu -Chuan ,et al.J -Sim :a sim 2

ulation and emulation environment for wireless sensor net 2works[J ].Wireless Communications ,2006,13(4):104-119.

[4] Sobeih A ,Viswanathan M ,Hou J C.Check and simulate :a

case for incorporating model checking in network simulation [C]∥Formal Methods and Models for Co -Desi gn ,2004.MEMOCODE ’04.Proceedings.Second ACM and IEEE In 2ternational Conference.San Diego :IEEE Communications So 2ciety ,2004:27-36.

[5] Chiras T ,Paterakis M ,K outsakis P.Improved medium ac 2

cess control for wireless sensor networks -a study on the S -MAC protocol[C]∥Local and Metropolitan Area Networks ,https://www.wendangku.net/doc/578235560.html,NMAN 2005.The 14th IEEE Workshop.San An 2

tonio ,Texas :2005.

[6] Yu Qicai ,X ing Jianping ,Zhou Y an ,et al.Performance Re 2

search and Simulation Analysis of the MAC Layer Protocols in Wireless Sensor Networks [C ]∥Communications and Net 2working in China.[s.l.]:[s.n.],2006.

(上接第93页)乱变异,冲出当前局部最优解,优化各子段的解,从而优化当前最优解,改善解的质量,改善蚁群算法过早停滞现象,取得较好的效果。

参考文献:

[1] Dorigo M ,Optimization ,Department of Electronics ,learning

and nature algorithms [D ].Politecnico di Milano ,Ital y :De 2partment of Electronics ,19921

[2] Colorni A.Ant system for job -shop scheduling[J ].JORBEL ,

1994,34(1):39-53.

[3] Colorm A ,Dorigo M ,Manieaao V.Distributed optimization by

ant colonies[C]//Proc of the First European Conf.On Artifi 2cial Life.Paris ,France :Elsevier Publishing ,1991:134-142.

[4] Coello C A C ,Gutierrez R L Z ,G arcia B M ,et al.Automated

design of combinational logic circuits using the Ant System [J ].Engineering Optimization ,2002,34(2):109-127.[5] Costa D ,Hertz A.Ants can color graphs [J ].Journal of the

Operational Research Societ y ,1997,48(3):295-305.[6] Bullnheimer B ,Hartl R F ,Strauss C.An improved ant system

algorithm for the vehicle routing problem[J ].Annals of Op 2erations Research ,1999,89:319-328.

[7] Stutzle T ,Hoos H H.MAX -MIN ant system [J ].Future

G eneration Computer Systems ,2000,16(8):889-914.[8] 吴 斌,史忠植.一种基于蚁群算法的TSP 问题分段求解

算法[J ].计算机学报,2001,24(12):1328-1333.

[9] 马少平,朱小燕.人工智能[M ].北京:清华大学出版社,

2004.

(上接第166页)着RFID 技术的不断发展,其他标准法规的不断完善,其在物流领域的应用也将不断深入。

参考文献:

[1] 刘守义,毛丰江.智能卡技术[M].西安:西安电子科技大

学出版社,2004.

[2] Finkenzeller K.射频识别(RFID )技术[M].陈大才,王卓人

译.北京:电子工业出版社,2001.

[3] 孙 红.基于物流信息系统[M].武汉:武汉理工大学出版

社,2005.

[4] 陈婀娜.RFID 射频识别技术———未来商场实现的关键技

术[J ].商场现代化,2006(2):24-25.

[5] Hendry M.智能卡安全与应用[M ].杨义先译.北京:人民

邮电出版社,2002.

?

071? 计算机技术与发展 第18卷

相关文档