Ant colony system A cooperative learning approach

DorigoandGambardella-AntColonySystem1AntColonySystem:ACooperativeLearningApproachtotheTravelingSalesmanProblemTR/IRIDIA/1996-5UniversitéLibredeBruxellesBelgiumMarcoDorigoIRIDIA,UniversitéLibredeBruxelles,CP194/6,AvenueFranklinRoosevelt501050Bruxelles,[e-mail],@idsia.ch,~lucaAbstractThispaperintroducesantcolonysystem(ACS),adistributedalgorithmthatisappliedtothetravelingsalesmanproblem(TSP).InACS,asetofcooperatingagentscalledantscooperatetofindgoodsolutionstoTSPs.AntscooperateusinganindirectformofcommunicationmediatedbypheromonetheydepositontheedgesoftheTSPgraphwhilebuildingsolutions.WestudyACSbyrunningexperimentstounderstanditsoperation.TheresultsshowthatACSoutperformsothernature-inspiredalgorithmssuchassimulatedannealingandevolutionarycomputation,andweconcludecomparingACS-3-opt,aversionofACSaugmentedwithalocalsearchprocedure,tosomeofthebestperformingalgorithmsforsymmetricandasymmetricTSPs.AcceptedforpublicationintheIEEETransactionsonEvolutionaryComputation,Vol.1,No.1,1997.Inpress.DorigoandGambardella-AntColonySystem2/24I.IntroductionThenaturalmetaphoronwhichantalgorithmsarebasedisthatofantcolonies.Realantsarecapableoffindingtheshortestpathfromafoodsourcetotheirnest[3],[22]withoutusingvisualcues[24]byexploitingpheromoneinformation.Whilewalking,antsdepositpheromoneontheground,andfollow,inprobability,pheromonepreviouslydepositedbyotherants.AwayantsexploitpheromonetofindashortestpathbetweentwopointsisshowninFig.1.ConsiderFig.1A:Antsarriveatadecisionpointinwhichtheyhavetodecidewhethertoturnleftorright.Sincetheyhavenoclueaboutwhichisthebestchoice,theychooserandomly.Itcanbeexpectedthat,onaverage,halfoftheantsdecidetoturnleftandtheotherhalftoturnright.Thishappensbothtoantsmovingfromlefttoright(thosewhosenamebeginswithanL)andtothosemovingfromrighttoleft(namebeginswithaR).Figs.1Band1Cshowwhathappensintheimmediatelyfollowinginstants,supposingallantswalkatapproximatelythesamespeed.Thenumberofdashedlinesisroughlyproportionaltotheamountofpheromonethattheantshavedepositedontheground.Sincethelowerpathisshorterthantheupperone,moreantswillvisititonaverage,andthereforepheromoneaccumulatesfaster.Afterashorttransitoryperiodthedifferenceintheamountofpheromoneonthetwopathissufficientlylargesoastoinfluencethedecisionofnewantscomingintothesystem(thisisshownbyFig.1D).Fromnowon,newantswillpreferinprobabilitytochoosethelowerpath,sinceatthedecisionpointtheyperceiveagreateramountofpheromoneonthelowerpath.Thisinturnincreases,withapositivefeedbackeffect,thenumberofantschoosingthelower,andshorter,path.Verysoonallantswillbeusingtheshorterpath.R2R1L1L2??R2R1L1L2R4R3L3L4R2R1L1R4L5L6R6R5L3L4L2R3R2R1L1R4R3L6L7R7R6L3L4L2L5R5ABCDFig.1.Howrealantsfindashortestpath.A)Antsarriveatadecisionpoint.B)Someantschoosetheupperpathandsomethelowerpath.Thechoiceisrandom.C)Sinceantsmoveatapproximatelyconstantspeed,theantswhichchoosethelower,shorter,pathreachtheoppositedecisionpointfasterthanthosewhichchoosetheupper,longer,path.D)Pheromoneaccumulatesatahigherrateontheshorterpath.Thenumberofdashedlinesisapproximatelyproportionaltotheamountofpheromonedepositedbyants.DorigoandGambardella-AntColonySystem3/24Theabovebehaviorofrealantshasinspiredantsystem,analgorithminwhichasetofartificialantscooperatetothesolutionofaproblembyexchanginginformationviapheromonedepositedongraphedges.Antsystemhasbeenappliedtocombinatorialoptimizationproblemssuchasthetravelingsalesmanproblem(TSP)[7],[8],[10],[12],andthequadraticassignmentproblem[32],[42].Antcolonysystem(ACS),thealgorithmpresentedinthisarticle,buildsonthepreviousantsysteminthedirectionofimprovingefficiencywhenappliedtosymmetricandasymmetricTSPs.Themainideaisthatofhavingasetofagents,calledants,searchinparallelforgoodsolutionstotheTSP,andcooperatethroughpheromone-mediatedindirectandglobalcommunication.Informally,eachantconstructsaTSPsolutioninaniterativeway:itaddsnewcitiestoapartialsolutionbyexploitingbothinformationgainedfrompastexperienceandagreedyheuristic.MemorytakestheformofpheromonedepositedbyantsonTSPedges,whileheuristicinformationissimplygivenbytheedge'slength.Themainnovelideaintroducedbyantalgorithms,whichwillbediscussedintheremainderofthepaper,isthesynergisticuseofcooperationamongmanyrelativelysimpleagentswhichcommunicatebydistributedmemoryimplementedaspheromonedepositedonedgesofagraph.Thearticleisorganizedasfollows.SectionIIputsACSincontextbydescribingantsystem,theprogenitorofACS.SectionIIIintroducesACS.SectionIVisdedicatedtothestudyofsomecharacteristicsofACS:Westudyhowpheromonechangesatruntime,estimatetheoptimalnumberofantstobeused,observetheeffectsofpheromone-mediatedcooperation,andevaluatetherolethatpheromoneandthegreedyheuristichaveinACSperformance.SectionVprovidesanoverviewofresultsonasetofstandardtestproblemsandcomparisonsofACSwithwell-knowngeneralpurposealgorithmslikeevolutionarycomputationandsimulatedannealing.InSectionVIweaddlocaloptimizationtoACS,obtaininganewalg