Selected Bibliography on Experimental Methods for the Analysis of Search and Optimization Algorithms

The articles included in this bibliography focus on methdological aspects of experimental analysis on algorithms for search and optimization.
Publications are organized in the following categories.

If opportune a publication may appear in more than one category. Entries follow a reverse date order. The list does not aim to be exhaustive. Moreover, published examples of experimental research on algorithms are not included.
Last update: April 2009


Philosophical

A. Newell, H. A. Simon (2007). Computer science as empirical inquiry: symbols and search. In ACM Turing award lectures, ACM, New York, NY, USA. [ DOI ]

T. Bartz-Beielstein (2006). Experimental Research in Evolutionary Computation - The New Experimentalism. Natural Computing Series, Springer, Berlin. [ DOI ]

P. J. Denning (2005). Is computer science science?. Communications of the ACM, vol. 48, no. 4. [ DOI ]

B. Moret (2002). Towards a discipline of experimental algorithmics. In M. H. Goldwasser, D. S. Johnson, C. C. McGeoch (Eds.), Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges, vol. 59 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 197-213, American Mathematical Society, Providence, RI, USA.

R. Fleischer, B. Moret, E. M. Schmidt (Eds.) (2002). Experimental Algorithmics: From Algorithm Design to Robust and Efficient Software, vol. 2547 of Lecture Notes in Computer Science. Springer Verlag, Berlin, Germany, Berlin, Germany.

C. Demetrescu, G. F. Italiano (2000). What do we learn from experimental algorithmics?. In M. Nielsen, B. Rovan (Eds.), MFCS, vol. 1893 of Lecture Notes in Computer Science, pp. 36-51, Springer Verlag, Berlin, Germany, Berlin.

W. Tichy (1998). Should computer scientists experiment more?. Computer, vol. 31, no. 5, pp. 32-40. [ DOI ]

J. N. Hooker (1996). Needed: An empirical science of algorithms. Operations Research, vol. 42, no. 2, pp. 201-212.

J. N. Hooker (1996). Testing heuristics: We have it all wrong. Journal of Heuristics, vol. 1, pp. 32-42.

C. C. McGeoch (1996). Toward an experimental method for algorithm simulation. INFORMS Journal on Computing, vol. 8, no. 1, pp. 1-15. This journal issue contains also commentaries by Pierre L'Ecuyer, James B. Orlin and Douglas R. Shier, and a rejoinder by C. McGeoch. [ DOI ]

P. J. Denning (1981). Performance evaluation: Experimental computer science at its best. In Proceedings of the 1981 ACM SIGMETRICS conference on Measurement and modeling of computer systems, ACM.



Algorithm Engineering

C. Demetrescu, I. Finocchi, G. Italiano (2004). Algorithm engineering. In A. G.Paun, G.Rozemberg (Ed.), Current Trends in Theoretical Computer Science: the Challenge of the New Century, vol. 1: Algorithms and Complexity, World Scientific Publishing.

D. Bader, B. Moret, P. Sanders (2002). In Algorithm Engineering for Parallel Computation, pp. 1-23. [ DOI ]

P. Sanders (2002). Presenting data from experiments in algorithmics. In Experimental Algorithmics - From Algorithm Design to Robust and Efficient Software,, vol. 2547 of LNCS, pp. 181-196, Springer. [ DOI ]

K. Weihe (2001). A software engineering perspective on algorithmics. ACM Computing Surveys, vol. 33, no. 1, pp. 89-134.



Plannig Experiments

M. Birattari, M. Dorigo (2007). How to assess and report the performance of a stochastic algorithm on a benchmark problem:. Optimization Letters, vol. 1, no. 3, pp. 309-311. [ DOI ]

M. Chiarandini, L. Paquete, M. Preuss, E. Ridge (2007). Experiments on metaheuristics: Methodological overview and open issues. Tech. Rep. DMF-2007-03-003, The Danish Mathematical Society. [ http ]

H. Bast, I. Weber (2005). Don't compare averages. In S. E. Nikoletseas (Ed.), Experimental and Efficient Algorithms, 4th InternationalWorkshop, WEA 2005, vol. 3503 of Lecture Notes in Computer Science, pp. 67-76, Springer, Santorini Island, Greece, May 10-13, 2005, Proceedings. [ DOI ]

M. Birattari (2004). On the estimation of the expected performance of a metaheuristic on a class of instances. How many instances, how many runs?. Tech. Rep. TR/IRIDIA/2004-01, IRIDIA, Université Libre de Bruxelles, Brussels, Belgium.

D. S. Johnson (2002). A theoretician's guide to the experimental analysis of algorithms. In M. H. Goldwasser, D. S. Johnson, C. C. McGeoch (Eds.), Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges, vol. 59 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 215-250, American Mathematical Society, Providence, RI, USA.

