Analysing the fitness landscape rotation for combinatorial optimisation.

Alza, Joan; Bartlett, Mark; Ceberio, Josu; McCall, John

Abstract

Fitness landscape rotation has been widely used in the field of dynamic combinatorial optimisation to generate test problems with academic purposes. This method changes the mapping between solutions and objective values, but preserves the structure of the fitness landscape. In this work, the rotation of the landscape in the combinatorial domain is theoretically analysed using concepts of discrete mathematics. Certainly, the preservation of the neighbourhood relationship between the solutions and the structure of the landscape are studied in detail. Based on the theoretical insights obtained, landscape rotation has been employed as a strategy to escape from local optima when local search algorithms get stuck. Conducted experiments confirm the good performance of the rotation-based local search algorithms to perturb the search towards unexplored local optima on a set of instances of the linear ordering problem.

Citation

ALZA, J., BARTLETT, M., CEBERIO, J. and MCCALL, J. 2022. Analysing the fitness landscape rotation for combinatorial optimisation. In Rudolph, G., Kononova, A.V., Aguirre, H., Kerschke, P., Ochoa, G. and Tušar, T. (eds.) Parallel problem solving from nature (PPSN XVII): proceedings of 17th Parallel problem solving from nature international conference 2022 (PPSN 2022), 10-14 September 2022, Dortmund, Germany. Lecture notes in computer science, 13398. Cham: Springer [online], pages 533-547. Available from: https://doi.org/10.1007/978-3-031-14714-2_37

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 17th Parallel problem solving from nature international conference 2022 (PPSN 2022)
• Start Date: Sep 10, 2022
• End Date: Sep 14, 2022
• Acceptance Date: Jun 6, 2022
• Online Publication Date: Aug 14, 2022
• Publication Date: Dec 31, 2022
• Deposit Date: Sep 16, 2022
• Publicly Available Date: Aug 15, 2023
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Pages: 533-547
• Series Title: Lecture notes in computer science (LNCS)
• Series Number: 13398
• Series ISSN: 0302-9743; 1611-3349
• Book Title: Parallel problem solving from nature (PPSN XVII): proceedings of 17th Parallel problem solving from nature international conference 2022 (PPSN 2022), 10-14 September 2022, Dortmund, Germany
• ISBN: 9783031147135
• DOI: https://doi.org/10.1007/978-3-031-14714-2_37
• Keywords: Landscape rotation; Combinatorial optimisation; Group theory
• Public URL: https://rgu-repository.worktribe.com/output/1753235