×

Towards a theory of practice in metaheuristics design: a machine learning perspective. (English) Zbl 1112.68109

Summary: 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, [R. Barr et al., J. Heuristics 1, No. 1, 9–32 (1995; Zbl 0853.68154); J. Hooker, J. Heuristics 1, No. 1, 33–42 (1995; Zbl 0853.68155); R. Rardin and R. Uzsoy, J. Heuristics 7, No. 3, 261–304 (2001; Zbl 0972.68634)]. 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.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68W20 Randomized algorithms
68W40 Analysis of algorithms
90C27 Combinatorial optimization

Software:

DIMACS
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML Link

References:

[1] R.S Barr , B.L. Golden , J.P. Kelly , M.G.C. Resende and W.R. Stewart , Designing and reporting computational experiments with heuristic methods . J. Heuristics 1 ( 1995 ) 9 - 32 . Zbl 0853.68154 · Zbl 0853.68154 · doi:10.1007/BF02430363
[2] M. Birattari , The Problem of Tuning Metaheuristics, as Seen from a Machine Learning Perspective . Ph.D. thesis, Université Libre de Bruxelles, Brussels, Belgium ( 2004 ). Zbl 1101.68748 · Zbl 1101.68748
[3] M. Birattari , T. Stützle , L. Paquete and K. Varrentrapp , 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 .
[4] M. Demenage , P. Grisoni and V.Th. Paschos , Differential approximation algorithms for some combinatorial optimization problems . Theoret. Comput. Sci. 209 ( 1998 ) 107 - 122 . Zbl 0912.68061 · Zbl 0912.68061 · doi:10.1016/S0304-3975(97)00099-6
[5] M. Dorigo and C. Blum , Ant colony optimization theory: A survey . Theoret. Comput. Sci. 344 ( 2005 ) 243 - 278 . Zbl pre02235590 · Zbl 1154.90626 · doi:10.1016/j.tcs.2005.05.020
[6] M. Dorigo and G. Di Caro , 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 .
[7] M. Dorigo , G. Di Caro and L. M. Gambardella , Ant algorithms for discrete optimization . Artificial Life 5 ( 1999 ) 137 - 172 .
[8] M. Dorigo , V. Maniezzo and A. Colorni , Ant System: Optimization by a colony of cooperating agents . IEEE Trans. Systems, Man, and Cybernetics - Part B 26 ( 1996 ) 29 - 41 .
[9] M. Dorigo and T. Stützle , Ant Colony Optimization . MIT Press, Cambridge, MA ( 2004 ). Zbl 1092.90066 · Zbl 1092.90066
[10] A.E. Eiben and M. Jelasity , 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 .
[11] L.J. Fogel , A.J. Owens and M.J. Walsh , Artificial Intelligence Through Simulated Evolution . John Wiley & Sons, New York, NY ( 1966 ). Zbl 0148.40701 · Zbl 0148.40701
[12] M.R. Garey and D.S. Johnson , Computers and Intractability: A Guide to the Theory of \({\mathcal{N}P}\)-Completeness . Freeman, San Francisco, CA ( 1979 ). MR 519066 | Zbl 0411.68039 · Zbl 0411.68039
[13] F. Glover , Tabu search - part I . ORSA J. Comput. 1 ( 1989 ) 190 - 206 . Zbl 0753.90054 · Zbl 0753.90054 · doi:10.1287/ijoc.1.3.190
[14] F. Glover , Tabu search - part II . ORSA J. Comput. 2 ( 1990 ) 4 - 32 . Zbl 0771.90084 · Zbl 0771.90084 · doi:10.1287/ijoc.2.1.4
[15] D.E. Goldberg , Genetic Algorithms in Search , Optimization, and Machine Learning. Addison-Wesley, Reading, MA ( 1989 ). Zbl 0721.68056 · Zbl 0721.68056
[16] R. Hassin and S. Khuller , Z-approximations . J. Algorithms 41 ( 2001 ) 429 - 442 . Zbl 1014.68222 · Zbl 1014.68222 · doi:10.1006/jagm.2001.1187
[17] J. Holland , Adaptation in Natural and Artificial Systems . University of Michigan Press, Ann Arbor, MI ( 1975 ). MR 441393 | Zbl 0317.68006 · Zbl 0317.68006
[18] J.N. Hooker , Testing heuristics: we have it all wrong . J. Heuristics 1 ( 1995 ) 33 - 42 . Zbl 0853.68155 · Zbl 0853.68155 · doi:10.1007/BF02430364
[19] D.S. Johnson , 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 1103.68997 · Zbl 1103.68997
[20] S.A. Kauffman , The Origins of Order . Self-Organization and Selection in Evolution. Oxford University Press, Oxford, UK ( 1993 ).
[21] S. Kirkpatrick , C.D. Gelatt Jr. and M.P. Vecchi , Optimization by simulated annealing . Science 220 ( 1983 ) 671 - 680 . · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[22] K. Liang , X. Yao and C. Newton , Adapting self-adaptive parameters in evolutionary algorithms . Appl. Intell. 15 ( 2001 ) 171 - 180 . Zbl 0992.68231 · Zbl 0992.68231 · doi:10.1023/A:1011286929823
[23] H.R. Lourenço , O. Martin and T. Stützle , 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 1116.90412 · Zbl 1116.90412
[24] D.G. Luenberger , Introduction to Linear and Nonlinear Programming . Addison-Wesley Publishing Company, Reading, MA ( 1973 ). Zbl 0297.90044 · Zbl 0297.90044
[25] O. Maron and A.W. Moore , 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 .
[26] C.C. McGeogh , Toward an experimental method for algorithm simulation . INFORMS J. Comput. 2 ( 1996 ) 1 - 15 . Zbl 0854.68038 · Zbl 0854.68038 · doi:10.1287/ijoc.8.1.1
[27] Z. Michalewicz and D.B. Fogel , How to Solve it: Modern Heuristics . Springer-Verlag, Berlin, Germany ( 2000 ). MR 1730907 | Zbl 0943.90002 · Zbl 0943.90002
[28] A.W. Moore and M.S. Lee , Efficient algorithms for minimizing cross validation error , in International Conference on Machine Learning. Morgan Kaufmann Publishers, San Francisco, CA ( 1994 ) 190 - 198 .
[29] B.L. Nelson , J. Swann , D. Goldsman and W. Song , Simple procedures for selecting the best simulated system when the number of alternatives is large . Oper. Res. 49 ( 2001 ) 950 - 963 .
[30] R.R. Rardin and R. Uzsoy , Experimental evaluation of heuristic optimization algorithms: A tutorial . J. Heuristics 7 ( 2001 ) 261 - 304 . Zbl 0972.68634 · Zbl 0972.68634 · doi:10.1023/A:1011319115230
[31] I. Rechenberg , Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Information . Fromman Verlag, Freiburg, Germany ( 1973 ).
[32] H.-P. Schwefel , Numerical Optimization of Computer Models . John Wiley & Sons, Chichester, UK ( 1981 ). Zbl 0451.65043 · Zbl 0451.65043
[33] I. Sommerville , Software Engineering . Addison Wesley, Harlow, UK, sixth edition ( 2001 ). Zbl 0557.68006 · Zbl 0557.68006
[34] M. Toussaint , Self-adaptive exploration in evolutionary search . Technical Report IRINI- 2001 - 05 , Institut für Neuroinformatik, Ruhr-Universität Bochum, Bochum, Germany ( 2001 ).
[35] D.H. Wolpert and W.G. Macready , No free lunch theorems for optimization . IEEE Transactions on Evolutionary Computation 1 ( 1997 ) 67 - 82 .
[36] E. Zemel , Measuring the quality of approximate solutions to zero-one programming problems . Math. Oper. Res. 6 ( 1981 ) 319 - 332 . Zbl 0538.90065 · Zbl 0538.90065 · doi:10.1287/moor.6.3.319
[37] M. Zlochin , M. Birattari , N. Meuleau and M. Dorigo , Model-based search for combinatorial optimization: A critical survey . Ann. Oper. Res. 131 ( 2004 ) 375 - 395 . Zbl 1067.90162 · Zbl 1067.90162 · doi:10.1023/B:ANOR.0000039526.52305.af
[38] M. Zlochin and M. Dorigo , 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 .
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.