tutorial

Fitness landscape characterisation of optimisation problems: GECCO 2017 tutorial

Authors:

Aldeida Aleti,

Katherine Malan,

Irene MoserAuthors Info & Claims

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

Pages 435 - 449

https://doi.org/10.1145/3067695.3067720

Published: 15 July 2017 Publication History

Get Access

References

[1]

Z.J. Czech (2008), "Statistical measures of a fitness landscape for the vehicle routing problem", In: IEEE International Symposium on Parallel and Distributed Processing, pp. 1--8.

Crossref

Google Scholar

[2]

F. Daolio, S. Verel, G. Ochoa, M. Tomassini (2012), "Local optima networks and the performance of iterated local search", In Proceedings of the 14th annual conference on Genetic and evolutionary computation, pp. 369--376.

Digital Library

Google Scholar

[3]

F. Daolio, S. Verel, G. Ochoa, M. Tomassini (2013), "Local optima networks of the permutation flow-shop problem", In International Conference on Artificial Evolution (Evolution Artificielle), pp. 41--52.

Google Scholar

[4]

W. Fontana, P.F. Stadler, E.G. Bornberg-Bauer, T. Griesmacher, I.L. Hofacker, M. Tacker, P. Tarazona, E.D. Weinberger and P. Schuster (1993), "RNA Folding and Combinatory Landscapes", Physical Review E, 47:2083--2099.

Crossref

Google Scholar

[5]

M. Franceschet (2011), "PageRank: standing on the shoulders of giants", Communications of the ACM, Vol. 54(6):92.

Digital Library

Google Scholar

[6]

S. Herrmann, F. Rothlauf (2015), "Predicting heuristic search performance with pageRank centrality in local optima networks", In Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, pp. 401--408.

Digital Library

Google Scholar

[7]

T. Jones and S. Forrest (1995), "Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms", In Proceedings of the Sixth International Conference on Genetic Algorithms, pp. 184--192.

Digital Library

Google Scholar

[8]

P. Kerschke and H Trautmann (2016), "The R-Package FLACCO for Exploratory Landscape Analysis with Applications to Multi-Objective Optimization Problems", In Proceedings of 2016 IEEE Congress on Evolutionary Computation, pp. 5262--5269.

Crossref

Google Scholar

[9]

M. Kubiak (2007), "Distance Measures and Fitness-Distance Analysis for the Capacitated Vehicle Routing Problem", In: Metaheuristics: Progress in Complex Systems Optimization, Operations Research/Computer Science Interfaces, vol. 39, pp. 345--364.

Crossref

Google Scholar

[10]

M. Lunacek and D. Whitley (2006), "The dispersion metric and the CMA evolution strategy", In Proceedings of the 8th Annual Genetic and Evolutionary Computation Conference, pp. 477--484.

Digital Library

Google Scholar

[11]

K.M. Malan and A.P. Engelbrecht (2009), "Quantifying Ruggedness of Continuous Landscapes using Entropy", In Proceedings of the IEEE Congress on Evolutionary Computation, pp. 1440--1447.

Digital Library

Google Scholar

[12]

K.M. Malan and A.P. Engelbrecht (2013), "Ruggedness, Funnels and Gradients in Fitness Landscapes and the Effect on PSO Performance", in Proceedings of the IEEE Congress on Evolutionary Computation, Cancun, Mexico, pp. 963--970.

Crossref

Google Scholar

[13]

K.M. Malan and A.P. Engelbrecht (2014), "Particle swarm optimisation failure prediction based on fitness landscape characteristics," 2014 IEEE Symposium on Swarm Intelligence, Orlando, FL, pp. 1--9.

Google Scholar

[14]

O. Mersmann, B. Bischl, H. Trautmann, M. Preuss, C. Weihs and G. Rudolph (2011), "Exploratory landscape analysis", In Proceedings of the 13th annual conference on Genetic and Evolutionary Computation, pp. 829--836.

Digital Library

Google Scholar

[15]

R. Morgan and M. Gallagher (2012), "Length Scale for Characterising Continuous Optimization Problems", In Parallel Problem Solving from Nature, Lecture Notes in Computer Science, Vol 7491, Springer, pp. 407--416.

Digital Library

Google Scholar

[16]

I. Moser and M. Gheorghita (2012), "Combining Search Space Diagnostics and Optimisation", in 2012 IEEE Congress on Evolutionary Computation, pp. 1--8.

Crossref

Google Scholar

[17]

C.L Müller and I.F. Sbalzarini (2011), "Global characterization of the CEC 2005 fitness landscapes using fitness-distance analysis", In Proceedings of the 2011 International Conference on Applications of Evolutionary Computation - Part I, pp. 294--303.

Digital Library

Google Scholar

[18]

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, pp. 555--562.

Digital Library

Google Scholar

[19]

E. Pitzer, M. Affenzeller, A. Beham, S. Wagner (2011), "Comprehensive and automatic fitness landscape analysis using heuristiclab", In Proceedings of the 13th International Conference on Computer Aided Systems Theory, pp. 424--431.

Digital Library

Google Scholar

[20]

