The effect of landscape funnels in QAPLIB instances

Thomson, Sarah L.; Ochoa, Gabriela; Daolio, Fabio; Veerapen, Nadarajen

Abstract

The effectiveness of common metaheuristics on combinatorial optimisation problems can be limited by certain characteristics of the fitness landscape. We use the local optima network model to compress the 'inherent structure' of a problem space into a network whose structure relates to the empirical hardness of the underlying landscape. Monotonic sequences axe used on the local optima networks of a benchmark set of QAP instances (QAPLIB) to expose landscape funnels. The results suggest links between features of these structures and lowered metaheuristic performance.

Citation

Thomson, S. L., Ochoa, G., Daolio, F., & Veerapen, N. (2017, July). The effect of landscape funnels in QAPLIB instances. Presented at GECCO '17: Genetic and Evolutionary Computation Conference, Berlin, Germany

• Presentation Conference Type: Conference Paper (published)
• Conference Name: GECCO '17: Genetic and Evolutionary Computation Conference
• Start Date: Jul 15, 2017
• End Date: Jul 19, 2017
• Online Publication Date: Jul 15, 2017
• Publication Date: 2017-07
• Deposit Date: Aug 16, 2023
• Publisher: Association for Computing Machinery (ACM)
• Pages: 1495-1500
• Book Title: GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference Companion
• ISBN: 9781450349390
• DOI: https://doi.org/10.1145/3067695.3082512
• Public URL: http://researchrepository.napier.ac.uk/Output/3169683