Towards the landscape rotation as a perturbation strategy on the quadratic assignment problem.

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

Abstract

Recent work in combinatorial optimisation have demonstrated that neighbouring solutions of a local optima may belong to more favourable attraction basins. In this sense, the perturbation strategy plays a critical role on local search based algorithms to kick the search of the algorithm into more prominent areas of the space. In this paper, we investigate the landscape rotation as a perturbation strategy to redirect the search of an stuck algorithm. This technique rearranges the mapping of solutions to different objective values without altering important properties of the problem's landscape such as the number and quality of optima, among others. Particularly, we investigate two rotation based perturbation strategies: (i) a profoundness rotation method and (ii) a broadness rotation method. These methods are applied into the stochastic hill-climbing heuristic and tested and compared on different instances of the quadratic assignment problem against other algorithm versions. Performed experiments reveal that the landscape rotation is an efficient perturbation strategy to shift the search in a controlled way. Nevertheless, an empirical investigation of the landscape rotation demonstrates that it needs to be cautiously manipulated in the permutation space since a small rotation does not necessarily mean a small disturbance in the fitness landscape.

Citation

ALZA, J., BARTLETT, M., CEBERIO, J. and MCCALL, J. 2021. Towards the landscape rotation as a perturbation strategy on the quadratic assignment problem. In Chicano, F. (ed.) GECCO '21: proceedings of 2021 Genetic and evolutionary computation conference companion, 10-14 July 2021, [virtual conference]. New York: ACM [online], pages 1405-1413. Available from: https://doi.org/10.1145/3449726.3463139

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 2021 Genetic and evolutionary computation conference (GECCO 2021)
• Start Date: Jul 10, 2021
• End Date: Jul 14, 2021
• Acceptance Date: Mar 26, 2021
• Online Publication Date: Jul 8, 2021
• Publication Date: Jul 31, 2021
• Deposit Date: Aug 23, 2021
• Publicly Available Date: Aug 23, 2021
• Publisher: Association for Computing Machinery (ACM)
• Peer Reviewed: Peer Reviewed
• Pages: 1405-1413
• Book Title: GECCO '21: proceedings of the 2021 Genetic and evolutionary computation conference companion
• ISBN: 9781450383516
• DOI: https://doi.org/10.1145/3449726.3463139
• Keywords: Quadratic assignment problem; Landscape rotation
• Public URL: https://rgu-repository.worktribe.com/output/1405791