Perturbation strength and the global structure of qap fitness landscapes

Citation

Ochoa G & Herrmann S (2018) Perturbation strength and the global structure of qap fitness landscapes. In: Fonseca C, Lourenco N, Machado P, Paquete L, Auger A & Whitley D (eds.) Parallel Problem Solving from Nature – PPSN XV. PPSN 2018. Lecture Notes in Computer Science, 11102. PPSN 2018: International Conference on Parallel Problem Solving from Nature, Coimbra, Portugal, 08.09.2018-12.09.2018. Cham, Switzerland: Springer Verlag, pp. 245-256. https://doi.org/10.1007/978-3-319-99259-4_20

Abstract
We study the effect of increasing the perturbation strength on the global structure of QAP fitness landscapes induced by Iterated Local Search (ILS). The global structure is captured with Local Optima Networks. Our analysis concentrates on the number, characteristics and distribution of funnels in the landscape, and how they change with increasing perturbation strengths. Well-known QAP instance types are considered. Our results confirm the multi-funnel structure of QAP fitness landscapes and clearly explain, visually and quantitatively, why ILS with large perturbation strengths produces better results. Moreover, we found striking differences between randomly generated and real-world instances, which warns about using synthetic benchmarks for (manual or automatic) algorithm design and tuning.

Keywords
Local Optima Network; Quadratic Assignment Problem; QAP; Iterated Local Search; Perturbation strength; Fitness landscapes

People

Professor Gabriela Ochoa

Professor, Computing Science