Towards the landscape rotation as a perturbation strategy on the quadratic assignment problem.
Alza, Joan; Bartlett, Mark; Ceberio, Josu; McCall, John
Dr Mark Bartlett email@example.com
Professor John McCall firstname.lastname@example.org
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.
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|
|Book Title||GECCO '21: proceedings of the 2021 Genetic and evolutionary computation conference companion|
|Keywords||Quadratic assignment problem; Landscape rotation|
ALZA 2021 Towards the landscape (AAM)
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 email@example.com.
You might also like
Prediction of casing critical buckling during shale gas hydraulic fracturing.
On the definition of dynamic permutation problems under landscape rotation.
Integer linear programming for the Bayesian network structure learning problem.