爱华网NeuralComput&Applic
DOI10.1007/s00521-015-1870-7
ORIGINALARTICLE
Multi-VerseOptimizer:anature-inspiredalgorithmforglobaloptimization
SeyedaliMirjalili?SeyedMohammadMirjalili?
AbdolrezaHatamlou
Received:6October2014/Accepted:22February2015óTheNaturalComputingApplicationsForum2015
AbstractThispaperproposesanovelnature-inspiredalgorithmcalledMulti-VerseOptimizer(MVO).Themaininspirationsofthisalgorithmarebasedonthreeconceptsincosmology:whitehole,blackhole,andwormhole.Themathematicalmodelsofthesethreeconceptsaredevelopedtoperformexploration,exploitation,andlocalsearch,re-spectively.TheMVOalgorithmis?rstbenchmarkedon19challengingtestproblems.Itisthenappliedto?verealengineeringproblemstofurthercon?rmitsperformance.Tovalidatetheresults,MVOiscomparedwithfourwell-knownalgorithms:GreyWolfOptimizer,ParticleSwarmOptimization,GeneticAlgorithm,andGravitationalSearchAlgorithm.Theresultsprovethattheproposedalgorithmisabletoprovideverycompetitiveresultsandoutperformsthebestalgorithmsintheliteratureonthemajorityofthetestbeds.Theresultsoftherealcasestudiesalso
ElectronicsupplementarymaterialTheonlineversionofthisarticle(doi:10.1007/s00521-015-1870-7)containssupplementarymaterial,whichisavailabletoauthorizedusers.
S.Mirjalili(&)
SchoolofInformationandCommunicationTechnology,Grif?thUniversity,NathanCampus,Brisbane,QLD4111,Australiae-mail:seyedali.mirjalili@grif?thuni.edu.auS.Mirjalili
QueenslandInstituteofBusinessandTechnology,MtGravatt,Brisbane,QLD4122,Australia
S.M.Mirjalili
ZharfaPajoheshSystem(ZPS)Co.,Unit5,NO.30,West208St.,ThirdSq.Tehranpars,P.O.Box1653745696,Tehran,IranA.Hatamlou
DepartmentofComputerScience,KhoyBranch,IslamicAzadUniversity,Khoy,Iran
demonstratethepotentialofMVOinsolvingrealproblemswithunknownsearchspaces.NotethatthesourcecodesoftheproposedMVOalgorithmarepubliclyavailableathttp://www.alimirjalili.com/MVO.html.
KeywordsOptimizationáMeta-heuristicáAlgorithmáBenchmarkáGeneticAlgorithmáParticleSwarmOptimizationáHeuristic
1Introduction
Naturehasbeenthemaininspirationforthemajorityofthepopulation-basedstochasticoptimizationtechniques.Asthenameofsuchtechniquesimplies,theyperformopti-mizationrandomly.Theoptimizationprocessisusuallystartedbycreatingasetofrandomsolutions.Theseinitialsolutionsarethencombined,moved,orevolvedoverapre-de?nednumberofstepscallediterationsorgenerations.Thisisalmostthemainframeworkofallpopulation-basedalgorithms.Whatmakesanalgorithmdifferentfromothersinthis?eldisthemechanismofcombining,moving,orevolvingthesolutionsduringoptimization.
Forinstance,GeneticAlgorithms(GAs)[1]utilizethesurvivalofthe?tterindividualsinnatureinordertoselectthebestsolutionsandthencombinethembasedonthereproductionofchromosomes.ParticleSwarmOptimiza-tion(PSO)[2]wasinspiredbysocialandindividualthinkingofbirdswhen?ying,soitobligesthecandidatesolutionstomovearoundasearchspacewithrespecttotheirownpersonalbestpositionobtainedsofaraswellasthebestpositionthattheswarmfoundsofar.GravitationalSearchAlgorithm(GSA)[3]usestheNewtonianlawsofmotioninordertomoveitssearchagentstowardsthepromisingregionsofasearch
space.
123
Anothercommonconceptsamongdifferentpopulation-basedalgorithmsareexplorationandexploitation.Theformerreferstothephasethatanalgorithmtriestodis-coverdifferentpromisingregionsofasearchspaceglob-ally.Generallyspeaking,abruptchangesincandidatesolutionsarefruitfulatthisstage.Incontrary,thelatterconceptistheconvergenceabilityanalgorithmaroundtheobtainedpromisingsolutionsintheexplorationphase.Aproperbalancebetweenexplorationandexploitationcanguaranteeproceedingtowardstheglobaloptimum.
Recently,therehasbeenagrowinginterestinproposingnewalgorithmsorimprovingthecurrentonesinthis?eld.Asigni?cantnumberofpracticalapplicationsalsoac-companiesthetheoreticalworks.Thereasonofthisre-markablepopularitymightbeoriginatedfromtheso-calledNoFreeLunch(NFL)theoremforoptimization[4].Thistheoremhasbeenprovedlogicallythatthereisnoopti-mizationtechniqueforsolvingalloptimizationproblems.TheNFLtheorem,obviously,makesthisareaofresearchopen,inwhichresearchersareallowedtoimprove/adaptthecurrentalgorithmsforsolvingdifferentproblemsorproposenewalgorithmsforprovidingcompetitiveresultscomparedtothecurrentalgorithms.
Inthiswork,anovelstochasticpopulation-basedalgo-rithmisproposedcalledMulti-VerseOptimizer(MVO).Asitsnameimplies,MVOisinspiredbythetheoryofmulti-verseinphysics.Threemainconceptsofthemulti-versetheory(whitehole,blackhole,andwormhole)aremathematicallymodelledtoconstructtheMVO.Therestofthepaperisorganizedasfollows.
Section2providestheliteraturereviewofthestochasticoptimizationtechniques.Section3discussestheconceptsofmulti-versetheoryandproposestheMVOalgorithm.ThetestbedsandresultsaredemonstratedinSect.4.TherealengineeringproblemsaresolvedanddiscussedattheendofSect.4aswell.Eventually,Sect.5concludestheworkandsuggestssomedirectionsforfuturestudies.
2Relatedworks
Generallyspeaking,stochasticoptimizationtechniquescanbedividedintotwomaincategories:single-solution-basedversuspopulation-based.Theformerclassofalgorithmsstartstheoptimizationprocesswithasinglerandomsolu-tionandimprovesitoverapre-de?nednumberofgen-erations.Simulateannealing(SA)[5],localsearches[6,7],andhillclimbing[8]belongtothisclassofalgorithms.Theadvantagesofsingle-solution-basedalgorithmsare:sim-plicityandlownumberoffunctionevaluation.However,themaindisadvantageisthehighprobabilityofentrapmentinlocaloptima.Inaddition,sinceateveryrunasinglesolutionisinvolved,thereisnoinformationsharing,and
123
NeuralComput&Applic
thealgorithmshoulddealwithlotsofissuessuchaslocaloptima,isolationofoptima,deceptiveness,biasofthesearchspace,andprematureconvergencewithonlyonecandidatesolution.
Incontrasttosingle-solution-basedalgorithms,popula-tion-basedalgorithmsinitiatetheoptimizationprocesswithasetofrandomsolutionsandimprovethemoverthecourseofiterations.Thissetofsolutionsissometimescalledcandidatesolutions’set.PSO,GA,AntColonyOptimiza-tion(ACO)[9,10],Arti?cialBeeColonies(ABC)[11],andGSA[11]aresomeofthemostpopularalgorithmsinthisclass.Themainadvantageofthepopulation-basedalgorithmsisthattherecanbeinformationexchangebe-tweenthecandidatesolutions.Therefore,theycanhandletheissuessuchaslocaloptima,isolationofoptima,de-ceptiveness,biasofthesearchspace,andprematurecon-vergenceeasierandfaster.Anotheradvantageisthelessprobabilityofentrapmentinlocalsolutionscomparedtothesingle-solution-basedalgorithms.Thedisadvantagesofthesealgorithmsare:lesssimplicityandtheneedforhighnumberoffunctionevaluationateachiteration.
Theliteratureshowsthatthepopulation-basedalgo-rithmshavebecomeareliablealternativetosingle-solu-tion-basedalgorithmsduetotheabove-mentionedadvantages.Theapplicationofthesemethodscanalsobefoundinawiderangeof?elds,emphasizingthemeritsofthesetechniques.Generallyspeaking,thedesignprocessofanalgorithmstartswithaninspiration.Theinspirationcouldbefrombehaviourofcreatures,naturalphenomena,orsocialevents.Aftertheinspiration,differentpotentialmathematicalmodelsaregeneratedtodesignthealgo-rithm.Thebestcombinationofmathematicalmodelsisthenfoundbyconductingexperimentsonvarioustestbeds.Theoperatorsofalgorithmsinthis?eldareusuallyde-signedtoaccomplishtwophases:explorationversusex-ploitation.Intheformerphase,analgorithmshouldbeequippedwithmechanismstosearchthesearchspaceasextensivelyaspossible.Infact,promisingregionsofthesearchspaceareidenti?edinthisphase.Intheexploitationphase,however,thereshouldbeemphasizesonlocalsearchandconvergencetowardspromisingareasobtainedintheexplorationphase.Explorationandexploitationaretwocon?ictingstageswithnospeci?cmathematicalde?nition.Theexplorationphaseusuallycomesbeforeexploitation,butthereisaneedtore-explorethesearchspaceincaseoflocaloptimastagnation,whichisquitecommoninrealproblemswithunknownsearchspaces.
Anotherchallengewhendesigninganalgorithmisthetransitionbetweenexplorationandexploitation.Thereisnoclearruleforanalgorithmtorealizethemostsuitabletimefortransitingfromexplorationtoexplorationduetobothunknownshapeofsearchspacesandstochasticnatureofpopulation-basedalgorithms.Themajorityofpopulation-
NeuralComput&Applic
basedalgorithmshavebeentunedadaptivelytosmoothlytransitbetweenexplorationandexploitation.Forinstance,theinertiaweightinPSOismostlydecreasedlinearlyfrom0.9to0.4inordertoreducetheimpactsofvelocityvectorsonparticlemovementsandemphasizeexploitationasit-erationsincrease.
Theaboveparagraphsshowthechallengesthatade-signerencounterswhendevelopinganewmeta-heuristic.Thefollowingsectionproposesanovelmeta-heuristicbasedontheconceptsofmulti-versetheory.
3Multi-VerseOptimizer3.1Inspiration
Thebigbangtheory[12]discussesthatouruniversestartswithamassiveexplosion.Accordingtothistheory,thebigbangistheoriginofeverythinginthisworld,andtherewasnothingbeforethat.Multi-versetheoryisanotherrecentandwell-knowntheorybetweenphysicists[13].Itisbe-lievedinthistheorythattherearemorethanonebigbangandeachbigbangcausesthebirthofauniverse.Thetermmulti-versestandsoppositeofuniverse,whichreferstotheexistenceofotheruniversesinadditiontotheuniversethatweallarelivingin[13].Multipleuniversesinteractandmightevencollidewitheachotherinthemulti-versethe-ory.Themulti-versetheoryalsosuggeststhattheremightbedifferentphysicallawsineachoftheuniverses.
Wechosethreemainconceptsofthemulti-versetheoryastheinspirationfortheMVOalgorithm:whiteholes,blackholes,andwormholes.Awhiteholehasneverseeninouruniverse,butphysiciststhinkthatthebigbangcanbeconsideredasawhiteholeandmaybethemaincomponentforthebirthofauniverse[14].Itisalsoarguedinthecyclicmodelofmulti-versetheory[15]thatbigbangs/whiteholesarecreatedwherethecollisionsbetweenpar-alleluniversesoccur.Blackholes,whichhavebeenob-servedfrequently,behavecompletelyincontrasttowhite
wholes.Theyattracteverythingincludinglightbeamswiththeirextremelyhighgravitationalforce[16].Wormholesarethoseholesthatconnectdifferentpartsofauniversetogether.Thewormholesinthemulti-versetheoryactastime/spacetraveltunnelswhereobjectsareabletotravelinstantlybetweenanycornersofauniverse(orevenfromoneuniversetoanother)[17].Conceptualmodelsofthesethreekeycomponentsofthemulti-versetheoryareillus-tratedinFig.1.
Everyuniversehasanin?ationrate(eternalin?ation)thatcausesitsexpansionthroughspace[18].In?ationspeedofauniverseisveryimportantintermsofformingstars,planets,asteroids,blackholes,whiteholes,worm-holes,physicallaws,andsuitabilityforlife.Itisarguedinoneofthecyclicmulti-versemodels[19]thatmultipleuniversesinteractviawhite,black,andwormholestoreachastablesituation.ThisistheexactinspirationoftheMVOalgorithm,whichisconceptuallyandmathematicallymodelledinthefollowingsubsection.3.2MVOalgorithm
Asdiscussedintheprecedingsection,apopulation-basedalgorithmdividesthesearchprocessintotwophases:ex-plorationversusexploitation.WeutilizetheconceptsofwhiteholeandblackholeinordertoexploresearchspacesbyMVO.Incontrast,thewormholesassistMVOinex-ploitingthesearchspaces.Weassumethateachsolutionisanalogoustoauniverseandeachvariableinthesolutionisanobjectinthatuniverse.Inaddition,weassigneachsolutionanin?ationrate,whichisproportionaltothecor-responding?tnessfunctionvalueofthesolution.Wealsousethetermtimeinsteadoftheiterationinthispapersinceitisacommonterminmulti-versetheoryandcosmology.Duringoptimization,thefollowingrulesareappliedtotheuniversesofMVO:1.
Thehigherin?ationrate,thehigherprobabilityofhavingwhite
hole.
Fig.1Whitehole,blackhole,andwormhole
123
NeuralComput&Applic
2.3.4.5.
Thehigherin?ationrate,thelowerprobabilityofhavingblackholes.
Universeswithhigherin?ationratetendtosendobjectsthroughwhiteholes.
Universeswithlowerin?ationratetendtoreceivemoreobjectsthroughblackholes.
Theobjectsinalluniversesmayfacerandommove-menttowardsthebestuniverseviawormholesregard-lessofthein?ationrate.
universesbasedoftheirin?ationratesandchoseoneofthembytheroulettewheeltohaveawhitehole.Thefol-lowingstepsaredoneinordertodothis.Assumethat2123x1x1...xd1
2d76x1x...x27622
U?6.7......4..5...
x1n
x2n
...xdn
wheredisthenumberofparameters(variables)andnisthenumberofuniverses(candidatesolutions):
&j
xkr1NIeUiTj
xi?e3:1T
xijr1!NIeUiTwherexijindicatesthejthparameterofithuniverse,Uishowstheithuniverse,NI(Ui)isnormalizedin?ationrateoftheithuniverse,r1isarandomnumberin[0,1],andxkjindicatesthejthparameterofkthuniverseselectedbyaroulettewheelselectionmechanism.
Thepseudocodesforthispartareasfollows:
SU=Sorteduniverses
NI=Normalize inflation rate (fitness) of the universesforeach universe indexed by i
Black_hole_index=i;
foreach objectindexedby j
r1=random([0,1]);ifr1<NI(Ui)
White_hole_index=RouletteWheelSelection(-NI);U(Black_hole_index,j)=SU(White_hole_index,j);
end if
end for
end for
Theconceptualmodeloftheproposedalgorithmisillus-tratedinFig.2.
This?gureshowsthattheobjectsareallowedtomovebetweendifferentuniversesthroughwhite/blackholetun-nels.Whenawhite/blacktunnelisestablishedbetweentwouniverses,theuniversewithhigherin?ationrateiscon-sideredtohavewhitehole,whereastheuniversewithlessin?ationrateisassumedtoownblackholes.Theobjectsarethentransferredfromthewhiteholesofthesourceuniversetoblackholesofthedestinationuniverse.Thismechanismallowstheuniversestoeasilyexchangeobjects.Inordertoimprovethewholein?ationrateoftheuni-verses,weassumethattheuniverseswithhighin?ationratesarehighlyprobabletohavewhiteholes.Incontrary,theuniverseswithlowin?ationrateshaveahighprob-abilityofhavingblackholes.Therefore,thereisalwayshighpossibilitytomoveobjectsfromauniversewithhighin?ationratetoauniversewithlowin?ationrate.Thiscanguaranteetheimprovementoftheaveragein?ationratesofthewholeuniversesovertheiterations.
Inordertomathematicallymodelthewhite/blackholetunnelsandexchangetheobjectsofuniverses,weutilizedaroulettewheelmechanism.Ateveryiteration,wesortthe
123
百度搜索“爱华网”,专业资料、生活学习,尽在爱华网!
