Theoretical andEmpirical Investigations onDifficulty inStructure Learning byEstimation ofDistribution Algorithms

Masaharu Munetomo, Kiyoshi Akama

Abstract

Estimation ofdistribution algorithms (EDAs) are population basedevolutionary algorithms derived fromgenetic algorithms (GAs) .EDAsbuild probabilistic models ofpromis- ingsolutions toguide further exploration ofthesearch space. Theyhavebeenconsidered tobehave insimilar waytoGAs.In this paper, weshowtheir different behaviors anddifficulties in applications ofEDAsbydesigning anEDAdifficult function in whichschemata thatarenotconsistent withproblem structure sometimes overwhelm those thatare. I.INTRODUCTION Estimation ofdistribution algorithms (EDAs)arepopu- lation basedevolutionary algorithms derived fromgenetic algorithms (GAs).Unlike GAs,EDAsbuild probabilistic models ofpromising solutions toguide further exploration of thesearch space. TheEDAsreplace explicit genetic operators suchascrossover andmutation bylearning andsampling fromtheprobability distribution ofpromising solutions at eachgeneration. Simple EDAsmodeleachvariable independently. Itis shownthatthesimple EDAsaresimilar tosimple GAs withuniform crossover (8), (10). However, ithasnotbeen investigated enoughwhether thecompetent EDAs,which construct morecomplex probabilistic models toencode rela- tionships between variables, aresimilar toGAswhichobtain therelationships insomewayorbyexperts. Thispaper discusses difficulties inapplications ofEDAs fromtheoretical andempirical point ofview. Although EDAs mustfind anappropriate probabilistic modelbyoptimizing themodel, thequality ofthemodelsometimes depends on thefunction tobesolved. Wedesign afunction that prevents EDAsfromconstructing correct models toinvestigate how thesuccess ofEDAsdepends onthequality oftheir models andtoshowanexample that EDAsbehave inadifferent way fromGAs. Theproposed function iscalled EDA-trap function. Inthe function, aschema onasetofvariables whichisinconsistent withtheproblem structure hashigher fitness thanaschema onasetofvariables whichisconsistent withthestructure. Whensuchinconsistent schema increases, modelbuildings inEDAsbecomedifficult.
BibTeX
@inproceedings{munetomo2006theoretical,
  author = {Masaharu Munetomo and Kiyoshi Akama},
  title = {{Theoretical andEmpirical Investigations onDifficulty inStructure Learning byEstimation ofDistribution Algorithms}},
  booktitle = {SMC},
  year = {2006},
  url = {https://openreview.net/forum?id=A2g91TYWzs},
}

Loading related content...

Figure