Behaviour ofUMDAC withTruncation Selection onMonotonous Functions
Jiorn Grahl, Stefan Minner · 2005
Oflate, muchprogress hasbeenmade indeveloping Estimation ofDistribution Algo- rithms(EDA),algorithms thatuseprobabilis- ticmodelling ofhighquality solutions toguide theirsearch.Whileexperimental results on EDA behaviour arewidely available, theoreti- calresults arestill rare.Thisisespecially the caseforcontinuous EDA.Inthisarticle, we de- veloptheory thatpredicts thebehaviour ofthe Univariate Marginal Distribution Algorithm in thecontinuous domain(UMDAC)withtrunca- tionselection on monotonousfitness functions. Monotonousfunctions arecommonlyusedto modelthealgorithm behaviour farfromtheop- timum.Ourresult includes formulae topre- dictpopulation statistics ina specific genera- tionaswellaspopulation statistics after con- vergence. We findthatpopulation statistics de- velopidentically formonotonousfunctions. We showthatifassuming monotonousfitness func- tions, thedistance thatUMDAC travels across thesearch spaceisboundedandsolely relies on thepercentage ofselected individuals andnot onthestructure ofthefitness landscape. This canbeproblematic ifthisdistance istoosmall forthealgorithm tofindtheoptimum.Also, bywronglysetting theselection intensity, one mightnotbeabletoexplore thewholesearch space.