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. Copyright 2011 ACM

Vanneschi, L., Castelli, M., Manzoni, L. (2011). The K landscapes: A tunably difficult benchmark for genetic programming. In GECCO-2011: PROCEEDINGS OF THE 13TH ANNUAL GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (pp.1467-1474). ASSOC COMPUTING MACHINERY [10.1145/2001576.2001773].

The K landscapes: A tunably difficult benchmark for genetic programming

VANNESCHI, LEONARDO;CASTELLI, MAURO;MANZONI, LUCA
2011

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. Copyright 2011 ACM
No
paper
Benchmarks; Epistasis; Genetic programming; Problem difficulty; Computational Theory and Mathematics; Theoretical Computer Science
English
Annual Genetic and Evolutionary Computation Conference (GECCO) JUL 12-16
978-1-4503-0557-0
Vanneschi, L., Castelli, M., Manzoni, L. (2011). The K landscapes: A tunably difficult benchmark for genetic programming. In GECCO-2011: PROCEEDINGS OF THE 13TH ANNUAL GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (pp.1467-1474). ASSOC COMPUTING MACHINERY [10.1145/2001576.2001773].
Vanneschi, L; Castelli, M; Manzoni, L
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/60781
Citazioni
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 14
Social impact