Conference Proceeding

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

StatusPublished
Title of seriesLecture Notes in Computer Science
Number in series11102
Publication date31/12/2018
Publication date online21/08/2018
URLhttp://hdl.handle.net/1893/27951
PublisherSpringer Verlag
Place of publicationCham, Switzerland
ISSN of series0302-9743
ISBN0302-9743
ConferencePPSN 2018: International Conference on Parallel Problem Solving from Nature
Conference locationCoimbra, Portugal
Dates

Research centres/groups