蚁群算法信息素更新方式的评价研究

蚁群算法信息素更新方式的评价研究*李

洋袁刘艳娜

渊中南大学地球科学与信息物理学院袁湖南

长沙410083冤

摘要院本文以求解TSP渊Travellingsalesmanproblem冤问题为例袁引入变量BESTPATHij来保存TSP中边对应的最优解袁通过计算边的最优解和对应信息素浓度之间的相关性袁来定量评价基本蚁群算法信息素更新方式的优劣遥以TSPLIB的多次实中验的中pr76袁相袁关ch130系数袁绝tsp225对值的为最测大试值数的据平均值分别袁计算最优是解院和0.723信息素3袁浓0.756度之2间袁的相0.795关袁系说数明,结基果本发蚁现群算在三法组的测中试边数最据优解和信息素浓度的相关性不是特别强袁表明其信息素更新方式难以充分利用已有的搜索成果袁存在较大改进空间遥关键词院蚁群算法曰信息素曰旅行商中图分类号院TP18文献标志码院ADOI院10.3969/j.issn.1674-9146.2016.03.065蚁群算法作为一种群集智能的优化算法袁

最早笔者以基本蚁群算法求解旅行商渊TSP冤为例袁是由意大利学者M.Dorigo等[1]人于1991年提出遥因引入变量BESTPATHij来保存边对应的最优解袁对为它具有正反馈尧分布式计算尧易于与其他方法相信息素的更新方式进行定量评价袁以为蚁群算法信结合等优点[2]息素更新方式的改进提供参考和指导遥问题袁如旅行袁商所以渊TSP广冤泛问题应用[3]于尧解决指派各种组合问题[4]尧集合优化

1蚁群算法解决旅行商问题

覆盖问题[5]等遥

旅行商问题袁就是有固定个数的城市袁一位商信息素作为蚁群算法非常重要的组成部分袁能人想要游览所有的城市袁所走的路程要最短且同时指导整个蚁群中众多蚂蚁的搜索行为遥很多人员对每个城市只能够游览一次遥蚁群算法解决TSP的原信息素的更新方式做了大量的研究工作遥Thomas理为

andsystemHolger[6]根据最大最小蚂蚁系统渊MAX-MINant到提高冤算人为法的限定精确信性息素遥郑的卫极国大等尧[7]在极小算法值中袁对从蚂蚁而达

pq扇设[子ij渊t冤]琢伊[浊茁

ij渊t冤]ij渊t冤=缮设袁若js沂[子琢[浊茁is渊t冤]伊is渊t冤]沂allowedq

进行区分袁达到直接控制信息素浓度的目的袁进行设设移allowed

q袁渊1冤有区别的更新袁从而提高了算法的精度遥研究者们式中院墒

U为所有要游0览的城市袁否则子ij渊t冤为在第t次迭

知道基本蚁群信息素更新方式不完善袁所以对信息代时路径渊i袁j冤的信息量袁蚂蚁q渊q=1袁2袁3袁素的改进研究主要集中在它的更新策略和变化机制噎袁冤上袁取得了一定程度的改进袁但是基本没有对信息市与当前在搜城索市接路下径来上的要达到的信息量和城市时启发袁函根数据决候定选其城下素的更新方式作出定量评价遥

一步要访问的城市袁pq

ij渊t冤为第t次迭代时袁蚂蚁q

[基金项目]国家自然科学基金项目渊41201383冤收稿日期院圆园15原11原30曰修回日期院圆园16原02原14作者简介院李

洋渊1988-冤袁男袁河北秦皇岛人袁在读硕士袁主要从事地理空间分析尧蚁群智能尧选址建模研究袁

E-mail院727060307@qq.com遥科技创新与生产力2016年3月总第266期065.com.cn. All Rights Reserved.应用技术AppliedTechnology由城市i运动到城市j的概率遥allowedq为蚂蚁q当前可以选择的城市曰琢为信息=指{U-tabuq数袁其}值越大袁则蚂蚁倾向于选择其它蚂蚁已经走过的路径袁即信息素浓度大的方向曰茁为启发指数袁反映启发信息的受重视程度曰浊ij式为

渊t冤为启发函数袁其表达浊ij渊t冤=1/dij.

渊2冤

式中院dij为两个城市之间的距离遥为了增加启发信息的影响袁要对信息素进行更新处理遥第t+1次迭代时路径子ij子渊ijt渊冤t的+1信冤=息渊量1-按籽冤如下伊规则进行调整遥

m

子ij渊tq

冤+驻子ij渊t冤.

渊驻子ij渊t冤=移q=1

