Parameterization of state-of-the-art performance indicators: a robustness study based on inexact TSP solvers

ABSTRACT

Performance comparisons of optimization algorithms are heavily influenced by the underlying indicator(s). In this paper we investigate commonly used performance indicators for single-objective stochastic solvers, such as the Penalized Average Runtime (e.g., PAR10) or the Expected Running Time (ERT), based on exemplary benchmark performances of state-of-the-art inexact TSP solvers. Thereby, we introduce a methodology for analyzing the effects of (usually heuristically set) indicator parametrizations - such as the penalty factor and the method used for aggregating across multiple runs - w.r.t. the robustness of the considered optimization algorithms.

References

1. Bernd Bischl, Pascal Kerschke, Lars Kotthoff, Marius Lindauer, Yuri Malitsky, Alexandre Fréchette, Holger H. Hoos, Frank Hutter, Kevin Leyton-Brown, Kevin Tierney, and Joaquin Vanschoren. 2016. ASlib: A Benchmark Library for Algorithm Selection. Artificial Intelligence Journal (AIJ) 237 (2016), 41 -- 58. https://www.sciencedirect.com/science/article/pii/S0004370216300388
2. Jakob Bossek and Heike Trautmann. 2018. Multi-Objective Performance Measurement: Alternatives to PAR10 and Expected Running Time. In Proceedings of 12th International Conference on Learning and Intelligent Optimization (LION). Publication status: Accepted.
3. Jérémie Dubois-Lacoste, Holger H. Hoos, and Thomas Stützle. 2015. On the Empirical Scaling Behaviour of State-of-the-art Local Search Algorithms for the Euclidean TSP. In Proceedings of the 17th Annual Conference on Genetic and Evolutionary Computation (GECCO). ACM, 377 -- 384.
4. Ágoston E. Eiben and James E. Smith. 2015. Introduction to Evolutionary Computing. Springer
5. Nikolaus Hansen, Anne Auger, Steffen Finck, and Raymond Ros. 2009. Real-Parameter Black-Box Optimization Benchmarking 2009: Experimental Setup. Technical Report RR-6828. INRIA. https://hal.inria.fr/inria-00362649v3/document
6. Keld Helsgaun. 2009. General k-opt Submoves for the Lin-Kernighan TSP Heuristic. Mathematical Programming Computation 1, 2--3 (2009), 119 -- 163.
7. Richard M. Karp. 1972. Reducibility among Combinatorial Problems. Springer, Boston, MA, USA, 85 -- 103.
8. Pascal Kerschke, Lars Kotthoff, Jakob Bossek, Holger H. Hoos, and Heike Trautmann. 2017. Leveraging TSP Solver Complementarity through Machine Learning. Evolutionary Computation Journal (ECJ) (2017), 1 -- 24.
9. Lars Kotthoff, Pascal Kerschke, Holger H. Hoos, and Heike Trautmann. 2015. Improving the State of the Art in Inexact TSP Solving Using Per-Instance Algorithm Selection. In Proceedings of 9th International Conference on Learning and Intelligent Optimization. Springer, 202 -- 217.
10. Tars Kotthoff. 2014. Algorithm Selection for Combinatorial Search Problems: A Survey. AI Magazine 35, 3 (2014), 48 -- 60.
11. Yuichi Nagata and Shigenobu Kobayashi. 2013. A Powerful Genetic Algorithm Using Edge Assembly Crossover for the Traveling Salesman Problem. INFORMS Journal on Computing 25, 2 (2013), 346 -- 363.
12. John Rischard Rice. 1976. The Algorithm Selection Problem. Advances in Computers 15 (1976), 65 -- 118.
13. Danilo Sanches, L. Darrell Whitley, and Renato Tinós. 2017. Building a Better Heuristic for the Traveling Salesman Problem: Combining Edge Assembly Crossover and Partition Crossover. In Proceedings of the 19th Annual Conference on Genetic and Evolutionary Computation (GECCO). ACM, 329 -- 336.
14. David Hilton Wolpert and William G. Macready. 1997. No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary Computation (TEVC) 1, 1 (1997), 67 -- 82.
15. Xiao-Feng Xie and Jiming Liu. 2009. Multiagent Optimization System for Solving the Traveling Salesman Problem (TSP). IEEE Transactions on Systems, Man, and Cybernetics, PartB: Cybernetics 39, 2 (2009), 489 -- 502. http://ieeexplore.ieee.org/document/4717264/

Index Terms

• Computing methodologies

  • Symbolic and algebraic manipulation

    • Symbolic and algebraic algorithms

      • Optimization algorithms

• Mathematics of computing

  • Discrete mathematics

    • Combinatorics

      • Combinatorial optimization