J. M. Hoenig, D. M. Heisey (2001). The abuse of power: The pervasive fallacy of power calculations for data analysis. The American Statistician, vol. 55, pp. 19-24.

R. K. Ahuja, J. B. Orlin (1996). Use of representative operation counts in computational testing of alg orithms. INFORMS JOURNAL ON COMPUTING, vol. 8, no. 3, pp. 318-330. [ DOI | arXiv | http ]

C. C. McGeoch (1996). Toward an experimental method for algorithm simulation. INFORMS Journal on Computing, vol. 8, no. 1, pp. 1-15. This journal issue contains also commentaries by Pierre L'Ecuyer, James B. Orlin and Douglas R. Shier, and a rejoinder by C. McGeoch. [ DOI ]

R. Barr, B. Golden, J. Kelly, M. Resende, W. Stewart (1995). Designing and reporting on computational experiments with heuristic methods. Journal of Heuristics, vol. 1, no. 1, pp. 9-32. [ DOI ]

P. R. Cohen (1995). Empirical Methods for Artificial Intelligence. MIT Press, Boston.

R. S. Barr, B. L. Hickman (1993). Reporting computational experiments with parallel algorithms: Issues, measures, and experts' opinions. ORSA Journal on Computing, vol. 5, no. 1.

L. A. Crowl (1993). Guidelines for presenting parallel performance. Tech. Rep. 92-80-07, Computer Science Department, Oregon State University, Corvallis, OR, USA.

C. C. McGeoch (1992). Analyzing algorithms by simulation: Variance reduction techniques and simulation speedups. ACM Computing Surveys, vol. 24, no. 2, pp. 195-212.

R. H. Jackson, P. T. Boggs, S. G. Nash, S. Powell (1991). Guidelines for reporting results of computational experiments. report of the ad hoc commitee. Mathematical Programming, vol. 49, pp. 413-425.

H. J. Greenberg (1990). Computational testing: Why, how and how much. INFORMS JOURNAL ON COMPUTING, vol. 2, no. 1, pp. 94-97. [ DOI | arXiv | http ]

B. L. Golden, A. A. Assad, E. A. Wasil, E. Baker (1986). Experimentation in optimization. European Journal of Operational Research, vol. 27, no. 1, pp. 1-16. [ http ]



Instance Generation

F. Brglez, X. Li, M. Stallmann (2005). On sat instance classes and a method for reliable performance experiments with sat solvers. Annals of Mathematics and Artificial Intelligence, vol. 43, no. 1, pp. 1-34. [ DOI ]

H. E. Romeijn, D. R. Morales (2001). Generating Experimental Data for the Generalized Assignment Problem, vol. 49. INFORMS. [ http ]

D. Achlioptas, C. P. Gomes, H. A. Kautz, B. Selman (2000). Generating satisfiable problem instances. In Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on on Innovative Applications of Artificial Intelligence, pp. 256-261, AAAI Press/The MIT Press.

R. D. Babayev (1987). Generation of covering and partition test problems. USSR Computational Mathematics and Mathematical Physics, vol. 27, no. 5, pp. 47-54. [ http ]

B. W. Y. Lin, R. L. Rardin (1977). Development of a parametric generating procedure for integer programming test problems. Journal of the ACM, vol. 24, no. 3, pp. 465-472. [ http ]



Experimental Design (DoE, ANOVA)

E. Ridge, D. Kudenko (2008). Determining whether a problem characteristic affects heuristic performance. In Recent Advances in Evolutionary Computation for Combinatorial Optimization, vol. 153 of Studies in Computational Intelligence, pp. 21-35, Springer. [ DOI ]

D. Basso, M. Chiarandini, L. Salmaso (2007). Synchronized permutation tests in IxJ designs. Journal of Statistical Planning and Inference, vol. 137, no. 8, pp. 2564-2578. [ DOI ]

L. Paquete, T. Stützle, M. López-Ibáñez (2007). Using experimental design to analyze stochastic local search algorithms for multiobjective problems. pp. 325-344. [ DOI ]

E. Ridge, D. Kudenko (2007). Analyzing heuristic performance with response surface models: prediction, optimization and robustness. In H. Lipson (Ed.), Proceedings of GECCO, pp. 150-157, ACM.

E. Ridge, D. Kudenko (2007). Screening the parameters affecting heuristic performance. In H. Lipson (Ed.), Proceedings of GECCO, p. 180, ACM.

J. P. C. Kleijnen, S. M. Sanchez, T. W. Lucas, T. M. Ci oppa (2005). State-of-the-art review: A user's guide to the brave new world of desi gning simulation experiments. INFORMS JOURNAL ON COMPUTING, vol. 17, no. 3, pp. 263-289. [ DOI ]

A. Czarn, C. MacNish, K. Vijayan, B. Turlach, R. Gupta (2004). Statistical exploratory analysis of genetic algorithms. Evolutionary Computation, IEEE Transactions on, vol. 8, no. 4, pp. 405-421. [ DOI ]

P. Castillo-Valdivieso, J. Merelo, A. Prieto, I. Rojas, G. Romero (2002). Statistical analysis of the parameters of a neuro-genetic algorithm. Neural Networks, IEEE Transactions on, vol. 13, no. 6, pp. 1374-1394. [ DOI ]

I. Rojas, J. Gonzalez, H. Pomares, J. Merelo, P. Castillo, G. Romero (2002). Statistical analysis of the main parameters involved in the design of a genetic algorithm. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on, vol. 32, no. 1, pp. 31-37. [ DOI ]

R. L. Rardin, R. Uzsoy (2001). Experimental evaluation of heuristic optimization algorithms: A tutorial. Journal of Heuristics, vol. 7, no. 3, pp. 261-304. [ DOI ]

O. François, C. Lavergne (2001). Design of evolutionary algorithms-a statistical perspective. Evolutionary Computation, IEEE Transactions on, vol. 5, no. 2, pp. 129-148. [ DOI ]

M. Coffin, M. J. Saltzman (2000). Statistical analysis of computational tests of algorithms and heuristics. INFORMS Journal on Computing, vol. 12, no. 1, pp. 24-44.

B. W. Lin, R. L. Rardin (1979). Controlled experimental design for statistical comparison of integer programming algorithms. Management Science, vol. 25, no. 12, pp. 1258-1271. [ http ]

B. W. Y. Lin, R. L. Rardin (1977). Development of a parametric generating procedure for integer programming test problems. Journal of the ACM, vol. 24, no. 3, pp. 465-472. [ http ]

S. H. Zanakis (1977). Heuristic 0-1 linear programming: An experimental comparison of three methods. Management Science, vol. 24, no. 1, pp. 91-104. [ http ]



Configuration and Tuning

M. Birattari (2009). Tuning Metaheuristics, A Machine Learning Perspective, vol. 197 of Studies in Computational Intelligence. Springer. [ DOI ]

J. Dréo (2009). Using performance fronts for parameter setting of stochastic metaheuristics. In F. Rothlauf (Ed.), Genetic and Evolutionary Computation Conference, GECCO 2009, Proceedings, pp. 2197-2200, ACM. Studies the performance of optimizers from both solution-quality and run-time from a multiobjective optimization perspective. Performance front of nondominated configurations attained by evolutionary algorithm for multiobjective optimization. Mainly aimed at parameter tuning. Tests on asymptotic metaheuristics for continous optimization. Estimates medians of several runs. Uses idle iterations for stopping. Done on one single instance. Evolutionary algorithm used to select the parameters to test. [ DOI ]

P. Balaprakash, M. Birattari, T. Stützle (2007). Improvement strategies for the f-race algorithm: Sampling design and iterative refinement. In T. Bartz-Beielstein, M. J. B. Aguilera, C. Blum, B. Naujoks, A. Roli, G. Rudolph, M. Sampels (Eds.), Hybrid Metaheuristics, vol. 4771 of Lecture Notes in Computer Science, pp. 108-122, Springer.

E. Ridge, D. Kudenko (2007). Analyzing heuristic performance with response surface models: prediction, optimization and robustness. In H. Lipson (Ed.), Proceedings of GECCO, pp. 150-157, ACM.

E. Ridge, D. Kudenko (2007). Screening the parameters affecting heuristic performance. In H. Lipson (Ed.), Proceedings of GECCO, p. 180, ACM.

F. G. Lobo, C. F. Lima, Z. Michalewicz (Eds.) (2007). Parameter Setting in Evolutionary Algorithms, vol. 54 of Studies in Computational Intelligence. Springer.

B. Adenso-Díaz, M. Laguna (2006). Fine-tuning of algorithms using fractional experimental designs and local search. Operations Research, vol. 54, no. 1, pp. 99-114.

T. Bartz-Beielstein (2006). Experimental Research in Evolutionary Computation - The New Experimentalism. Natural Computing Series, Springer, Berlin. [ DOI ]

B. Yuan, M. Gallagher (2004). Statistical racing techniques for improved empirical evaluation of evolutionary algorithms. In X. Y. et al. (Ed.), Parallel Problem Solving from Nature - PPSN VIII, 8th International Conference, Birmingham, UK, September 18-22, 2004, Proceedings, vol. 3242 of Lecture Notes in Computer Science, pp. 172-181, Springer Verlag, Berlin, Germany.

M. Birattari, T. Stützle, L. Paquete, K. Varrentrapp (2002). A racing algorithm for configuring metaheuristics. In W. B. Langdon, E. Cantú-Paz, K. Mathias, R. Roy, D. Davis, R. Poli, K. Balakrishnan, V. Honavar, G. Rudolph, J. Wegener, L. Bull, M. Potter, A. Schultz, J. Miller, E. Burke, N. Jonoska (Eds.), Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2002), pp. 11-18, Morgan Kaufmann Publishers, New York.

O. Maron, A. W. Moore (1997). The racing algorithm: Model selection for lazy learners.. Artificial Intelligence Review, vol. 11, no. 1-5, pp. 193-225.



Modelling Algorithm Performance

M. Gagliolo, J. Schmidhuber (2006). Impact of censored sampling on the performance of restart strategies. In F. Benhamou (Ed.), Proceedings of Principles and Practice of Constraint Programming - CP 2006, vol. 4204 of Lecture Notes in Computer Science, pp. 167-181, Springer. [ DOI ]

F. Brglez, X. Li, M. Stallmann (2005). On sat instance classes and a method for reliable performance experiments with sat solvers. Annals of Mathematics and Artificial Intelligence, vol. 43, no. 1, pp. 1-34. [ DOI ]

J. Hüsler, P. Cruz, A. Hall, C. M. Fonseca (2003). On optimization and extreme value theory. Methodology and Computing in Applied Probability, vol. 5, pp. 183-195.

C. McGeoch, P. Sanders, R. Fleischer, P. R. Cohen, D. Precup (2002). Using finite experiments to study asymptotic performance. In R. Fleischer, B. Moret, E. M. Schmidt (Eds.), Experimental Algorithmics: From Algorithm Design to Robust and Efficient Software, vol. 2547 of Lecture Notes in Computer Science, pp. 93-126, Springer Verlag, Berlin, Germany, Berlin, Germany.

H. H. Hoos (2002). A mixture-model for the behaviour of sls algorithms for sat. In Proceedings of the 18th National Conference on Artificial Intelligence (AAAI-02), pp. 661-667, AAAI Press / The MIT Press.

P. Sanders, R. Fleischer (2001). Asymptotic complexity from experiments? a case study for randomized algorithms. In Proceedings of Algorithm Engineering: 4th International Workshop, WAE 2000, vol. 1982 of Lecture Notes in Computer Science, pp. 135-146, Saarbrücken,Germany, September 2000. [ http ]

C. Gomes, B. Selman, N. Crato, H. Kautz (2000). Heavy-tailed phenomena in satisfiability and constraint satisfaction problems. Journal of Automated Reasoning, vol. 24, no. 1-2, pp. 67-100. [ DOI ]

H. H. Hoos, T. Stützle (1998). Evaluating Las Vegas algorithms - pitfalls and remedies. In G. F. Cooper, S. Moral (Eds.), Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI-98), pp. 238-245, Morgan Kaufmann Publishers, San Francisco, CA, USA.

D. Frost, I. Rish, L. Vila (1997). Summarizing CSP hardness with continuous probability distributions.. In Proceedings of AAAI/IAAI, pp. 327-333.

P. Cheeseman, B. Kanefsky, W. M. Taylor (1991). Where the really hard problems are. In J. Mylopoulos, R. Reiter (Eds.), Proceedings of the 12th International Joint Conference on Artificial Intelligence, pp. 331-337, Morgan Kaufmann Publishers, San Francisco, CA, USA.



Multivariate Analysis and Multiobjective

E. Zitzler, J. Knowles, L. Thiele (2008). Quality assessment of pareto set approximations. In Multiobjective Optimization, pp. 373-404, Springer. [ DOI ]

L. Paquete, T. Stützle, M. López-Ibáñez (2007). Using experimental design to analyze stochastic local search algorithms for multiobjective problems. pp. 325-344. [ DOI ]

C. M. Fonseca, V. G. da Fonseca, L. Paquete (2005). Exploring the performance of stochastic multiobjective optimisers with the second-order attainment function. In Evolutionary Multi-Criterion Optimization, pp. 250-264. [ http ]

E. Zitzler, L. Thiele, M. Laumanns, C. M. Fonseca, V. G. da Fonseca (2003). Performance assessment of multiobjective optimizers: an analysis and review.. IEEE Trans. Evolutionary Computation, vol. 7, no. 2, pp. 117-132. [ DOI ]

V. G. da Fonseca, C. M. Fonseca, A. O. Hall (2001). Inferential performance assessment of stochastic optimisers and the attainment function. In C. Coello, D. Corne, K. Deb, L. Thiele, E. Zitzler (Eds.), Proceedings of Evolutionary Multi-Criterion Optimization First International Conference, EMO 2001, vol. 1993 of Lecture Notes in Computer Science, pp. 213-224, Springer Verlag, Berlin, Germany.

C. Fonseca, P. Fleming (1996). On the performance assessment and comparison of stochastic multiobjective optimizers. In Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, Lecture Notes In Computer Science, pp. 584-593, Springer Verlag, Berlin, Germany. [ DOI ]