An Introduction to Genetic Algorithms - Melanie Mitchell.pdf

(6351 KB) Pobierz
An Introduction to Genetic Algorithms
Mitchell Melanie
A Bradford Book The MIT Press
Cambridge, Massachusetts • London, England
Fifth printing, 1999
First MIT Press paperback edition, 1998
Copyright © 1996 Massachusetts Institute of Technology
All rights reserved. No part of this publication may be reproduced in any form by any electronic or
mechanical means (including photocopying, recording, or information storage and retrieval) without
permission in writing from the publisher.
Set in Palatino by Windfall Software using ZzT
E
X.
Library of Congress Cataloging−in−Publication Data
Mitchell, Melanie.
An introduction to genetic algorithms / Melanie Mitchell.
p. cm.
"A Bradford book."
Includes bibliographical references and index.
ISBN 0−262−13316−4 (HB), 0−262−63185−7 (PB)
1. Genetics—Computer simulation.2. Genetics—Mathematical models.I. Title.
QH441.2.M55 1996
575.1'01'13—dc20 95−24489
CIP
1
Table of Contents
An Introduction to Genetic Algorithms............................................................................................................1
Mitchell Melanie......................................................................................................................................1
Chapter 1: Genetic Algorithms: An Overview.................................................................................................2
Overview..................................................................................................................................................2
1.1 A BRIEF HISTORY OF EVOLUTIONARY COMPUTATION.....................................................2
1.2 THE APPEAL OF EVOLUTION.....................................................................................................4
1.3 BIOLOGICAL TERMINOLOGY.....................................................................................................5
1.4 SEARCH SPACES AND FITNESS LANDSCAPES.......................................................................6
1.5 ELEMENTS OF GENETIC ALGORITHMS...................................................................................7
Examples of Fitness Functions...................................................................................................7
GA Operators..............................................................................................................................8
1.6 A SIMPLE GENETIC ALGORITHM..............................................................................................8
1.7 GENETIC ALGORITHMS AND TRADITIONAL SEARCH METHODS..................................10
1.9 TWO BRIEF EXAMPLES..............................................................................................................12
Using GAs to Evolve Strategies for the Prisoner's Dilemma...................................................13
Hosts and Parasites: Using GAs to Evolve Sorting Networks
..................................................16
1.10 HOW DO GENETIC ALGORITHMS WORK?...........................................................................21
THOUGHT EXERCISES......................................................................................................................23
COMPUTER EXERCISES...................................................................................................................24
Chapter 2: Genetic Algorithms in Problem Solving......................................................................................27
Overview................................................................................................................................................27
2.1 EVOLVING COMPUTER PROGRAMS.......................................................................................27
Evolving Lisp Programs...........................................................................................................27
Evolving Cellular Automata.....................................................................................................34
2.2 DATA ANALYSIS AND PREDICTION.......................................................................................42
Predicting Dynamical Systems.................................................................................................42
Predicting Protein Structure......................................................................................................47
2.3 EVOLVING NEURAL NETWORKS............................................................................................49
Evolving Weights in a Fixed Network.....................................................................................50
Evolving Network Architectures..............................................................................................53
Direct Encoding........................................................................................................................54
Grammatical Encoding.............................................................................................................55
Evolving a Learning Rule.........................................................................................................58
THOUGHT EXERCISES......................................................................................................................60
COMPUTER EXERCISES...................................................................................................................62
Chapter 3: Genetic Algorithms in Scientific Models.....................................................................................65
Overview................................................................................................................................................65
3.1 MODELING INTERACTIONS BETWEEN LEARNING AND EVOLUTION...........................66
The Baldwin Effect...................................................................................................................66
A Simple Model of the Baldwin Effect....................................................................................68
Evolutionary Reinforcement Learning.....................................................................................72
3.2 MODELING SEXUAL SELECTION
.............................................................................................75
Simulation and Elaboration of a Mathematical Model for Sexual Selection...........................76
3.3 MODELING ECOSYSTEMS.........................................................................................................78
3.4 MEASURING EVOLUTIONARY ACTIVITY.............................................................................81
Thought Exercises
..................................................................................................................................84
Computer Exercises...............................................................................................................................85
Table of Contents
Chapter 4: Theoretical Foundations of Genetic Algorithms........................................................................87
Overview................................................................................................................................................87
4.1 SCHEMAS AND THE TWO−ARMED BANDIT PROBLEM.....................................................87
The Two−Armed Bandit Problem............................................................................................88
Sketch of a Solution..................................................................................................................89
Interpretation of the Solution....................................................................................................91
Implications for GA Performance
.............................................................................................92
Deceiving a Genetic Algorithm................................................................................................93
Limitations of "Static" Schema Analysis
..................................................................................93
4.2 ROYAL ROADS.............................................................................................................................94
Royal Road Functions
...............................................................................................................94
Experimental Results................................................................................................................95
Steepest−ascent hill climbing (SAHC).....................................................................................96
Next−ascent hill climbing (NAHC)..........................................................................................96
Random−mutation hill climbing (RMHC)...............................................................................96
Analysis of Random−Mutation Hill Climbing.........................................................................97
Hitchhiking in the Genetic Algorithm......................................................................................98
An Idealized Genetic Algorithm...............................................................................................99
4.3 EXACT MATHEMATICAL MODELS OF SIMPLE GENETIC ALGORITHMS
.....................103
Formalization of GAs.............................................................................................................103
Results of the Formalization...................................................................................................108
A Finite−Population Model....................................................................................................108
4.4 STATISTICAL−MECHANICS APPROACHES.........................................................................112
THOUGHT EXERCISES....................................................................................................................114
COMPUTER EXERCISES.................................................................................................................116
5.1 WHEN SHOULD A GENETIC ALGORITHM BE USED?........................................................116
5.2 ENCODING A PROBLEM FOR A GENETIC ALGORITHM...................................................117
Binary Encodings
....................................................................................................................117
Many−Character and Real−Valued Encodings......................................................................118
Tree Encodings.......................................................................................................................118
5.3 ADAPTING THE ENCODING....................................................................................................118
Inversion.................................................................................................................................119
Evolving Crossover "Hot Spots"............................................................................................120
Messy Gas...............................................................................................................................121
5.4 SELECTION METHODS.............................................................................................................124
Fitness−Proportionate Selection with "Roulette Wheel" and "Stochastic Universal"
Sampling................................................................................................................................124
Sigma Scaling.........................................................................................................................125
Elitism.....................................................................................................................................126
Boltzmann Selection...............................................................................................................126
Rank Selection........................................................................................................................127
Tournament Selection.............................................................................................................127
Steady−State Selection...........................................................................................................128
5.5 GENETIC OPERATORS..............................................................................................................128
Crossover................................................................................................................................128
Mutation..................................................................................................................................129
Other Operators and Mating Strategies..................................................................................130
5.6 PARAMETERS FOR GENETIC ALGORITHMS.......................................................................130
THOUGHT EXERCISES....................................................................................................................132
COMPUTER EXERCISES.................................................................................................................133
Table of Contents
Chapter 6: Conclusions and Future Directions
............................................................................................135
Overview..............................................................................................................................................135
Incorporating Ecological Interactions..................................................................................................136
Incorporating New Ideas from Genetics..............................................................................................136
Incorporating Development and Learning...........................................................................................137
Adapting Encodings and Using Encodings That Permit Hierarchy and Open−Endedness.................137
Adapting Parameters............................................................................................................................137
Connections with the Mathematical Genetics Literature.....................................................................138
Extension of Statistical Mechanics Approaches..................................................................................138
Identifying and Overcoming Impediments to the Success of GAs......................................................138
Understanding the Role of Schemas in GAs
........................................................................................138
Understanding the Role of Crossover..................................................................................................139
Theory of GAs With Endogenous Fitness...........................................................................................139
Appendix A: Selected General References...................................................................................................140
Appendix B: Other Resources.......................................................................................................................141
SELECTED JOURNALS PUBLISHING WORK ON GENETIC ALGORITHMS..........................141
SELECTED ANNUAL OR BIANNUAL CONFERENCES INCLUDING WORK ON
GENETIC ALGORITHMS................................................................................................................141
INTERNET MAILING LISTS, WORLD WIDE WEB SITES, AND NEWS GROUPS WITH
INFORMATION AND DISCUSSIONS ON GENETIC ALGORITHMS........................................142
Bibliography........................................................................................................................................143

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin