1.3 Theoretical Foundations and Practical Design of EAs............. 5

HybridEvolutionaryAlgorithmsforCombinatorialOptimization

eingereichtander

TechnischenUniversit¨atWien

Fakult¨atf¨urTechnischeNaturwissenschaftenundInformatik

von

Dipl.-Ing.Dr.techn.G¨untherRaidl

Breiteneckergasse28/2,1230Wien

Wien,imNovember2002....................

Contents

1Introduction1.11.21.31.41.51.6

CombinatorialOptimizationandSolutionTechniques.............EvolutionaryAlgorithms.............................TheoreticalFoundationsandPracticalDesignofEAs.............Hybridization...................................SelectedArticles.................................Acknowledgements................................

11356611

2TheMultipleContainerPackingProblem:AGeneticAlgorithmAp-proachwithWeightedCodings173TheEffectsofLocalityontheDynamicsofDecoder-BasedEvolutionarySearch374Edge-Sets:AnEffectiveEvolutionaryCodingofSpanningTrees5OnWeight-BiasedMutationforGraphProblems

5183

6AMemeticAlgorithmforMinimum-CostVertex-BiconnectivityAug-mentationofGraphs95

i

ii

Chapter1

Introduction

ThiscumulativehabilitationthesisgivesashortintroductiontotheareaofmyresearchinthelastyearsasamemberoftheAlgorithmsandDataStructuresGroupattheInstituteofComputerGraphicsandAlgorithms,ViennaUniversityofTechnology.Themainpartconsistsoffivepublishedorforpublicationacceptedarticles.Theywereselectedassamplestorepresentdifferentbutrelatedresearchtopicsofmyself.Mycontributiontoeachofthesearticlesandthescientificworkbehindissubstantial(≥50%).Asthisthesisprovidesonlyaroughoverviewandfiveexemplaryarticles,Irefertomypublicationlist,whichisavailableathttp://www.ads.tuwien.ac.at/raidl,andmycurriculumvitaeforfurtherinformationaboutmywork.

1.1CombinatorialOptimizationandSolutionTechniques

Manyproblemswithimportantpracticalapplicationsareconcernedwiththeselectionofa“best”configurationorsetofparameterstoachievesomeobjectivecriteria.Suchproblemsaregenerallyreferredtoasoptimizationproblems.Iftheentitiestobeoptimizedarediscrete,thenumberoffeasiblesolutionsisfinite.Wecallsuchproblemscombinatorialoptimizationproblems.

Acombinatorialoptimizationproblemisspecifiedmoreformallybyasetofproblemin-stancesandiseitheraminimizationproblemoramaximizationproblem.Aninstanceofacombinatorialminimizationproblemisapair(X,f),wherethesolutionsetXisthesetofallfeasiblesolutionsandthecostfunctionfisamappingf:X→R(AartsandLenstra,1997).Theproblemistofindagloballyoptimalsolution,i.e.,anx∗∈Xsuchthatf(x∗)≤f(x)forallx∈X.Maximizationproblemscanbetriviallytransformedintominimizationproblemsbychangingthesignofthecostfunctionf.

Weconsiderprimarilycombinatorialoptimizationproblemsthataredifficulttosolveinpractice.Prominentexamplesarethetravelingsalespersonproblemandrelatedroutingandtransportationproblems,cuttingandpackingtasks,scheduling,andtime-tabling.MostoftheseproblemsareNP-hard.However,NP-hardnessandpracticaldifficultydonotalwaysmeanthesame:Sometimes,allpracticallyrelevantinstancesofanNP-hardproblemmightbesolvableinacceptabletime.Conversely,analgorithmforapolynomial-timesolvableproblemmightbetooexpensiveinpractice.

Awiderangeofdifferentalgorithmicstrategiesexiststodealwithsuchproblems.Wecanroughlyclassifytheseapproachesasfollows.

1

Exacttechniques:Thesemethodsareusuallybasedonsomeenumerationschemelike

branch-and-boundordynamicprogrammingandyieldprovablyoptimalsolutions.Inparticulartechniquesutilizinglinearprogrammingworkremarkablywellinmanycases.Nevertheless,theapplicabilityofexactmethodsisoftenrestrictedtosmallinstancesduetotheproblem’scomplexity.Approximationalgorithms:If,forsomereason,exactalgorithmsarenotapplicableto

aproblem,approximationalgorithmsmaybeconsidered.Thesealgorithmsingeneraldonotyieldoptimalsolutions,butsolutionswithinaguaranteedrelativeerrorboundtotheoptimum.Heuristics:Formanypracticalapplications,alsoapproximationalgorithmsarenosuitable

choice.Theirqualityguaranteesmaybetooweakandtheiractualsolutionstoopoor,ortheymaybecomputationallytooexpensive.Inthiscase,heuristicalgorithmsmaybeapplied.Theyusuallydonotgivequalityguaranteesbutmaybehighlyeffectiveinpractice.Besidesproblem-specificheuristics,moregeneralstrategiesapplicabletoabroaderrangeofproblemsexist.Meta-heuristicsaresuchstrategiesthatperformatypicallyincompletesearchinthespaceofsolutionsXbyiterativelycreatingandevaluatingnewcandidatesolutions.Themostprominentandsuccessfulmeta-heuristicsarethefollowingfour.AartsandLenstra(1997)andMichalewiczandFogel(2000)provideamoredetailedintroductiontothisarea.

Standardlocalsearch:Startingfromasolutioncreatedatrandomorbysomeproblem

specificheuristic,standardlocalsearchtriestoimproveonitbyiterativelyderivingasimilarsolutionintheneighborhoodoftheso-farbestsolution.Responsibleforfindinganeighboringsolutionisamove-operator,whichmustbecarefullydefinedaccordingtotheproblem.Themajordisadvantageofstandardlocalsearchisitshighprobabilityofgettingtrappedatapoorlocaloptimum.Asimpleimprovementisiteratedlocalsearch.Itappliesstandardlocalsearchmultipletimesfromdifferentstartingsolutionsandreturnsthebestlocaloptimumidentified.Simulatedannealing:Anotherwayforenablinglocalsearchtoescapefromlocaloptima

andapproachnewareasofattractioninthesearchspaceistosometimesalsoacceptworseneighboringsolutions.Simulatedannealingdoesthisinaprobabilisticway.Atthebeginningoftheoptimization,worsesolutionsareacceptedwitharelativelyhighprobability,andthisprobabilityisreducedovertimeinordertoachieveconvergence.Foramoredetailedintroductiontosimulatedannealing,seeKirkpatricketal.(1983).Tabusearch:Thisstrategyextendslocalsearchbytheintroductionofmemory.Astag-nationatalocaloptimumisavoidedbymaintainingadatastructure,calledhistory,inwhichthelastcreatedsolutionsoralternativelythelastmoves(i.e.,changesfromonecandidatesolutiontothenext)arestored.Thesesolutions,respectivelymoves,areforbidden(tabu)inthenextiteration,andthealgorithmisforcedtoapproachunexploredareasofthesearchspace.Foramoredetailedintroductiontotabusearch,seeGlover(1990).Evolutionaryalgorithms(EAs):Theyareabroaderclassofmeta-heuristicsbasedon

thecommonideaofadoptingprinciplesfromnaturalevolutioninsimplifiedways.

2

GeneticAlgorithmbegint←0;

initialize(P(t));evaluate(P(t));

whileterminationconditionnotfulfilleddot←t+1;

Qs(t)←select(P(t−1));Qr(t)←recombine(Qs(t));P(t)←mutate(Qr(t));evaluate(P(t));doneend

Algorithm1:PrincipleofaclassicalgeneticalgorithmaccordingtoGoldberg(19).Theseprinciplesareprimarilynaturalselection(survivalofthefittest)andrepro-ductionwithinheritanceandmutation.Classicalevolutionaryalgorithmsaregeneticalgorithms(Holland,1975,Goldberg,19)andevolutionstrategies(Rechenberg,1973,Schwefel,1981),howeveravarietyofotheralgorithmsandhybridsystemshasemergedoverthelastdecades.Geneticprogramming,particleswarmsystems,scattersearch,differentialevolution,andestimationofdistributionalgorithms,suchasantcolonyoptimization,areexamplesofmorerecenttrends(Corneetal.,1999).Onecommoncharacteristicofmost—butnotall—evolutionaryalgorithms,whichdistin-guishestheminparticularfromstandardlocalsearch,simulatedannealing,andtabusearch,istheirpopulation-basedapproach.Theyworkonasetofconcurrentcandi-datesolutions,calledpopulation,insteadofmaintainingonlyasinglecurrentsolution.Evolutionaryalgorithmsarenotjustusedasoptimizationtools,butarealsoappliedindomainslikeartificiallifeandthesimulationofnaturalevolutionarybehaviorsandphenomena.Here,however,weconsideronlytheoptimizationaspect.

1.2EvolutionaryAlgorithms

Thissectiongivesabriefoverviewontheprincipleofgeneticalgorithmsandissuesarisinginthedevelopmentofconcretealgorithmsforspecificproblems.Foramoredetailedin-troductiontoevolutionarycomputationingeneral,seeB¨acketal.(2000)andMichalewicz(1996)or,foracomprehensivesurvey,B¨acketal.(1997).Algorithm1showsaclassicalgeneticalgorithm(GA)accordingtoGoldberg(19).AninitialpopulationP(0)ofdiversesolutionsiscreatedeitherrandomlyorbyproblem-specificheuristics.Intheevaluationstep,eachsolutionx∈P(0)getsassignedafitnessvalue,whichiscalculatedfromthecostsf(x)byappropriatescaling.Inthemainloop,anewpopulationP(t)isderivedfromthe“parental”populationP(t−1)bymeansofselection,recombination,andmutation.TheaimofselectionistochoosesolutionsfromP(t−1)foractingasparentsinthefollowingreproduction.Fittersolutionsareingeneralselectedmoreoften,althoughsolutionshavingsmallfitnessarealsooccasionallychosen.Recombinationcreatesnewsolutionsbycrossingoverthepropertiesoftwoormoreselectedparents.Finally,mutationmakesatypicallysmallrandomchangeinsomesolutions;itcanbecomparedtothemove-3

operatoroflocalsearch,simulatedannealing,andtabu-search.Thenewpopulationisevaluatedandreplacestheformerone.Thisprocessisiterateduntilagiventerminationconditionisfulfilled(e.g.,apermittedcomputationtimeisexhaustedortheGAhasnotimprovedonthebestsolutionforacertainnumberofiterations).

Evolutionaryalgorithmsaretypicallystochasticprocesses:Duringthecreationofinitialsolutions,selection,recombination,andmutation,randomdecisionsareusuallymade.Fur-thermore,recombinationandmutationareoftennotalwaysappliedbutonlywithcertainprobabilities.

Inordertoefficientlyapplyanevolutionaryalgorithmtoaspecificproblem,severalissuesmustbecarefullyconsidered.Somemostimportantare:

Representation:Howshouldacandidatesolutiontotheproblemberepresented?What

kindofdatastructureshouldbeused?Initialization:Howshouldinitialsolutionsbecreated?Purelyrandomlyorbysome

problem-specificheuristics?Inthelattercaseitmustbeensuredthattheinitialpopulationprovidesenoughdiversity,i.e.,thesolutionsmaynotbetoosimilar.Evaluation:Howshouldacandidatesolutionbeevaluated?Whilefortraditional“aca-demic”combinatorialoptimizationproblems,theobjectivefunctionisusuallygivenorstraight-forward,thisisoftennotthecaseinpractice.Sometimes,theevaluationofasolutioniseventhemostexpensivestep,andapproximationsofdifferentcomplexityandaccuracymustbeconsidered.Variationoperators:Whatshouldthevariationoperators,i.e.,recombinationandmuta-tion,looklike?Recombinationshouldderivemeaningfulnewsolutionswithpropertiesinheritedfromtheparents.Whatkindofneighborhood-structureshouldberealizedbymutation?Typically,mutationshouldmakeonlyasmallchangewhichshouldusuallyalsocorrespondtoasmallchangeinthesolution’sfitness.Thecomputa-tionalcomplexityofthevariationoperatorsisafurtherimportantissue,sincetheyareappliedmanytimes.Constraints:Combinatorialoptimizationproblemsareoftenconstrainedinsomeway.

