When is an estimation of distribution algorithm better than an evolutionary algorithm?

Tianshi Chen, Per Kristian Lehre, Ke Tang, Xin Yao

Abstract

Despite the wide-spread popularity of estimation of distribution algorithms (EDAs), there has been no theoretical proof that there exist optimisation problems where EDAs perform significantly better than traditional evolutionary algorithms. Here, it is proved rigorously that on a problem called SUBSTRING, a simple EDA called univariate marginal distribution algorithm (UMDA) is efficient, whereas the (1+1) EA is highly inefficient. Such studies are essential in gaining insight into fundamental research issues, i.e., what problem characteristics make an EDA or EA efficient, under what conditions an EDA is expected to outperform an EA, and what key factors are in an EDA that make it efficient or inefficient.
BibTeX
@inproceedings{chen2009when,
  author = {Tianshi Chen and Per Kristian Lehre and Ke Tang and Xin Yao},
  title = {{When is an estimation of distribution algorithm better than an evolutionary algorithm?}},
  booktitle = {IEEE CEC},
  year = {2009},
  doi = {10.1109/cec.2009.4983116},
}

Loading related content...

Figure