AnIntroductionToGeneticAlgorithms(MIT).pdf资源-CSDN文库

Genetic

5星 · 超过95%的资源需积分: 9 101 浏览量 2009-01-06 13:10:18 上传评论 2 收藏 6.2MB PDF 举报

资源推荐

资源详情

资源评论

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

剩余161页未读，继续阅读

评论收藏

内容反馈