Experimental Methods for the Analysis of Optimization Algorithms



In operations research and computer science it is common practice to evaluate the performance of optimization algorithms on the basis of computational results, and the experimental approach should follow accepted principles that guarantee the reliability and reproducibility of results. However, computational experiments differ from those in other sciences, and the last decade has seen considerable methodological research devoted to understanding the particular features of such experiments and assessing the related statistical methods.

This book consists of methodological contributions on different scenarios of experimental analysis. The first part overviews the main issues in the experimental analysis of algorithms, and discusses the experimental cycle of algorithm development; the second part treats the characterization by means of statistical distributions of algorithm performance in terms of solution quality, runtime and other measures; and the third part collects advanced methods from experimental design for configuring and tuning algorithms on a specific class of instances with the goal of using the least amount of experimentation. The contributor list includes leading scientists in algorithm design, statistical design, optimization and heuristics, and most chapters provide theoretical background and are enriched with case studies.

This book is written for researchers and practitioners in operations research and computer science who wish to improve the experimental assessment of optimization algorithms and, consequently, their design.

Edited Book

Experimental Methods for the Analysis of Optimization Algorithms, Springer, November 2010

Cited by

Year 2015 : 12 citations

 S Hatami, R Ruiz, C Andrés-Romano
Heuristics and metaheuristics for the distributed assembly permutation flowshop scheduling problem with sequence dependent setup times
International Journal of Production, 2015

 N Xiong, D Molina, ML Ortiz
A Walk into Metaheuristics for Engineering Optimization: Principles, Methods and Recent Trends
International Journal of Computational Intelligence Systems, 2015

 M Drexl, M Schneider
A survey of variants and extensions of the location-routing problem
European Journal of Operational Research, 2015

 J King, S Yarkoni, MM Nevisi, JP Hilton
Benchmarking a quantum annealing processor with the time-to-target metric
arXiv, 2015

 M Preuss
Multimodal Optimization by Means of Evolutionary Algorithms
Springer, 2015

 R Morgan
Analysing and comparing problem landscapes for black-box optimization via length scale
PhD Thesis, School of Information Technology and Electrical Engineering, The University of Queensland, 2015

 R Morgan, M Gallagher
Analysing and characterising optimization problems using length scale
Soft Computing, 2015

 R Nemati-Chari, K Dehghani, A Kami
Application of response surface methodology for study of effective strain in equal channel angular pressing of AA6061 alloy

 Catherine C. McGeoch
Benchmarking D-Wave quantum annealing systems: some challenges
Electro-Optical and Infrared Systems: Technology and Applications XII; and Quantum Information Science and Technology, 2015

 S Wessing
Two-stage methods for multimodal optimization
University of Dortmund, 2015

 MA Wolters
A Genetic Algorithm for Selection of Fixed-Size Subsets with Application to Design Problems
Journal of Statistical Software, 2015

 Kashfi, S. Ruhollah
Towards Evaluation of the Adaptive-Epsilon-R-NSGA-II algorithm (AE-R-NSGA-II) on industrial optimization problems
MSc thesis, University of Skovde

Year 2014 : 10 citations

 B Naderi, R Ruiz, A scatter search algorithm for the distributed permutation flowshop scheduling problem, European Journal of Operational Research, 2014

 F Mascia, M López-Ibáñez, J Dubois-Lacoste, Thomas Stützle, Grammar-based generation of stochastic local search heuristics through automatic algorithm configuration tools, Computers & Operations Research, 2014

 S Cai, K Su, C Luo, A Sattar, NuMVC: An efficient local search algorithm for minimum vertex cover, ArXIV, 2014

 M Drexl, M Schneider,A survey of variants and extensions of the location-routing problem, European Journal of Operational Research, 2014

 M Drexl, M Schneider, A Survey of the Standard Location-Routing Problem, Working paper LPIS-03/2014, TU-Darmstadt, 2014

 E Segredo, C Segura, C León, E Hart, A fuzzy logic controller applied to a diversity-based multi-objective evolutionary algorithm for single-objective optimisation, Soft Computing, 2014

 S Lee, Dynamic Resource Allocation in Human-Centered Service Robot Applications, Laser and Photonic Systems: Design and Integration, 2014

 MC Dhaenens, Caractérisation des instances difficiles de problèmes d'optimisation NP-difficiles, Université de Grenoble.

 S. Lee, Role of Parallelism in Ambulance Dispatching, IEEE Transactions on Systems, Man, and Cybernetics: Systems, Volume:44 Issue:8, 2014

 MS Pais, Estudo da Influência dos Parâmetros de Algoritmos Paralelos da Computaçao Evolutiva no seu Desempenho em Plataformas Multicore, PhD Thesis

Year 2013 : 11 citations

 Carlos Andujar, Viola Schiaffonati, Fabio A. Schreiber, Letizia Tanca, Matti Tedre, Kees van Hee, Jan van Leeuwen, The Role and Relevance of Experimentation in Informatics, Workshop on the Role and Relevance of Experimentation in
