On the avoidance of fruitless wraps in grammatical evolution

Conor Ryan, Maarten Keijzer, Miguel Nicolau

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

Abstract

Grammatical Evolution (GE) is an evolutionary system that employs variable length linear chromosomes to represent computer programs. GE uses the individuals to produce derivation trees that adhere to a Backus Naur Form grammar, which are then mapped onto a program. One unusual characteristic of the system is the manner in which chromosomes can be "wrapped", that is, if an individual has used up all of its genes before a program is completely mapped, the chromosome is reread. While this doesn't guarantee that an individual will map, prior work suggested that wrapping is beneficial for the system, both in terms of increased success rates and a reduced number of invalid individuals. However, there has been no research into the number of times an individual should be wrapped before the system gives up, and an arbitrary upper limit is usually chosen. This paper discusses the different types of grammars that could be used with this system, and indicates the circumstances under which individuals will fail. It then presents a heuristic to minimize the number of wraps that have to be made before the system can determine that an individual will fail. It is shown that this can drastically reduce the amount of wrapping on a pathologically difficult problem, as well as on two classes of grammar often used by the system.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsErick Cantú-Paz, James A. Foster, Graham Kendall, Mark Harman, Dipankar Dasgupta, Kalyanmoy Deb, Lawrence David Davis, Rajkumar Roy, Una-May O'Reilly, Hans-Georg Beyer, Russell Standish, Stewart Wilson, Joachim Wegener, Mitch A. Potter, Alan C. Schultz, Kathryn A. Dowsland, Natasha Jonoska, Julian Miller
PublisherSpringer Verlag
Pages1752-1763
Number of pages12
ISBN (Print)3540406034, 9783540406037
DOIs
Publication statusPublished - 2003

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2724
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint

Dive into the research topics of 'On the avoidance of fruitless wraps in grammatical evolution'. Together they form a unique fingerprint.

Cite this