The Importance of Selection Mechanisms in Distribution Estimation Algorithms
Andrew Johnson8 and Jonathan Shapiro8
| (8) |
Computer Science Department, University of Manchester, M13 9PL Manchester, UK |
Abstract
The evolutionary algorithms that use probabilistic graphical models to represent properties of selected solutions are known
as Distribution Estimation Algorithms (DEAs). Work on such algorithms has generally focused on the complexity of the models
used. Here, the performance of two DEAs is investigated. One takes problem variables to be independent while the other uses
pairwise conditional probabilities to generate a chain in which each variable conditions another. Three problems are considered
that differ in the extent to which they impose a chain-like structure on variables. The more complex algorithm performs better
on a function that exactly matches the structure of its model. However, on other problems, the selection mechanism is seen
to be crucial, some previously reported gains for the more complex algorithm are shown to be unfounded and, with comparable
mechanisms, the simpler algorithm gives better results. Some preliminary explanations of the dynamics of the algorithms are
also offered.
The first author is supported by a UK EPSRC Studentship.
References secured to subscribers.