Thus,notallpotentialsolutionsarefeasible.Techniquestoconsidersuchconstraintsinevolutionaryalgorithmsare:(a)todiscardinfeasiblesolutions;(b)toaddappropri-atepenaltiestothefitnessofinfeasiblesolutions;(c)totransforminfeasiblesolutionsintofeasibleonesbyrepair-algorithms;(d)touseanindirectrepresentationandadecoderthatmapsanypossibleencodedsolution,calledgenotype,toafeasiblerealsolution,thephenotype;or(e)tousespecializedvariationoperatorscreatingonlyfeasiblesolutions.Generalcharacteristicsandparameters:Differentmethodsofperformingselection

areknown;whichoneshouldbeused?Howlargeshouldthepopulationbe?Withwhichprobabilitiesshouldthevariationoperatorsbeapplied?Therearemanyques-tionslikethosetowhichtherearenosimpleanswers.Thegeneralinterestinevolutionaryalgorithmsandtheirsuccessisdemonstratedbymanyreal-worldapplicationsandbythelargenumberofpublications,conferences,andworkshopsinthisarea.RecenttrendspointouttheparticularusefulnessofEAsinthefollowingcasesbesidesclassicalcombinatorialoptimizationtasks.

4

Highlynon-linearornoisyobjectivefunctions:Problemswithlinearobjectivefunc-tionscanoftenbeeffectivelysolvedbyutilizinglinearprogrammingtechniques.Iftheobjectivefunctionismorecomplex,suchtechniquesareusuallynotapplicableany-more.Evolutionaryalgorithmsintheiroriginalformsneedonlytoevaluatecandidatesolutionsandarethereforenotrestrictedinsuchaway.Multi-objectiveoptimization:Inreal-worldproblems,thereareoftenmultipleobjec-tivefunctionsinsteadofasinglecostfunctionandtheyconflictwitheachother.Thereisnosinglesolutionthatisbestforalltheobjectives.Inthiscase,oneistypicallyinterestedingettingasetofPareto-optimalsolutions.Eachsuchsolutioncannotbeimprovedwithrespecttooneobjectivewithoutworseningitwithrespecttoanotherobjective.Duetotheirpopulation-basedapproach,EAsareoftenwellsuitedforsuchoptimizationtasks.Time-dependentobjectivefunctions:Problemsinwhichtheobjectivefunctionchan-gesoverthetimeandnear-optimalsolutionmustberepeatedlyfoundarealsoanimportantchallenge.Anexampleistime-tabling:Howshouldapreviouslyoptimaltime-tablebemodifiedifsomeunderlyingconstraintchanges?Anevolutionaryalgo-rithmmaystoremanysuboptimalbutpromisingcandidatesolutionsinitspopulation;afterachangeintheproblem,thesesolutionsmayefficientlyleadtoanewoptimalsolution.

1.3TheoreticalFoundationsandPracticalDesignofEAs

Muchworkhasbeendoneandisstillgoingonintheoreticalfoundationsofevolutionaryalgorithms.Unfortunately,themanyrandomdecisionsinEAscomplicatetheorymuch.TheschematheoremfromGoldberg(19)isoneoriginalattempttoexplainhowsimplegeneticalgorithmswork.Ithasbeencriticizedbecauseitisbasedonaweakinequalityandisnorealmathematicalproof.Nevertheless,thistheoremandinparticularseveralimprovedvariantsfromotherresearchersaretodaywidelyacceptedassomeaidinunderstandinganddesigninggeneticalgorithms.MoreexactmodelsarebasedonavarietyofmathematicaltechniquessuchasMarkovchainsandWalshtransforms(Vose,1999).AgoodsourcefortheoreticalinvestigationsarealsotheproceedingsoftheConferencesonFoundationsofGeneticAlgorithms(MartinandSpears,2001).

Thiskindoftheoreticalworkisimportant,sinceitprovidesuswithunderstandingandsomeguidelinesforthedesignofmoreeffectiveevolutionaryalgorithms.However,wearetodaystillfarawayfrombeingabletomakecompletetheoreticalanalysesofstate-of-the-artEAsforhardproblems.Onlysimplisticevolutionaryalgorithmsforeasyproblemscancurrentlybefullyunderstood.Togiveoneexample:Scharnowetal.(2002)analyzedanEAsimilartostandardlocalsearchfortheproblemofsortingnitems.Assuminganappro-priatecostfunctiontoevaluateanypermutationofitemsandasuitablemutationoperator(recombinationhasnotbeenconsidered),theycouldprovetheexpectedoptimizationtimeforfindingasortedsequencetobeboundedabovebyO(n2logn)andboundedbelowbyΩ(n2).Ofcourse,usinganEAforsortinghasnodirectpracticalrelevance,sincemoreefficientalgorithmsareknownforthiseasystandardtask.

Inordertoassesstheperformanceofastate-of-the-artEAforahardproblem,onetypicallyreliesonperformingmanyempiricaltests.Nevertheless,thedevelopmentofanEAneednotnecessarilyfollowthe“try-and-error”principle.Toolsexistthatsupportthedesignprocess

5

bypointingoutcertainpropertiesofthegivenproblem.Theinvestigationofthefitnesslandscapebymeansoffitness-distancecorrelationanalysisisanexample(JonesandForrest,1995).Toacertaindegree,suchastudycanpredictthehardnessoftheproblemwithrespecttoaspecificneighborhoodstructure,andifrecombinationandmutationoperatorswillperformefficiently(MerzandFreisleben,1999).However,insomecasessuchanalysesmayalsobemisleading(Altenberg,1997).

SeveralconditionsareknowntobeofcrucialimportanceineffectiveEAs.Diversityisoneexample:thepopulation’ssolutionsmaynotbetoosimilar.Anotherimportantconditionwithrespecttothevariationoperatorsisstronglocality:Asmallchangeinasolutionasperformedbymutationshouldusuallyalsoresultinasmallchangeofthesolution’scosts.Similarly,recombinationshouldusuallyproduceasolutionhavingcoststhatliesomewherenearorbetweentheparentalsolutions’costs.Iflocalityisweak,wemaynotexpecttheEAtobesignificantlymoreefficientthanrandomsearch.SuchconditionsguidethedesignofaneffectiveEA.

1.4Hybridization

Formanycombinatorialoptimizationproblems,asimpleEAcanbedevelopedwithinashorttime.Whileinsomecasestheobtainedresultsmaybesufficient,wemaynotusuallyexpectsuchasimplealgorithmtoexhibitextraordinaryperformance.State-of-the-artEAsforcomplexcombinatorialproblemsalmostalwaysexploitproblem-specificcharacteristicsinspecialways.Often,othereffectiveheuristicsarecombinedwiththeEAtoamorecomplexhybridsystem.

Someprominenthybridizationstrategiesareasfollows.

•Asalreadymentioned,thesolutionsoftheEA’sinitialpopulationmaybecreatedbyproblem-specificheuristics.

•SomeorallofthesolutionscreatedbytheEAmaybeimprovedbylocalsearch.Thiskindofalgorithmsisoftenreferredtoasmemeticalgorithms(Moscato,1999).•Intelligentdecodersareanotherpossibility.Solutionsarerepresentedinanindirectwayandadecodingalgorithmmapsanygenotypetoacorrespondingphenotypicsolution.Inthismapping,thedecodercanexploitproblem-specificcharacteristicsandapplyheuristics.

•Variationoperatorsmayexploitproblemknowledge.Forexample,inrecombinationmorepromisingpropertiesofoneparentsolutionmaybeinheritedwithhigherprob-abilitiesthanthecorrespondingpropertiesoftheotherparent(s).Alsomutationmaybebiasedtoincludeinsolutionspromisingpropertieswithhigherprobabilitiesthanothers.

1.5SelectedArticles

Thissectionintroducesthefiveselectedarticlesofthefollowingchaptersanddescribestheirrelationships.

6

Paper#1:TheMultipleContainerPackingProblem:AGeneticAlgo-rithmApproachwithWeightedCodings(Raidl,1999a)

AsmentionedinSect.1.4,onepossibilityforcombininganevolutionaryalgorithmwithaproblem-specificheuristicistouseanintelligentdecoder.Weightedcodings(Julstrom,1997)followthisprincipleandcanberelativelyeasilyadaptedtoawiderangeofcombinatorialoptimizationproblems.

Inaweightedcoding,asolutionisrepresentedbyavectorofreal-valuedweights.Todeterminethesolutionencodedinsuchagenotype,theweightsareusedtotemporarilymodify(bias)suitableparametersoftheproblem.Theproblem-specificheuristicisthenappliedtothismodifiedproblem,andtheobtainedsolutionisinterpretedandevaluatedfortheoriginal(unbiased)problem.Therefore,theevolutionaryalgorithmoptimizespa-rametersfortransformingtheprobleminstanceinordertoobtainabettersolutionfromtheproblem-specificheuristic.

Oneadvantageofthisapproachisthedirectapplicabilityofstandardrecombinationandmutationoperatorslikek-pointcrossoverandposition-wisemutation.Furthermore,con-straintsoftheproblemneednottobeconsideredintheevolutionaryalgorithmframework.ThearticleinChapter2investigatesweight-codedEAsforthemultiplecontainerpackingproblem,whichisacombinationofthebetterknownknapsackandbinpackingproblems.Here,nitemsandCcontainersaregiven.Eachitemj=1,...,nhasassignedavaluevjandasizesj;eachcontainerhasmaximumcapacitySmax.ThegoalistoselectCdisjointsubsetsX1,...,Xcontainer,i.e.Coftheitems{1,...,n}suchthateachsubsetfitsintoa󰀂󰀂󰀂C∀i=1,...,C:j∈Xisj≤Smax,andthetotalvalueoftheselecteditemsi=1j∈Xivjismaximum.

Fourgreedyheuristicsfortheproblemaresuggestedasdecoders.Agenotypecontainsoneweightforeachitem.Theseweightsareusedtobiastheitems’sizessjineitherauniformadditiveoralog-normalmultiplicativeway.Thelatterapproachhasbeenorigi-nallyintroducedin(Raidl,1999c)andprovestobesuperiorsincetheevolutionarysearchfocusesmoreonpromisingregionsofthesearchspacelyingneartheunbiasedcase.Fortheinitializationofweights,astrategyparameterγcontrollingtheaveragebiasingstrengthexists.Thechoiceofanappropriatevalueistheoreticallyandempiricallyanalyzed.Inaseriesofexperiments,thedifferentvariantsoftheweight-codedEAarecomparedtoeachotherandtoGAsemployingdirectandorder-basedrepresentations.

Apreviousversionofthisarticle(Raidl,1999b)hasbeenselectedasbestpaperoftheEvo-lutionaryComputationandOptimizationTrackatthe1999ACMSymposiumonAppliedComputing.

Paper#2:TheEffectsofLocalityontheDynamicsofDecoder-BasedEvolutionarySearch(GottliebandRaidl,2000)

Sections1.2and1.3alreadypointedoutthedifficultiesinthedesignofefficientEAs.InGottliebandRaidl(1999),weproposedapracticaltechniqueforstudyingandquantify-inglocalitypropertiesofrecombinationandmutationoperatorswithrespecttotheusedrepresentationswithoutactuallyperformingcompleteEAruns.

InthepaperpresentedinChapter3,weextendthistechniqueandapplyitduringEAruns.Weintroducethenotionsofcrossoverinnovation,crossoverloss,andmutationinnovation.

