research-article

Public Access

Local optima organize into lattices under recombination: an example using the traveling salesman problem

Authors:

Darrell Whitley,

Gabriela OchoaAuthors Info & Claims

GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 757 - 765

https://doi.org/10.1145/3512290.3528747

Published: 08 July 2022 Publication History

Abstract

Local optima networks (LONs) model the global distribution and connectivity pattern of local optima under given search operators. Recent research has looked at how recombination operators can jump from a pair of parents that are locally optimal to a new child that is either a local optimum, or is guaranteed to be in a new basin of attraction. Recombination can therefore also induce a local optima network which maps how crossover moves between local optima. In this paper, we prove that recombination induces a LON which is actually a network of overlapping hypercube lattices. Given two or more samples from any lattice, we can also infer the existence of additional local optima that have not previously been reached by sampling. We prove that these lattices can be exponentially large. Finally, we prove that there exists TSP instances can be solved in polynomial time by exploiting Partition Crossover; these same instances are not solved by local search.

References

[1]

Khulood Alyahya and Jonathan E Rowe. 2016. Simple random sampling estimation of the number of local optima. In Parallel Problem Solving from Nature. Springer, 932--941.

[2]

David Applegate, Robert Bixby, Vašek Chvátal, and William Cook. 2003. Concorde TSP Solver. http://www.math.uwaterloo.ca/tsp/concorde.html

[3]

D Applegate, Wm Cook, and A Rhohe. 2003. Chained Lin-Kernighan for large traveling salesman problems. INFORMS Journal on Computing 15, 1 (2003), 82--92.

Digital Library

[4]

William J Cook. 2011. In pursuit of the traveling salesman: mathematics at the limits of computation. Princeton University Press.

[5]

T. Cormen, C. Leiserson, R. Rivest, and C. Stein. 2001. Introduction to Algorithms, 2nd Edition. MIT Press, New York.

[6]

G. Csardi and T. Nepusz. 2006. The igraph software package for complex network research. InterJournal Complex Systems (2006), 1695.

[7]

F. Daolio, M. Tomassini, S. Verel, and G. Ochoa. 2011. Communities of minima in local optima networks of combinatorial spaces. Physica A 390(9) (2011), 1684-- 1694.

[8]

OQ de Carvalho, R Tinós, D Whitley, and DS Sanches. 2019. A new method for identification of recombining components in the Generalized Partition Crossover. In Brazilian Conference on Intelligent Systems. IEEE, 36--41.

[9]

Thomas M. J. Fruchterman and Edward M. Reingold. 1991. Graph Drawing by Force-directed Placement. Softw. Pract. Exper. 21, 11 (Nov. 1991), 1129--1164.

Digital Library

[10]

J Garnier and L Kallel. 2002. Efficiency of Local Search Multiple Local Optima. SIAM J Discrete Mathematics 15, 1 (2002), 122--141.

Digital Library

[11]

Lov K. Grover. 1992. Local search and the local structure of NP-complete problems. Operations Research Letters 12 (1992), 235--243.

Digital Library

[12]

Michael Hahsler and Kurt Hornik. 2007. TSP---Infrastructure for the Traveling Salesperson Problem. Journal of Statistical Software 23, 2 (2007), 1--21.

[13]

D. Hains, D. Whitley, and A. Howe. 2011. Revisiting the big valley search space structure in the TSP. J. Operational Research Society 62(2) (2011), 305--312.

[14]

Th. Hales. 2007. The Jordan curve theorem, formally and informally. The American Mathematical Monthly 114 (2007), 882--894.

[15]

Keld Helsgaun. 2000. An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research 126, 1 (2000), 106-- 130.

[16]

A Mendiburu IL Hernando and JA Lozano. 2013. An evaluation of methods for estimating the number of local optima in combinatorial optimization problems. Evolutionary Computation 21, 4 (2013), 625--658.

Digital Library

[17]

S. Lin and B. W. Kernighan. 1973. An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Research 21 (1973), 498--516.

Digital Library

[18]

Olivier Martin, Steve W Otto, and Edward W Felten. 1992. Large-step markov chains for the TSP incorporating local search heuristics. Operations Research Letters 11 (1992), 219--224.

Digital Library

[19]

A Möbius, B Freisleben, P Merz, and M Schreiber. 1999. Combinatorial optimization by iterative partial transcription. Physical Review E 59, 4 (1999), 4667.

[20]

G. Ochoa, F. Chicano, R. Tinos, and D. Whitley. 2015. Tunnelling Crossover Networks. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO). ACM, 449--456.

