Introduction

Evolutionary algorithms have been widely applied in ecological modeling. They owe their success to simplicity of application - they work well 'out of the box', with little need to tune parameters. Changes in the relative cost of computational power and human expertise are increasing this appeal. Evolutionary algorithms are suited to parallel implementation, their speed scaling near-linear with the number of processors. With the current emphasis on multicore architectures, this appeal is likely to increase.

Evolutionary algorithms are inspired by Darwin's theory of evolution through natural selection (see Evolutionary Ecology: Overview for biological aspect of evolution).

Darwin's theory assumes that inherited characteristics determine an individual's likelihood of reproduction. Two classes of stochastic operators are defined, selection and reproduction/variation. These operate repeatedly on a population to generate new individuals, and over time, the population's fitness increases, usually converging to a good solution to the problem ofsurvival.

Evolutionary algorithms abstract this model. Given a problem domain - the set of all potential solutions to the problem, together with a definition of what constitutes a good solution - evolutionary algorithms repeatedly apply selection and variation operators to a population, with the aim of finding good solutions. Even for quite tough optimization problems, relatively modest resources -

populations of hundreds or thousands, run for tens to thousands of generations - can reliably generate good solutions. For more complex problems, more resources may be required.

In the following, we introduce two basic evolutionary algorithms, survey a range of applications in ecological modeling, and finally consider some variant algorithms.

Simple Evolutionary Algorithms

The history of evolutionary algorithms is complex and controversial, but most subsequent work was based on the evolution strategies of Rechenberg and Schwefel, and the genetic algorithms (GAs) of Holland.

Evolution strategies

In an evolution strategy (ES), the solution space is R" (i.e., vectors of real numbers - Figure 1). An initial population is generated, by sampling some number m of initial solutions from a suitable prior probability distribution. In each generation, A of the current population are chosen to generate children (see Optimal Foraging and Evolution of 'Prey-Predator' Systems for biological aspects of evolution strategy). Each parent in turn is used as the mean of an "-dimensional Gaussian with a suitable standard deviation u, and a single sample is taken as the child (Figure 2). Finally, parents and children join together into a single population of size p + A, the fittest p individuals being chosen to form the next population. Known as a p + A ES, it is characterized by real number representation, Gaussian mutation without recombination, deterministic selection, and overlapping of generations.

7384.438 979 210

87.908 132 47

0.891 237 094 124

Figure 1 Evolution strategies: typical chromosome.

Figure 1 Evolution strategies: typical chromosome.

Location relative to parent (a = 1.0)

Figure 2 Evolution strategies: Gaussian mutation, probability of selection.

Location relative to parent (a = 1.0)

Figure 2 Evolution strategies: Gaussian mutation, probability of selection.

At first, the standard deviation u was fixed, limiting convergence to the optimum. Later versions use a fixed heuristic for varying u, or evolve u itself.

Genetic algorithms

Holland's early GAs used binary representation - even for continuous problems. The initial population of size p was generated randomly. To generate children, parents were selected stochastically, using fitness-proportionate probabilities. The reproduction operators were bit-flipping mutation (bits in the parent are flipped with uniform probability - Figure 3) and one-point crossover (two parents are cut at corresponding locations, and the bits after the cut-point are exchanged to generate the children - Figure 3). Once p children had been generated in this way, the parent generation was discarded. So this form of GA is characterized by bit representation, bit-flipping mutation and one-point crossover, roulette-wheel selection, and separation of generations.

Later methods

The direct descendants of these methods use a wide range of representations, often problem specific; a wide range of mutation and recombination operators; and a variety of selection mechanisms, with separation of generations being more common than overlapping.

Project Earth Conservation

Project Earth Conservation

Get All The Support And Guidance You Need To Be A Success At Helping Save The Earth. This Book Is One Of The Most Valuable Resources In The World When It Comes To How To Recycle to Create a Better Future for Our Children.

Get My Free Ebook


Post a comment