16. Theory

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

Suggested Reading

Exercises

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

The on-line accompaniment to the book Introduction to Evolutionary Computing