驻子ij渊t冤.

渊43冤

冤

式中院籽为挥发系数曰驻子ij渊t冤为q

第t次迭代时袁路径渊i袁j冤上的信息素增量袁驻子ij第t次迭代在路径渊i袁j冤上留下的渊t冤信为息第量遥

q只蚂蚁其中驻子q

ij略进行计算院

渊t嗓冤按Ant-Cycle模型的信息素更新策驻子q

Q/ij渊t冤=

式中院Q为信息素0L强袁q袁度否则

若蚂蚁经过渊i袁j冤.渊5冤

袁Lq为第q只蚂蚁遍历完所

有城市所走过的总路径长度遥

2信息素更新方式的评价和结果分析2.1相关性的验证

为了评价基本蚁群算法信息素更新方式的好

坏袁以求解TSP问题为例袁引入变量BESTPATHijBESTPATHij表示城市渊i袁j冤之间的边在所有迭代遥过程中蚂蚁找到的经过此边的最优路径的长度值遥初始时袁BESTPATHij值遥当一次迭代完成后=袁MAX按如下袁MAX方式为一更新个本无次穷迭大代中蚂蚁所找到路径包含的边的BESTPATHijBESTPATHijBESTPATHij跃曰L对于r袁BESTPA城市模TH型ij为=Lnr曰的ElseTSPBESTPATH院袁存在有nijif=渊n-1冤/2条边遥蚁群算法迭代过程中袁BESTPATH伊

ij集合里会有大量的劣质解和值为MAX的解袁这些BESTPATHij对应的大部分子ij过程中发挥作用袁会被野淹没渊k冤冶遥很难由在于算蚁法群算寻优法已的找到的较优解在下一次寻优中占有重要地位袁能不

能充分利用较优解决定算法能否继续发现更好的解遥为了更好地验证较优解的利用情况袁在求信息素浓度和较优解二者的相关系数时袁实验选取前2n个最优ij的称为BESTPA最优解THijBESTPATH遥BESTPATH袁这些较ij优都有的与其2n个对066SCI-TECHINNOVATION&PRODUCTIVITY晕燥援3Mar.圆园16袁栽燥贼葬造晕燥援266应的信息素浓度子ij优解之间的相关系数渊来k冤袁达到通过计评价的算目信的息素遥

浓度和最实验的测试城市数据来源于http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95从中选取pr76袁ch130袁tsp225三个测试数据网进站行遥实验袁实验所用程序为C#语言编写袁在MicrosoftVisual代次数为Studio20104000袁参开数发设环置境参考上运M.Dorigo行遥每组等实[11-验12]的用迭蚁群算法解决TSP中的参数数值袁具体如下院琢=1袁茁=2袁籽=0.1袁M.Dorigo[11]认为蚂蚁个数m和要解决的TSP中城市规模有关遥根据其思想袁实验所用三组数据中m的取值设置成各自城市规模的三分之一袁Q设置成第一次迭代后m个蚂蚁闭合路径长度平均值的百分之一遥每个测试数据做10次实验袁每隔10次迭代计算一次相关系数袁所以一次实验会有400个相关系数袁表1是3个测试数据的相关系数的绝对值的最大值遥pr76的一次随机实验中相关系数随迭代次数变化情况见图1遥

表1每次实验中的最大相关系数值

实验相关系数实验相关系数序号pr76ch130tsp225序号pr76ch130tsp22510.7070.6680.79060.7470.7570.79420.7400.7160.83070.6640.8040.80130.7050.7500.79080.7100.7090.80040.7350.7960.78090.7300.7940.77050.7700.8030.798100.7250.7650.801-0.3-0.4-0.5-0.6-0.7-0.805001000150020002500300035004000迭代次数图1pr76的相关系数随迭代次数变化

结合表1和图1可以得出最优解和信息素之间存在相关关系袁但是相关系数最大值很难大于0.8袁在三组测试数据的多次实验中袁相关系数的绝对值的平均值分别是0.7233袁0.7562袁0.795袁可知相关性不够强遥

2.2较优解对应的信息素浓度研究

为了探求相关性不够强的原因袁在三个测试数据的实验中袁进行每组实验的第2000次迭代时袁通过标记算法找到的最优解所对应的城市间的n条边袁并且将全部的n伊渊n-1冤/2个信息素浓度值按降序排序袁统计n条边对应的信息素在全部信息素中的位置排序情况遥

从第67页图2可知袁在n个信息素之中袁位

.com.cn. All Rights Reserved.置排序序号大于1.5伊n的信息素值过小袁在下一次搜索时袁对应的边很可能会被野淹没冶袁这些信息素就是较差的信息素遥以pr76数据为例袁统计n个信息素中较差的信息素位置序号见表2遥

403530252015105-0506001200180024003000序号

图2信息素值按降序排序的情况

表2pr76相对较差的信息素的排序位置

位实验序号置12345678910322145054634134128361829811491601671099283319246168541155561127163829191256179143283124292123155505162207153133247112252119146467158163137126202109219110排1414221451591361221919714596序位1382791311441301201799514495置1302571231341191141699114093序号128226103129113113147901398910820299123991011318713885102194951229493120831308396177921188888115811258195176911028686112791237691153899482859576120758615185918180947510770从表2可知袁pr76数据的10次实验平均值中有9个信息素浓度值的位置排序大于1.5伊76曰ch130值的位和置tsp225排序大则于分别有1.5伊n遥

10个和17个信息素浓度从表1知袁pr76和ch130两个测试数据在10次实验中的相关系数绝对值的最大值都很难达到图0.81袁发tsp225现相关中相系关数系在达到数也只某是一偶极尔值后略大不于会0.8继续袁变从

大袁趋势会趋于稳定或出现减小的情况遥从表2中寻找相关性不强的原因袁发现通过蚁群算法找到的三个城市的最优解所对应的信息素浓度中会有一部分较差的信息素存在遥表2中pr76的10次实验中袁每次实验平均会有9个信息素浓度值位置排序大于1.5伊76遥这些排序大于1.5伊n的信息素值过小袁在下一次搜索时袁对应的边会被很快野淹没冶袁蚁群算法难以利用相对较好的解袁而此次之所以能找到这个较优解袁存在偶然因素遥算法虽然找到一AppliedTechnology应用技术些最优边袁但是难以充分利用这些较优边袁一些较差边会存在算法搜索到的最优路径中袁而较优解的某些优质边会因为信息素过小而被野淹没冶[11]3结束语

遥

信息素更新方式是蚁群算法的核心组成部分袁笔者通过对TSP中边的最优解和信息素浓度之间相关性进行研究袁发现二者之间的相关性不是很强遥并发现通过实验已找到的最优解对应的信息素中会有部分较差值袁因而算法不能充分利用所找到的较优解遥该研究方法可为蚁群算法信息素更新方式的理论提供定量评价方面的补充袁也可为基本蚁群算法信息素更新方式的改进提供新的参考和指导遥

参考文献院[1]COLORNIA,DORIGOM,MANIEZZOV.Distributedoptimizationbyantcolonies[C]//ProceedingsofthefirstEuropeanconferenceonartificiallife.1991,142:134-142.[2]梁德赛,梁高业,韦思庆.求解旅行商问题的自适应蚁群算法[J].计算机与现代化,2012(7):14-16.[3]李成冰,郭瑞雪,李敏.改进蚁群算法在旅行商问题中的应用[J].计算机应用,2014,34(S1):131-132,165.[4]MANIEZZOV.Theant-systemappliedtothequadraticassignmentproblem[J].IEEETRANSACTIONSONKN-OWLEDGEANDDATAENGINEERING,1999,11(5):769-778.[5]SILVADA,RICARDOM,RAMALHOGL.Antsystemforthesetcoveringproblem[C]//Systems,Man,andCy-bernetics,2001IEEEInternationalConferenceon.IEEE,2001,5:3129-3133.[6]STUTZLET,HOOSHH.MAX–MINantsystem[J].Fu-turegenerationcomputersystems,2000,16(8):889-914.[7]郑卫国,田其冲.张磊.基于信息素强度的改进蚁群算法[J].计算机仿真,2010,27(7):191-193.[8]DORIGOM,MANIEZZOV,COLORNIA.Antsystem:optimizationbyacolonyofcooperatingagents[J].IEEETr-ansactiononSystems,Man,andCybernetics-PartB,1996,26(1):29-41.[9]DORIGOM,GAMBARDELLALM.Antcoloniesforthetravellingsalesmanproblem[J].BioSystems,1997,43(2):73-81.[10]DORIGOM,GAMBARDELLALM.Antcolonysystem:acooperativelearningapproachtothetravelingsalesmanproblem[J].EvolutionaryComputation,IEEETransactionson,1997,1(1):53-66.[11]吴庆洪,张颖,马宗民.蚁群算法综述[J].微计算机信息,2011(3):18-23.渊责任编辑

石俊仙冤

渊英文部分下转第72页冤

科技创新与生产力2016年3月总第266期067.com.cn. All Rights Reserved.应用技术AppliedTechnology据曰为出行模拟提出了基于四阶段模型和GIS松散2004(38A):643-675.结合的解决方法遥

[8]GolobTF,BeckmannMJ,ZahaviY.Autility-theorytravel参考文献院demandmodelincorporatingtravelbudgets[J].Tmnsporta-[1]柴彦威,沈洁,赵莹.城市交通出行行为研究方法前沿[J].中tionResearch,1981(5B):375-389.国科技论文在线,2010,5(5):402-409.[9]GoodwinPB.Theusefulnessoftravelbudgets[J].Transpo-[2]易汉文.出行预测方法从出行模型到行为模型的变革[J].rtationResearch,198l(15A):97-106.城市交通,2007,5(1):72-79.[10]BlackWR.RenectionsonUrbanTravelandUIbanTravel[3]隽志才,李志瑶,宗芳.基于活动链的出行需求预测方法综Models[R].Italy:UniversityofMilan,2002.述[J].公路交通科技,2005,22(6):108-113.[11]陈述彭,鲁学军,周成虎.地理信息系统导论[M].北京:科[4]DevlinGerJ,McDonnellKevin,WardShane.Timberhaul-学出版社,2000.ageroutinginIreland:ananalysisusingGISandGPS[J].[12]邬伦,刘瑜,张晶,等.地理信息系统要要要原理尧方法与应JournalofTransportGeography,2008(16):63-72.用[M].北京:科学出版社,2010.[5]杨天宝,刘军.应用改进重力模型法预测铁路行包OD运[13]长沙市国土资源局.长沙市行政区划[EB/OL].[2015-量的研究[J].铁道运输与经济,2006,28(3):84-86.09-21].http://www.csgtzy.gov.cn/.[6]柴彦威,沈洁.基于活动分析法的人类空间行为研究[J].地[14]赖春晖.基于神经网络的交通信号模糊控制策略[D].广理科学,2008,28(5):594-600.州:暨南大学,2010.[7]MokhtarianPL,ChenC.TTBorNotTTB,thatisthequ-[15]李擎,宋顶立,张双江,等.两种改进的最优路径规划算estion:Areviewandanalysisoftheempiricallitemtureon法[J].北京科技大学学报,2005,27(3):367-370.traveltime(andmoney)budgets[J].TransponationResearch,Spatio-temporalSimulationand渊责任编辑

高

腾onRouteStatisticalPlanningData

ofUrbanTravelBehaviorBased

冤

DengJi-qiu袁LiYang袁OuyangFang

Abstract院

Combined渊SchoolofwithGeosciencesGIStechnologyandInfo-Physics,andfourstageCentralmodel,Souththespatio-temporalUniversity,Changshasimulation410083methodChinaof冤

travelhasbeenproposedbasedonstatisticaldatainthispaper.Bysimulatingthespatialdistributionofpopulationstatistics,combiningthelandfactorandthefactorsoftravel,thepredictionofthetripgeneration,tripdistribution,modeselectionandtrafficdistribu-tioninChangshacityhasbeencarriedout,andtheapplicationoftheoptimaltimeandtheshortestpathrouteplanninghasbeenrealized.Keywords院travelsimulation;routeplanning;GIS;fourstagemodel渊上接第67页冤

EvaluationofthePheromoneUpdatingAlgorithm

MethodoftheBasicAntColony

LiYang袁LiuYan-na

Abstract院A渊quantitativeSchoolofGeosciencesassessmentofandpheromoneInfo-physic,updateCentralmethodSouthhasUniversity,beencarriedChangshaoutinthis410083paper.ChinaA冤

variablecalledBESTPATHijwasintroducedintotheassessmenttosavethecorrespondingoptimalsolutionofedgeinTSP,andthepheromoneupdatingmethodwasevaluatedthroughtheanalysisofcorrelationbetweenopticalsolutionsoftheedgesanditscorrespondingpheromonesvalue.ThreeTSPproblem,pr76,ch130andtsp225wereusedasthetestdataintheexperiment.Themeanvalueofabsolutemaximumvalueofcorrelationcoefficientis0.7233,0.7562and0.795inthethreetestdatawhichshowsthattherelativityofthemarenotveryintense.Sothesearchingachievementofthealgorithmcan'tbeenfullyused.Itindicatesthatlotsofmodificationcanbeendoneonpheromoneupdatingmethod.Keywords院antcolonyalgorithm;pheromones;travelingsalesman072SCI-TECHINNOVATION&PRODUCTIVITY晕燥援3Mar.圆园16袁栽燥贼葬造晕燥援266.com.cn. All Rights Reserved.