Evolutionary Algorithms

by Spears, William M.

• ISBN13: 9783540669500
• ISBN10: 3540669507
• eBook ISBN(s): 9783662041994
• Format: Hardcover
• Copyright: 2000-07-01
• Publisher: Springer-Verlag New York Inc
• More Book Details
• Purchase Benefits

Summary

Despite decades of work in evolutionary algorithms, there remains a lot of uncertainty as to when it is beneficial or detrimental to use recombination or mutation. This book provides a characterization of the roles that recombination and mutation play in evolutionary algorithms. It integrates prior theoretical work and introduces new theoretical techniques for studying evolutionary algorithms. An aggregation algorithm for Markov chains is introduced which is useful for studying not only evolutionary algorithms specifically, but also complex systems in general. Practical consequences of the theory are explored and a novel method for comparing search and optimization algorithms is introduced. A focus on discrete rather than real-valued representations allows the book to bridge multiple communities, including evolutionary biologists and population geneticists.

Table of Contents

Notation	xiii
Part I. Setting the Stage
Introduction	3	(16)
Evolutionary Algorithms	3	(6)
Overview of Related Work	9	(6)
Issues and Goals	15	(2)
Outline	17	(2)
Background	19	(20)
No Free Lunch	19	(2)
A Boolean Satisfiability Problem Generator	21	(3)
Using SAT to Creat Multimodal and Epistatic Problems	24	(4)
Speciation	28	(6)
Summary	34	(5)
Part II. Static Theoretical Analyses
A Survival Schema Theory for Recombination	39	(20)
Introduction	39	(1)
Framework	40	(2)
Survival Theory for n-point Recombination	42	(3)
Graphing Disruption	45	(2)
Estimates Using Population Homogeneity	47	(4)
Survival Theory for P0 Uniform Recombination	51	(5)
Expected Number of Offspring in Hk	56	(2)
Summary	58	(1)
A Construction Schema Theory for Recombination	59	(18)
Introduction	59	(1)
Construction Theory for n-point Recombination	60	(2)
Graphing Construction	62	(2)
Construction Theory for P0 Uniform Recombination	64	(8)
Expected Number of Offspring in Hk	72	(2)
Summary	74	(3)
Survival and Construction Schema Theory for Recombination	77	(6)
Introduction	77	(1)
Survival and Construction	77	(4)
Expected Number of Offspring in Hk	81	(1)
Summary	82	(1)
A Survival Schema Theory for Mutation	83	(8)
Introduction	83	(1)
Framework	84	(6)
Summary	90	(1)
A Construction Schema Theory for Mutation	91	(10)
Introduction	91	(1)
Framework	91	(8)
Summary	99	(2)
Schema Theory: Mutation versus Recombination	101	(16)
Introduction	101	(1)
Survival	101	(3)
Construction	104	(9)
Survival and Construction	113	(1)
Summary	114	(3)
Other Static Characterizations of Mutation and Recombination	117	(12)
Introduction	117	(1)
Exploratory Power	118	(3)
Positional Bias	121	(1)
Distributional Bias	122	(3)
Summary	125	(4)
Part III. Dynamic Theoretical Analyses
Dynamic Analyses of Mutation and Recombination	129	(18)
Introduction	129	(1)
The Limiting Distribution for Recombination	129	(8)
The Limiting Distribution for Mutation	137	(7)
The Limiting Distribution for Mutation and Recombination	144	(1)
Summary	145	(2)
A Dynamic Model of Selection and Mutation	147	(8)
Introduction	147	(1)
Selection and Mutation	147	(4)
Summary	151	(4)
A Dynamic Model of Selection, Recombination, and Mutation	155	(14)
Introduction	155	(1)
EA Performance	155	(1)
Overview of Markov Chains	156	(3)
The Nix and Vose Markov Chain Model for EAs	159	(2)
Instantaneous Transient Behavior of EAs	161	(6)
Summary and Discussion	167	(2)
An Aggregation Algorithm for Markov Chains	169	(24)
Introduction	169	(1)
The Aggregation Algorithm at a High Level	170	(1)
The Aggregation Algorithm in More Detail	171	(5)
Special Cases in Which Aggregation Is Perfect	176	(5)
Error Analysis and a Similarity Metric	181	(2)
Some Experiments	183	(4)
Related Work	187	(2)
Summary	189	(4)
Part IV. Empirical Analyses
Empirical Validation	193	(12)
Introduction	193	(1)
The Multimodal Problem Generator	194	(4)
The Relationship of Multimodality to Epistasis	198	(3)
Summary	201	(4)
Part V. Summary
Summary and Discussion	205	(6)
Summary and Contributions	205	(3)
Future Work	208	(1)
Conclusions	209	(2)
Appendix: Formal Computations for Aggregation	211	(2)
References	213	(6)
Index	219