embedding branch and bound within evolutionary algorithms

《embedding branch and bound within evolutionary algorithms》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、EmbeddingBranchandBoundwithinEvolutionaryAlgorithmsCarlosCottaandJos¶eM.TroyaDept.LenguajesyCienciasdelaComputaci¶on,UniversityofM¶alagaETSIInform¶atica(3.2.49),CampusdeTeatinos,29071-M¶alaga,SPAINccottap@lcc.uma.esAbstractAframeworkforhybridizingevolutionaryalgori

2、thmswiththebranch-and-boundalgorithm(B&B)ispresentedinthispaper.ThisframeworkisbasedonusingB&Basanoperatorembeddedintheevolutionaryalgorithm.Theresultinghybridoperatorwillintelligentlyexplorethedynasticpotential(possiblechildren)ofthesolutionsbeingrecombined,provid

3、ingthebestcombinationofformae(generalizedschemata)thatcanbeconstructedwithoutintroducingimplicitmutation.Asabasisforstudyingthisoperator,thegeneralfunctioningoftransmittingrecombinationisconsidered.Twoimportantconceptsareintroduced,compatibilitysets,andgranularityo

4、ftherepresentation.Theseconceptsarestudiedinthecontextofdi®erentkindsofrepresentation:orthogonal,non-orthogonalseparable,andnon-separable.Theresultsofanextensiveexperimentalevaluationarereported.Itisshownthatthismodelcanbeusefulwhenproblemknowledgeisavailableinthef

5、ormofanoptimisticevaluationfunction.Scalabilityissuesarealsoconsidered.Acontrolmechanismisproposedtoalleviatetheincreasingcomputationalcostofthealgorithmforhighlymultidimensionalproblems.1IntroductionEvolutionaryAlgorithms[1]arepowerfulheuristicsforoptimizationbase

6、dontheprinciplesofnaturalevolution,namelyadaptationandsurvivalofthe¯ttest.Thesetechniquesarebasedontheiterativegenerationoftentativesolutionsforatargetproblem:startingfromapopulation(pool)ofrandomlycreatedindividuals(solutions),abasiccyclecomprisingselection(promis

7、ingsolutionsarepickedfromthepool),reproduction(newsolutionsarecreatedbymodifyingselectedsolutions),andreplacement(thepoolisupdatedbyreplacingsomeexistingsolutionsbythenewlycreatedones)isperformed.A¯tnessfunctionmeasuringthegoodnessofsolutionsisusedtodrivethewholepr

8、ocess,especiallydur-ingtheselectionstage.Evolutionarycomputationconstitutesnowadaysastate-of-the-artapproachtotacklehardoptimizationproblemsforwh