Grammatical Evolution

by O'Neill, Michael; Ryan, Conor

• ISBN13: 9781402074448
• ISBN10: 1402074441
• Format: Hardcover
• Copyright: 2003-05-01
• Publisher: Kluwer Academic Pub

Summary

Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language provides the first comprehensive introduction to Grammatical Evolution, a novel approach to Genetic Programming that adopts principles from molecular biology in a simple and useful manner, coupled with the use of grammars to specify legal structures in a search. Grammatical Evolution's rich modularity gives a unique flexibility, making it possible to use alternative search strategies - whether evolutionary, deterministic or some other approach - and to even radically change its behavior by merely changing the grammar supplied. This approach to Genetic Programming represents a powerful new weapon in the Machine Learning toolkit that can be applied to a diverse set of problem domains. Beginning with an overview of the necessary background material in Genetic Programming and Molecular Biology, Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language outlines the current state of the art in grammatical and genotype-phenotype-based approaches. Following a description of Grammatical Evolution and its application to a number of example problems, an in-depth analysis of the approach is conducted, focusing on areas such as the degenerate genetic code, wrapping, and crossover. The book continues with a description of hot topics in Grammatical Evolution and presents possible directions for future research.

Author Biography

Michael O'Neill: University of Limerick, Ireland Conor Ryan: University of Limerick, Ireland

Table of Contents

Preface	ix
Foreword	xi
Acknowledgments	xv
Introduction	1	(4)
Evolutionary Automatic Programming	1	(1)
Molecular Biology	2	(1)
Grammars	2	(1)
Outline	3	(2)
Survey of Evolutionary Automatic Programming	5	(18)
Introduction	5	(1)
Evolutionary Automatic Programming	6	(2)
Origin of the Species	8	(2)
Tree-based Systems	10	(7)
Genetic Programming	11	(2)
Grammar based Genetic Programming	13	(1)
Backus Naur Form	13	(3)
Cellular Encoding	16	(1)
Bias in GP	16	(1)
Genetic Programming Kernel	16	(1)
Combining GP and ILP	16	(1)
Auto-parallelisation with GP	17	(1)
String based GP	17	(4)
BGP	18	(1)
Machine Code Genetic Programming	19	(1)
Genetic Algorithm for Deriving Software	20	(1)
CFG/GP	21	(1)
Conclusions	21	(2)
Lessons From Molecular Biology	23	(10)
Introduction	23	(1)
Genetic Codes & Gene Expression Models	24	(2)
Neutral Theory of Evolution	26	(2)
Further Principles	28	(1)
Desirable Features	29	(3)
Conclusions	32	(1)
Grammatical Evolution	33	(16)
Introduction	33	(1)
Background	34	(1)
Grammatical Evolution	35	(10)
The Biological Approach	36	(1)
The Mapping Process	36	(1)
Backus Naur Form	37	(2)
Mapping Process Outline	39	(1)
Example Individual	40	(2)
Genetic Code Degeneracy	42	(2)
The Search Algorithm	44	(1)
Discussion	45	(2)
Conclusions	47	(2)
Four Examples of Grammatical Evolution	49	(14)
Introduction	49	(1)
Symbolic Regression	49	(3)
Results	51	(1)
Symbolic Integration	52	(3)
Results	52	(3)
Santa Fe Ant Trail	55	(2)
Results	56	(1)
Caching Algorithms	57	(5)
Results	60	(2)
Conclusions	62	(1)
Analysis of Grammatical Evolution	63	(16)
Introduction	63	(1)
Wrapping Operator	64	(3)
Results	64	(1)
Invalid Individuals	64	(1)
Cumulative Frequency of Success	65	(1)
Genome Lengths	65	(2)
Discussion	67	(1)
Degenerate Genetic Code	67	(5)
Results	69	(1)
Diversity Measures	70	(2)
Discussion	72	(1)
Removal of Wrapping and Degeneracy	72	(2)
Results	72	(2)
Mutation Rates	74	(3)
Results	76	(1)
Conclusions	77	(2)
Crossover in Grammatical Evolution	79	(20)
Introduction	79	(2)
Homologous Crossover	81	(11)
Experimental Approach	81	(2)
Results	83	(8)
Discussion	91	(1)
Headless Chicken	92	(6)
Experimental Approach	93	(1)
Results	94	(1)
Discussion	95	(3)
Conclusions	98	(1)
Extensions & Applications	99	(30)
Translation	99	(2)
Alternative Search Strategies	101	(1)
Grammar Defined Introns	102	(1)
Gauge	103	(10)
Problems	105	(1)
Onemax	106	(1)
Results	107	(1)
Mastermind - a deceptive ordering version	108	(1)
Results	109	(3)
Discussion	112	(1)
Conclusions and Future Work	112	(1)
Chorus	113	(4)
Example Individual	114	(2)
Results	116	(1)
Financial Prediction	117	(4)
Trading Market Indices	117	(2)
Experimental Setup & Results	119	(2)
Adaptive Logic Programming	121	(4)
Logic Programming	121	(2)
GE and Logic Programming	123	(1)
Backtracking	124	(1)
Initialisation	125	(1)
Discussion	125	(1)
Sensible Initialisation	125	(2)
Genetic Programming	127	(1)
Conclusions	128	(1)
Conclusions & Future Work	129	(14)
Summary	129	(1)
Future Work	130	(13)
Index	143