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

research-article

The K landscapes: a tunably difficult benchmark for genetic programming

Authors:

Leonardo Vanneschi,

Mauro Castelli,

Luca ManzoniAuthors Info & Claims

GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

Pages 1467 - 1474

https://doi.org/10.1145/2001576.2001773

Published: 12 July 2011 Publication History

Abstract

The NK landscapes are a well known benchmark for genetic algorithms (GAs) in which it is possible to tune the ruggedness of the fitness landscape by simply modifying the value of a parameter K. They have successfully been used in many theoretical studies, allowing researchers to discover interesting properties of the GAs dynamics in presence of rugged landscapes. A similar benchmark does not exist for genetic programming (GP) yet. Nevertheless, during the EuroGP conference debates of the last few years, the necessity of defining new benchmark problems for GP has repeatedly been expressed by a large part of the attendees. This paper is intended to fill this gap, by introducing an extension of the NK landscapes to tree based GP, that we call K landscapes. In this benchmark, epistasis are expressed as growing mutual interactions between the substructures of a tree as the parameter K increases. The fact that the problem becomes more and more difficult as the value of K increases is experimentally demonstrated. Interestingly, we also show that GP "bloats" more and more as K increases.

References

[1]

L. Altenberg. B2.7.2 NK fitness landscapes. In T. Baeck, et al., editors, Handbook of evolutionary computation. New York: Oxford University Press, 1997.

[2]

A. Asuncion and D. Newman. UCI machine learning repository, 2007.

[3]

J. M. Daida, R. Bertram, S. Stanhope, J. Khoo, S. Chaudhary, and O. Chaudhary. What makes a problem GP-hard? analysis of a tunably difficult problem in genetic programming. Genetic Programming and Evolvable Machines, 2:165--191, 2001.

Digital Library

[4]

K. Deb and D. E. Goldberg. Analyzing deception in trap functions. In D. Whitley, editor, Foundations of Genetic Algorithms, 2, pages 93--108. Morgan Kaufmann, 1993.

[5]

D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1989.

Digital Library

[6]

S. Gustafson, E. Burke, and N. Krasnogor. The tree-string problem: An artificial domain for structure and content search. In M. Keijzer, et al., editors, EuroGP 2005, pages 215--226. Springer, 2005.

Digital Library

[7]

J. H. Holland. Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, Michigan, 1975.

[8]

S. Kauffman and S. Levin. Towards a general theory of adaptive walks on rugged landscapes. J. Theoret. Biol., 128(1):11--45, 1987.

[9]

S. A. Kauffman. The Origins of Order. Oxford University Press, New York, 1993.

[10]

J. Kingman. Mathematics of genetic diversity. Number 34 in CBMS-NSF regional conference series in applied mathematics. Society for Industrial and Applied Mathematics, Philadelphia, Pa., 2. druck edition, 1980.

[11]

J. R. Koza. Genetic Programming. The MIT Press, Cambridge, Massachusetts, 1992.

Digital Library

[12]

M. Mitchell, S. Forrest, and J. Holland. The royal road for genetic algorithms: fitness landscapes and ga performance. In F. J. Varela and P. Bourgine, editors, Toward a Practice of Autonomous Systems, Proc. of the First European Conf. on Artif. Life, pages 245--254. The MIT Press, 1992.

[13]

M. O'Neill, L. Vanneschi, S. Gustafson, and W. Banzhaf. Open issues in genetic programming. Genetic Programming and Evolvable Machines, 11(3--4):339--363, 2010.

Digital Library

[14]

A. Orfila, J. M. Estevez-Tapiador, and A. Ribagorda. Evolving high-speed, easy-to-understand network intrusion detection rules with genetic programming. In M. Giacobini, et al., editors, App. of Evolutionary Computing, EvoWorkshops2009, LNCS. Springer Verlag, 2009.

Digital Library

[15]

R. Poli, W. B. Langdon, and N. F. McPhee. A field guide to genetic programming. Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk, 2008. (With contributions by J. R. Koza).

Digital Library

[16]

B. Punch, D. Zongker, and E. Goodman. The royal tree problem, a benchmark for single and multiple population genetic programming. In P. Angeline and K. Kinnear, editors, Advances in Genetic Programming 2, pages 299--316, Cambridge, MA, 1996. The MIT Press.

Digital Library

[17]

D. Song, M. I. Heywood, and A. N. Zincir-Heywood. A linear genetic programming approach to intrusion detection. In E. Cantú-Paz, et al., editors, Genetic and Evolutionary Computation -- GECCO-2003, volume 2724 of LNCS, pages 2325--2336, Chicago, 12--16 July 2003. Springer-Verlag.

Digital Library

[18]

W. A. Tackett. Recombination, Selection, and the Genetic Construction of Computer Programs. PhD thesis, University of Southern California, Department of Electrical Engineering Systems, USA, 1994.

Digital Library

[19]

M. Tomassini, L. Vanneschi, P. Collard, and M. Clergue. A study of fitness distance correlation as a difficulty measure in genetic programming. Evolutionary Computation, 13(2):213--239, Summer 2005.

Digital Library

[20]

L. Vanneschi. Theory and Practice for Efficient Genetic Programming. Ph.D. thesis, Faculty of Science, University of Lausanne, Switzerland, 2004. Downlodable version at: http://www.disco.unimib.it/vanneschi.

