Approaches to selection and their effect on fitness modelling in an Estimation of Distribution Algorithm

Abstract

Selection is one of the defining characteristics of an evolutionary algorithm, yet inherent in the selection process is the loss of some information from a population. Poor solutions may provide information about how to bias the search toward good solutions. Many Estimation of Distribution Algorithms (EDAs) use truncation selection which discards all solutions below a certain fitness, thus losing this information. Our previous work on Distribution Estimation using Markov networks (DEUM) has described an EDA which constructs a model of the fitness function; a unique feature of this approach is that because selective pressure is built into the model itself selection becomes optional. This paper outlines a series of experiments which make use of this property to examine the effects of selection on the population. We look at the impact of selecting only highly fit solutions, only poor solutions, selecting a mixture of highly fit and poor solutions, and abandoning selection altogether. We show that in some circumstances, particularly where some information about the problem is already known, selection of the fittest only is suboptimal.