Foreword	5
	Preface	8
	Acknowledgments	8
	Contents	10
	List of Contributors	18
	Chapter 1 Introduction	22
	1.1 Optimization Algorithms	22
	1.2 Analysis of Algorithms	24
	1.2.1 Theoretical Analysis	24
	1.2.2 Experimental Analysis	24
	1.3 Bridging the Gap Between Theoretical and Empirical Analysis	26
	1.4 The Need for Statistics	28
	1.5 Book Contents	29
	References	33
	Part I Overview	35
	Chapter 2 The Future of Experimental Research	36
	2.1 Introduction	36
	2.2 Experimental Goals in Computer Science	38
	2.2.1 Improving the Performance	39
	2.2.2 Understanding	40
	2.3 Problems	40
	2.3.1 Problems Related to the Experimental Setup	41
	2.3.2 Problems Related to the Significance of Experimental Results	41
	2.3.3 Problems Related to High-Level Theory	44
	2.4 The New Experimentalism	46
	2.5 Experimental Models	47
	2.5.1 The Role of Models in Science	47
	2.5.2 Representational Models	48
	2.5.3 A Framework of Models	49
	2.5.4 Mayo’s Learning Model	51
	2.5.5 Sequential Parameter Optimization	53
	2.5.6 The Large n Problem Revisited	57
	2.6 Pitfalls of Experimentation with Randomized Algorithms	57
	2.6.1 Floor and Ceiling Effects	58
	2.6.2 Confounded Effects	59
	2.6.3 Fairness in Parameter Settings	59
	2.6.4 Failure Reasons and Prevention	60
	2.7 Tools: Measures and Reports	61
	2.7.1 Measures	61
	2.7.2 Reporting Experiments	63
	2.8 Methodology, Open Issues, and Development	64
	2.9 Summary	65
	References	66
	Chapter 3 Design and Analysis of Computational Experiments: Overview	69
	3.1 Introduction	69
	3.2 Classic Designs and Metamodels	72
	3.3 Screening: Sequential Bifurcation	75
	3.4 Kriging	76
	3.4.1 The Kriging Predictor Variance	78
	3.4.2 Designs for Kriging	79
	3.5 Optimization	81
	3.5.1 Response Surface Methodology (RSM)	81
	3.5.2 Kriging and Mathematical Programming	83
	3.5.3 Taguchian Robust Optimization	85
	3.6 Conclusions	87
	References	88
	Chapter 4 The Generation of Experimental Data for Computational Testing in Optimization	91
	4.1 Introduction	91
	4.2 A Protocol	94
	4.2.1 Generation Principles and Properties	96
	4.2.2 Features of the Model	99
	4.2.3 Validating the Data	99
	4.3 Applications to Optimization	101
	4.3.1 Generalized Assignment and Knapsack	102
	4.3.2 Supply Chains	103
	4.3.3 Scheduling	105
	4.3.4 Graphs and Networks	106
	4.3.5 Routing	107
	4.3.6 Data Mining	108
	4.3.7 Stochastic Programming	109
	4.3.8 Intractable Problems	110
	4.4 Concluding Remarks	112
	References	112
	Chapter 5 The Attainment-Function Approach to Stochastic Multiobjective Optimizer Assessment and Comparison	120
	5.1 Introduction	120
	5.2 Statistics and the Attainment-Function Approach	122
	5.2.1 Stochastic Optimizers as Statistical Estimators	122
	5.2.2 Optimizer Performance as Statistical Estimator Performance	123
	5.2.3 Performance Assessment via Estimation and Hypothesis Testing	125
	5.3 Multiobjective Optimizer Outcomes	126
	5.3.1 Random Nondominated Point Sets	126
	5.3.2 Alternative View: The Attained Set	126
	5.4 Multiobjective Optimizer Performance	127
	5.4.1 Distribution of a General Random Closed Set: The Capacity Functional	128
	5.4.2 Distribution of a Random Nondominated Point Set: The K-th-Order Attainment Function	128
	5.5 Partial Aspects of Multiobjective Optimizer Performance	130
	5.5.1 Distribution Location: The First-Order Attainment Function	130
	5.5.2 Distribution Spread: The Variance Function	133
	5.5.3 Inter-Point Dependence Structures: Second and Higher-Order Attainment Functions	134
	5.6 Multiobjective Optimizer Performance Assessment: Estimation	136
	5.7 Multiobjective Optimizer Performance Comparison: Hypothesis Testing	138
	5.7.1 Two-Sided Test Problem	139
	5.7.2 Permutation Test Procedure	140
	5.7.3 Multistage Testing	141
	5.7.4 One-Sided Tests	143
	5.8 Discussion and Future Perspectives	144
	References	145
	Chapter 6 Algorithm Engineering: Concepts and Practice	148
	6.1 Why Algorithm Engineering?	148
	6.1.1 Early Days and the Pen-and-Paper Era	149
	6.1.2 Errors	150
	6.2 The Algorithm Engineering Cycle	152
	6.3 Current Topics and Issues	154
	6.3.1 Properties of and Structures in the Input	155
	6.3.2 Large Datasets	156
	6.3.3 Memory Efficiency	157
	6.3.4 Distributed Systems and Parallelism	160
	6.3.5 Approximations and Heuristic Algorithms	161
	6.3.6 Succinct Data Structures	162
	6.3.7 Time-Critical Settings	163
	6.3.8 Robustness	163
	6.4 Success Stories	164
	6.4.1 Shortest Path Computation	164
	6.4.2 Full-Text Indexes	167
	6.5 Summary and Outlook	170
	References	171
	Part II Characterizing Algorithm Performance	176
	Chapter 7 Algorithm Survival Analysis	177
	7.1 Introduction	177
	7.2 Modeling Runtime Distributions	178
	7.2.1 Basic Quantities and Concepts	179
	7.2.2 Censoring	181
	7.2.3 Estimation in Survival Analysis	182
	7.2.4 Competing Risks	185
	7.3 Model-Based Algorithm Selection	187
	7.3.1 RTD of an Algorithm Portfolio	189
	7.3.2 Model-Based Time Allocators	190
	7.3.3 Algorithms as Competing Risks	191
	7.4 Experiments	191
	7.5 Related Work	195
	7.6 Summary and Outlook	196
	References	197
	Chapter 8 On Applications of Extreme Value Theory in Optimization	201
	8.1 Introduction	201
	8.2 Extreme Value Theory	202
	8.2.1 Extreme Value Theory for Minima	202
	8.2.2 Peaks Over Threshold Method (POT) for Minima	205
	8.2.3 Assessment of an Optimizer	207
	8.3 Experiments Using Random Search	208
	8.3.1 Samples with Simulations Near the Optimum	209
	8.3.2 Samples with Simulations Away from the Optimum	210
	8.4 Analytical Results	211
	8.5 Experiments Using Evolution Strategies	215
	8.6 Summary	221
	References	222
	Chapter 9 Exploratory Analysis of Stochastic Local Search Algorithms in Biobjective Optimization	224
	9.1 Introduction	224
	9.2 Stochastic Local Search for Multiobjective Problems	225
	9.3 Examination of the Attainment Surfaces	227
	9.3.1 The eafplot.p1 Program	228
	9.3.2 Example Application of eafplot.p1	229
	9.4 Examining the Differences Between EAFs	230
	9.5 Examples	232
	9.5.1 Effect of Problem Structure	232
	9.5.2 Differences in Algorithmic Performance	233
	9.5.3 Biased Behavior	234
	9.6 Summary and Outlook	235
	References	236
	Part III Algorithm Configuration and Tuning	238
	Chapter 10 Mixed Models for the Analysis of Optimization Algorithms	239
	10.1 Introduction	239
	10.2 Experimental Designs and Statistical Modeling	242
	10.2.1 Case(-,q(-),r): Random-Effects Design	243
	10.2.2 Case (N ,q(-),r):Mixed-Effects Design	247
	10.2.3 Case (-,q(M),r): Nested-Effects Design	250
	10.2.4 Case (N,q(M),r): General Mixed-Effects Design	251
	10.3 An Application Example in Optimization Heuristic Design	254
	10.3.1 Definitions and Problem Formulation	254
	10.3.2 Local Search Algorithms	255
	10.3.3 Problem Instances	256
	10.4 Numerical Examples	256
	10.4.1 Case (-,q(-),r): Random-Effects Design	257
	10.4.2 Case (N ,q(-),r):Mixed-Effects Design	261
	10.4.3 Case (-,q(M),r): Nested Design	270
	10.4.4 Case (N,q(M),r): General Design	272
	10.5 Summary and Outlook	274
	References	276
	Chapter 11 Tuning an Algorithm Using Design of Experiments	279
	11.1 Introduction	279
	11.2 Research Questions Addressed with DOE	280
	11.3 Experiment Designs	280
	11.3.1 Full and 2k Factorial Designs	281
	11.3.2 Fractional Factorial Designs	281
	11.3.3 Response Surface Designs	284
	11.3.4 Efficiency of Fractional Factorial Designs	285
	11.4 Error, Significance, Power, and Replicates	285
	11.5 Benchmarking the Experimental Testbed	286
	11.6 Case Study	287
	11.6.1 Problem Instances	287
	11.6.2 Stopping Criterion	288
	11.6.3 Response Variables	288
	11.6.4 Factors, Levels and Ranges	288
	11.6.5 Model Fitting	291
	11.6.6 Results	293
	11.6.7 Discussion	298
	11.6.8 Summary	299
	References	299
	Chapter 12 Using Entropy for Parameter Analysis of Evolutionary Algorithms	301
	12.1 Introduction and Background	301
	12.2 Evolutionary Algorithms	302
	12.3 EA Design, EA Parameters	305
	12.4 Shannon and Differential Entropy	308
	12.4.1 Using Success Ranges for Relevance Estimation	308
	12.4.2 Shannon Entropy	309
	12.4.3 Using the Shannon Entropy for Relevance Estimation	309
	12.4.4 Differential Entropy	311
	12.4.5 Joint Entropy	312
	12.5 Estimating Entropy	312
	12.5.1 REVAC: the Algorithm	314
	12.5.2 REVAC: the Data Generated	315
	12.6 Case Study	316
	12.6.1 Experimental Setup	317
	12.6.2 Entropy of Parameters	318
	12.6.3 Entropy of Operators	319
	12.6.4 Entropy of EAs	320
	12.7 Conclusions	321
	Acknowledgement	322
	References	322
	Chapter 13 F-Race and Iterated F-Race: An Overview	325
	13.1 Introduction	325
	13.2 The Algorithm Configuration Problem	327
	13.2.1 The Algorithm Configuration Problem	327
	13.2.2 Types of Parameters	329
	13.3 F-Race	330
	13.3.1 The Racing Approach	330
	13.3.2 The Peculiarity of F-Race	331
	13.4 The Sampling Strategy for F-Race	334
	13.4.1 Full Factorial Design	334
	13.4.2 Random Sampling Design	334
	13.4.3 Iterated F-Race	335
	13.4.4 An Example Iterated F-Race Algorithm	337
	13.5 Case Studies	339
	13.5.1 Case Study 1: MMAS under Four Parameters	340
	13.5.2 Case Study 2: MMAS under Seven Parameters	341
	13.5.3 Case Study 3: ACOTSP under 12 Parameters	342
	13.6 A Review of F-RaceApplications	343
	13.7 Summary and Outlook	346
	References	346
	Chapter 14The Sequential Parameter Optimization Toolbox	351
	14.1 Introduction	351
	14.2 Applications	352
	14.2.1 Bioinformatics	352
	14.2.2 Water-Resource Management	353
	14.2.3 Mechanical Engineering	353
	14.2.4 Biogas	353
	14.2.5 Shipbuilding	354
	14.2.6 Fuzzy Operator Trees	354
	14.3 Objectives	354
	14.4 Elements of the SPOT Framework	355
	14.4.1 The General SPOT Scheme	355
	14.4.2 SPOT Tasks	356
	14.4.3 Running SPOT	358
	14.5 Statistical Considerations	359
	14.5.1 Sequential Models	359
	14.5.2 Residuals and Variance	362
	14.5.3 Standardized Variables and Transformations	362
	14.5.4 Design Considerations and the Region of Interest	363
	14.6 A Case Study: Simple Regression Applied to Evolution Strategies	364
	14.6.1 Pre-experimental Planning	364
	14.6.2 Performing the First Regression Analysis	365
	14.6.3 Steepest Descent	368
	14.7 Additional Model Considerations	371
	14.8 The Automated Mode	374
	14.9 Summary	374
	References	375
	Chapter 15 Sequential Model-Based Parameter Optimization: an Experimental Investigation of Automated and Interactive Approaches	377
	15.1 Introduction	378
	15.2 Target Algorithms and Experimental Setup	381
	15.3 Existing Methods for Sequential Model-Based Optimization of Noisy Functions	383
	15.3.1 General Gaussian Process Regression	383
	15.3.2 A Common Framework for Sequential Model-Based Optimization	385
	15.3.3 Empirical Comparison of SKO and SPO	390
	15.4 Model Quality	394
	15.4.1 Choosing the Initial Design	394
	15.4.2 Transforming Performance Data	396
	15.5 Sequential Experimental Design	397
	15.5.1 Intensification Mechanism	398
	15.5.2 Expected Improvement Criterion	405
	15.5.3 Overall Evaluation	407
	15.6 Interactive Exploration of Parameter Space	408
	15.6.1 Using SPOT Interactively	409
	15.6.2 Further Interactive Tuning Results	416
	15.6.3 Comparison of Solutions Found Automatically and Interactively	421
	15.6.4 Discussion of the Interactive Approach	422
	15.7 Conclusions and Future Work	423
	Appendix	424
	References	424
	Appendix	429
	Appendix A A Brief Introduction to Inferential Statistics	430
	A.1 Introduction	430
	A.1.1 Random Variables	432
	A.1.2 Examples of Statistical Models	434
	A.2 Point Estimation	439
	A.3 Hypothesis Testing	444
	A.4 Confidence Intervals	453
	A.5 Regression and Modeling	455
	A.5.1 Linear Regression	455
	A.5.2 Model Fitting	460
	References	463
	Index	465