DOC

Ant colony algorithm based on genetic method for continuous optimization problem

By Anne Owens,2014-02-17 20:28
12 views 0
Ant colony algorithm based on genetic method for continuous optimization problem

    Ant colony algorithm based on genetic

    method for continuous optimization

    problem

    JournalD,ShanghaiUniversity(EnglishEdition),2007,11(6):597602

    DigitalObjectIdentifier(DOI):10.1007/s11741007-0614-1

    An?colonyalgorithmbasedon

    optimizationproblem

    geneticmethodforcontinuous

    ZHUJingwei(朱经纬),MENGPeisheng(蒙陪生),WANGCheng(王乘)

    DepartmentofMechanics,HuazhongUniversityofScienceandTechnology,Wuhan430074,P.R.China

    AbstractAnewalgorithmispresentedbyusingtheantcolonyalgorithmbasedongeneticmethod(ACG)tosolvethe

    continuousoptimizationproblem.Eachcomponenthasaseedset.Theseedinthesethasthevalueofcomponent,trall

    informationandfitness.Theantchoosesaseedfromtheseedsetwiththepossibilitydeterminedbytrailinformationand

    fitnessoftheseed.Thegeneticmethodisusedtoformnewsolutionsfromthesolutionsgotbytheants.Bestsolutionsare

    selectedtoupd~etheseedsinthesetsandtrai1informationoftheseeds.Inupdatingthetrailinformation,adiffusionfunction

    isusedtoachievethediffusenessoftrai1information.Thenewalgorithmistestedwith8difierentbenchmarkfunctions.

    Keywordsantcolonyalgorithm,geneticmethod,diffusionfunction,continuousoptimizationproblem

    1Introduction

    AntcolonyfAC1algorithmwasfirstintroducedby Dortgo.eta1.l,2JItisaheuristicalgorithminspiredby forgingbehavioroftheantcolony.Sinceitspublication, theACalgorithmhasbeencontinuouslyimproved,and widelyappliedtotheNPcompletehardproblems[3,4.. CombinationoftheACalgorithmwithotherheuristic algorithmisalsoachieved[bJ.

    Inrecentyears,theantcolonyalgorithmhasbeen appliedtosolvecontinuousoptimizationproblems.In f71,the'trailremaining'processintraditionalASisex- pandedinto'traildistributionfunction'incontinuous space.Inf81,anantmovingdirectionisdetermined duringglobalsearchingbyusingpheromoneandheuris

    ticfunction.Adeterministicsearchingalgorithmisem

    beddedtoimprovetheoptimizationperformanceand enhancethefastconvergenceduringlocalsearch.InJ9l, thespaceofthecomponentisseparatedtosmallparts andeachhasthecandidatevaluesfortheantstosearch. Inthispaper,wepresentanewalgorithmusingthe antcolonyalgorithmbasedongeneticmethod(ACG1to solvethecontinuousoptimizationproblem.IntheACG algorithm.eachcomponenthasaseedset.Theseedin thesethasthreevalues.Theyarethevalueofthecom- ponent.trailinformationandfitness.Ineachiteration theantchoosesoneseedfromeachseedsetwithpossi

    bilitydeterminedbytrailinformationandfitnessofthe seed.Ageneticmethodisusedtoformnewsolutions fromthesolutionsobtainedbytheants.Somebestso 1utionsareselectedtoupdatetheseedsinthesetsand

trailinformationoftheseeds.Inupdatingtrailinfor

    mation.thediffusionfunctionisusedtoachievedifluse- nessofthepheromone.Itwillenhancetheinformation exchangeamongtheants.Finally,thenewalgorithm istestedwith8differentbenchmarkfunctions,showing thatthenewalgorithmissuitableforsolvingcontinuous optimizationproblems.

    2Roadandseedsetsinthecontinuous

    optimizationproblem

    Thecontinuousoptimizationproblemtobesolvedin thispaperis

    (1)

    Letf(x)befitnessofthesolution,f(X)>0.Ifthere aretwosolutionsX1andX2,F(X1)<F(X2),fitnessof thetwosolutionssatisfies,(1)>f(X2).Thewayof settingfitnessofthesolutionshoulddependontheform ofthefunction.

    Fig.1showsnlines.eachrepresentsonecomponent ofthesolution.Denotetheithlineas,min?

    ft?xim.Eachlinehasaseedset,withtheseed

    setoflibeingseed_set.Thenumberofseedsinone seedsetisseed_nub.Thejthseedinseedsetis seed~(,,()),whereisthecomponentvalue,

    thefitnessoftheseedand(t)thetrailinformationof theseed.First,seed-hubsolutionsarecreatedrandomly ReceivedJu1.10,2006;RevisedJan.5,2007

    ProjectsupportedbytheNationalHigh-TechnologyResearchandDevelopmentProgramof

    China(GrantNo.863

    2005AA642010)'

    CorrespondingauthorZHUJing-wei,PhDCandidate,Email:zhujingwei@163.com 宅苫

    m

    Z

    ?

    ?

    m

    n

    .

    ,

    2

    n

    m

598JournalofShanghaiUniversity

    inthesolutionspace.Eachcomponentofthesolution formsoneseedintheseedset.Forexampleisone solutionwithfitnessfjandxistheithcomponent ofthesolutionwhichformsoneseedinseedset.The

    seedisseed:(x;,,(0)),wherex=xj=,

    (0)=To,andToisaconstant.

    ??

    Fig.1Roadfortheartificialants

    3Actionoftheartificialant

    Letthetotalnumberofartificialantsbem.each beingasimpleagentwiththefollowingcharacteristics. Tocompleteitstour.theantbeginsitstourfromthe firstline.Itwillselectoneseedfromeachseedsetwith probabilitydeterminedbytrailinformationandfitness oftheseed.Whentheantreachesthefinalline,itCOID_-

    pletesitstour.Forthekthant,definetheprobability ofselectingthejthseedintheithseedsetas p?:

    ?(((t))())

    q1

    whereoListheparametercontrollingtherelativeimpor

    tanceoftrailinformationinthedecisionmakingpro

    cess.andtheparametercontrollingtherelativeim- portanceofdesirability.Thealgorithmbecomesatra

    ditionalgreedyalgorithmwhileoL:0,andacomplete heuristicalgorithmwithpositivefeedbackwhile:0.

    Ifthekthantselectsthejthseedintheithseedcol

    lection.thevalueoftheithcomponentofthesolutionis =

    ;.Whenthekthantfinishesltstour,itwillget, asolutionXk.Thesolution'sfitnessisfk.Whenallm antsfinishtheirtoursthecolonywillgetmsolutions. 4Geneticoperationsofcrossoverand

    mutation

    Inordertoenhancediversityofthecomponentval

    ues.weupdatetheselectedmsolutionsusingthege

    neticoperationsofcrossoverandnmtation.LetPmbe themutationprobability,andPcbethecrossoverprob

    ability.ProbabilityofXitobeselectedtooperationis determinedbyitsfitness,asgivenby

    |t

    ?

    J=1

    Inthemutation,supposeX1isselectedand transformedintoXi,Xicanbeobtainedfrom

x=xi+ail,

    (3)

    willbe

    whereaiisarandomnumberbetween(0,1),and1isthe footstep,whichisaconstant.

    Inthecrossoveroperation,supposeX1andX2are selectedandwillbetransformedintoXiand, andcanbeobtainedby

    .

    {=axl,+(1a)x2,

    .

    t=bx2,+(1b)xl,{,

    (5)

    whereaandbarerandomnumbersbetween(0,1),which meeta+b=1.

    Byusinggeneticoperationsofcrossoverandmuta- tion.thealgorithmwillgetmnewsolutions. 5Updateseedsetandtrailinformation

    oftheseed

    whenthegeneticoperationshavebeenfinished thereare2msolutionsconsistingofmformersolutions andmnewsolutions.Thenfromthese2msolutions,m solutionswiththehighestfitnessshouldbeselectedto updatetheseedsintheseedsetsandtrailinformationof theseeds.themselectedsolutionsareX…二n.

    Theselectedmsolutionsareusedtoupdatetheseeds intheseedsets.Inseed_seti.mseedswiththelowest fitnessshouldbedeletedfirst.Thenmnewseedsare addedtotheseedcollection.Thekthsolutionusedto updateseedsintheseedsetis.Itsfitnessis/k.The

    ithcomponentof:isXk,i,whichwillformanewseed seed(xk.i,fk,0)addedtoseed_seti.rnailinformation oftheseedisfirstsetto0.Theactualvalueoftrail informationwillbecalculatedinthetrailinformation updatingprocess.

    Theselectedmsolutionsareusedtoupdatethetrail informationoftheseeds.Inthenature,whenanant passessomewhereitdepositsthepheromoneonthe road.Thepheromonewillpervadeinthenearbyarea, whichwillaffectnotonlyasinglepointorasingleline butalsoanarea.Inthecontinuousoptimizationprob- lem.thetrailinformationdepositmodeoftheantcolony ineachoptimizationiterationshouldnotcorrespondto discretepointsordiscretecomponents.Thetrailin

    formationdepositedbytheantshouldalsoaffectthe ambientfieldoftheroad.Weusethediflusionfunction toachievethediffusenessofthetrailinformation. Wesetthemaximumtrailinformationoftheseedto beTinax,andtheminimumtrailinformationoftheseed

Vo1.11No.6Dec.2007ZHUJW,eta1.:Antcolonyalgorithmbasedongeneticmethodfor599

    tobeTmin.Theintensity

    updatedaccordingtothe

    oftrailinformationshouldbe

    updatingformula:

    (+1):p(t)+?霄,

    ifTmi?p(t)+??Till

    (t+1)=Till,

    ifp()+?>m

(+1)=mi,

    ifp(t)+?<Tmi

    (6)

    whereP?(0,1),and1Prepresentstheevaporationof betweentandt+1.?istheincrementof(t):

    ?霄=??

    =1

    Here,?isthetrailinformationaddedbytothe seedbetweentandt+1,and,

    theithcomponentof

    .

    Let

    -{?(8)

    whereQisaconstant,fkthefitnessof,fmthe maximumfitnessalreadyobtained,andoLtheparame

    terdeterminedbythediffusenessfunction: oL

    (),//2兀唧

    (())

    whereo(t)isthediffusenesscoefficient.Inthebeginning

    o(0)=cr0,anditchangeswithiteration: o(t+1)=ao(t),ifo(t)>o-i

    whereisaconstant.0<<1

    (10)

    6FrameworkoftheACGalgorithm

    TheframeworkoftheACGalgorithmisdescribedas thefollows:

    Step1Initializeparametersseed_nub,m,oL,,Q, min,ax,TO,Pm,Pc,f,min,gr0,and. Step2Generatetheseedsetforeachcomponent

    fromthesolutionswhichhavebeencreatedinrandom, t=0.

    Step3Eachantinthecolonyfinishesitstourand getsasolution.

    Step4Usethegeneticoperationstoformnewso

    lutionsfromthesolutionsgotbytheantcolony. Step5Usethebestsolutionstoupdateseedsets andtailinformationoftheseeds.

    Step6Ift=m,terminatethealgorithm,oth

    erwiselett=t+1andgotoStep3.

    7Experimentalresults

    AsshowninTable1,8benchmarkfunctionsareused totestthealgorithm.Thesefunctionsarealsousedfor testingthefastevolutionaryprogramming(FEP)algo

    rithminI10.F1throughF4areunimodalfunctions, througharemultimodalfunctions.,vesetfitnessof F6to,6()=20000F6().Fortheotherfunctions, thefitnessisf(X)=1/(1+F()).Foreachfunction, letXmaxbethemaximumvaluethatthecomponentcan take.Letxminbetheminimumvaluethatthecompo

    nentcantake

    Wesetseedmub=200,m----100,a=l,:1,Q=10, Tmin=10,Tmax:100,TO=Tmin,Pm=0.3,

    P=0.7,f=1,Cr0=i)/1000,o-i:

    (xxi)/10000,and=0.995.

    ,IIable1Benchmarkfunctions

600JournalofShanghaiUniversity

    TheRosenbrockfunction(X)iSselectedasan exampleoftheunimodalfunction.TheRosenbrock

    function'SglobalminimumsolutioniS(1,1,,1),the globalminimumvalueis0.Settmaxto20000.

    Fig.2showsthedistributionoftrailinformation

    7_f1.X)indifierentiterations,theordinateiSi.Thevalue

    oficanonlychangediscretely,1?i?30.Theab

    scissaiSX,whichiScontinuous,0.6??1.4.FOr seed~(k,,(10)),ApointexistsinFig.2(a)showing

    fli{l"I?}{

    t

    Il-_IIIIllI--t

    .|l1l

    I

    

    0.6O.2O.20.61.01.4

    TmiIinformation

    (a)t=l0

    TraiIinformation

    (b)t=100

    TraiIinformation

    (c)t=5000

    10o

    75

    50

    25

    O

    1oo

    75

    50

    O

    1OO

Report this document

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