Digital Library

[21]

G. Ochoa, M. Tomassini, S. Verel, and C. Darabos. 2008. A Study of NK Landscapes' Basins and Local Optima Networks. In Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation (Atlanta, GA, USA) (GECCO '08). ACM, New York, NY, USA, 555--562.

Digital Library

[22]

Gabriela Ochoa and Nadarajen Veerapen. 2016. Deconstructing the Big Valley Search Space Hypothesis. In Evolutionary Computation in Combinatorial Optimization, EvoCOP 2016 (LNCS, Vol. 9595). Springer International Publishing, Cham, 58--73.

[23]

Gabriela Ochoa and Nadarajen Veerapen. 2018. Mapping the global structure of TSP fitness landscapes. J. Heuristics 24, 3 (2018), 265--294.

Digital Library

[24]

C R Reeves and A V Eremeev. 2004. Statistical analysis of local search landscapes. J Operational Research Society 55, 7 (2004), 687--693.

[25]

Christian M. Reidys and Peter F. Stadler. 2002. Combinatorial Landscapes. SIAM Rev. 44 (2002), 3--54.

Digital Library

[26]

Renato Tinós, Keld Helsgaun, and Darrell Whitley. 2018. Efficient recombination in the Lin-Kernighan-Helsgaun traveling salesman heuristic. In International Conference on Parallel Problem Solving from Nature. Springer, 95--107.

[27]

R. Tinos, D. Whitley, and F. Chicano. 2015. Partition Crossover for Pseudo-Boolean Optimization. In Foundations of Genetic Algorithms. ACM Press, 137--149.

[28]

Renato Tinós, Darrell Whitley, and Gabriela Ochoa. 2014. Generalized Asymmetric Partition Crossover (GAPX) for the Asymmetric TSP. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'14). ACM, 501--508.

Digital Library

[29]

Renato Tinós, Darrell Whitley, and Gabriela Ochoa. 2020. A new generalized partition crossover for the traveling salesman problem: tunneling between local optima. Evolutionary computation 28(2) (2020), 255--288.

[30]

N Veerapen, G Ochoa, R Tinós, and D Whitley. 2016. Tunnelling crossover networks for the Asymmetric TSP. In PPSN. Springer, 994--1003.

[31]

L. Darrell Whitley, Andrew M. Sutton, and Adele E. Howe. 2008. Understanding Elementary Landscapes. In Proceedings of the Genetic and Evolutionary Computation Conference. ACM Press.

Cited By

Thomson SVeerapen NOchoa Gvan den Berg DSilva SPaquete L(2023)Randomness in Local Optima Network SamplingProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3596309(2099-2107)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3596309

Index Terms

Local optima organize into lattices under recombination: an example using the traveling salesman problem
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
    2. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Discrete optimization
        Optimization with randomized search heuristics
        Evolutionary algorithms

Recommendations

A parallel ensemble genetic algorithm for the traveling salesman problem
GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference

A parallel ensemble of Genetic Algorithms for the Traveling Salesman Problem (TSP) is proposed. Different TSP solvers perform efficiently on different instance types. However, finding the best solver for all instances is challenging. A hybrid of the ...
Analysis of evolutionary multi-tasking as an island model
GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Recently, an idea of evolutionary multi-tasking has been proposed and applied to various types of optimization problems. The basic idea of evolutionary multi-tasking is to simultaneously solve multiple optimization problems (i.e., tasks) in a ...
Tunneling between optima: partition crossover for the traveling salesman problem
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

A new recombination operator is introduced for the Traveling Salesman Problem called partition crossover. Theoretical and empirical results indicate that when two local optima are recombined using partition crossover, two offspring are produced that are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference

July 2022

1472 pages

ISBN:9781450392372

DOI:10.1145/3512290

Editor:
Jonathan E. Fieldsend
University of Exeter
,
General Chair:
Markus Wagner
The University of Adelaide

Copyright © 2022 ACM.

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 protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF (National Science Foundation)

Conference

GECCO '22

Sponsor:

SIGEVO

GECCO '22: Genetic and Evolutionary Computation Conference

July 9 - 13, 2022

Massachusetts, Boston

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
198
Total Downloads

Downloads (Last 12 months)79
Downloads (Last 6 weeks)4

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Thomson SVeerapen NOchoa Gvan den Berg DSilva SPaquete L(2023)Randomness in Local Optima Network SamplingProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3596309(2099-2107)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3596309

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten