Weighted Hierarchical Grammatical Evolution

Alberto Bartoli, Mauro Castelli, Eric Medvet

Research output: Contribution to journalArticle

1 Citation (Scopus)
6 Downloads (Pure)

Abstract

Grammatical evolution (GE) is one of the most widespread techniques in evolutionary computation. Genotypes in GE are bit strings while phenotypes are strings, of a language defined by a user-provided context-free grammar. In this paper, we propose a novel procedure for mapping genotypes to phenotypes that we call weighted hierarchical GE (WHGE). WHGE imposes a form of hierarchy on the genotype and encodes grammar symbols with a varying number of bits based on the relative expressive power of those symbols. WHGE does not impose any constraint on the overall GE framework, in particular, WHGE may handle recursive grammars, uses the classical genetic operators, and does not need to define any bound in advance on the size of phenotypes. We assessed experimentally our proposal in depth on a set of challenging and carefully selected benchmarks, comparing the results of the standard GE framework as well as two of the most significant enhancements proposed in the literature: 1) position-independent GE and 2) structured GE. Our results show that WHGE delivers very good results in terms of fitness as well as in terms of the properties of the genotype-phenotype mapping procedure.

Original languageEnglish
Number of pages13
JournalIEEE Transactions on Cybernetics
Early online date6 Nov 2018
DOIs
Publication statusPublished - Mar 2019

Fingerprint

Context free grammars
Evolutionary algorithms

Keywords

  • Benchmark testing
  • Genetic programming
  • Genetics
  • genotype-phenotype mapping
  • Grammar
  • Indexing
  • Production
  • Proposals
  • representation
  • Standards

Cite this

@article{9282a719d62143b8bcb7d63dd186190a,
title = "Weighted Hierarchical Grammatical Evolution",
abstract = "Grammatical evolution (GE) is one of the most widespread techniques in evolutionary computation. Genotypes in GE are bit strings while phenotypes are strings, of a language defined by a user-provided context-free grammar. In this paper, we propose a novel procedure for mapping genotypes to phenotypes that we call weighted hierarchical GE (WHGE). WHGE imposes a form of hierarchy on the genotype and encodes grammar symbols with a varying number of bits based on the relative expressive power of those symbols. WHGE does not impose any constraint on the overall GE framework, in particular, WHGE may handle recursive grammars, uses the classical genetic operators, and does not need to define any bound in advance on the size of phenotypes. We assessed experimentally our proposal in depth on a set of challenging and carefully selected benchmarks, comparing the results of the standard GE framework as well as two of the most significant enhancements proposed in the literature: 1) position-independent GE and 2) structured GE. Our results show that WHGE delivers very good results in terms of fitness as well as in terms of the properties of the genotype-phenotype mapping procedure.",
keywords = "Benchmark testing, Genetic programming, Genetics, genotype-phenotype mapping, Grammar, Indexing, Production, Proposals, representation, Standards",
author = "Alberto Bartoli and Mauro Castelli and Eric Medvet",
note = "Bartoli, A., Castelli, M., & Medvet, E. (2018). Weighted Hierarchical Grammatical Evolution. IEEE Transactions on Cybernetics. DOI: 10.1109/TCYB.2018.2876563",
year = "2019",
month = "3",
doi = "10.1109/TCYB.2018.2876563",
language = "English",
journal = "IEEE Transactions on Cybernetics",
issn = "2168-2267",
publisher = "IEEE Advancing Technology for Humanity",

}

Weighted Hierarchical Grammatical Evolution. / Bartoli, Alberto; Castelli, Mauro; Medvet, Eric.

In: IEEE Transactions on Cybernetics, 03.2019.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Weighted Hierarchical Grammatical Evolution

AU - Bartoli, Alberto

AU - Castelli, Mauro

AU - Medvet, Eric

N1 - Bartoli, A., Castelli, M., & Medvet, E. (2018). Weighted Hierarchical Grammatical Evolution. IEEE Transactions on Cybernetics. DOI: 10.1109/TCYB.2018.2876563

PY - 2019/3

Y1 - 2019/3

N2 - Grammatical evolution (GE) is one of the most widespread techniques in evolutionary computation. Genotypes in GE are bit strings while phenotypes are strings, of a language defined by a user-provided context-free grammar. In this paper, we propose a novel procedure for mapping genotypes to phenotypes that we call weighted hierarchical GE (WHGE). WHGE imposes a form of hierarchy on the genotype and encodes grammar symbols with a varying number of bits based on the relative expressive power of those symbols. WHGE does not impose any constraint on the overall GE framework, in particular, WHGE may handle recursive grammars, uses the classical genetic operators, and does not need to define any bound in advance on the size of phenotypes. We assessed experimentally our proposal in depth on a set of challenging and carefully selected benchmarks, comparing the results of the standard GE framework as well as two of the most significant enhancements proposed in the literature: 1) position-independent GE and 2) structured GE. Our results show that WHGE delivers very good results in terms of fitness as well as in terms of the properties of the genotype-phenotype mapping procedure.

AB - Grammatical evolution (GE) is one of the most widespread techniques in evolutionary computation. Genotypes in GE are bit strings while phenotypes are strings, of a language defined by a user-provided context-free grammar. In this paper, we propose a novel procedure for mapping genotypes to phenotypes that we call weighted hierarchical GE (WHGE). WHGE imposes a form of hierarchy on the genotype and encodes grammar symbols with a varying number of bits based on the relative expressive power of those symbols. WHGE does not impose any constraint on the overall GE framework, in particular, WHGE may handle recursive grammars, uses the classical genetic operators, and does not need to define any bound in advance on the size of phenotypes. We assessed experimentally our proposal in depth on a set of challenging and carefully selected benchmarks, comparing the results of the standard GE framework as well as two of the most significant enhancements proposed in the literature: 1) position-independent GE and 2) structured GE. Our results show that WHGE delivers very good results in terms of fitness as well as in terms of the properties of the genotype-phenotype mapping procedure.

KW - Benchmark testing

KW - Genetic programming

KW - Genetics

KW - genotype-phenotype mapping

KW - Grammar

KW - Indexing

KW - Production

KW - Proposals

KW - representation

KW - Standards

UR - http://www.scopus.com/inward/record.url?scp=85056325866&partnerID=8YFLogxK

U2 - 10.1109/TCYB.2018.2876563

DO - 10.1109/TCYB.2018.2876563

M3 - Article

JO - IEEE Transactions on Cybernetics

JF - IEEE Transactions on Cybernetics

SN - 2168-2267

ER -