A long-standing problem in Evolutionary Computation consists in how to choose an appropriate representation for the solutions. In this work we investigate the feasibility of synthesizing a representation automatically, for the large class of problems whose solution spaces can be defined by a context-free grammar. We propose a framework based on a form of meta-evolution in which individuals are candidate representations expressed with an ad hoc language that we have developed to this purpose. Individuals compete and evolve according to an evolutionary search aimed at optimizing such representation properties as redundancy, locality, uniformity of redundancy. We assessed experimentally three variants of our framework on established benchmark problems and compared the resulting representations to human-designed representations commonly used (e.g., classical Grammatical Evolution). The results are promising in the sense that the evolved representations indeed exhibit better properties than the human-designed ones. Furthermore, while those improved properties do not result in a systematic improvement of search effectiveness, some of the evolved representations do improve search effectiveness over the human-designed baseline.

On the Automatic Design of a Representation for Grammar-Based Genetic Programming

Medvet, Eric
;
Bartoli, Alberto
2018-01-01

Abstract

A long-standing problem in Evolutionary Computation consists in how to choose an appropriate representation for the solutions. In this work we investigate the feasibility of synthesizing a representation automatically, for the large class of problems whose solution spaces can be defined by a context-free grammar. We propose a framework based on a form of meta-evolution in which individuals are candidate representations expressed with an ad hoc language that we have developed to this purpose. Individuals compete and evolve according to an evolutionary search aimed at optimizing such representation properties as redundancy, locality, uniformity of redundancy. We assessed experimentally three variants of our framework on established benchmark problems and compared the resulting representations to human-designed representations commonly used (e.g., classical Grammatical Evolution). The results are promising in the sense that the evolved representations indeed exhibit better properties than the human-designed ones. Furthermore, while those improved properties do not result in a systematic improvement of search effectiveness, some of the evolved representations do improve search effectiveness over the human-designed baseline.
2018
978-3-319-77552-4
978-3-319-77553-1
https://link.springer.com/chapter/10.1007/978-3-319-77553-1_7
File in questo prodotto:
File Dimensione Formato  
2018-EuroGP-GrammarGPRepresentationGeneration (2).pdf

accesso aperto

Descrizione: Articolo principale
Tipologia: Bozza finale post-referaggio (post-print)
Licenza: Creative commons
Dimensione 323.6 kB
Formato Adobe PDF
323.6 kB Adobe PDF Visualizza/Apri
front matter+eurogp2018.pdf

Accesso chiuso

Tipologia: Documento in Versione Editoriale
Licenza: Copyright Editore
Dimensione 493.1 kB
Formato Adobe PDF
493.1 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

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/11368/2921572
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact