Top

Published in:

2018 | OriginalPaper | Chapter

How Perturbation Strength Shapes the Global Structure of TSP Fitness Landscapes

Authors : Paul McMenemy, Nadarajen Veerapen, Gabriela Ochoa

Published in: Evolutionary Computation in Combinatorial Optimization

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Local optima networks are a valuable tool used to analyse and visualise the global structure of combinatorial search spaces; in particular, the existence and distribution of multiple funnels in the landscape. We extract and analyse the networks induced by Chained-LK, a powerful iterated local search for the TSP, on a large set of randomly generated (Uniform and Clustered) instances. Results indicate that increasing the perturbation strength employed by Chained-LK modifies the landscape’s global structure, with the effect being markedly different for the two classes of instances. Our quantitative analysis shows that several funnel metrics have stronger correlations with Chained-LK success rate than the number of local optima, indicating that global structure clearly impacts search performance.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter On the Fractal Nature of Local Optima Networks

next chapter Worst Improvement Based Iterated Local Search

dimacs.rutgers.edu/Challenges/TSP/download.html.

Ochoa, G., Tomassini, M., Verel, S., Darabos, C.: A study of NK landscapes’ basins and local optima networks. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO), pp. 555–562. ACM (2008)

Verel, S., Ochoa, G., Tomassini, M.: Local optima networks of NK landscapes with neutrality. IEEE Trans. Evol. Comput. 15(6), 783–797 (2011)CrossRef

Newman, M.E.J.: Networks: An Introduction. Oxford University Press, Oxford (2010)CrossRef

Ochoa, G., Veerapen, N.: Mapping the global structure of tsp fitness landscapes. J. Heuristics 1–30 (2017). https://doi.org/10.1007/s10732-017-9334-0. ISSN 15729397

Ochoa, G., Veerapen, N.: Deconstructing the big valley search space hypothesis. In: Chicano, F., Hu, B., García-Sánchez, P. (eds.) EvoCOP 2016. LNCS, vol. 9595, pp. 58–73. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-30698-8_5CrossRef

Doye, J.P.K., Miller, M.A., Wales, D.J.: The double-funnel energy landscape of the 38-atom Lennard-Jones cluster. J. Chem. Phys. 110(14), 6896–6906 (1999)CrossRef

Applegate, D., Cook, W., Rohe, A.: Chained Lin-Kernighan for large traveling salesman problems. INFORMS J. Comput. 15, 82–92 (2003)MathSciNetCrossRef

Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21, 498–516 (1973)MathSciNetCrossRef

Lourenço, H.R., Martin, O.C., Stützle, T.: Iterated local search. In: Handbook of Metaheuristics, pp. 320–353. Kluwer Academic Publishers, Boston (2003)

10.

Herrmann, S., Herrmann, M., Ochoa, G., Rothlauf, F.: Shaping communities of local optima by perturbation strength. In: Genetic and Evolutionary Computation Conference, GECCO, pp. 266–273 (2017)

11.

Martin, O., Otto, S.W., Felten, E.W.: Large-step Markov chains for the TSP incorporating local search heuristics. Oper. Res. Lett. 11, 219–224 (1992)MathSciNetCrossRef

12.

Stadler, P.F.: Fitness landscapes. Appl. Math. Comput. 117, 187–207 (2002)MathSciNet

13.

Veerapen, N., Ochoa, G., Tinós, R., Whitley, D.: Tunnelling crossover networks for the asymmetric TSP. In: Handl, J., Hart, E., Lewis, P.R., López-Ibáñez, M., Ochoa, G., Paechter, B. (eds.) PPSN XIV. LNCS, vol. 9921, pp. 994–1003. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45823-6_93CrossRef

14.

Ochoa, G., Veerapen, N., Daolio, F., Tomassini, M.: Understanding phase transitions with local optima networks: number partitioning as a case study. In: Hu, B., López-Ibáñez, M. (eds.) EvoCOP 2017. LNCS, vol. 10197, pp. 233–248. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-55453-2_16CrossRef

15.

Applegate, D.L., Bixby, R.E., Chvátal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton (2007)MATH

16.

Applegate, D., Bixby, R., Chvátal, V., Cook, W.: Concorde TSP solver (2003). http://www.math.uwaterloo.ca/tsp/concorde.html

17.

Csardi, G., Nepusz, T.: The igraph software package for complex network research. Int. J. Complex Syst. 1695, 1–9 (2006)

Title: How Perturbation Strength Shapes the Global Structure of TSP Fitness Landscapes
Authors: Paul McMenemy
Nadarajen Veerapen
Gabriela Ochoa
Publisher: Springer International Publishing
Book: Evolutionary Computation in Combinatorial Optimization
Print ISBN: 978-3-319-77448-0

Electronic ISBN: 978-3-319-77449-7

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-77449-7_3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner