In this chapter we present a brief overview of some of the approaches taken to analysing and modelling the behaviour of evolutionary algorithms. The Holy Grail of these efforts is the

formulation of predictive models describing the behaviour of an EA on arbitrary problems, and permitting the specification of the most

efficient form of optimiser for any given problem. However, (at least

in the authors’ opinions) this is unlikely ever to be realised, and

most researchers will currently happily settle for techniques that

provide * any* verifiable insights into EA behaviour, even on

simple test problems. The reason for what might seem like limited

ambition lies in one simple fact: evolutionary algorithms are hugely

complex systems, involving many random factors. Moreover, while the field of EAs is fairly young, it is worth noting that the field of

population genetics and evolutionary theory has a head start of more than a hundred years, and is still battling against the barrier of

complexity.

Full descriptions and analysis of the various techniques currently

used to develop EA theory would require both an amount of space and an assumption of prior knowledge of mathematics and statistics that are unsuitable here. We therefore restrict ourselves to a

fairly brief description of the principal methods and results which historically informed the field.

We begin by describing some of the approaches taken to modelling EAs using a discrete representation (i.e., for combinatorial optimisation problems), before moving on to describe the techniques used for continuous representations. This chapter finishes with a description of an important theoretical result concerning all optimisation algorithms, the No Free Lunch (NFL) theorem.

Contents:

16.1 Competing Hyperplanes in Binary Spaces: The Schema

Theorem ………………………………………..232

16.2 Criticisms and Recent Extensions of the Schema Theorem . . . 236

16.3 Gene Linkage: Identifying and Recombining Building Blocks . . 237

16.4 Dynamical Systems ………………………………..238

16.5 Markov Chain Analysis …………………………….239

16.6 Statistical Mechanics Approaches……………………..241

16.7 Reductionist Approaches ……………………………241

16.8 Black Box Analsyis ………………………………..242

16.9 Analysing EAs in Continuous Search Spaces …………….243

16.10 No Free Lunch Theorem…………………………….243