The simple genetic algorithm

Table of contents

1 Introduction

2 Notation

3 Random Heuristic Search

3.1 Representation

3.2 Nondeterminism

3.3 Markov Chain

4 The Simple Genetic Algorithm

4.1 Algebra

4.2 Selection

4.3 Mutation

4.4 Crossover

4.5 Mixing

4.6 SGA's Heuristic

5 Implementation

5.1 Selection

5.2 Mutation

5.3 Crossover

5.4 The Classical SGA

5.5 Random Sampling

6 The Walsh Transform

6.1 Basic Properties

6.2 The Twist and Transform of Mixing

6.3 The Spectrum of dM

6.4 The Walsh Basis

7 Computing with the Heuristic

7.1 Selection

7.2 Mixing

7.3 Fixed Points

8 Basic Examples

8.1 Transient Population Trajectories

8.2 Long Term Probabilities

8.3 Trajectory of Expectations

9 The Inverse Heuristic

9.1 Selection

9.2 Mixing

9.3 G

10 Focused Heuristics

10.1 Lyapunov's Criterion

10.2 Selection

10.3 Mixing

10.4 Summary

11 Linear Fitness

11.1 Crossover

11.2 Monotone Selection

11.3 Hyperbolicity

12 Perturbation Arguments

12.1 Small Perturbations

12.2 Application

13 Transient Behavior

13.1 Large Populations

13.2 Logarithmic Convergence

13.3 Summary

14 Asymptotic Behavior

14.1 The Fixed point Graph

14.2 Approximating Transition Probabilities

14.3 Unstable Fixed Points

14.4 Asymptotic Approximation

15 Hyperbolicity

16 Geometric Invariance

16.1 Elementary Invariance

16.2 Proportional Selection and the GA Surface

17 Quotients

17.1 Equivalence

17.2 Operators

17.3 Models

18 Schemata

18.1 Definition

18.2 Mixing

18.3 Selection

Appendix

A.1 Analysis

A.2 Linear Algebra

A.3 Probability

A.4 Dynamical Systems

Notation Index

Index