E. Pitzer, S. Vonolfen, A. Beham, M. Affenzeller, V. Bolshakov, and G. Merkuryeva (2012), "Structural Analysis of Vehicle Routing Problems using General Fitness Landscape Analysis and Problem Specific Measures", In Proceedings of 1st Austalian Conference on the Application of Systems Engineering, Sydney, pp. 36--38.

Google Scholar

[21]

A. Runka, B. Ombuki-Berman, M. Ventresca (2009), "A search space analysis for the waste collection vehicle routing problem with time windows", In Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pp. 1813--1814.

Digital Library

Google Scholar

[22]

J. Tavares, F.B. Pereira and E. Costa (2006), "The role of representation on the multidimensional knapsack problem by means of fitness landscape analysis", In Proceedings of the 2006 IEEE Congress on Evolutionary Computation, pp. 2307--2314.

Crossref

Google Scholar

[23]

L. Vanneschi, M. Clergue, P. Collard, M. Tomassini, and S. Verel (2004). "Fitness Clouds and Problem Hardness in Genetic Programming", In Proceedings of Genetic and Evolutionary Computation Conference, volume 3103 of Lecture Notes in Computer Science, pp. 690--701. Springer Berlin Heidelberg.

Digital Library

Google Scholar

[24]

V.K. Vassilev, T.C. Fogarty and J.F. Miller (2003), "Smoothness, Ruggedness and Neutrality of Fitness Landscapes: from Theory to Application", In Advances in Evolutionary Computing: Theory and Applications, Springer-Verlag New York, Inc.,pp. 3--44.

Digital Library

Google Scholar

[25]

M. Ventresca, B. Ombuki-Berman, A. Runka (2013), "Predicting Genetic Algorithm Performance on the Vehicle Routing Problem Using Information Theoretic Landscape Measures", In: Middendorf M., Blum C. (eds) Evolutionary Computation in Combinatorial Optimization, EvoCOP 2013, Lecture Notes in Computer Science, vol 7832.

Digital Library

Google Scholar

[26]

S. Verel, P. Collard and M. Clergue (2003), "Where are bottlenecks in NK fitness landscapes?", In the 2003 Congress on Evolutionary Computation, pp. 273 -- 280.

Crossref

Google Scholar

[27]

S. Verel, F. Daolio, G. Ochoa and M. Tomassini (2012), "Local optima networks with escape edges", In Proceedings of the International Conference on Artificial Evolution, volume 7401 of Lecture Notes in Computer Science, pp. 49--60, Springer.

Digital Library

Google Scholar

[28]

J. Watson, L. Barbulescu, L. Whitley, A. Howe (2002), "Contrasting structured and random permutation flow-shop scheduling problems: search-space topology and algorithm performance", INFORMS Journal on Computing 14(2), pp. 98--123.

Digital Library

Google Scholar

[29]

E. Weinberger (1990), "Correlated and Uncorrelated Fitness Landscapes and How to Tell the Difference", Biological Cybernetics, 63(5):325--336.

Digital Library

Google Scholar

[30]

S. Wright (1932), "The Roles of Mutation, Inbreeding, Crossbreeding, and Selection in evolution", In Proceedings of the Sixth International Congress on Genetics, pp. 356--366.

Google Scholar

Cited By

View all

Sala RMuller R(2020)Benchmarking for Metaheuristic Black-Box Optimization: Perspectives and Open Challenges2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185724(1-8)Online publication date: Jul-2020
https://doi.org/10.1109/CEC48606.2020.9185724
Sala RMuller R(2020)Benchmarking for Metaheuristic Black-Box Optimization: Perspectives and Open Challenges2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185593(1-8)Online publication date: Jul-2020
https://doi.org/10.1109/CEC48606.2020.9185593

Recommendations

Analysis of fitness landscape modifications in evolutionary dynamic optimization

In this work, discrete dynamic optimization problems (DOPs) are theoretically analysed according to the modifications produced in the fitness landscape during the optimization process. Using the proposed analysis framework, the following DOPs are ...
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 ...
Bag of local landscape features for fitness landscape analysis

Evolutionary computation is a research field dealing with black-box and complex optimization problems whose fitness landscapes are usually unknown in advance. It is difficult to select an appropriate evolutionary algorithm and parameters for a given ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

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

July 2017

1934 pages

ISBN:9781450349390

DOI:10.1145/3067695

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 July 2017

Check for updates

Qualifiers

Tutorial

Conference

GECCO '17

Sponsor:

SIGEVO

GECCO '17: Genetic and Evolutionary Computation Conference

July 15 - 19, 2017

Berlin, Germany

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
209
Total Downloads

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

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Sala RMuller R(2020)Benchmarking for Metaheuristic Black-Box Optimization: Perspectives and Open Challenges2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185724(1-8)Online publication date: Jul-2020
https://doi.org/10.1109/CEC48606.2020.9185724
Sala RMuller R(2020)Benchmarking for Metaheuristic Black-Box Optimization: Perspectives and Open Challenges2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185593(1-8)Online publication date: Jul-2020
https://doi.org/10.1109/CEC48606.2020.9185593

View Options

Login options

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

Cited By

Recommendations

Analysis of fitness landscape modifications in evolutionary dynamic optimization

Self-feedback differential evolution adapting to fitness landscape characteristics

Bag of local landscape features for fitness landscape analysis