7

Bymeasuringdescriptivevaluesforthemonline,wegetacloseinsightintotheinterplayofthedifferentcomponents–theEA’sdynamics.Thisenablesustoobserveandexplaineffectssuchasthepost-convergencediversityincrease,andgoodorbadbehaviorsofoperatorscanberecognized.TheproposedmeasurementsalsohelpintuningstrategicparametersoftheEA.Inthispaper,weapplythetechniquetofourdifferentdecoder-basedEAsforthemultidimensionalknapsackproblem.TwoofthemuseweightedcodingsandwereoriginallyproposedinRaidl(1999c).Theothertwoemployapermutationrepresentationandanordinalrepresentation.

Weconsidersuchananalysistobeparticularlyimportantfordecoder-basedEAs,sincetheirdecoderstransformtheproblem’ssearchspace.Variationoperatorsappliedtothegenotypesmaythenhavesometimesunexpectedorunderestimatedeffects.Thetwoweight-codedEAsconsideredinthearticleareshowntoexhibitrelativelystronglocality,whatpartlyexplainstheirhigheffectivity.Ontheotherside,theEAusingtheordinalrepresentationisproventoperformpoormainlyduetoitsweaklocality.

Withrespecttothemultidimensionalknapsackproblem,anotherhybridevolutionaryal-gorithmhasbeenpublishedinRaidl(1998).Itisamoresophisticatedapproachemployingadirectrepresentationandusingspecializedinitializationandvariationoperators.Theseoperatorsexploitfeaturesoftheoptimalsolutiontothelinearprogrammingrelaxationofthemultidimensionalknapsackproblem.

Paper#3:Edge-Sets:AnEffectiveEvolutionaryCodingofSpanningTrees(RaidlandJulstrom,toappear)

Therearemanyproblemsinnetworkdesignandareassuchastransportationplanninginwhichafeasiblesolutionisaspanningtreeofagraph.Whilethewell-knownminimumspanningtreeofaweightedgraphcanbeefficientlydetermined,additionalconstraintsormoredifficultobjectivefunctionsoftenmakesuchproblemshard.

Inthepast,manyresearchershaveaddressedtheseproblemsalsowithevolutionaryalgo-rithms.Severaltechniquesforrepresentingspanningtreesandassociatedrecombinationandmutationoperatorshavebeenproposed.MostprominentwerePr¨ufernumbers,whichweshowedtobehighlyineffectiveduetotheirlackoflocality(Gottliebetal.,2000).Vari-antsofweightedcodingshavebeenappliedwithsomesuccess(PalmerandKershenbaum,1994,RaidlandJulstrom,2000).

InthepaperpresentedinChapter4,weproposetorepresentaspanningtreedirectlybyitssetofedgesinformofahash-table.Thismakesnewvariationandmutationoperatorsnecessary.Wesuggestseveralsuchoperatorsandanalyzetheirpropertiestheoreticallyandempirically.Inparticularweinvestigatetheprobabilitiesforcreatingcertainstructures(starsandlists)andproposeonecrossoverthatreturnseachpossiblespanningtreecon-sistingofinheritededgesonlywithequalprobability.Thesenewvariationoperatorshaveseveraladvantagesoverpreviousrepresentationsandassociatedoperators:

•Theycanconstructnew,promisingcandidatesolutionsinlinearornear-lineartime.Therefore,theseoperatorsscalewelltolargeprobleminstances.•Theyexhibitstrongestpossiblelocality.

•Theycreateonlyfeasiblespanningtreesandarerelativelyflexibleforadaptionstofurtherproblem-specificconstraints.

8

•Theirefficacycanoftenbeimprovedbylocalheuristics,suchasbiasingthechoiceofedgestobeincludedinanewsolutiontowardsedgeswithlowerweights.

Asanexample,theperformanceofthisnewapproachisdemonstratedonthedegree-constrainedminimumspanningtreeproblem.Degreeconstraintsonthenodesareefficientlyconsideredinthevariationoperators.Empiricalresultsindicateaclearsuperiorityofthismethodoverpreviousstate-of-the-artheuristicsforthisproblem,inparticularonlarge,difficultinstances.

Anoriginalversionoftheedge-setrepresentationwithvariationoperatorsforthedegree-constrainedminimumspanningtreeproblemhasbeenpublishedinRaidl(2000).Fur-thermore,weshowedthegeneralapproachtoalsoworkwellonthecapacitatedminimumspanningtreeproblem(RaidlandDrexel,2000)andthebounded-diameterminimumspan-ningtreeproblem(RaidlandJulstrom,toappear2003).

Paper#4:OnWeight-BiasedMutationforGraphProblems(Raidletal.,2002)

ManyproblemsonweightedgraphsG=(V,E)seeksubgraphsGS=(V,S),S⊂E,ofminimumweightsatisfyingproblem-specificconstraints.Thedegree-constrainedminimumspanningtreeproblem(degMST)consideredintheprevioussectionortheclassicaltravelingsalespersonproblem(TSP)areexamples.Itisnotsurprisingthatlow-weightedgesusuallypredominateinoptimalsolutionstosuchproblems.Thisfactisexploitedingreedyheuris-ticsandoftenalsointheoperatorsofevolutionaryalgorithms:Morepromisinglow-weightedgesareusedwithhigherprobabilitiesthanotheredgeswhenderivingnewcandidatesolutions.

Forrecombination,westudiedandempiricallycomparedsuchtechniquesinJulstromandRaidl(2001).InthearticlepresentedinChapter5,weanalyzetheappearanceoflow-weightedgesingloballyoptimalsolutionstoalargenumberofinstancesofthedegMSTproblemandtheTSPinmoredetail.Theoptimalsolutionsweredeterminedbyusingbranch-and-cut.Itturnsoutthattheaverageprobabilityp(r)withwhichanedgeappearsinanoptimalsolutionasafunctionoftheedge’sweight-basedrankr(r=1,...,|E|)canbeapproximatedbytheexponentialfunction

󰀁r󰀃

|S|

pA(r)=

|S|+1withsmallerror.

Inthefollowing,wederiveatheoreticalmodelforoptimalprobabilitieswithwhichedgesshouldbechosenwithrespecttotheirrankforinclusioninnewcandidatesolutionsofanEA.Thederivedprobabilitydistributionminimizestheaverageexpectednumberofedgeselectionsuntileachedgeofanoptimalsolutionischosen.Weshowthisaverageexpectedtimetobelinearinthenumberofverticesincaseofouroptimaledgeselectionprobabilities,whileitisquadraticincaseofauniformdistribution.

ThetheoreticallyderivedoptimaledgeselectionprobabilitiesarethenappliedinmutationoperatorsoftheEAforthedegMSTproblemdescribedinChapter4andasimpleEAfortheTSP.IncaseofthedegMSTproblem,anempiricalcomparisonwithotherbiasedmutationoperatorsconfirmsthebenefitsofthenewtechnique.FortheTSP,theinclusionofonenewedgeinatourrequiresatleasttheinclusionofanotherdependentedgeandtheremovaloftwoexistingedges;theseside-effectsweakentheadvantages.

9

Paper#5:AMemeticAlgorithmforMinimum-CostVertex-Bicon-nectivityAugmentationofGraphs(Ljubi´candRaidl,toappear)

Innetworkdesign,reliabilityandsurvivabilityareoftenimportantissues.Insimplenet-workshavingtreestructure,thefailureofasinglelinkornodemaydisconnectlargeportionsofthewholenetwork.Therefore,existingnetworksoftenneedtobeaugmentedbyacheap-estpossiblesetofadditionallinksinordertoachieverobustnessagainstsinglelinkornodefailures.Ingraphtheory,agraphiscallededge-biconnectedorvertex-biconnected,ifthere-movalofanysingleedge,respectivelyvertex,doesnotdisconnectthegraphintoseparatedcomponents.

Inapreviouswork(RaidlandLjubi´c,2002),wedevelopedanefficienthybridEAforleast-costedge-biconnectivityaugmentationofgraphs.ThepaperpresentedinChapter6extendsthisapproachtothemoredifficultvertex-biconnectivityaugmentationcase.

Thealgorithmstartsbyperformingasophisticatedpreprocessingontheoriginalproblemdata.Biconnectedcomponentsoftheexistingnetworkareshrinkedintosinglemeta-nodes,yieldingablock-cuttree.Possibleaugmentationedgesaresuperimposedonthistree,anddeterministicreductionrulesareapplied:Certainaugmentationedgescannotbecontainedinoptimalsolutionsandarethereforediscarded.Otheredgescansometimesbeshowntonecessarilyappearinanyoptimalsolution;theyareprematurelyfixed.Preprocessingalsocreatessupportingdatastructuresforthemainpartofthealgorithm.Theyenableanefficientdeterminationofthetree-nodescoveredbyeachpossibleaugmentationedgeand,vice-versa,thedeterminationofallaugmentationedgessuitableforcoveringagivennode.TheEAitselfisaso-calledmemeticalgorithm,sinceitappliesalocal-improvementproce-duretoeachcreatedcandidatesolution.Thislocalimprovementinparticularguaranteesanysolutiontobefreeofredundantedgesthatcanberemovedwithoutviolatingfeasibility.Variationoperatorswerespecificallydesignedtoprovidestronglocalityandtobecompu-tationallyefficientintheexpectedcase.Theydirectlyworkonthesetsofaugmentationedges,alwayscreatefeasiblesolutions,andemployfurtherlocalheuristics.

Thememeticalgorithmistestedandcomparedtopreviousheuristicandapproximativealgorithmsonmanydifferentlystructuredprobleminstances.Innearlyallcases,ityieldsthebestsolutions.Resultsalsodocumentthegoodscalabilitytolargeprobleminstances.ApreviousversionofthispaperhasbeenpublishedinKerstingetal.(2002).

10

1.6Acknowledgements

Iwanttothankem.Univ.-Prof.Dr.WilhelmBarth,whohassupervisedmyPh.D.andencouragedmetocontinueasaresearcherandteacheratourUniversity.Inparticularhistrustinmeandthefreedomhegaveme,butalsohismanywiseadvisesattherighttimewerethemostimportantcontributionstomycareer.

IalsothankPetraMutzel,thecurrentheadofourgroup,verymuch.FromherIgotadifferentperspectiveofdoingresearch.Inparticular,sheopenedmymindalsoforexactoptimizationtechniquesutilizinglinearprogramming.Iamalsogratefultoherforherstrongsupportofmyinterestsinresearchandteaching.

Furthermore,IwanttothankJensGottliebfromSAPAG,Walldorf,Germany,forourgoodandsuccessfulcooperation,inparticularwithrespecttoourEvoCOPworkshops.Ihopewewilltogetherorganizemanymoresuchworkshopsinthefuture.

ThanksalsotoBryantJulstromfromtheSt.CloudStateUniversity,St.Cloud,MN,USA.Ienjoytocollaboratewithhiminresearchandlookforwardtomanymorejointprojects.IalsothankallmycurrentandformercolleaguesfromtheAlgorithmsandDataStructuresGroupattheViennaUniversityofTechnology.Wenearlyalwayshadandhavegoodteamworkwithrespecttoourteachingresponsibilitiesandwhendoingjointresearch.Thegeneralatmosphereisexcellentandfruitful.Inparticular,IwanttomentionGabrieleKodydek.Workingtogetherwithherisefficientandmakesalsomuchfun.Sheisprobablytheonepersonwhoknowsmyresearchworkbest:Thankyou,Gabi,forproofreadingsomanyofmypublicationsincludingthisthesis.

Finally,Ithankthemostimportantpeopleinmylife:

Myparentsmadeitpossibleformetostudyandstronglysupportedandstillsupportmeinmanybelongings.Manythanksforallthat.