[21]

S. Wright. The roles of mutation, inbreeding, crossbreeding and selection in evolution. In D. F. Jones, editor, Proceedings og the Sixth International Congress on Genetics, volume 1, pages 356--366, 1932.

Cited By

Rodrigues NBatista JCava WVanneschi LSilva S(2023)Exploring SLUG: Feature Selection Using Genetic Algorithms and Genetic ProgrammingSN Computer Science10.1007/s42979-023-02106-35:1Online publication date: 8-Dec-2023
https://dl.acm.org/doi/10.1007/s42979-023-02106-3
Medvet ENadizar GManzoni LWagner M(2022)JGEAProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533960(2009-2018)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3533960
Rodrigues NBatista JLa Cava WVanneschi LSilva S(2022)SLUG: Feature Selection Using Genetic Algorithms and Genetic ProgrammingGenetic Programming10.1007/978-3-031-02056-8_5(68-84)Online publication date: 13-Apr-2022
https://doi.org/10.1007/978-3-031-02056-8_5
Show More Cited By

Index Terms

The K landscapes: a tunably difficult benchmark for genetic programming
1. Information systems

Recommendations

Fitness landscapes and problem hardness in genetic programming
GECCO '10: Proceedings of the 12th annual conference companion on Genetic and evolutionary computation

The performance of searching agents, or metaheuristics, like evolutionary algorithms (genetics algorithms, genetic programming, etc.) or local search algorithms (simulated annealing, tabu search, etc.) depend on some properties of the search space ...
A tunable model for multi-objective, epistatic, rugged, and neutral fitness landscapes
GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

The fitness landscape of a problem is the relation between the solution candidates and their reproduction probability. In order to understand optimization problems, it is essential to also understand the features of fitness landscapes and their ...
Analysis of epistasis correlation on NK landscapes with nearest-neighbor interactions
GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

Epistasis correlation is a measure that estimates the strength of interactions between problem variables. This paper presents an empirical study of epistasis correlation on a large number of random problem instances of NK landscapes with nearest ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

July 2011

2140 pages

ISBN:9781450305570

DOI:10.1145/2001576

Editor:
Natalio Krasnogor
University of Nottingham, UK
,
General Chair:
Pier Luca Lanzi
Politecnico di Milano, Italy

Copyright © 2011 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: 12 July 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '11

Sponsor:

SIGEVO

GECCO '11: Genetic and Evolutionary Computation Conference

July 12 - 16, 2011

Dublin, Ireland

Acceptance Rates

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
155
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Rodrigues NBatista JCava WVanneschi LSilva S(2023)Exploring SLUG: Feature Selection Using Genetic Algorithms and Genetic ProgrammingSN Computer Science10.1007/s42979-023-02106-35:1Online publication date: 8-Dec-2023
https://dl.acm.org/doi/10.1007/s42979-023-02106-3
Medvet ENadizar GManzoni LWagner M(2022)JGEAProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533960(2009-2018)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3533960
Rodrigues NBatista JLa Cava WVanneschi LSilva S(2022)SLUG: Feature Selection Using Genetic Algorithms and Genetic ProgrammingGenetic Programming10.1007/978-3-031-02056-8_5(68-84)Online publication date: 13-Apr-2022
https://doi.org/10.1007/978-3-031-02056-8_5
Nadizar GMedvet EMiras K(2022)On the Schedule for Morphological Development of Evolved Modular Soft RobotsGenetic Programming10.1007/978-3-031-02056-8_10(146-161)Online publication date: 13-Apr-2022
https://doi.org/10.1007/978-3-031-02056-8_10
Bartoli ACastelli MMedvet E(2020)Weighted Hierarchical Grammatical EvolutionIEEE Transactions on Cybernetics10.1109/TCYB.2018.287656350:2(476-488)Online publication date: Feb-2020
https://doi.org/10.1109/TCYB.2018.2876563
Medvet EVirgolin MCastelli MBosman PGonçalves ITušar T(2018)Unveiling evolutionary algorithm representation with DU mapsGenetic Programming and Evolvable Machines10.1007/s10710-018-9332-519:3(351-389)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s10710-018-9332-5
Medvet EBartoli ADe Lorenzo ATarlao F(2018)GOMGE: Gene-Pool Optimal Mixing on Grammatical EvolutionParallel Problem Solving from Nature – PPSN XV10.1007/978-3-319-99253-2_18(223-235)Online publication date: 22-Aug-2018
https://doi.org/10.1007/978-3-319-99253-2_18
Medvet EBartoli A(2018)On the Automatic Design of a Representation for Grammar-Based Genetic ProgrammingGenetic Programming10.1007/978-3-319-77553-1_7(101-117)Online publication date: 2-Mar-2018
https://doi.org/10.1007/978-3-319-77553-1_7
Vanneschi LBakurov ICastelli M(2017)An initialization technique for geometric semantic GP based on demes evolution and despeciation2017 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2017.7969303(113-120)Online publication date: Jun-2017
https://doi.org/10.1109/CEC.2017.7969303
Griffiths TEkárt A(2017)Improving the Tartarus Problem as a Benchmark in Genetic ProgrammingGenetic Programming10.1007/978-3-319-55696-3_18(278-293)Online publication date: 15-Mar-2017
https://doi.org/10.1007/978-3-319-55696-3_18
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