An Introduction to Genetic Algorithms

Melanie Mitchell9780262631853, 0262631857, 0262133164, 9780262133166, 9780585030944

Genetic algorithms have been used in science and engineering as adaptive algorithms for solving practical problems and as computational models of natural evolutionary systems. This brief, accessible introduction describes some of the most interesting research in the field and also enables readers to implement and experiment with genetic algorithms on their own. It focuses in depth on a small set of important and interesting topics—particularly in machine learning, scientific modeling, and artificial life—and reviews a broad span of research, including the work of Mitchell and her colleagues. The descriptions of applications and modeling projects stretch beyond the strict boundaries of computer science to include dynamical systems theory, game theory, molecular biology, ecology, evolutionary biology, and population genetics.

---

Table of contents :
An Introduction to Genetic Algorithms……Page 2
Table of Contents……Page 3
1.1 A BRIEF HISTORY OF EVOLUTIONARY COMPUTATION……Page 6
1.2 THE APPEAL OF EVOLUTION……Page 8
1.3 BIOLOGICAL TERMINOLOGY……Page 9
1.4 SEARCH SPACES AND FITNESS LANDSCAPES……Page 10
Examples of Fitness Functions……Page 11
1.6 A SIMPLE GENETIC ALGORITHM……Page 12
1.7 GENETIC ALGORITHMS AND TRADITIONAL SEARCH METHODS……Page 14
1.9 TWO BRIEF EXAMPLES……Page 16
Using GAs to Evolve Strategies for the Prisoner’s Dilemma……Page 17
Hosts and Parasites: Using GAs to Evolve Sorting Networks……Page 20
1.10 HOW DO GENETIC ALGORITHMS WORK?……Page 25
THOUGHT EXERCISES……Page 27
COMPUTER EXERCISES……Page 28
Evolving Lisp Programs……Page 31
Evolving Cellular Automata……Page 38
Predicting Dynamical Systems……Page 46
Predicting Protein Structure……Page 51
2.3 EVOLVING NEURAL NETWORKS……Page 53
Evolving Weights in a Fixed Network……Page 54
Evolving Network Architectures……Page 57
Direct Encoding……Page 58
Grammatical Encoding……Page 59
Evolving a Learning Rule……Page 62
THOUGHT EXERCISES……Page 64
COMPUTER EXERCISES……Page 66
Overview……Page 69
The Baldwin Effect……Page 70
A Simple Model of the Baldwin Effect……Page 72
Evolutionary Reinforcement Learning……Page 76
3.2 MODELING SEXUAL SELECTION……Page 79
Simulation and Elaboration of a Mathematical Model for Sexual Selection……Page 80
3.3 MODELING ECOSYSTEMS……Page 82
3.4 MEASURING EVOLUTIONARY ACTIVITY……Page 85
Thought Exercises……Page 88
Computer Exercises……Page 89
4.1 SCHEMAS AND THE TWO-ARMED BANDIT PROBLEM……Page 91
The Two-Armed Bandit Problem……Page 92
Sketch of a Solution……Page 93
Interpretation of the Solution……Page 95
Implications for GA Performance……Page 96
Limitations of “Static” Schema Analysis……Page 97
Royal Road Functions……Page 98
Experimental Results……Page 99
Random-mutation hill climbing (RMHC)……Page 100
Analysis of Random-Mutation Hill Climbing……Page 101
Hitchhiking in the Genetic Algorithm……Page 102
An Idealized Genetic Algorithm……Page 103
Formalization of GAs……Page 107
A Finite-Population Model……Page 112
4.4 STATISTICAL-MECHANICS APPROACHES……Page 116
THOUGHT EXERCISES……Page 118
5.1 WHEN SHOULD A GENETIC ALGORITHM BE USED?……Page 120
Binary Encodings……Page 121
5.3 ADAPTING THE ENCODING……Page 122
Inversion……Page 123
Evolving Crossover “Hot Spots”……Page 124
Messy Gas……Page 125
Fitness-Proportionate Selection with “Roulette Wheel” and “Stochastic Universal” Sampling……Page 128
Sigma Scaling……Page 129
Boltzmann Selection……Page 130
Tournament Selection……Page 131
Crossover……Page 132
Mutation……Page 133
5.6 PARAMETERS FOR GENETIC ALGORITHMS……Page 134
THOUGHT EXERCISES……Page 136
COMPUTER EXERCISES……Page 137
Overview……Page 139
Incorporating New Ideas from Genetics……Page 140
Adapting Parameters……Page 141
Understanding the Role of Schemas in GAs……Page 142
Theory of GAs With Endogenous Fitness……Page 143
Appendix A: Selected General References……Page 144
SELECTED ANNUAL OR BIANNUAL CONFERENCES INCLUDING WORK ON GENETIC ALGORITHMS……Page 145
INTERNET MAILING LISTS, WORLD WIDE WEB SITES, AND NEWS GROUPS WITH INFORMATION AND DISCUSSIONS ON GENETIC ALGORITHMS……Page 146
Bibliography……Page 147