Experimental Research in Evolutionary Computation

by Bartz-beielstein, Thomas

• ISBN13: 9783540320265
• ISBN10: 3540320261
• Format: Hardcover
• Copyright: 2006-04-15
• Publisher: Springer-Verlag New York Inc

Summary

Experimentation is necessary - a purely theoretical approach is not reasonable. The new experimentalism, a development in the modern philosophy of science, considers that an experiment can have a life of its own. It provides a statistical methodology to learn from experiments, where the experimenter should distinguish between statistical significance and scientific meaning. This book introduces the new experimentalism in evolutionary computation, providing tools to understand algorithms and programs and their interaction with optimization problems. The book develops and applies statistical techniques to analyze and compare modern search heuristics such as evolutionary algorithms and particle swarm optimization. Treating optimization runs as experiments, the author offers methods for solving complex real-world problems that involve optimization via simulation, and he describes successful applications in engineering and industrial control projects. The book bridges the gap between theory and experiment by providing a self-contained experimental methodology and many examples, so it is suitable for practitioners and researchers and also for lecturers and students. It summarizes results from the author's consulting to industry and his experience teaching university courses and conducting tutorials at international conferences. The book will be supported online with downloads and exercises.

Table of Contents

Part I Basics
1 Research in Evolutionary Computation	3	(10)
1.1 Research Problems	3	(1)
1.2 Background	4	(4)
1.2.1 Effective Approaches	5	(1)
1.2.2 Meta-Algorithms	6	(1)
1.2.3 Academic Approaches	6	(1)
1.2.4 Approaches with Different Goals	7	(1)
1.3 Common Grounds: Optimization Runs Treated as Experiments	8	(2)
1.3.1 Wind Tunnels	9	(1)
1.3.2 The New Experimentalism	10	(1)
1.4 Overview of the Remaining Chapters	10	(3)
2 The New Experimentalism	13	(28)
2.1 Demonstrating and Understanding	13	(4)
2.1.1 Why Do We Need Experiments in Computer Science?	14	(3)
2.1.2 Important Research Questions	17	(1)
2.2 Experimental Algorithmics	17	(2)
2.2.1 Preexperimental Planning	17	(1)
2.2.2 Guidelines from Experimental Algorithmics	18	(1)
2.3 Observational Data and Noise	19	(1)
2.4 Models	20	(1)
2.5 The New Experimentalism	21	(15)
2.5.1 Mayo's Models of Statistical Testing	23	(1)
2.5.2 Neyman–Pearson Philosophy	23	(3)
2.5.3 The Objectivity of NPT: Problems and Misunderstandings	26	(1)
2.5.4 The Objectivity of NPT: Defense and Understanding	27	(8)
2.5.5 Related Approaches	35	(1)
2.6 Popper and the New Experimentalists	36	(2)
2.7 Summary	38	(1)
2.8 Further Reading	39	(2)
3 Statistics for Computer Experiments	41	(24)
3.1 Hypothesis Testing	42	(3)
3.1.1 The Two-Sample z-Test	42	(1)
3.1.2 The Two-Sample t-Test	43	(1)
3.1.3 The Paired t-Test	44	(1)
3.2 Monte Carlo Simulations	45	(3)
3.3 DOE: Standard Definitions	48	(1)
3.4 The Analysis of Variance	48	(1)
3.5 Linear Regression Models	49	(2)
3.6 Graphical Tools	51	(4)
3.6.1 Half-Normal Plots	51	(1)
3.6.2 Design Plots	51	(1)
3.6.3 Interaction Plots	51	(2)
3.6.4 Box Plots	53	(1)
3.6.5 Scatter Plots	53	(1)
3.6.6 Trellis Plots	54	(1)
3.7 Tree-Based Methods	55	(4)
3.8 Design and Analysis of Computer Experiments	59	(3)
3.8.1 The Stochastic Process Model	59	(1)
3.8.2 Regression Models	59	(1)
3.8.3 Correlation Models	60	(1)
3.8.4 Effects and Interactions in the Stochastic Process Model	61	(1)
3.9 Comparison	62	(1)
3.10 Summary	63	(1)
3.11 Further Reading	64	(1)
4 Optimization Problems	65	(14)
4.1 Problems Related to Test Suites	66	(1)
4.2 Test Functions	67	(2)
4.2.1 Test Function for Schwefel's Scenario 1 and 2	67	(1)
4.2.2 Test Functions for Schwefel's Scenario 2	67	(2)
4.2.3 Test Function for Schwefel's Scenario 3	69	(1)
4.3 Elevator Group Control	69	(7)
4.3.1 The Elevator Supervisory Group Controller Problem	69	(3)
4.3.2 A Simplified Elevator Group Control Model: The S-Ring	72	(3)
4.3.3 The S-Ring Model as a Test Generator	75	(1)
4.4 Randomly Generated Test Problems	76	(1)
4.5 Recommendations	77	(1)
4.6 Summary	77	(1)
4.7 Further Reading	77	(2)
5 Designs for Computer Experiments	79	(14)
5.1 Computer Experiments	80	(1)
5.2 Classical Algorithm Designs	81	(3)
5.3 Modern Algorithm Designs	84	(2)
5.4 Sequential Algorithm Designs	86	(1)
5.5 Problem Designs	87	(3)
5.5.1 Initialization	87	(2)
5.5.2 Termination	89	(1)
5.6 Discussion: Designs for Computer Experiments	90	(1)
5.6.1 Problems Related to Classical Designs	90	(1)
5.6.2 Problems Related to Modern Designs	90	(1)
5.7 Recommendations	90	(1)
5.8 Summary	91	(1)
5.9 Further Reading	92	(1)
6 Search Algorithms	93	(12)
6.1 Deterministic Optimization Algorithms	93	(2)
6.1.1 Nelder and Mead	93	(1)
6.1.2 Variable Metric	94	(1)
6.2 Stochastic Search Algorithms	95	(5)
6.2.1 The Two-Membered Evolution Strategy	95	(1)
6.2.2 Multimembered Evolution Strategies	96	(2)
6.2.3 Particle Swarm Optimization	98	(2)
6.3 Summary	100	(1)
6.4 Further Reading	101	(4)
Part II Results and Perspectives
7 Comparison	105	(40)
7.1 The Fiction of Optimization	106	(2)
7.2 Performance Measures	108	(11)
7.2.1 Scenarios	109	(1)
7.2.2 Effectivity or Robustness	110	(1)
7.2.3 Efficiency	111	(7)
7.2.4 How to Determine the Maximum Number of Iterations	118	(1)
7.3 The Classical DOE Approach	119	(6)
7.3.1 A Three-Stage Approach	119	(1)
7.3.2 Tuning an Evolution Strategy	120	(5)
7.4 Design and Analysis of Computer Experiments	125	(1)
7.5 Sequential Parameter Optimization	126	(3)
7.6 Experimental Results	129	(10)
7.6.1 Optimizing the PSO Inertia Weight Variant	129	(6)
7.6.2 Optimizing the PSO Constriction Factor Variant	135	(3)
7.6.3 Comparing Particle Swarm Variants	138	(1)
7.6.4 Optimizing the Nelder—Mead Simplex Algorithm and a Quasi-Newton Method	138	(1)
7.7 Experimental Results for the S-Ring Model	139	(2)
7.8 Criteria for Comparing Algorithms	141	(1)
7.9 Summary	142	(1)
7.10 Further Reading	143	(2)
8 Understanding Performance	145	(30)
8.1 Selection Under Uncertainty	145	(8)
8.1.1 A Survey of Different Selection Schemes	146	(1)
8.1.2 Indifference Zone Approaches	147	(1)
8.1.3 Subset Selection	148	(2)
8.1.4 Threshold Selection	150	(3)
8.1.5 Sequential Selection	153	(1)
8.2 Case Study I: How to Implement the (1 + 1)-ES	153	(10)
8.2.1 The Problem Design Sphere I	155	(8)
8.3 Case Study II: The Effect of Thresholding	163	(8)
8.3.1 Local Performance	163	(8)
8.4 Bounded Rationality	171	(2)
8.5 Summary	173	(1)
8.6 Further Reading	173	(2)
9 Summary and Outlook	175	(10)
9.1 The New Experimentalists	175	(1)
9.2 Learning from Error	176	(3)
9.3 Theory and Experiment	179	(2)
9.4 Outlook	181	(4)
References	185	(18)
Index	203	(8)
Nomenclature	211