ToGabi,mywife,Manuela,mydaughter,andTobias,myson:Iapologizeforspendingsomanyeveningsandsometimeseventheweekendsatwork.Thankyouforyourbigunderstandingandgreatsupport.Youarepartofmysuccess.Ithereforewanttodedicatethisthesistoyou.

Thankyou,ManuelaandTobias,youencouragemetodream,andthankstoalltheothers,

whohelpmeinmakingsomedreamscometrue.

11

12

Bibliography

E.AartsandJ.K.Lenstra.LocalSearchinCombinatorialOptimization.JohnWileyandSons,Chichester,U.K.,1997.L.Altenberg.Fitnessdistancecorrelationanalysis:Aninstructivecounterexample.InR.Eberhart,P.Angeline,T.B¨ack,etal.,editors,Proceedingsof1997IEEEInternationalConferenceonEvolutionaryComputation,pages57–.IEEEPress,1997.T.B¨ack,D.B.Fogel,andZ.Michalewicz.HandbookofEvolutionaryComputation.OxfordUniversityPress,NewYork,1997.T.B¨ack,D.B.Fogel,andZ.Michalewicz.EvolutionaryComputation1+2.InstituteofPhysicsPublishing,Bristol,U.K.,2000.

D.Corne,M.Dorigo,andF.Glover.NewIdeasinOptimisation.McGraw-Hill,Berkshire,England,1999.F.Glover.Tabusearch:Atutorial.Interfaces,20:74–94,1990.

D.E.Goldberg.GeneticAlgorithmsinSearch,Optimization,andLearning.Addison-Wesley,Reading,Massachusetts,19.

J.Gottlieb,B.A.Julstrom,G.R.Raidl,andF.Rothlauf.Pr¨ufernumbers:Apoorrepresentationofspanningtreesforevolutionarysearch.InL.Spector,E.Goodman,A.Wu,etal.,editors,Proceedingsofthe2001GeneticandEvolutionaryComputationConference,pages343–350.MorganKaufmann,2000.J.GottliebandG.R.Raidl.Characterizinglocalityindecoder-basedEAsforthemul-tidimensionalknapsackproblem.InC.Fonlupt,J.-K.Hao,E.Lutton,etal.,editors,ProceedingsofArtificialEvolution:FourthEuropeanConference,volume1829ofLNCS,pages38–52.Springer,1999.

J.GottliebandG.R.Raidl.Theeffectsoflocalityonthedynamicsofdecoder-basedevolutionarysearch.InD.Whitley,D.Goldberg,E.Cantu-Paz,etal.,editors,Proceedingsofthe2000GeneticandEvolutionaryComputationConference,pages283–290.MorganKaufmann,2000.

J.J.M.Guervos,P.Adamidis,H.-G.Beyer,etal.,editors.ParallelProblemSolvingfromNature–PPSNVII,volume2439ofLNCS,2002.Springer.

J.H.Holland.AdaptioninNaturalandArtificialSystems.TheUniversityofMichiganPress,AnnArbor,1975.J.JonesandS.Forrest.Fitnessdistancecorrelationasameasureofproblemdifficultyforgeneticalgorithms.InL.J.Eshelman,editor,ProceedingsoftheSixthInternationalConferenceonGeneticAlgorithms,pages184–192.MorganKaufmann,1995.

13

B.A.Julstrom.Stringsofweightsaschromosomesingeneticalgorithmsforcombinatorialproblems.InJ.T.Alander,editor,ProceedingsoftheThirdNordicWorkshoponGeneticAlgorithmsandtheirApplications,pages33–48,1997.

B.A.JulstromandG.R.Raidl.Weight-biasededge-crossoverinevolutionaryalgorithmsfortwographproblems.InG.Lamont,J.Carroll,H.Haddad,etal.,editors,Proceedingsofthe16thACMSymposiumonAppliedComputing,pages321–326.ACMPress,2001.S.Kersting,G.R.Raidl,andI.Ljubi´c.Amemeticalgorithmforvertex-biconnectivityaugmentation.InS.Cagnoni,J.Gottlieb,E.Hart,M.Middendorf,andG.R.Raidl,editors,ApplicationsofEvolutionaryComputing:EvoWorkshops2002,volume2279ofLNCS,pages102–111.Springer,2002.

S.Kirkpatrick,C.Gellat,andM.Vecchi.Optimizationbysimulatedannealing.Science,220:671–680,1983.

I.Ljubi´candG.R.Raidl.Amemeticalgorithmforminimum-costvertex-biconnectivityaugmentationofgraphs.JournalofHeuristics,toappear.AcceptedsubjecttominorrevisionsinOctober2002(therevisionsarealreadyincorporatedintheversionofthisthesis;apreliminaryversionofthisarticlehasbeenpublishedinKerstingetal.(2002)).W.N.MartinandW.Spears,editors.FoundationsofGeneticAlgorithms6,2001.MorganKaufmann.

P.MerzandB.Freisleben.Fitnesslandscapesandmemeticalgorithmdesign.InNewIdeasinOptimisationCorneetal.(1999),pages245–260.

Z.Michalewicz.GeneticAlgorithms+DataStructures=EvolutionPrograms.Springer,Berlin,1996.

Z.MichalewiczandD.B.Fogel.HowtoSolveit:ModernHeuristics.Springer,2000.P.Moscato.Memeticalgorithms:Ashortintroduction.InNewIdeasinOptimisationCorneetal.(1999),pages219–234.

C.C.PalmerandA.Kershenbaum.Representingtreesingeneticalgorithms.InD.Schaffer,H.-P.Schwefel,andD.B.Fogel,editors,ProceedingsoftheFirstIEEEConferenceonEvolutionaryComputation,pages379–384.IEEEPress,1994.

G.R.Raidl.Animprovedgeneticalgorithmforthemulticonstrained0–1knapsackproblem.InP.K.Simpson,K.Haines,D.Fogel,etal.,editors,Proceedingsofthe1998IEEEIn-ternationalConferenceonEvolutionaryComputationProceedings,pages207–211.IEEEPress,1998.

G.R.Raidl.Themultiplecontainerpackingproblem:Ageneticalgorithmapproachwithweightedcodings.ACMSIGAPPAppliedComputingReview,7(2):22–31,1999a.G.R.Raidl.Aweight-codedgeneticalgorithmforthemultiplecontainerpackingproblem.InJ.Carroll,H.Haddad,D.Oppenheim,etal.,editors,Proceedingsofthe1999ACMSymposiumonAppliedComputing,pages291–296.ACMPress,1999b.

G.R.Raidl.Weight-codingsinageneticalgorithmforthemulticonstraintknapsackprob-lem.InP.J.Angeline,Z.Michalewicz,M.Schoenauer,etal.,editors,Proceedingsofthe1999IEEECongressonEvolutionaryComputation,pages596–603.IEEEPress,1999c.

14

G.R.Raidl.Anefficientevolutionaryalgorithmforthedegree-constrainedminimumspan-ningtreeproblem.InC.Fonseca,J.-H.Kim,andA.Smith,editors,Proceedingsofthe2000IEEECongressonEvolutionaryComputation,pages104–111.IEEEPress,2000.G.R.RaidlandC.Drexel.Apredecessorcodinginanevolutionaryalgorithmforthecapacitatedminimumspanningtreeproblem.InC.Armstrong,editor,LateBreakingPapersatthe2000GeneticandEvolutionaryComputationConference,pages309–316,LasVegas,NV,2000.G.R.RaidlandB.A.Julstrom.Aweightedcodinginageneticalgorithmforthedegree-constrainedminimumspanningtreeproblem.InJ.Carroll,E.Damiani,H.Haddad,andD.Oppenheim,editors,Proceedingsofthe2000ACMSymposiumonAppliedComputing,pages440–445.ACMPress,2000.

G.R.RaidlandB.A.Julstrom.Edge-sets:Aneffectiveevolutionarycodingofspanningtrees.IEEETransactionsonEvolutionaryComputation,toappear.AcceptedinOctober2002.

G.R.RaidlandB.A.Julstrom.Greedyheuristicsandanevolutionaryalgorithmforthebounded-diameterminimumspanningtreeproblem.InProceedingsofthe2003ACMSymposiumonAppliedComputing.ACMPress,toappear2003.

G.R.Raidl,G.Kodydek,andB.Julstrom.Onweight-biasedmutationforgraphproblems.InGuervosetal.(2002),pages204–213.

G.R.RaidlandI.Ljubi´c.Evolutionarylocalsearchfortheedge-biconnectivityaugmenta-tionproblem.InformationProcessingLetters,82(1):39–45,2002.

I.Rechenberg.Evolutionsstrategie:OptimierungtechnischerSystemenachPrinzipienderbiologischenEvolution.Fromman-Holzbook,Stuttgart,Germany,1973.

J.Scharnow,K.Tinnefeld,andI.Wegener.Fitnesslandscapesbasedonsortingandshortestpathsproblems.InGuervosetal.(2002),pages54–63.H.P.Schwefel.NumericalOptimizationofComputerModels.JohnWiley,1981.

M.D.Vose.TheSimpleGeneticAlgorithm–FoundationsandTheory.TheMITPress,London,U.K.,1999.

15

16

Chapter2

TheMultipleContainerPackingProblem:AGeneticAlgorithmApproachwithWeightedCodings

byG¨untherR.Raidl

inACMSIGAPPAppliedComputingReview,volume7,number2,pp.22–31,ACMPress,1999.

Apreviousversionofthisarticlehasbeenpublishedas:

G.R.Raidl:AWeight-CodedGeneticAlgorithmfortheMultipleContainerPackingProblem,inProceedingsofthe14thACMSymposiumonAppliedComputing,SanAntonio,TX,pp.291–296,ACMPress,1999.

ThisarticlehasbeenselectedasbestpaperoftheEvolutionaryComputationandOptimizationTrackatthesymposium.

17

18

Chapter3

TheEffectsofLocalityontheDynamicsofDecoder-BasedEvolutionarySearch

byJensGottliebandG¨untherR.Raidl

inProceedingsofthe2000GeneticandEvolutionaryComputationConference,LasVegas,NV,pp.283–2,MorganKaufmann,2000.

37

38

Chapter4

Edge-Sets:AnEffectiveEvolutionaryCodingofSpanningTrees

byG¨untherR.RaidlandBryantA.Julstrom

toappearintheIEEETransactionsonEvolutionaryComputation,IEEEPress,acceptedinOctober2002.

Anoriginalversionoftheedge-setrepresentationwithvariationoperatorsforthedegree-constrainedminimumspanningtreeproblemhasbeenpublishedin:G.R.Raidl:AnEfficientEvolutionaryAlgorithmfortheDegree-ConstrainedMini-mumSpanningTreeProblem,inProceedingsofthe2000IEEECongressonEvolu-tionaryComputation,WashingtonD.C.,pp.104–111,IEEEPress,2000.

51

52

Chapter5

OnWeight-BiasedMutationforGraphProblems

byG¨untherR.Raidl,GabrieleKodydek,andBryantA.Julstrom

inProceedingsoftheInt.ConferenceonParallelProblemSolvingFromNatureVII,Granada,Spain,SpringerLectureNotesinComputerScience,volume2439,pp.204–213,2002.

83

84

Chapter6

AMemeticAlgorithmforMinimum-CostVertex-BiconnectivityAugmentationofGraphs

byIvanaLjubi´candG¨untherR.Raidl

toappearintheJournalofHeuristics,

KluwerAcademicPublishers,acceptedinOctober2002subjecttominorrevisions;theserevisionarealreadyincorporatedinthisversion.

Apreliminaryversionofthisworkhasbeenpublishedin:

S.Kersting,G.R.Raidl,I.Ljubic:AMemeticAlgorithmfortheVertex-BiconnectivityAugmentationProblem,inApplicationsofEvolutionaryComputing,ProceedingsofEvoWorkshops2002,Kinsale,Ireland,SpringerLectureNotesinCom-puterScience,volume2279,pp.102–111,2002.

95

96