In this blog, 25.000 books will be uploaded, so far more than 1400 books are available. Books, will be added daily, please check this blog daily.
Friday, October 21, 2011
An Introduction to Genetic Algorithms
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
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
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
Another Genetic Algorithm Books
Download
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment