Skip to main content

Research Repository

Advanced Search

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

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

Authors

Josu Ceberio



Contributors

Francisco Chicano
Editor

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

Conference Name 2021 Genetic and evolutionary computation conference (GECCO 2021)
Conference Location [virtual conference)
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)
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

Files

ALZA 2021 Towards the landscape (AAM) (2.7 Mb)
PDF

Copyright Statement
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.





You might also like



Downloadable Citations