《一种求解TSP的混合遗传蚁群算法.docx》由会员分享，可在线阅读，更多相关《一种求解TSP的混合遗传蚁群算法.docx（10页珍藏版）》请在三一文库上搜索。
1、 6- 7第 28卷第 8期计算机应用V ol. 28 No. 82008年 8月C ompu ter App licationsAug. 2008文章编号: 1001- 9081( 2008) 08- 2084- 04一种求解 TSP的混合遗传蚁群算法徐金荣1, 李允1, 刘海涛1, 刘 攀2( 1. 西南交通大学信息科学与技术学院, 成都 610031;2. 西南交通大学 CAD 中心, 成都 610031)( xu _jin_rong 163. com )摘 要: 结合遗传算法和蚁群算法, 提出了一种求解 TSP 的基于启发式遗传信息的蚁群遗传算法。该算法由蚁群遗传算法和基于启发式遗传信
2、息的蚁群算法两部分组成。蚁群遗传算法将蚁群算法和遗传算法结合起来, 提高了遗传算法的种群的多样性; 基于启发式遗传信息的蚁群算法是将启发式遗传信息加入到蚁群算法中, 防止蚁群算法对信息素过分依赖, 缩小最优解的搜索空间。HG I A CGA 算法是将启发式遗传信息加入到蚁群遗传算法中, 可以提高蚁群算法的收敛速度和寻优能力。实验结果表明, HG I A CGA 算法在收敛速度和收敛精度上均优于 A CGA 和 ACA 算法。关键词: 遗传算法; 蚁群算法; 信息素; 启发式遗传信息; 旅行商问题中图分类号: T P301. 6文献标志码: AHybrid genetic ant colony
3、algorithm for traveling salesman problemXU Jin rong1, LI Yun1, LIU H ai tao1,LIU Pan2(1. S chool of Inform ation S cience and Technology, S outhw est Jia otong University, Chengdu S ichuan 610031, Ch ina;2. CAD C en ter, S ou thw est Jia otong Un iversity, Chengdu S ichuan 610031, Ch ina )Abstract:
4、A new H euristic G enetic Inform ation based Ant Colony G ene tic A lgor ithm (HG I ACGA ) to solve T rave lingSa lesm an P roblem s(T SP) w as proposed.HG I ACGAs tw o sub a lgor ithm s are A nt Co lony G enetic A lgorithm ( ACGA )andH euristic G enetic Inform ation based A nt Colony A lgor ithm (H
5、G I ACA ).ACGA enhances g enetic a lgo rithms popu la tiondiv ers ity and reduces the search dom a in, while HG I ACA e lim inates the creation o f inva lid tours and a lso avo ids depending onpheromone excess ive ly. A comb ination of genetic in fo rm ation and phe romone leads to a sign ificant im
6、provem ent in per fo rm ance. T he stra tegy o fHG I ACGA a lgo rithm can im prove convergence ra te and capac ity o f searching optim a l so lution.Expe rim en tal results show that the proposed algor ithm genera lly exhib its a better so lution and a higher rate o f convergence fo r TSP than ACGA
7、and ACA.K ey words: G enetic A lgor ithm ( GA ); An t Co lony A lgo rithm ( ACA ); pherom one; heuristic genetic inform ation; T rave ling Sa lesm an Problem (T SP )0 引言T SP问题即给定一组 N 个城市和它们两两之间的直达距离 , 寻找一条闭合的旅程, 使得每个城市刚好经过一次且总的旅行距离最短。用图语言来描述 T SP: 给出一个图 G = ( V,E ), 每边 e E 上有非负权值 ( e), 寻找 G 的 H am i
8、lton回路 C, 使得该回路 C 的总权值最小。T SP 问题是一个典型的组合优化问题, 其可能的搜索路径随着城市数目 N 的增加呈指数增长, 属于 N P完全问题。求解 TSP的启发式算法很多, 如遗传算法、蚁群算法等。遗传算法 ( G enetic A lgor ithm, GA ) 1 对非线性复杂问题显示出很强的求解能力 2 , 因而被成功地应用于模式识别、智能控制等领域。但基本遗传算法 ( Sim ple G ene tic A lgo rithm s, SGA ) 3 在解决一些复杂问题时, 存在着早熟、收敛速度慢及优化精度低的缺陷。为克服基本遗传算法的这些缺陷, 目前相关的研究
9、工作主要集中在对编码方式、选择算子、变异算子等方面对基本遗传算法加以改进。蚁群算法 ( An tCo lony A lgor ithm, ACA ) 4- 5 是一种模拟蚂蚁群体智能行为的仿生优化算法, 它具有较强的鲁棒性、优良的分布式计算机制、易于与其他算法相结合等优点 。但蚁群算法也有其突出的缺点, 在初期信息素缺乏, 导致搜索初期积累信息素占用的时间较长, 并且易陷于局部最优解。针对这些缺陷, 近些年来众多国内外学者在蚁群算法的改进方面做了大量的研究工作, 目标就是为了在合理时间复杂度的限制条件下, 尽可能提高蚁群算法在一定空间复杂度下的寻优能力, 从而改善蚁群算法的全局收敛性, 并拓宽
10、蚁群算法的应用领域 8 。本文结合了遗传算法和蚁群算法的优点, 提出一种新型的基于启发式遗传信息的蚁群遗传算法 ( H eu ristic G enetic Inform ation based Ant Co lony G enetic A lgor ithm, HG I A CGA )。该算法由基于启发式遗传信息的蚁群算法 ( H eur istic G enetic Inform ation based A nt Co lony A lgo rithm, HG I ACA )和由蚁群算法驱动的遗传算法 ( A nt Co lony G enetic A lgor ithm, A CGA )
11、 共同组成。HG I ACA 算法的性能由信息素和遗传信息两个因素来决定, 可以避免对信息素的依赖性, 同时遗传算法的概率搜索优势可以降低蚁群算法陷入局部最优解的概率。A CGA 算法让 HG I A CA 算法中每个蚂蚁搜索到的最优个体进入进化池, 和自身所产生的新个体共同构成遗传算法的新一代种收稿日期: 2008- 02- 29; 修回日期: 2008- 04- 14。基金项目: 国家 863 计划项目 ( 2005AA1Z2060) 。作者简介: 徐金荣 ( 1982- ), 男, 江苏泰州人, 硕士研究生, 主要研究方向: 普适计算、人工智能、计算机网络;李允 ( 1971 - ),
12、男, 重庆人,副教授, 博士, 主要研究方向: 普适计算、实时嵌入式操作系统;刘海涛 ( 1982 - ), 男, 江西萍乡人, 硕士研究生, 主要研究方向: 嵌入式操作系统;刘攀 ( 1983- ), 男, 湖北当阳人, 硕士研究生, 主要研究方向: 计算机 CAD、人工智能。第 8期徐金荣等: 一种求解 TSP的混合遗传蚁群算法2085群。这样保证了遗传算法的种群的多样性, 可以有效防止陷入局部收敛, 同时提高了收敛的速度。1 求解 TSP 的蚁群遗传算法A CGA 算法的基本思想是在 SGA 算法的基础上, 加入了蚁群算法, 目的是让蚁群算法中产生的个体也作为遗传算法产生新一代种群的依据
13、, 这样可以提高种群的多样性, 防止遗传算法陷入局部收敛。下面为 ACGA 算法的伪代码, 其中 P 0 表示初始种群, M e 表示种群的规模, P c 表示交叉概率, Pm 表示变异概率, T 表示进化算法的终止代数。其中 P ( t) 表示第 t代种群, P ( t) =( P1, t, P2, t, !, P ,i t, !, PM e, t ), 其中P ,i t 表示第 t代种群中的第 i个个体。该算法由 6部分组成, step2 step4分别对应于选择算子、交叉算子和变异算子, 这几个遗传算子是独立于 ACGA算法的, 参考文献 9 提供了多种遗传算子。 step5 描述的是A
14、CA 产生一个种群 P ( t), 其个体数目为 M a, 并且按照适应度值由高到低进行了排列, 这样做是便于 step6进行操作。step6描述了产生下一代种群的过程, 如果选择算子所选择出的个体数与M a 之和小于M e, 则种群 P( t) 中全部个体会进入下一代种群, 不足 M e 部分的个体通过随机产生, 如果选择算子所选择出的个体数与M a 之和不小于M e, 则P( t) 中只有一部分个体会被选择进入下一代种群, 其选择的方法是从 P( t) 的第一个个体开始往下选, 直到进入下一代种群的个体数目等于 M e。A CGA 算法伪代码如下:step 1.in itializet #
15、 0P ( 0) # (P 1, 0, P2, 0, !, PM e, 0 ) # P 0w h ile t #t+ 1 Tstep 2.selection operators # 0/ / s is theind iv idu al num ber selected by selection operatorfor i #1toM edo if evaluate( P i,t) % averagefitn essth en P s, t+ 1 #P i, ts #s + 1step 3.crossover operatorfor i #1 to s - 1do if Random 0, 1
16、Pcth en crossP i, t+ 1w ithP i+ 1, t+ 1step 4.mu tation op eratorfor i #1to sdo ifRandom 0,1 Pmthen mu tateP i, t+ 1step 5. ACAcreate aM a -sized popu lationP ( t)in descend ing orderP( t) # NULLfor i #1 toM a/ /M a is the numb er of ants in ACAdoP ( t) # P ( t) & P ,i tfor i #1 toM a -1for k #i+ 1
17、toM ado if evalu ate( Pi, t ) evaluate( Pk, t )then exchangeP tP i,k, tstep 6.produ ce the next gen eration popu lationif s+ M a n ); k,i j ( t) 表示第 k 只蚂蚁第 t代时, 留在路径( i, j ) 上所释放的信息素浓度, 此处使用的是 D or igo M 提出的 A nt Q uantity 4 模型, 如式 ( 5)所示。t +n= ( 1 - % )( t) + % ( ( t)( 3),i j (C),i ji, jM a i, j (
18、t) = ) i,k j ( t)( 4)k = 10,第 k 只蚂蚁经过的路型 ki, j ( t) =( 5)di, j0 ,其他ACA 算法伪代码。step 1. in itializechooseM acities and p lace all ants on those citiesfor i #1 to nfor j #1 tondo i, j #0 ,i j ( 0) # 0step 2.every ant search a TSP pathfork #1 toM ado set tabuk emp tyw h ile ta buk is not fu lldo choose n
19、ext city, w ith probab ility given by equation ( 3 )move th ekth an t to th e chosen cityinsert the chosen city in to the tabuk of the k th ant com pute ki, j ( t) as defin ed in equ ation ( 7)2086计算机应用第 28卷Pk, t # TSP path th ek th an t have found compu te i, j ( t) as defined in equation ( 6)step
20、3.updatetab lecom pu te the new value for tab le as equation ( 5)step 4.create popu lation group P( t)P( t) # NULLfor k #1 toM a/ /M a is the numb er of ants in ACAdoP ( t) # P ( t) & P k, tfor i #1 toM a- 1for k #i+ 1 toM ado if evaluate( P i, t) evaluate( P k,t+ 1 )then k =iglobal update& tab le a
21、s defined in ( 11 ),( 12)在每一代进化过程中, 选择算子会选出 s 个优秀的个体进入下一代种群, 算法会根据这 s条 TSP路径来更新 (表中遗传信息, 称之为局部更新, 见式 ( 8) ( 10)。式中 p& 0, 1) 表示遗传信息局部更新系数; &i, j ( t) 表示在第 t代时, 路径( ,i j ) 上的遗传信息增量。&k,i j ( t) 表示选择算子所选择出的第 k 个个体在路径 ( i, j ) 上留下的遗传信息量。&i, j ( t + 1) = ( 1 - %& ) &i, j ( t) + %&( &i, j ( t)( 6)s&,i j (
22、t) = ) &k,i j ( t)( 7)k = 1&k( t) =,i j&0 ,个体 P k, t+ 1 中包含 edge ( ,i j )( 8)di, j0 ,其他 局部更新完成后 , 系统会从 s 个个体中选出适应度值最高个体 , 假设为第 k 个个体 P k, t+ 1 , 然后针对该个体 , 对 & 表进行全局更新 , 见式 ( 11 ), ( 12 ) 。式中 & 表示遗传信息全局更新系数 , & 0 , 1 ) ; & ,i j ( t) 表示在第 t 代时 , 路径 ( i, j ) 上的遗传信息增量 ; Lk表示最优个体Pk,t+1所对应的度。& i ,j(t+1)=(
23、1-&)&i,j(t)+&(&i,j(t) & , ij(t)= L & 0 , 个体 P k, t+ 1 中包含 edg e ( i, j)kTSP路径长(9)(10)0 ,其他HG I ACGA 算法中, 使用 HG I A CA 算法取代 ACGA 算法中使用的 ACA 算法, HG I ACA 算法在 ACA 算法的基础上对转移概率和更新策略上进行了改进。蚂蚁在搜索过程中, 根据各条路径上的信息素浓度, 启发信息以及遗传信息来计算状态转移概率。Pk,i j ( t) 表示 t时刻蚂蚁 k 由城市 i转移到城市j的状态转移概率, 见式 ( 11)。Pkj( t)=i,( ( ( t) +
24、 ( 1 - () ( & ( t) ) ( # ( t) !)( ( ,i j ( t) + ( 1 - () ( &,i j ( t) ) ( #i, j ( t) !,i ji, j,i jsallow edkj allow edk0 ,其他( 11)式中,、!、 、# 的定义和式 ( 1) 相同, 表示遗传信息启发因子, 其值越大, 则蚂蚁倾向于选择遗传信息较强的路径; ( 0, 1 表示信息素表 和遗传信息表 &之间的平衡因子, (其值越大, 说明遗传信息对 HG I ACA 算法的影响就越小, 信息素对 HG I ACA 算法的影响越大。每一代进化过程中, A CA 算法中, 仅对
25、信息素表进行一次更新, 而 HG I ACA 算法, 会对信息素表进行两次更新, 一次是局部信息素更新, 另一次是全局更新。当所有蚂蚁搜索完毕后, 会使用 An t Q uantity 模型对信息素表 ( 进行一次局部更新, 见式 ( 3) ( 5) 。为了能够使特性较好的路径占有一定的优势, 系统会根据最优的 T SP 路径, 对信息素表进行一次全局更新, 全局更新采用的是一种简化的 A nt Cy cle 4 模型, 见式 ( 12)和 ( 13)。式中 0, 1) 表示信息素全局更新系数; ,i j ( t) 表示在第 t代时, 路径 ( i, j ) 上的信息素增量。Lk 表示所有蚂蚁
26、发现的最优的 T SP 路径长度, 即表示第 k 只蚂蚁搜索到了第 t代中最优的 TSP路径。i, j(t +n)=( 1 - ),i j( t) + ( ,i j( t)( 12)Ci, j( t)=L0,第 k 只蚂蚁经过的路径( 13)k0,其他HG I ACA 算法的伪代码如下所示, 使用 HG I ACA 代替标准 ACA 算法, 可以提高 HG I ACGA 算法中产生的新一代种群的多样性, 增加全局收敛概率和收敛速度。HG I ACA 伪代码如下:step 1 initialize第 8期徐金荣等: 一种求解 TSP的混合遗传蚁群算法2087chooseM acities and
27、 p lace all an ts on those cities法对 berlin52问题进行详细的测试。图 5描述了 10 次求解for i #1tonberlin52问题的最优值统计图。从中可以看出, HG I ACGA 算for j #1to n法求得的最差解和最优解均优于 A CA 和 ACGA 算法。doj #i,0从表 3和图 1可以看出, 第 4, 9, 10次的测试结果具有代,i j( 0) # 0step 2 every an t search a TSP path表性。为了对三种算法进行进一步分析和比较, 对第 9次的for k #1 toM a测试结果进行研究。图 2描
28、述了三种算法求解 ber lin52时最do set tabuk emp ty优值的进化过程, 在进化过程中, HG I ACGA 的最优值不断得w h ile tabuk is not full到更新, 在第 485 代获得了最优值 8 196, ACGA 算法在第 88do choose the city to m ove to w ith equation ( 13)m ove the k th ant to the chosen city代获得了最优值 8 292, ACA 算法在第 26 代获得了最优值insert th e chosen cityin to the tabuk of
29、 the k th ant8895。com pute k( t) as defined in equation ( 7 ),i jcompu te i, j ( t)asdefin ed in表 3 三种算法求解 10次结果的统计比较equ ation ( 6)最优值平均值误差率 /%step 3local updatetab leTSPACA ACGA HGI ACGAACA ACGA HG I ACGAACA ACGA HGI ACGAcom pu te the newvaluefortab leas equationeil514674634535024994879. 68. 76. 3(
30、 5)berlin528 1388 0307 7138 8198 4988 2718. 86. 52. 3step 4 global update tab lest7077176073885381679114. 212. 69. 3if th ekth anthas found abest TSP ingeneration teil7665660558969466664221. 912. 59. 5th encom pute th e newva luefortab le aspr10747 875 47 59446 66249 852 49 38248 9928. 17. 45. 3equ ation ( 14 ) ( 15)step 5 create popu lation group P( t)P( t) # NULLfor i #1 toM a/ /M a is the numb er of ants in ACAdoP ( t) # P ( t) & P ,i tfor i #1 toM a - 1for k #i + 1 toM ado if evaluate( P