Evolutionary Computation (eBook)

David B. Fogel is chief executive officer of Natural Selection, Inc. in La Jolla, CA--a small business focused on solving difficult problems in industry, medicine, and defense using evolutionary computation, neural networks, fuzzy systems, and other methods of computational intelligence. Dr. Fogel's experience in evolutionary computation spans 20 years and includes applications in pharmaceutical design, computer-assisted mammography, data mining, factory scheduling, financial forecasting, traffic flow optimization, agent-based adaptive combat systems, and many other areas. Prior to cofounding Natural Selection, Inc. in 1993, Dr. Fogel was a systems analyst at Titan Systems, Inc. (1984-1988), and a senior principal engineer at ORINCON Corporation (1988-1993). Dr. Fogel received his Ph.D. degree in engineering sciences (systems science) from the University of California at San Diego (UCSD) in 1992. He earned an M.S. degree in engineering sciences (systems science) from UCSD in 1990, and a B.S. in mathematical sciences (probability and statistics) from the University of California at Santa Barbara in 1985. He has taught university courses at the graduate and undergraduate level in stochastic processes, probability and statistics, and evolutionary computation. Dr. Fogel is a prolific author in evolutionary computation, having published over 50 journal papers, as well as 100 conference publications, 20 contributions in book chapters, two videos, four computer games, and six books--most recently, Blondie24: Playing at the Edge of AI (Morgan Kaufmann, 2002). In addition, Dr. Fogel is coeditor in chief of the Handbook of Evolutionary Computation (Oxford, 1997) and was the founding editor-in-chief of the IEEE Transactions on Evolutionary Computation (1996-2002). He serves as editor-in-chief for the journal BioSystems and is a member of the editorial board of several other international technical journals. Dr. Fogel served as a Visiting Fellow of the Australian Defence Force Academy in November 1997, and is a member of many professional societies including the American Association for the Advancement of Science, the American Association for Artificial Intelligence, Sigma Xi, and the New York Academy of Sciences. He was the founding president of the Evolutionary Programming Society in 1991 and is a Fellow of the IEEE, as well as an associate member of the Center for the Study of Evolution and the Origin of Life (CSEOL) at the University of California at Los Angeles. Dr. Fogel is a frequently invited lecturer at international conferences and a guest for television and radio broadcasts. His honors and awards include the 2001 Sigma Xi Southwest Region Young Investigator Award, the 2003 Sigma Xi San Diego Section Distinguished Scientist Award, the 2003 SPIE Computational Intelligence Pioneer Award, and the 2004 IEEE Kiyo Tomiyasu Technical Field Award.

Preface to the Third Edition.

Preface to the Second Edition.

Preface to the First Edition.

1 Defining Artificial Intelligence.

1.1 Background.

1.2 The Turing Test.

1.3 Simulation of Human Expertise.

1.3.1 Samuel's Checker Program.

1.3.2 Chess Programs.

1.3.3 Expert Systems.

1.3.4 A Criticism of the Expert Systems or Knowledge-BasedApproach.

1.3.5 Fuzzy Systems.

1.3.6 Perspective on Methods Employing Specific Heuristics.

1.4 Neural Networks.

1.5 Definition of Intelligence.

1.6 Intelligence, the Scientific Method, and Evolution.

1.7 Evolving Artificial Intelligence.

References.

Chapter 1 Exercises.

2 Natural Evolution.

2.1 The Neo-Darwinian Paradigm.

2.2 The Genotype and the Phenotype: The Optimization ofBehavior.

2.3 Implications of Wright's Adaptive Topography:Optimization Is Extensive Yet Incomplete.

2.4 The Evolution of Complexity: Minimizing Surprise.

2.5 Sexual Reproduction.

2.6 Sexual Selection.

2.7 Assessing the Beneficiary of Evolutionary Optimization.

2.8 Challenges to Neo-Darwinism.

2.8.1 Neutral Mutations and the Neo-Darwinian Paradigm.

2.8.2 Punctuated Equilibrium.

2.9 Summary.

References.

Chapter 2 Exercises.

3 Computer Simulation of Natural Evolution.

3.1 Early Speculations and Specific Attempts.

3.1.1 Evolutionary Operation.

3.1.2 A Learning Machine.

3.2 Artificial Life.

3.3 Evolutionary Programming.

3.4 Evolution Strategies.

3.5 Genetic Algorithms.

3.6 The Evolution of Evolutionary Computation.

References.

Chapter 3 Exercises.

4 Theoretical and Empirical Properties of EvolutionaryComputation.

4.1 The Challenge.

4.2 Theoretical Analysis of Evolutionary Computation.

4.2.1 The Framework for Analysis.

4.2.2 Convergence in the Limit.

4.2.3 The Error of Minimizing Expected Losses in SchemaProcessing.

4.2.3.1 The Two-Armed Bandit Problem.

4.2.3.2 Extending the Analysis for "Optimally"Allocating Trials.

4.2.3.3 Limitations of the Analysis.

4.2.4 Misallocating Trials and the Schema Theorem in thePresence of Noise.

4.2.5 Analyzing Selection.

4.2.6 Convergence Rates for Evolutionary Algorithms.

4.2.7 Does a Best Evolutionary Algorithm Exist?

4.3 Empirical Analysis.

4.3.1 Variations of Crossover.

4.3.2 Dynamic Parameter Encoding.

4.3.3 Comparing Crossover to Mutation.

4.3.4 Crossover as a Macromutation.

4.3.5 Self-Adaptation in Evolutionary Algorithms.

4.3.6 Fitness Distributions of Search Operators.

4.4 Discussion.

References.

Chapter 4 Exercises.

5 Intelligent Behavior.

5.1 Intelligence in Static and Dynamic Environments.

5.2 General Problem Solving: Experiments with Tic-Tac-Toe.

5.3 The Prisoner's Dilemma: Coevolutionary Adaptation.

5.3.1 Background.

5.3.2 Evolving Finite-State Representations.

5.4 Learning How to Play Checkers without Relying on ExpertKnowledge.

5.5 Evolving a Self-Learning Chess Player.

5.6 Discussion.

References.

Chapter 5 Exercises.

6 Perspective.

6.1 Evolution as a Unifying Principle of Intelligence.

6.2 Prediction and the Languagelike Nature of Intelligence.

6.3 The Misplaced Emphasis on Emulating Genetic Mechanisms.

6.4 Bottom-Up Versus Top-Down.

6.5 Toward a New Philosophy of Machine Intelligence.

References.

Chapter 6 Exercises.

Glossary.

Index.

About the Author.

"...a major contribution to the evolutionary computation literature...recommended reading for experienced researchers, as well as novice students..." (Computing Reviews.com, May 26, 2006)