Analysing the Fitness Landscape Rotation for Combinatorial Optimisation
Pages 533 - 547
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.
References
[1]
Alza, J., Bartlett, M., Ceberio, J., McCall, J.: On the definition of dynamic permutation problems under landscape rotation. In: Proceedings of GECCO, pp. 1518–1526 (2019)
[2]
Alza, J., Bartlett, M., Ceberio, J., McCall, J.: Towards the landscape rotation as a perturbation strategy on the quadratic assignment problem. In: Proceedings of GECCO, pp. 1405–1413 (2021)
[3]
Branke J Evolutionary Optimization in Dynamic Environments 2002 Heidelberg Springer
[4]
Ceberio, J.: Solving Permutation Problems with Estimation of Distribution Algorithms and Extensions Thereof. Ph.D. thesis, UPV/EHU (2014)
[5]
Ceberio J, Mendiburu A, and Lozano JA The linear ordering problem revisited EJOR 2015 241 3 686-696
[6]
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)
[7]
Hernando L, Mendiburu A, and Lozano JA An evaluation of methods for estimating the number of local optima in combinatorial optimization problems Evol. Comput. 2013 21 4 625-658
[8]
Hernando L, Mendiburu A, and Lozano JA Anatomy of the attraction basins: breaking with the intuition Evol. Comput. 2019 27 3 435-466
[9]
Irurozki, E.: Sampling and learning distance-based probability models for permutation spaces. Ph.D. thesis, UPV/EHU (2014)
[10]
Martí R and Reinelt G The Linear Ordering Problem: Exact and Heuristic Methods in Combinatorial Optimization 2011 Heidelberg Springer
[11]
Mavrovouniotis, M., Yang, S., Yao, X.: A benchmark generator for dynamic permutation-encoded problems. In: PPSN, pp. 508–517 (2012)
[12]
Nguyen TT, Yang S, and Branke J Evolutionary dynamic optimization: a survey of the state of the art Swarm Evol. Comput. 2012 6 1-24
[13]
Ochoa G, Malan KM, and Blum C Search trajectory networks: a tool for analysing and visualising the behaviour of metaheuristics Appl. Soft Comput. 2021 109 107492
[14]
Reidys, C.M., Stadler, P.F.: Combinatorial Landscapes. Working Papers 01–03-014, Santa Fe Institute (2001)
[15]
Tayarani-N., M.H., Prügel-Bennett, A.: On the landscape of combinatorial optimization problems. IEEE TEVC 18(3), 420–434 (2014)
[16]
Tinós R and Yang S Analysis of fitness landscape modifications in evolutionary dynamic optimization Inf. Sci. 2014 282 214-236
[17]
Vérel S, Daolio F, Ochoa G, and Tomassini M Hao J-K, Legrand P, Collet P, Monmarché N, Lutton E, and Schoenauer M Local optima networks with escape edges Artificial Evolution 2012 Heidelberg Springer 49-60
[18]
Yang, S.: Non-stationary problem optimization using the primal-dual genetic algorithm. In: Proceedings of CEC, vol. 3, pp. 2246–2253 (2003)
[19]
Yang S and Yao X Experimental study on population-based incremental learning algorithms for dynamic optimization problems Soft Comput. 2005 9 815-834
[20]
Yazdani D, Cheng R, Yazdani D, Branke J, Jin Y, and Yao X A survey of evolutionary continuous dynamic optimization over two decades-part b IEEE TEVC 2021 25 4 630-650
[21]
Younes, A., Calamai, P., Basir, O.: Generalized benchmark generation for dynamic combinatorial problems. In: Proceedings of GECCO, pp. 25–31 (2005)
Recommendations
The effect of landscape funnels in QAPLIB instances
GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference CompanionThe effectiveness of common metaheuristics on combinatorial optimisation problems can be limited by certain characteristics of the fitness landscape. We use the local optima network model to compress the 'inherent structure' of a problem space into a ...
Climbing combinatorial fitness landscapes
Graphical abstractDisplay Omitted HighlightsComparison of the behavior of classical basic local search techniques and their ability to reach high local optima in combinatorial fitness landscapes.Two particular aspects of local search are considered: ...
Self-feedback differential evolution adapting to fitness landscape characteristics
Differential evolution (DE) is one of the most powerful and versatile evolutionary algorithms for efficiently solving complex real-world optimization problems in recent years. Since its introduction in 1995, the research focus in DE has mostly been on ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sep 2022
631 pages
ISBN:978-3-031-14713-5
DOI:10.1007/978-3-031-14714-2
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2022.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 10 September 2022
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 07 Jan 2025