More Web Proxy on the site http://driver.im/

research-article

Comparing communities of optima with funnels in combinatorial fitness landscapes

Authors:

Sarah L. Thomson,

Gabriela OchoaAuthors Info & Claims

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

Pages 377 - 384

https://doi.org/10.1145/3071178.3071211

Published: 01 July 2017 Publication History

Abstract

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 could help with designing effective diversification mechanisms for a 'smoothing' effect, making optimisation easier. We model fitness landscapes as local optima networks. The relationship between communities of local optima found by network clustering algorithms and funnels is explored. Funnels are identified using the notion of monotonic sequences from the study of energy landscapes in theoretical chemistry. NK Landscapes and the Quadratic Assignment Problem are used as case studies. Our results show that communities are linked to funnels. The analysis exhibits relationships between these landscape structures and the performance of trajectory-based metaheuristics such as Simulated Annealing (SA) and Iterated Local Search (ILS). In particular, ILS gets trapped in funnels, and modular communities of optima slow it down. The funnels contribute to lower success for SA. We show that increasing the strength of ILS perturbation helps to 'smooth' the funnels and improves performance in multi-funnel landscapes.

References

[1]

Thomas Bartz-Beielstein, Marco Chiarandini, Luís Paquete, and Mike Preuss. 2010. Experimental methods for the analysis of optimization algorithms. Springer.

Digital Library

[2]

Douglas Bates, Martin Mächler, Ben Bolker, and Steve Walker. 2015. Fitting Linear Mixed-Effects Models Using lme4. Journal of Statistical Software 67, 1 (2015), 1--48.

[3]

R Stephen Berry and Ralph Breitengraser-Kunz. 1995. Topography and dynamics of multidimensional interatomic potential surfaces. Physical review letters 74, 20 (1995), 3951.

[4]

Gabor Csardi and Tamas Nepusz. 2006. The igraph software package for complex network research. InterJournal Complex Systems (2006), 1695. http://igraph.org

[5]

Fabio Daolio, Marco Tomassini, Sebastien Verel, and Gabriela Ochoa. 2011. Communities of minima in local optima networks of combinatorial spaces. Physica A: Statistical Mechanics and its Applications 390, 9 (2011), 1684--1694.

[6]

Jonathan PK Doye, Mark A Miller, and David J Wales. 1999. The double-funnel energy landscape of the 38-atom Lennard-Jones cluster. The Journal of Chemical Physics 110, 14 (1999), 6896--6906.

[7]

Santo Fortunate 2010. Community detection in graphs. Physics reports 486, 3 (2010), 75--174.

[8]

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

[9]

Sebastian Herrmann, Gabriela Ochoa, and Franz Rothlauf. 2016. Communities of Local Optima as Funnels in Fitness Landscapes. In Proceedings of the 2016 on Genetic and Evolutionary Computation Conference. 325--331.

Digital Library

[10]

Jérémie Humeau, Arnaud Liefooghe, E-G Talbi, and Sébastien Verel. 2013. ParadisEO-MO: From fitness landscape analysis to efficient local search algorithms. Journal of Heuristics 19, 6 (2013), 881--915.

Digital Library

[11]

J. Knowles and D. Corne. 2003. Instance Generators and Test Suites for the Multiobjective Quadratic Assignment Problem. In Proceedings of the Evolutionary Multi-Criterion Optimization Conference (EMO 2003) (LNCS). Springer, 295--310.

Digital Library

[12]

Shinichi Nakagawa and Holger Schielzeth. 2013. A general and simple method for obtaining R2 from generalized linear mixed-effects models. Methods in Ecology and Evolution 4, 2 (2013), 133--142.

[13]

Gabriela Ochoa and Nadarajen Veerapen. 2016. Deconstructing the big valley search space hypothesis. In European Conference on Evolutionary Computation in Combinatorial Optimization. Springer, 58--73.

[14]

Martin Rosvall, Daniel Axelsson, and Carl T Bergstrom. 2009. The map equation. The European Physical Journal Special Topics 178, 1 (2009), 13--23.

[15]

Peter F Stadler. 2002. Fitness landscapes. In Biological evolution and statistical physics. Springer, 183--204.

[16]

Thomas Stützle. 2006. Iterated local search for the quadratic assignment problem. European Journal of Operational Research 174, 3 (2006), 1519--1539.

[17]

Marco Tomassini, Sebastien Verel, and Gabriela Ochoa. 2008. Complex-network analysis of combinatorial spaces: The NK landscape case. Physical Review E 78, 6 (2008), 066114.

[18]

Stijn Van Dongen. 2000. A cluster algorithm for graphs. Report-Information systems 10 (2000), 1--40.

Cited By

Dang DLehre PLi XHandl J(2024)The SLO Hierarchy of pseudo-Boolean Functions and Runtime of Evolutionary AlgorithmsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654221(1551-1559)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654221
Richter HThomson S(2024)Information Flow and Laplacian Dynamics on Local Optima Networks2024 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC60901.2024.10612156(01-08)Online publication date: 30-Jun-2024
https://doi.org/10.1109/CEC60901.2024.10612156
Dolgui AEremeev ASigaev V(2024)Fitness landscapes of buffer allocation problem for production lines with unreliable machinesComputers and Operations Research10.1016/j.cor.2024.106819172:COnline publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1016/j.cor.2024.106819
Show More Cited By

Index Terms

Comparing communities of optima with funnels in combinatorial fitness landscapes
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies

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 ...
Communities of Local Optima as Funnels in Fitness Landscapes
GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

We conduct an analysis of local optima networks extracted from fitness landscapes of the Kauffman NK model under iterated local search. Applying the Markov Cluster Algorithm for community detection to the local optima networks, we find that the ...
Funnels in Multi-objective Fitness Landscapes
Parallel Problem Solving from Nature – PPSN XVIII
Abstract
Funnels are related to the big-valley hypothesis in combinatorial fitness landscapes. It suggests that local optima are not randomly distributed but are instead clustered around the global optimum, forming a coarse-grained global structure. Multi-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

July 2017

1427 pages

ISBN:9781450349208

DOI:10.1145/3071178

General Chair:
Peter A. N. Bosman
Centrum Wiskunde & Informatica (CWI)

Copyright © 2017 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: 01 July 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

GECCO '17

Sponsor:

SIGEVO

GECCO '17: Genetic and Evolutionary Computation Conference

July 15 - 19, 2017

Berlin, Germany

Acceptance Rates

GECCO '17 Paper Acceptance Rate 178 of 462 submissions, 39%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
145
Total Downloads

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

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Dang DLehre PLi XHandl J(2024)The SLO Hierarchy of pseudo-Boolean Functions and Runtime of Evolutionary AlgorithmsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654221(1551-1559)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654221
Richter HThomson S(2024)Information Flow and Laplacian Dynamics on Local Optima Networks2024 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC60901.2024.10612156(01-08)Online publication date: 30-Jun-2024
https://doi.org/10.1109/CEC60901.2024.10612156
Dolgui AEremeev ASigaev V(2024)Fitness landscapes of buffer allocation problem for production lines with unreliable machinesComputers and Operations Research10.1016/j.cor.2024.106819172:COnline publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1016/j.cor.2024.106819
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
Benavides XCeberio JHernando LLozano JSilva SPaquete L(2023)New Knowledge about the Elementary Landscape Decomposition for Solving the Quadratic Assignment ProblemProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590369(239-247)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590369
Tanaka STakadama KSato H(2023)Multi-objectivization Relaxes Multi-funnel Structures in Single-objective NK-landscapesEvolutionary Computation in Combinatorial Optimization10.1007/978-3-031-30035-6_13(195-210)Online publication date: 31-Mar-2023
https://doi.org/10.1007/978-3-031-30035-6_13
Thomson SOchoa GWagner M(2022)On funnel depths and acceptance criteria in stochastic local searchProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528831(287-295)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528831
Dang DEremeev ALehre PKrawiec K(2021)Non-elitist evolutionary algorithms excel in fitness landscapes with sparse deceptive regions and dense valleysProceedings of the Genetic and Evolutionary Computation Conference10.1145/3449639.3459398(1133-1141)Online publication date: 26-Jun-2021
https://dl.acm.org/doi/10.1145/3449639.3459398
Thomson SOchoa GVerel SVeerapen N(2020)Inferring Future LandscapesEvolutionary Computation10.1162/evco_a_0027128:4(621-641)Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1162/evco_a_00271
Martins MYafrani MDelgado MLüders RCoello Coello C(2020)Multi-layer local optima networks for the analysis of advanced local search-based algorithmsProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390179(219-227)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3390179
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.

Media

Figures

Other

Tables

View Table of Contents