A number of methodological papers published during the last years testify that a need for a thorough revision of the research methodology is felt by the operations research community - see, for example, [Barr et al., J. Heuristics 1 (1995) 9-32; Eiben and Jelasity, Proceedings of the 2002 Congress on Evolutionary Computation (CEC'2002) 582-587; Hooker, J. Heuristics 1 (1995) 33-42; Rardin and Uzsoy, J. Heuristics 7 (2001) 261-304]. In particular, the performance evaluation of nondeterministic methods, including widely studied metaheuristics such as evolutionary computation and ant colony optimization, requires the definition of new experimental protocols. A careful and thorough analysis of the problem of evaluating metaheuristics reveals strong similarities between this problem and the problem of evaluating learning methods in the machine learning field. In this paper, we show that several conceptual tools commonly used in machine learning - such as, for example, the probabilistic notion of class of instances and the separation between the training and the testing datasets - fit naturally in the context of metaheuristics evaluation. Accordingly, we propose and discuss some principles inspired by the experimental practice in machine learning for guiding the performance evaluation of optimization algorithms. Among these principles, a clear separation between the instances that are used for tuning algorithms and those that are used in the actual evaluation is particularly important for a proper assessment.

@article{ITA_2006__40_2_353_0, author = {Birattari, Mauro and Zlochin, Mark and Dorigo, Marco}, title = {Towards a theory of practice in metaheuristics design : a machine learning perspective}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {353--369}, publisher = {EDP-Sciences}, volume = {40}, number = {2}, year = {2006}, doi = {10.1051/ita:2006009}, mrnumber = {2252644}, zbl = {1112.68109}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ita:2006009/} }

TY - JOUR AU - Birattari, Mauro AU - Zlochin, Mark AU - Dorigo, Marco TI - Towards a theory of practice in metaheuristics design : a machine learning perspective JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2006 SP - 353 EP - 369 VL - 40 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2006009/ DO - 10.1051/ita:2006009 LA - en ID - ITA_2006__40_2_353_0 ER -

%0 Journal Article %A Birattari, Mauro %A Zlochin, Mark %A Dorigo, Marco %T Towards a theory of practice in metaheuristics design : a machine learning perspective %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2006 %P 353-369 %V 40 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2006009/ %R 10.1051/ita:2006009 %G en %F ITA_2006__40_2_353_0

Birattari, Mauro; Zlochin, Mark; Dorigo, Marco. Towards a theory of practice in metaheuristics design : a machine learning perspective. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 40 (2006) no. 2, pp. 353-369. doi : 10.1051/ita:2006009. http://www.numdam.org/articles/10.1051/ita:2006009/

[1] Designing and reporting computational experiments with heuristic methods. J. Heuristics 1 (1995) 9-32. | Zbl

, , , and ,[2] The Problem of Tuning Metaheuristics, as Seen from a Machine Learning Perspective. Ph.D. thesis, Université Libre de Bruxelles, Brussels, Belgium (2004). | Zbl

,[3] A racing algorithm for configuring metaheuristics, in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2002), edited by W.B. Langdon, et al. Morgan Kaufmann Publishers, San Francisco, CA (2002) 11-18.

, , and ,[4] Differential approximation algorithms for some combinatorial optimization problems. Theoret. Comput. Sci. 209 (1998) 107-122. | Zbl

, and ,[5] Ant colony optimization theory: A survey. Theoret. Comput. Sci. 344 (2005) 243-278.

and ,[6] The Ant Colony Optimization meta-heuristic, in New Ideas in Optimization, edited by D. Corne, M. Dorigo and F. Glover. McGraw Hill, London, UK (1999) 11-32.

and ,[7] Ant algorithms for discrete optimization. Artificial Life 5 (1999) 137-172.

, and ,[8] Ant System: Optimization by a colony of cooperating agents. IEEE Trans. Systems, Man, and Cybernetics - Part B 26 (1996) 29-41.

, and ,[9] Ant Colony Optimization. MIT Press, Cambridge, MA (2004). | Zbl

and ,[10] A Critical Note on Experimental Research Methodology in EC, in Proceedings of the 2002 Congress on Evolutionary Computation (CEC'2002), Piscataway, NJ, IEEE Press (2002) 582-587.

and ,[11] Artificial Intelligence Through Simulated Evolution. John Wiley & Sons, New York, NY (1966). | Zbl

, and ,[12] Computers and Intractability: A Guide to the Theory of $\mathcal{N}P$-Completeness. Freeman, San Francisco, CA (1979). | MR | Zbl

and ,[13] Tabu search - part I. ORSA J. Comput. 1 (1989) 190-206. | Zbl

,[14] Tabu search - part II. ORSA J. Comput. 2 (1990) 4-32. | Zbl

,[15] Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA (1989). | Zbl

,[16] Z-approximations. J. Algorithms 41 (2001) 429-442. | Zbl

and ,[17] Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI (1975). | MR | Zbl

,[18] Testing heuristics: we have it all wrong. J. Heuristics 1 (1995) 33-42. | Zbl

,[19] A theoretician's guide to the experimental analysis of algorithms, in Data structures, near neighbor searches, and methodology: 5th and 6th DIMACS implementation challenges. American Mathematical Society, Providence, RI (2002) 215-250. | Zbl

,[20] The Origins of Order. Self-Organization and Selection in Evolution. Oxford University Press, Oxford, UK (1993).

,[21] Optimization by simulated annealing. Science 220 (1983) 671-680.

, and ,[22] Adapting self-adaptive parameters in evolutionary algorithms. Appl. Intell. 15 (2001) 171-180. | Zbl

, and ,[23] Iterated local search, in Handbook of Metaheuristics. International Series in Operations Research & Management Science, edited by F. Glover and G. Kochenberger. Kluwer Academic Publishers, Norwell, MA 57 (2002) 321-353. | Zbl

, and ,[24] Introduction to Linear and Nonlinear Programming. Addison-Wesley Publishing Company, Reading, MA (1973). | Zbl

,[25] Hoeffding races: Accelerating model selection search for classification and function approximation, in Advances in Neural Information Processing Systems, edited by J.D. Cowan, G. Tesauro and J. Alspector. Morgan Kaufmann Publishers, San Francisco, CA 6 (1994) 59-66.

and ,[26] Toward an experimental method for algorithm simulation. INFORMS J. Comput. 2 (1996) 1-15. | Zbl

,[27] How to Solve it: Modern Heuristics. Springer-Verlag, Berlin, Germany (2000). | MR | Zbl

and ,[28] Efficient algorithms for minimizing cross validation error, in International Conference on Machine Learning. Morgan Kaufmann Publishers, San Francisco, CA (1994) 190-198.

and ,[29] Simple procedures for selecting the best simulated system when the number of alternatives is large. Oper. Res. 49 (2001) 950-963.

, , and ,[30] Experimental evaluation of heuristic optimization algorithms: A tutorial. J. Heuristics 7 (2001) 261-304. | Zbl

and ,[31] Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Information. Fromman Verlag, Freiburg, Germany (1973).

,[32] Numerical Optimization of Computer Models. John Wiley & Sons, Chichester, UK (1981). | Zbl

,[33] Software Engineering. Addison Wesley, Harlow, UK, sixth edition (2001). | Zbl

,[34] Self-adaptive exploration in evolutionary search. Technical Report IRINI-2001-05, Institut für Neuroinformatik, Ruhr-Universität Bochum, Bochum, Germany (2001).

,[35] No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation 1 (1997) 67-82.

and ,[36] Measuring the quality of approximate solutions to zero-one programming problems. Math. Oper. Res. 6 (1981) 319-332. | Zbl

,[37] Model-based search for combinatorial optimization: A critical survey. Ann. Oper. Res. 131 (2004) 375-395. | Zbl

, , and ,[38] Model based search for combinatorial optimization: A comparative study, in Parallel Problem Solving from Nature - PPSN VII, edited by M. Guervós, J.J. et al. Springer Verlag, Berlin, Germany (2002) 651-661.

and ,*Cited by Sources: *