×

zbMATH — the first resource for mathematics

Towards objective measures of algorithm performance across instance space. (English) Zbl 1348.90646
Summary: This paper tackles the difficult but important task of objective algorithm performance assessment for optimization. Rather than reporting average performance of algorithms across a set of chosen instances, which may bias conclusions, we propose a methodology to enable the strengths and weaknesses of different optimization algorithms to be compared across a broader instance space. The results reported in a recent Computers and Operations Research paper comparing the performance of graph coloring heuristics are revisited with this new methodology to demonstrate (i) how pockets of the instance space can be found where algorithm performance varies significantly from the average performance of an algorithm; (ii) how the properties of the instances can be used to predict algorithm performance on previously unseen instances with high accuracy; and (iii) how the relative strengths and weaknesses of each algorithm can be visualized and measured objectively.

MSC:
90C59 Approximation methods and heuristics in mathematical programming
68W99 Algorithms in computer science
05C15 Coloring of graphs and hypergraphs
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Hooker, J., Neededan empirical science of algorithms, Oper Res, 201-212, (1994) · Zbl 0805.90119
[2] Hooker, J., Testing heuristicswe have it all wrong, J Heuristics, 1, 1, 33-42, (1995) · Zbl 0853.68155
[3] Beasley, J., OR-librarydistributing test problems by electronic mail, J Oper Res Soc, 1069-1072, (1990)
[4] Hill, R.; Reilly, C., The effects of coefficient correlation structure in two-dimensional knapsack problems on solution procedure performance, Manag Sci, 302-317, (2000) · Zbl 1231.90323
[5] Wolpert, D. H.; Macready, W. G., No free lunch theorems for optimization, IEEE Trans Evolut Comput, 1, 1, 67-82, (1997)
[6] Culberson, J., On the futility of blind searchan algorithmic view of ‘no free lunch’, Evolut Comput, 6, 2, 109-127, (1998)
[7] Igel, C.; Toussaint, M., A no-free-lunch theorem for non-uniform distributions of target functions, J Math Model Algorithms, 3, 4, 313-322, (2005) · Zbl 1079.90111
[8] Margulies S, Ma J, Hicks I. The Cunningham-Geelen method in practice: branch-decompositions and integer programming. INFORMS J Comput, Published online before print November 27, 2012. doi: http://dx.doi.org/10.1287/ijoc.1120.0524.
[9] Smith-Miles K, Tan T. Measuring algorithm footprints in instance space. In: IEEE congress on evolutionary computation (CEC), Piscataway, NJ: IEEE; 2012. p. 1-8.
[10] Smith-Miles, K.; Lopes, L., Measuring instance difficulty for combinatorial optimization problems, Comput Oper Res, 39, 5, 875-889, (2012) · Zbl 1251.90339
[11] Smith-Miles, K.; van Hemert, J., Discovering the suitability of optimisation algorithms by learning from evolved instances, Ann Math Artif Intell, 61, 2, 87-104, (2011) · Zbl 1236.49008
[12] Smith-Miles, K.; Wreford, B.; Lopes, L.; Insani, N., Predicting metaheuristic performance on graph coloring problems using data mining, (Talbi, E. G., Hybrid metaheuristics, (2013), Springer-Verlag; Springer Berlin Heidelberg), 417-432
[13] Smith-Miles K, van Hemert J, Lim X. Understanding TSP difficulty by learning from evolved instances. In: Learning and intelligent optimization, Lecture notes in computer science, vol. 6073, 2010. p. 266-80.
[14] Smith-Miles K, James R, Giffin J, Tu Y. A knowledge discovery approach to understanding relationships between scheduling problem structure and heuristic performance. In: Learning and intelligent optimization, 2009. p. 89-103.
[15] Smith-Miles K. Towards insightful algorithm selection for optimisation using meta-learning concepts. In: IEEE international joint conference on neural networks, 2008. p. 4118-24.
[16] Smith-Miles K, Baatar D. Exploring the role of graph spectra in graph coloring algorithm performance. Discrete Appl Math, in press, 10.1016/j.dam.2013.11.005. · Zbl 1298.05208
[17] Smith-Miles K, Lopes L. Generalising algorithm performance in instance space: a timetabling case study. In: Lecture notes in computer science, vol. 6683, 2011. p. 524-39.
[18] Lopes L, Smith-Miles KA. Generating applicable synthetic instances for branch problems. Operations Research, 2013; 61(3):563-577. · Zbl 1273.90243
[19] Lewis, R.; Thompson, J.; Mumford, C.; Gillard, J., A wide-ranging computational comparison of high-performance graph colouring algorithms, Comput Oper Res, 39, 9, 1933-1950, (2012) · Zbl 1250.05109
[20] Rice, J., The algorithm selection problem, Adv Comput, 15, 65-117, (1976)
[21] Weerawarana, S.; Houstis, E. N.; Rice, J. R.; Joshi, A.; Houstis, C. E., Pythiaa knowledge-based system to select scientific algorithms, ACM Trans Math Softw, 22, 4, 447-468, (1996) · Zbl 0884.65123
[22] Ramakrishnan, N.; Rice, J.; Houstis, E., Gaussan online algorithm selection system for numerical quadrature, Adv Eng Softw, 33, 1, 27-36, (2002) · Zbl 1003.68581
[23] Smith-Miles K. Cross-disciplinary perspectives on meta-learning for algorithm selection. ACM Comput Surv 2008; 41 (1).
[24] Xu L, Hutter F, Hoos H, Leyton-Brown K. SATzilla-07: the design and analysis of an algorithm portfolio for SAT. In: Lecture notes in computer science, vol. 4741, 2007. p. 712. · Zbl 1182.68272
[25] Gagliolo, M.; Schmidhuber, J., Learning dynamic algorithm portfolios, Ann Math Artif Intell, 47, 3, 295-328, (2006) · Zbl 1113.68101
[26] O’Mahony E, Hebrard E, Holland A, Nugent C, O’Sullivan B. Using case-based reasoning in an algorithm portfolio for constraint solving. In: Irish conference on artificial intelligence and cognitive science, 2008.
[27] Jolliffe, I., Principal component analysis, (2002), Springer New York · Zbl 1011.62064
[28] Kohonen, T., Self-organized formation of topologically correct feature maps, Biol Cybern, 43, 1, 59-69, (1982) · Zbl 0466.92002
[29] Mitchell, T. M., Machine learning (mcgraw-Hill series in computer science), (1997), McGraw-Hill Higher Education New York, NY, USA
[30] Goldberg D. Genetic algorithms in search and optimization, 1989. · Zbl 0721.68056
[31] Tsymbal A, Pechenizkiy M, Cunningham P. Diversity in ensemble feature selection. Technical Report TCD-CS-2003-44, The University of Dublin.
[32] Bengio, Y.; Chapados, N., Extensions to metric based model selection, J Mach Learn Res, 3, 1209-1227, (2003) · Zbl 1102.68529
[33] Guyon, I.; Elisseeff, A., An introduction to variable and feature selection, J Mach Learn Res, 3, 1157-1182, (2003) · Zbl 1102.68556
[34] Burke, E.; McCollum, B.; Meisels, A.; Petrovic, S.; Qu, R., A graph-based hyper-heuristic for educational timetabling problems, Eur J Oper Res, 176, 1, 177-192, (2007) · Zbl 1137.90602
[35] de Werra, D., An introduction to timetabling, Eur J Oper Res, 19, 2, 151-162, (1985) · Zbl 0553.90059
[36] Lewis, R., A survey of metaheuristic-based techniques for university timetabling problems, OR Spectr, 30, 1, 167-190, (2008) · Zbl 1133.90341
[37] Culberson J. Graph coloring page. URL: 〈http://www.cs.ualberta.ca/ joe/Coloring〉: 2010.
[38] Johnson DS, Trick MA. Cliques, coloring, and satisfiability: second DIMACS implementation challenge, October 11-13, 1993, vol. 26. Boston, MA: American Mathematical Society, 1996.
[39] Hagberg A, Schult D, Swart P. NetworkX library developed at the Los Alamos national laboratory labs library (DOE) by the university of California. Code available at 〈https://networkx.lanl.gov〉.
[40] Moody, J.; White, D. R., Structural cohesion and embeddednessa hierarchical concept of social groups, Am Soc Rev, 103-127, (2003)
[41] De Werra, D., Some models of graphs for scheduling sports competitions, Discrete Appl Math, 21, 1, 47-65, (1988) · Zbl 0656.90060
[42] Carter, M. W.; Laporte, G.; Lee, S. Y., Examination timetablingalgorithmic strategies and applications, J Oper Res Soc, 373-383, (1996)
[43] Johnson, D.; Aragon, C.; McGeoch, L.; Schevon, C., Optimization by simulated annealingan experimental evaluation; part ii, graph coloring and number partitioning, Oper Res, 378-406, (1991) · Zbl 0739.90055
[44] Culberson J, Beacham A, Papp D. Hiding our colors. In: In CP95 workshop on studying and solving really hard problems, 1995.
[45] Smith-Miles, K. A.; Lopes, L. B., Measuring instance difficulty for combinatorial optimization problems, Comput Oper Res, 39, 5, 875-889, (2012) · Zbl 1251.90339
[46] Read, R.; Wilson, R., An atlas of graphs, (1998), Oxford University Press USA · Zbl 0908.05001
[47] Brinkmann, G.; Coolsaet, K.; Goedgebeur, J.; Melot, H., House of graphsa database of interesting graphs, Discrete Appl Math, 161, 311-314, (2013) · Zbl 1292.05254
[48] Mélot, H., Facet defining inequalities among graph invariantsthe system graphedron, Discrete Appl Math, 156, 10, 1875-1891, (2008) · Zbl 1152.05380
[49] Soffer, S.; Vázquez, A., Network clustering coefficient without degree-correlation biases, Phys Rev E, 71, 5, 057101, (2005)
[50] Pisanski, T.; Randić, M., Use of the Szeged index and the revised Szeged index for measuring network bipartivity, Discrete Appl Math, 158, 17, 1936-1944, (2010) · Zbl 1215.05194
[51] Estrada, E.; Rodríguez-Velázquez, J. A., Spectral measures of bipartivity in complex networks, Phys Rev E, 72, 4, 046105, (2005)
[52] Balakrishnan, R., The energy of a graph, Linear Algebra Appl, 387, 287-295, (2004) · Zbl 1041.05046
[53] Mohar, B., The Laplacian spectrum of graphs, Graph Theory Combin Appl, 2, 871-898, (1991) · Zbl 0840.05059
[54] Biggs, N., Algebraic graph theory, vol. 67, (1993), Cambridge University Press Cambridge, UK
[55] Brélaz, D., New methods to color the vertices of a graph, Commun ACM, 22, 4, 251-256, (1979) · Zbl 0394.05022
[56] Wood, D., An algorithm for finding a maximum clique in a graph, Oper Res Lett, 21, 5, 211-217, (1997) · Zbl 0908.90264
[57] Lewis, R., A general-purpose Hill-climbing method for order independent minimum grouping problemsa case study in graph colouring and bin packing, Comput Oper Res, 36, 7, 2295-2310, (2009) · Zbl 1158.90415
[58] Galinier, P.; Hao, J., Hybrid evolutionary algorithms for graph coloring, J Comb Optim, 3, 4, 379-397, (1999) · Zbl 0958.90071
[59] Blöchliger, I.; Zufferey, N., A graph coloring heuristic using partial solutions and a reactive tabu scheme, Comput Oper Res, 35, 3, 960-975, (2008) · Zbl 1278.90327
[60] Dowsland, K. A.; Thompson, J. M., An improved ant colony optimisation heuristic for graph colouring, Discrete Appl Math, 156, 3, 313-324, (2008) · Zbl 1136.90529
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.