A cellular genetic algorithm with self-adjusting acceptance thereshold

We present a genetic algorithm (GA) whose population possesses a spatial structure. The GA is formulated as a probabilistic cellular automaton: The individuals are distributed over a connected graph and the genetic operators are applied locally in some nei

ACellularGeneticAlgorithmwithSelf–Adjusting

AcceptanceThreshold

G¨unterRudolph

InformatikCentrumDortmunde.VJoseph-von-Fraunhofer-Str.20

D–44227Dortmund

Rudolph@http://www.mianfeiwendang.comrmatik.Uni-Dortmund.de

Abstract

Wepresentageneticalgorithm(GA)whosepop-ulationpossessesaspatialstructure.TheGAisformulatedasaprobabilisticcellularauto-maton:Theindividualsaredistributedoveraconnectedgraphandthegeneticoperatorsareappliedlocallyinsomeneighborhoodofeachindividual.Byaddingaself–organizingaccept-ancethresholdscheduletotheproportionatere-productionoperatorwecanprovethattheal-gorithmconvergestotheglobaloptimum.Firstresultsforamultipleknapsackproblemindicateasigni cantimprovementinconvergencebeha-vior.Thealgorithmcanbemappedeasilyontoparallelcomputers.

1Introduction

Evolutionaryalgorithms(EAs)formaclassofstochasticoptimizationalgorithmsinwhichprinciplesoforganicevolutionareregardedasrulesforoptimization.Theyareoftenappliedtoparameteroptimizationproblems[1]whenspe-cializedtechniquesarenotavailableorstand-ardmethodsfailtogivesatisfactoryanswersduetomultimodality,nondifferentiabilityordis-continuitiesoftheproblemunderconsideration.HerewefocusonpseudobooleanoptimizationandaspecialclassofEAs,namelygenetical-gorithms(GAs)[6].SinceGAsusebitstringstoencodeelementsofthesearchspace,theyarenaturalcandidatesforpseudobooleanoptimiza-tion.

IntraditionalrealizationsofGAsthepopula-1

JoachimSpraveUniversit¨atDortmundFachbereichInformatikXID–44221Dortmund

Sprave@http://www.mianfeiwendang.comrmatik.Uni-Dortmund.de

tionofindividualsisjustamultisetoffeasibletrialpointsinthesearchspace.Theexchangeofinformationbetweentwoindividualsbyim-itatingtheprincipleofinheritancemayoccureverywherewithinthepopulation,i.e.,thepop-ulationdoesnotpossessaspatialstructure.Recentexperiences,however,revealthatGAswithaspatialpopulationstructurearenotonlyeasilytomapontomassivelyparallelcomputersbutalsoofferabettersolutionqualitythantra-ditionalGAs[11,5,17,12,16].Recently,thisapproachwasalsousedforcontinuoussearchspacesintheframeworkofevolutionstrategies[13,14,18]aswellasforhybridparallelversionsofevolutionaryalgorithmsandsimulatedan-nealing[10,14].Itwasrecognizedseveraltimesthatthese ne–grainedparallelalgorithmsmayberegardedascellularautomata[17,19,21].ToprovideatheoreticalframeworktostudythedifferencesweformallypresentaGAasaprob-abilisticcellularautomaton,inwhichallgeneticoperatorsareappliedlocallyinacertainneigh-borhood.Thisrequiresamodi cationoftheproportionatereproductionorselectionmech-anismoftraditionalGAs.

Sinceproportionatereproductionpreventsglobalconvergence[15]weaddedaself–adjustingacceptancethresholdwhichisrelatedtotheGreatDelugealgorithmpresentedin[3].Thisrisingthresholdensuresthatthealgorithmconvergestotheglobaloptimumin niteexpec-tedtimeregardlessoftheobjectivefunctionandtheinitializationofthealgorithm.

Theremainderofthepaperisorganizedasfollows:Section2presentsadescriptionofthe

Word文档免费下载Word文档免费下载:A cellular genetic algorithm with self-adjusting acceptance thereshold (共8页,当前第1页)

A cellular genetic algorithm with self adjusting acceptance thereshold相关文档

最新文档

返回顶部