DOC

Multi-group ant colony algorithm based on simulated annealing method

By Johnny Butler,2014-02-18 01:55
11 views 0
Multi-group ant colony algorithm based on simulated annealing methodon,ant,based,ants,multi,Multi,Ant,Based

    Multi-group ant colony algorithm based on

    simulated annealing method

    JShanghaiUniv(EnglEd),2010,14(6):464468

    DigitalObjectIdentifier(D0I):10.1007/s1174101006792

    Multigroupantcolonyalgorithmbasedonsimulatedannealingmethod

    ZHUJing-wei(朱经纬),RUITing(芮挺),LIAOMing(廖明),ZHANGJinlin(张金林)

    EngineeringInstituteofEngineeringCorps,People'sLiberationArmyUniversityofScienceandTechnology

    Naujing210007,P.R.China

    ?ShanghaiUniversityandSpringerVerlagBerlinHeidelberg2010

    AbstractToovercomethedefaultofsinlglesearchtendency.theantsjnthecolonyaredividedintoseveralsub-groups.The

    antsindifferentsubgroupshavediirerenttrailinformationandexpectationcoefficients.Thesimulatedannealingmethodis

    iutroducedtothealgorithm.Throughsettingthetemperaturechangingwiththeiterations,aftereachturnoftours,the

    solutionsetobtainedbytheantsistakenasthecandidateset.Theupdatesetisobtainedbyaddingthesolutionsinthe

    candidatesettothepreviousupdatesetwiththeprobabilitydeterminedbythetemperature.Thesolutionsinthecandidate

    setareusedtoupdatethetrailinformation.Ineachturnofupdating,thecurrentbestsolutionisalsousedtoenhancethe

    trailinformationonthecurrentbestroute.Thetrailinformationisresetwhenthealgorithmisinstagnationstate.The

    computerexperimentsdemonstratethattheproposedalgorithmhashigherstabilityandconvergencespeed.

    Keywordsantcolonyalgorithm,simulatedannealingmethod,multi

group,candidateset,updateset

    Introduction

    TheantcolonyfAC)algorithmwasfirstintroduced byDorigo.eta1.jasaheuristicalgorithminspiredby theforgingbehavioroftheAC.Itwasfirstappliedto solvingthetravelingsalesmanproblemfTSP).TheAC algorithmachievesoptimumcalculationbysimulating theinformationexchangemechanismandtheinforma. tionpositivefeedbackmechanismamongtherealants. Sinceitspublication.theACalgorithmhasbeencon

    tinuouslyimproved.Theimprovedalgorithms,suchas MMAS[2]ACS[3],ACOI4.havebeenproposedoneafter another.TheACalgorithmwasalsousedtosolvethe continuousoptimizationproblems[.

    CombinationoftheACalgorithmwithotherheuris

    ticalgorithmshasalsobeenproposed.InI6-8l,theAC algorithmwascombinedwiththegeneticalgorithm. Thesolutionset.whichhasbeenobtainedbytheant colony,wasfurtheroptimizedbythemutationand crossoveroperatorsofthegeneticalgorithm.InI91,the ACalgorithmwascombinedwiththeartificialimmune algorithm.Inthefirstpartofthealgorithm,theartifi

    cialimmunealgorithmwasusedtosearchtheoptimum feasiblesolutionaccordingtoitsquickandglobalcon

    vergencecharacteristics.Inthe1atterpartofthealgo

    rithm,theACalgorithmwasusedtofurtheroptimize thesolutionaccordingtoitspositivefeedbackcharac

    teristic.

    Inthispaper,weproposeanewalgorithmcalled

    themultigroupACalgorithmbasedonthesimulated annealingmethodfMACSA).Theantsaredivided

    intoseveralsubgroups.Theantsindifierentsubgroups haveditierentinformationandexpectationcoecients.

    Thismakestheantshavingdifierentsearchtendencies. ThesimulatedannealingmethodisintroducedtOthe algorithm.Thetemperaturewhichchangeswiththeit

    erationsissetinthealgorithm.Thesolutionsetob- tainedbytheantsistakenasthecandidateset.The probabilityofaddingonesolutionofthecandidatesetto theupdatesetisdeterminedbythetemperature.The solutionsintheupdatesetareusedtoupdatethetail information.Ineachturn.thecurrentbestsolutionis usedtoenhancethetailinformationonthecurrentbest rout.Whenthealgorithmentersthelow-temperature stage,thealgorithmcontinuouslyachievesthesamecur

    rentroundbestsolutions.Thismeansthatthetrail informationisoverconcentratedandshouldbereset. Numericalexperimentsshowthattheproposedalgo

    rithmcaneffectivelye3sethecontradictionofearliness, stagnancyandslowconvergence,andhashigherstabil

    ityandconvergencespeed.

    1BasicACalgorithm

    InthispapertheTSPproblemistakenasanexam

    ple.Tobeappliedtotheotherproblems,thisalgorithm canbeslightlymodified.Givenasetoftowns.theTSP canbestatedastheproblemoffindingaminimalroute ReceivedOct.9,2009;RevisedJan.11,2010

    ProjectsupportedbytheNationalNaturalScienceFoundationofChinafGrantNo.50608069

    )

CorrespondingauthorZHUJing-wei,PhD,E-maihzhu_jingwei@163.com

    JShanghaiUniv(EnglEd),2010,14(6):464468465 bystartingfromonetowntotravelalltownsandeven?

    tuallyreturningtothestartingtown,andeachtowncan onlybepassedonetime.Dijisthelengthoftheedge connectingtownsiandJ.

    Letthetotalnumberofartificialantsinthecolony bem,andAkbethekthant.Eachantisasimple

    agentwiththefollowingcharacteristics:Itchoosesthe towntogotowithaprobabilitywhichisafunctionof thetowndistanceandtheamountoftrailinformation presentontheconnectingedge.Toforcetheanttomake legaltours,transitionstothealreadyvisitedtownsare disalloweduntilatouriscompleted.Thisiscontrolled byatabulist.thetabulistofthekthantisUk.When theantcompletesatour.itlaysasubstancecalledthe trailinformationoneachedge(i,J)visited.Let(t)

    betheintensityofthetrailinformationonedge(i,J)at timet.

    ThetransitionprobabilityfromtownitotownJfor thekthantisdefinedas

    ,JUk

    otherwise,

    (1)

    whereisthetrailinformationcoemcient.thedesir

    abilitycoefficient,andthevisibilitycoefficient,which iscommonlysettobe77=寿.

    Whenalltheantshavecompletedtheirtours.thein

    tensitytrailinformationontheedgesshouldbeupdated accordingtothefollowingformula:

Tij(t+1)=pTij(t)+??呓

    =1

    wherePistheevaporationcoefficient;1-Prepresents theevaporationofthetrailinformationbetweentand 1;?呜isthequantityperunitofthetrailsubstance lengthlaidonedge(i,J)bythekthantbetweentimet andt+l,whichisgivenby

    ge(i,J)(3)

    whereQisaconstant,andIkisthetourlengthofthe kthant.

    2Designofmulti-groupACalgorithm

    basedonthesimulatedannealing

    mechanism

    2.1Multi-groupsoftheAC

    IntheACalgorithm,theprobabilityofAkmoving fromtownitotownJisdeterminedbytheintensityof thetrailinformationonedge(i,J)andthelengthofthe pathbetweentownsiandJ.Thealgorithmbecomes atraditionalgreedyalgorithmwhilea=0.andacom- pletedheuristicalgorithmwithpositivefeedbackwhile fl=0.Withdifierentcoemcientsofand.theantwill showdifierentsearchtendencies.Inpreviousstudies, theantsinthecolonyalwayshavethesamecoemcients andwhichhavebeenobtainedthroughexperiments. Inthispaper,theantsintheACaredividedintosev- eralsubgroups.Theantsinthesamesubgrouphave

    thesametrailinformationandexpectationcoecients.

    whiletheantsindifierentsubgroupshavedifierenttrail informationandexpectationcoemcients.Thiswillmake theantsshowdifierentsearchtrends.Thecoefficients

forantsintheithsubgroupare(oli,fli).

    2.2Introduceofsimulatedannealing

    method

    Whenalltheantshavefinishedtheirtours,updat

    ingthetrailinformationisalsoanimportantaspectfor thealgorithm.Inthispaper,thesimulatedannealing methodisusedtodecidewhichsolutionsobtainedby theantsshouldbeusedtoupdatethetailinformation. 2.2.1Simulatedannealingalgorithm

    Thesimulatedannealingalgorithmwasfirstintro- ducedbyKirkpatrickl10J.Thealgorithmisbasedonthe comparabilityoftheannealingprocessforthesolidand thesolvingprocessfortheoptimizationproblem.By settingthetemperatureT,thesolutionandthetar

    getfunctionoftheoptimizationproblemfforminimum problem)correspondtoonemicrocosmicstateanden

    ergyofthesolidannea1.Letthetemperatureslowly declinefromanadequatelyhighvalue.Undereachtem

    perature,thealgorithmiteratesforagivennumberof times.Ineachiteration,anewsolution:1isachieved byrandomlydistributingthecurrentsolutionx.A,is theincrementoftheobjectfunction.If?f<0,:+

    wouldbeacceptedasthecurrentsolution.0therwise, :1wouldbeacceptedasthecurrentsolutionwiththe possibilityofexp(T1.Thesimulatedannealingal-

    gorithmacceptsnotonlytheoptima1solutionbutalso thenonoptimalsolutionwithaprobability.Itwilleffi

    cientlyavoiddroppingintotheloca1optimum. 2.2.2Introducingsimulatedannealingmethod TointroducesimulatedannealingmethodtotheAC

    algorithm,thetemperatureTwhichchangeswiththe iterationsshouldbesetinthealgorithm. Whenallantshavefinishedtheirtours,thesolution set{A(8k,Ik)l1?尼?m)gotbytheantsistakenas

    thecandidateset,where%(s,lk)thesolutiongotby thekthant,stherouteoftour,andfthelengthof therotate.

    ThebestsolutioninthecandidatesetisA10calJIlin (81ocalmin,/localmin),calledthecurrentroundbest solution.Thebestsolutiongotbythealgorithmis d,ee

    s

    

    Q

    ,??-(1

    =

    

    ?

    466JShanghaiUniv(EnglEd),2010,14(6):464-468 min(smin,Imin),calledasthecurrentbestsolution. Theupdateset{(8Ck,ICk)ll?k?m)isusedto

    updatethetailinformation.Ck(8Ok,fCk)isonesolution inthecandidateset.

    Eachsolutioninthecandidatesetshouldbede

    terminedwiththepossibilitytoointheupdateset. %(s,)isonesolutioninthecandidateset

    Al=fllocalmin

    p='

    Ifp=l,thenAk(sk,Ik)willbeaddedtotheupdatesetto besolutionCk(8Ck,Ick).Otherwise,arandomnumber

?between(0,1)shouldbegenerated

    IP>?,addAktotheupdateset,

    lP??,addA1..litotheupdateset(6)

    ThealgorithmacceptsA%(s,lk)addingtotheupdate setwithapossibilitydeterminedbythecurrenttemper

    ature.Ifthealgorithmdoesnotacceptthe(s,f) addingtotheupdateset,thecurrentroundbestso

    lutionA1ocalmin(sl0caI_TIlin,/loca1min)wouldbeaddedto theupdateset.

    2.2.3Updatingthetrailinformation

    Theupdatesetisusedtoupdatethetrailinforma- tion.Theintensityofthetrailinformationontheedges shouldbebiggerthanmin.Theupdatingformulais

    (+1)=J()+??呜+qAT~7'n,

    JTij(t+1)=((+1),(t+1)>in,

    【死J(t+1)=mi,(t+1)?Tmi.

    ?呜isthequantityperunitofthetrailsubstancelength laidonedge(/,J)byCkintheupdatesetbetweentime tandt+1.Itisgivenby

    /local_min

    

    Ck

    

    usesed

    ,

    g

    whereQisaconstant.isthestrengthenterm carriedoutbythecurrentbestsolutionantnlinsmin, f),whereqisthestrengthencoefficientand?四

    isgivenby

?=

    Q,Aiusesedge(/,

    otherwise

    2.2.4Numberofants

    Inthispaper,theantsaredividedintoseveralsub- groups.FortheTSP,thetotalnumberoftownsisn. Thesubgroupnumberissettobee.Thetotalnumber oftheantsism.whichisdeterminedby

    e?72,

    g(1e)<凡一g,

    9e?100,

    g(1e)<100g,

    wheregisthenumberoftheantsinonesubgroup.

    2.2.5Initializationandresettingofthetailin. formation

    Inthealgorithm,wedonotconsidertheenhance

    mentofthetrailinformationbythebestcurrentsolu

    tion.IfallantsfoCUSonthesameroute,theintensity ofthetrailinformationwouldtendtobe.Inthe beginningofthealgorithm,theinitializedintensityof thetrailinformationontheroadsshouldbedetermined by

    Qm

    Intheiterativeproces,ifthereareamaxcontinuous timesofiterations,thenthealgorithmobtainsthesame currentroundbestsolutions.Thismeansthatthetrail informationontheroadsisoverconcentrated.andthe algorithmentersthestagnationstage.Resettingshould bemadeforthetrailinformation.Thespecificmethod istoresetallthetrailinf0lrmationtobe7o.

2.2.6'mperaturecontrol

    Thetemperaturetwhichchangeswiththeiterations shouldbesetinthealgorithm.Thetemperaturerange isl,in.

    Inthebeginningofthealgorithm,initialtempera

    tureissettobenax.Thegreedyalgorithmisusedto identifyTmax.Startingfromarandomtown,theobject townis.thenearestlegaltown.fisthelengthofthe routeobatinedbythegreedyalgorithm.bisapositive integermeetingtherequirementof10.<10f?10.,

    andthenax=10..inisthelowesttemperature, whichisasmallnumber.

    Whenoneturnofthetourandthetrailinformation updatinghasbeenfinished,thetemperatureshouldbe declined.Thetemperaturedecliningfunctionis T(t+1)=T(t)a,(13)

    whereaisthetemperaturedeclinecoefficient,ae(0,1). IfT(t)<?]min,thenthealgorithmisover,andthebest solutionshouldbeexported.

    ,??1?L,??,1?

    00

    0O

    ,

    11

    

    :n

    m

    ??

    n

    0

Report this document

For any questions or suggestions please email
cust-service@docsford.com