Algorithm selection on generalized quadratic assignment problem landscapes

ABSTRACT

Algorithm selection is useful in decision situations where among many alternative algorithm instances one has to be chosen. This is often the case in heuristic optimization and is detailed by the well-known no-free-lunch (NFL) theorem. A consequence of the NFL is that a heuristic algorithm may only gain a performance improvement in a subset of the problems. With the present study we aim to identify correlations between observed differences in performance and problem characteristics obtained from statistical analysis of the problem instance and from fitness landscape analysis (FLA). Finally we evaluate the performance of a recommendation algorithm that uses this information to make an informed choice for a certain algorithm instance.

References

1. Michael Affenzeller, Stephan Winkler, Stefan Wagner, and Andreas Beham. 2009. Genetic Algorithms and Genetic Programming - Modern Concepts and Practical Applications. CRC Press.
2. Eric Angel and Vassilis Zissimopoulos. 1998. Autocorrelation coefficient for the graph bipartitioning problem. Theoretical Computer Science 191,1--2 (1998), 229--243.
3. A. Auger and N. Hansen. 2005. Performance evaluation of an advanced local search evolutionary algorithm. In Proceedings of the 2005 IEEE Congress on Evolutionary Computation (CEC), Vol. 2. 1777--1784.
4. Thomas Bartz-Beielstein. 2006. Experimental Research in Evolutionary Computation: The New Experimentalism. Springer.
5. Thomas Bartz-Beielstein, Christian WG Lasarczyk, and Mike Preuß. 2005. Sequential parameter optimization. In Evolutionary Computation, 2005. The 2005 IEEE Congress on, Vol. 1. IEEE, 773--780.
6. Mosab Bazargani and Fernando G. Lobo. 2017. Parameter-less Late Acceptance Hill-climbing. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '17). ACM, New York, NY, USA, 219--226.
7. Andreas Beham, Michael Affenzeller, and Stefan Wagner. 2017. Instance-based Algorithm Selection on Quadratic Assignment Problem Landscapes. In Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO '17). ACM, New York, NY, USA, 1471--1478.
8. Andreas Beham, Stefan Wagner, and Michael Affenzeller. 2016. Optimization Knowledge Center: A Decision Support System for Heuristic Optimization. In Companion Publication of the 2016 Genetic and Evolutionary Computation Conference, GECCO'16 Companion. ACM, 1331--1338.
9. Thierry Benoist, Bertrand Estellon, Frédéric Gardi, Romain Megel, and Karim Nouioua. 2011. Localsolver 1.x: a black-box local-search solver for 0--1 programming. 40R: A Quarterly Journal of Operations Research 9, 3 (2011), 299--316.
10. Rainer E. Burkard, Stefan E. Karisch, and Franz Rendl. 1997. QAPLIB - A Quadratic Assignment Problem Library. Journal of Global Optimization 10, 4 (June 1997), 391--403. http://www.opt.math.tu-graz.ac.at/qaplib/
11. Edmund K. Burke and Yuri Bykov. 2017. The late acceptance Hill-Climbing heuristic. European Journal of Operational Research 258, 1 (2017), 70 -- 78.
12. Francisco Chicano, Gabriel Luque, and Enrique Alba. 2012. Autocorrelation measures for the quadratic assignment problem. Applied Mathematics Letters 25, 4 (2012), 698--705.
13. Jean-François Cordeau, Manlio Gaudioso, Gilbert Laporte, and Luigi Moccia. 2006. A memetic heuristic for the generalized quadratic assignment problem. INFORMS Journal on Computing 18, 4 (2006), 433--443.
14. Alan M Frieze and Joseph Yadegar. 1983. On the Quadratic Assignment Problem. Discrete applied mathematics 5, 1 (1983), 89--98.
15. H. H. Hoos and T. Stützte. 1998. Evaluating Las Vegas Algorithms - Pitfalls and Remedies. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI-98). Morgan Kaufmann, San Francisco, CA, 238--245.
16. Gregory S. Hornby. 2006. ALPS: The Age-layered Population Structure for Reducing the Problem of Premature Convergence. In Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation (GECCO '06). ACM, New York, NY, USA, 815--822.
17. Frank Flutter, Holger H Hoos, Kevin Leyton-Brown, and Thomas Stützle. 2009. ParamILS: an automatic algorithm configuration framework. Journal of Artificial Intelligence Research 36, 1 (2009), 267--306.
18. Kalervo Järvelin and JaanaKekäläinen. 2002. Cumulated gain-based evaluation of IR techniques. ACM Transactions on Information Systems (TOIS) 20, 4 (2002), 422--446.
19. L Kaufman and Fernand Broeckx. 1978. An Algorithm for the Quadratic Assignment Problem using Bender's Decomposition. European Journal of Operational Research 2, 3 (1978), 207--211.
20. Lars Kotthoff. 2014. Algorithm selection for combinatorial search problems: A survey. AI Magazine 35, 3 (2014), 48--60.
21. Kevin Leyton-Brown, Eugene Nudelman, Galen Andrew, Jim McFadden, and Yoav Shoham. 2003. A portfolio approach to algorithm selection. In IJCAI, Vol. 3. 1542--1543.
22. Manuel López-Ibáñez, Jérémie Dubois-Lacoste, Thomas Stützle, and Mauro Birattari. 2011. The irace package, Iterated Race for Automatic Algorithm Configuration. Technical Report TR/IRIDIA/2011-004. IRIDIA, Université Libre de Bruxelles, Belgium. http://iridia.ulb.ac.be/IridiaTrSeries/IridiaTr2011-004.pdf
23. Helena R Lourenço, Olivier C Martin, and Thomas Stutzle. 2003. Iterated local search. International series in operations research and management science (2003), 321--354.
24. Geraldo R Mateus, Mauricio GC Resende, and Ricardo MA Silva. 2011. GRASP with path-relinking for the generalized quadratic assignment problem. Journal of Heuristics 17, 5 (2011), 527--565.
25. Olaf Mersmann, Bernd Bischl, Heike Trautmann, Mike Preuss, Claus Weihs, and Günter Rudolph. 2011. Exploratory Landscape Analysis. In Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation (GECCO '11). ACM, New York, NY, USA, 829--836.
26. Peter Merz and Bernd Freisleben. 2000. Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. Evolutionary Computation, IEEE Transactions on 4, 4 (2000), 337--352.
27. G. Ochoa, S. Verel, F. Daolio, and M. Tomassini. 2014. Local Optima Networks: A New Model of Combinatorial Fitness Landscapes. In Recent Advances in the Theory and Application of Fitness Landscapes. Springer-Verlag Berlin Heidelberg.
28. Artur Alves Pessoa, Peter M. Hahn, Monique Guignard, and Yi-Rong Zhu. 2010. Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the Reformulation-Linearization Technique. European Journal of Operational Research 206, 1 (2010), 54--63.
29. Erik Pitzer and Michael Affenzeller. 2012. A comprehensive survey on fitness landscape analysis. In Recent Advances in Intelligent Engineering Systems. Springer, 161--191.
30. John R. Rice. 1976. The Algorithm Selection Problem. Advances in Computers 15 (1976), 65--118.
31. David M Tate and Alice E Smith. 1995. A genetic approach to the quadratic assignment problem. Computers & Operations Research 22, 1 (1995), 73--83.
32. Vesselin K Vassilev, Terence C Fogarty, and Julian F Miller. 2000. Information Characteristics and the Structure of Landscapes. Evolutionary Computation 8, 1 (2000), 31--60.
33. H. Wang and M. Song. 2011. Ckmeans.1d.dp: optimal k-means clustering in one dimension by dynamic programming. The R Journal 3, 2 (2011), 29--33.
34. Darrell Whitley, Andrew M Sutton, and Adele E Howe. 2008. Understanding elementary landscapes. In Proceedings of the 10th annual conference on Genetic and evolutionary computation. ACM, 585--592.
35. David H. Wolpert and William G. Macready. 1997. No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary Computation 1, 1 (1997), 67--82.
36. Lin Xu, Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown. 2008. SATzilla: portfolio-based algorithm selection for SAT. Journal of artificial intelligence research 32 (2008), 565--606.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Search methodologies

      • Randomized search

• Information systems

  • Information retrieval

    • Retrieval models and ranking

      • Learning to rank

  • Information systems applications

    • Decision support systems

      • Expert systems

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Facility location and clustering