Informatics, 2013

 Kjetil Kjernsmo, John S. Tyssedal, Introducing Statistical Design of Experiments to SPARQL Endpoint Evaluation, The Semantic Web – ISWC 2013, Lecture Notes in Computer Science Volume 8219, pp 360-375, 2013

 Iftikhar Ahmad, Analysis of algorithms for online uni-directional conversion problem, PhD thesis, Universität des Saarlandes, Germany

 Leo Lopes, Kate Smith-Miles, Generating Applicable Synthetic Instances for Branch Problems, Operations Research, 61(3), 563-577, 2013

 S Cai, K Su, C Luo, A Sattar, Journal of Artificial Intelligence Research, NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover,Volume 46, pages 687-716, 2013

 HJC Barbosa, HS Bernardino, AMS Barreto, Using Performance Profiles for the Analysis and Design of Benchmark Experiments, Advances in Metaheuristics, Springer, 2013

 IG del Amo, DA Pelta, SRCS: a technique for comparing multiple algorithms under several factors in dynamic optimization problems, Metaheuristics for Dynamic Optimization, Springer, 2013

 Laura Cruz-Reyes, Claudia Gómez-Santillán, Norberto Castillo-García, Marcela Quiroz, Alberto Ochoa, Paula Hernández-Hernández , A Visualization Tool for Heuristic Algorithms Analysis, 7th International Conference on Knowledge Management in Organizations: Service and Cloud Computing Advances in Intelligent Systems and Computing Volume 172, 2013, pp 515-524

 S. Meyer-Nieberg, E. Kropat, S. Pickl, A. Bordetsky, Intercepting a Target with Sensor Swarms, 46th Hawaii International Conference on System Sciences (HICSS), IEEE press, 1222 - 1230, 2013

 Palupi Diah Kusuma, Extending traditional telecom churn prediction using social network data, Internal Report 2013–03,Universiteit Leiden Computer Science, 2013

 Kuo-Hao Chang, L. Jeff Hong ( and Hong Wan, Stochastic Trust-Region Response-Surface Method (STRONG)—A New Response-Surface Framework for Simulation Optimization, INFORMS Journal on Computing, vol. 25 no. 2 230-243, 2013

Year 2012 : 8 citations

 Florian Siegmund, Jacob Bernedixen, Leif Pehrsson, Amos H.C. Ng, Kalyanmoy Deb, Reference Point-Based Evolutionary Multi-Objective Optimization for Industrial Systems Simulation, Proceedings of the 2012 Winter Simulation Conference, 2012

 KH Chang, LJ Hong, H Wan, Stochastic Trust-Region Response-Surface Method (STRONG)—A New Response-Surface Framework for Simulation Optimization, INFORMS Journal on Computing, 2012

 N. Beume, Hypervolume based metaheuristics for multiobjective optimization, PhD thesis, Technical University of Dortmund, 2012.

 Morgan R, Gallagher M., Using Landscape Topology to Compare Continuous Metaheuristics: A Framework and Case Study on EDAs and Ridge Structure, Evolutionary Computation, 2012 (to appear)

 Marco Gavanelli, Maddalena Nonato, Andrea Peano, Stefano Alvisi, Marco Franchini:
Genetic Algorithms for Scheduling Devices Operation in a Water Distribution System in Response to Contamination Events. Evolutionary Computation in Combinatorial Optimization - 12th European Conference, EvoCOP 2012, LNCS 7245, Springer, 124-135,2012.

 Wahabou Abdou, Christelle Bloch, Damien Charlet, François Spies: Adaptive multi-objective genetic algorithm using multi-pareto-ranking, Proceedings of the fourteenth international conference on Genetic and evolutionary computation, 2012

 Wahabou Abdou, Christelle Bloch, Damien Charlet, François Spies:
Multi-Pareto-Ranking Evolutionary Algorithm. Evolutionary Computation in Combinatorial Optimization - 12th European Conference, EvoCOP 2012, LNCS 7245, Springer, 194-205, 2012.

 Catherine Mc Geoch, A guide to experimental algorithmics, Cambridge Press, 2012.

Year 2011 : 4 citations

 Eiben A. E. and Smit S. K., Evolutionary Algorithm Parameters and Methods to Tune them , Y. Hamadi E. Monfroy and Saubion F. (eds.) , Autonomous Search , Springer , 2011

 Christian Blum, Jakob Puchinger, Günther Raidl and Andrea Roli, Hybrid Metaheuristics, Hybrid Optimization, Springer Optimization and Its Applications, Volume 45, 305-335, 2011

 Christian Blum, Jakob Puchinger, Günther R. Raidl, Andrea Roli: Hybrid metaheuristics in combinatorial optimization: A survey. Appl. Soft Comput. 11(6): 4135-4151, 2011

 A. Davtyan, S. Hoffmann, R. Scheuring, Optimization of model predictive control by means of sequential parameter optimization, IEEE Symposium on Computational Intelligence in Control and Automation (CICA), pp 11-16, 2011

Year 2010 : 1 citations

 Manuel López-Ibáñez, Thomas Stützle, Automatic configuration of multi-objective ACO algorithms, Proceedings of the 7th international conference on Swarm intelligence, LNCS 6234, 95-106, 2011