research-article

Additional Dimensions to the Study of Funnels in Combinatorial Landscapes

Authors:

Gabriela Ochoa,

Nadarajen VeerapenAuthors Info & Claims

GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

Pages 373 - 380

https://doi.org/10.1145/2908812.2908820

Published: 20 July 2016 Publication History

Abstract

The global structure of travelling salesman's fitness landscapes has recently revealed the presence of multiple 'funnels'. This implies that local optima are organised into several clusters, so that a particular local optimum largely belongs to a particular funnel. Such a global structure can increase search difficulty, especially, when the global optimum is located in a deep, narrow funnel. Our study brings more precision (and dimensions) to the notion of funnels with a data-driven approach using Local Optima Networks and the Chained Lin-Kernighan heuristic. We start by exploring the funnel `floors', characterising them using the notion of communities from complex networks. We then analyse the more complex funnel `basins'. Since their depth is relevant to search, we visualise them in 3D. Our study, across a set of TSP instances, reveals a multi-funnel structure in most of them. However, the specific topology varies across instances and relates to search difficulty. Finally, including a stronger perturbation into Chained Lin-Kernighan proved to smooth the funnel structure, reducing the number of funnels and enlarging the valley leading to global optima.

References

[1]

D. Applegate, R. Bixby, V. Chvátal, and W. Cook. Concorde TSP solver, 2003.

[2]

D. Applegate, W. Cook, and A. Rohe. Chained Lin-Kernighan for Large Traveling Salesman Problems. INFORMS Journal on Computing, 15:82--92, 2003.

Digital Library

[3]

K. D. Boese, A. B. Kahng, and S. Muddu. A new adaptive multi-start technique for combinatorial global optimizations. Operations Research Letters, 16:101--113, 1994.

Digital Library

[4]

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

[5]

F. Daolio, M. Tomassini, S. Vérel, and G. Ochoa. Communities of minima in local optima networks of combinatorial spaces. Physica A: Statistical Mechanics and its Applications, 390(9):1684--1694, 2011.

[6]

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

[7]

C. Flamm, I. L. Hofacker, P. F. Stadler, and M. T. Wolfinger. Barrier Trees of Degenerate Landscapes. Phys. Chem., 216:155--173, 2002.

[8]

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

[9]

J. Hallam and A. Prugel-Bennett. Large barrier trees for studying search. IEEE Transactions on Evolutionary Computation, 9(4):385--397, 2005.

Digital Library

[10]

D. Iclanzan, F. Daolio, and M. Tomassini. Data-driven local optima network characterization of QAPLIB instances. In Genetic and Evolutionary Computation Conference, GECCO 2014, pages 453--460, 2014.

Digital Library

[11]

E. D. Kolaczyk. Statistical Analysis of Network Data: Methods and Models. Springer Series in Statistics. 2010.

Digital Library

[12]

A. Lancichinetti and S. Fortunato. Community detection algorithms: a comparative analysis. Physical Review E, 80(5):56117, 2009.

[13]

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

Digital Library

[14]

M. Locatelli. On the Multilevel Structure of Global optimization problems. Computational Optimization and Applications, pages 5--22, 2005.

Digital Library

[15]

M. Lunacek and D. Whitley. The dispersion metric and the CMA evolution strategy. In Genetic and Evolutionary Computation Conference, GECCO 2006, pages 477--484, 2006.

Digital Library

[16]

M. Lunacek, D. Whitley, and A. M. Sutton. The impact of global structure on search. In Parallel Problem Solving from Nature - PPSN X, volume 5199 of LNCS, pages 498--507. Springer, 2008.

[17]

O. Martin, S. W. Otto, and E. W. Felten. Large-step markov chains for the TSP incorporating local search heuristics. Operations Research Letters, 11:219--224, 1992.

Digital Library

[18]

C. L. Müller and I. F. Sbalzarini. Energy landscapes of atomic clusters as black box optimization benchmarks. Evolutionary Computation, 20(4):543--573, 2012.

Digital Library

[19]

M. E. J. Newman. Networks: An Introduction. Oxford University Press, Oxford, UK, 2010.

Digital Library

[20]

G. Ochoa, M. Tomassini, S. Verel, and C. Darabos. A study of NK landscapes' basins and local optima networks. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2008, pages 555--562. ACM, 2008.

Digital Library

[21]

G. Ochoa and N. Veerapen. Deconstructing the Big Valley Search Space Hypothesis. In Evolutionary Computation in Combinatorial Optimization, EvoCOP 2016, volume 9595 of Lecture Notes in Computer Science, pages 58--73. Springer, 2016.

[22]

G. Ochoa, N. Veerapen, D. Whitley, and E. K. Burke. The Multi-Funnel Structure of TSP Fitness Landscapes: A Visual Exploration. In Artificial Evolution: 12th International Conference, Evolution Artificielle, EA 2015, volume 9554 of Lecture Notes in Computer Science, pages 1--13. Springer, 2016.

Digital Library

[23]

G. Reinelt. TSPLIB--a traveling salesman problem library. ORSA Journal on Computing, 3(4):376--384, 1991.

[24]

M. Rosvall and C. T. Bergstrom. Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences of the United States of America, 105(4):1118--23, 2008.

[25]

P. F. Stadler. Fitness landscapes. Appl. Math. and Comput, 117:187--207, 2002.

[26]

D. J. Wales. Energy landscapes and properties of biomolecules. Physical Biology, 2(4):S86--S93, 2005.

Cited By

Kerschke PHoos HNeumann FTrautmann H(2019)Automated Algorithm SelectionEvolutionary Computation10.1162/evco_a_0024227:1(3-45)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1162/evco_a_00242
Wuijts RThierens DAuger AStützle T(2019)Investigation of the traveling thief problemProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321766(329-337)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321766
Gnatowski ANiżyński T(2019)On Estimating LON-Based Measures in Cyclic Assignment Problem in Non-permutational Flow Shop Scheduling ProblemModelling and Performance Analysis of Cyclic Systems10.1007/978-3-030-27652-2_4(63-84)Online publication date: 17-Aug-2019
https://doi.org/10.1007/978-3-030-27652-2_4
Show More Cited By

Index Terms

Additional Dimensions to the Study of Funnels in Combinatorial Landscapes

Recommendations

Local optima networks for continuous fitness landscapes
GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Local Optima Networks (LONs) have been proposed as a coarsegrained model of discrete (combinatorial) fitness landscapes, where nodes are local optima and edges are search transitions based on an exploration search operator. This paper presents one of ...
Comparing communities of optima with funnels in combinatorial fitness landscapes
GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

The existence of sub-optimal funnels in combinatorial fitness landscapes has been linked to search difficulty. The exact nature of these structures --- and how commonly they appear --- is not yet fully understood. Improving our understanding of funnels ...
Mapping the global structure of TSP fitness landscapes

The global structure of combinatorial landscapes is not fully understood, yet it is known to impact the performance of heuristic search methods. We use a so-called local optima network model to characterise and visualise the global structure of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

July 2016

1196 pages

ISBN:9781450342063

DOI:10.1145/2908812

Editor:
Tobias Friedrich
Hasso Plattner Institute
,
General Chair:
Frank Neumann
University of Adelaide
,
Program Chair:
Andrew M. Sutton
Hasso Plattner Institute

Copyright © 2016 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: 20 July 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

GECCO '16

Sponsor:

SIGEVO

GECCO '16: Genetic and Evolutionary Computation Conference

July 20 - 24, 2016

Colorado, Denver, USA

Acceptance Rates

GECCO '16 Paper Acceptance Rate 137 of 381 submissions, 36%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
120
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kerschke PHoos HNeumann FTrautmann H(2019)Automated Algorithm SelectionEvolutionary Computation10.1162/evco_a_0024227:1(3-45)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1162/evco_a_00242
Wuijts RThierens DAuger AStützle T(2019)Investigation of the traveling thief problemProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321766(329-337)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321766
Gnatowski ANiżyński T(2019)On Estimating LON-Based Measures in Cyclic Assignment Problem in Non-permutational Flow Shop Scheduling ProblemModelling and Performance Analysis of Cyclic Systems10.1007/978-3-030-27652-2_4(63-84)Online publication date: 17-Aug-2019
https://doi.org/10.1007/978-3-030-27652-2_4
Ochoa GVeerapen N(2018)Mapping the global structure of TSP fitness landscapesJournal of Heuristics10.1007/s10732-017-9334-024:3(265-294)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1007/s10732-017-9334-0
Bożejko WGnatowski ANiżyński TAffenzeller MBeham A(2018)Local Optima Networks in Solving Algorithm Selection Problem for TSPContemporary Complex Systems and Their Dependability10.1007/978-3-319-91446-6_9(83-93)Online publication date: 27-May-2018
https://doi.org/10.1007/978-3-319-91446-6_9
Sanches DWhitley DTinós RBosman P(2017)Improving an exact solver for the traveling salesman problem using partition crossoverProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071304(337-344)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071304
Thomson SOchoa GDaolio FVeerapen N(2017)The effect of landscape funnels in QAPLIB instancesProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3067695.3082512(1495-1500)Online publication date: 15-Jul-2017
https://dl.acm.org/doi/10.1145/3067695.3082512
Hernando LDaolio FVeerapen NOchoa G(2017)Local Optima Networks of the Permutation Flowshop Scheduling Problem: Makespan vs. total flow time2017 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2017.7969541(1964-1971)Online publication date: 5-Jun-2017
https://dl.acm.org/doi/10.1109/CEC.2017.7969541
Langdon WVeerapen NOchoa G(2017)Visualising the Search Landscape of the Triangle ProgramGenetic Programming10.1007/978-3-319-55696-3_7(96-113)Online publication date: 15-Mar-2017
https://doi.org/10.1007/978-3-319-55696-3_7
Ochoa GVeerapen NDaolio FTomassini M(2017)Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case StudyEvolutionary Computation in Combinatorial Optimization10.1007/978-3-319-55453-2_16(233-248)Online publication date: 9-Mar-2017
https://doi.org/10.1007/978-3-319-55453-2_16
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten