GENETIC PROGRAMMING AND DATA STRUCTURES

Genetic Programming + Data Structures = Automatic Programming!

by

William B. Langdon

With a Foreward by John R. Koza

Springer E-Book flyer

ISBN 0-7923-8135-1 978-0-7923-8135-8
ISBN: 978-1-4613-7625-5 (Print) 978-1-4615-5731-9 (Online)

Cover evolved using genetic programming by Anargiros Sarafopoulos

Foreword

This book, Genetic Programming and Data Structures, is the first book in the Springer's series on genetic programming.

Genetic programming addresses the problem of automatic program synthesis and automatic programming, namely the problem of how to enable a computer to do useful things without instructing it, step by step, how to do it. Genetic programming accomplishes this by breeding a population of computer programs over many generations using the operations of Darwinian natural selection, crossover (sexual recombination), and mutation. The publication of more than 800 papers by some 250 authors since l992 attests to the wide range of problems that can be solved with this biologically inspired metaphor.

However, early work on genetic programming was largely confined to evolving computer programs with either rudimentary forms of memory (such as named memory, indexed memory, and matricial memory) or, in many cases, no memory at all.

It was at this point that Bill Langdon, a professional software engineer, entered the fray and showed how the lessons of software production and the essential role of abstraction can be advantageously used in the context of genetic programming. In particular, Langdon demonstrates in this excellent volume how a large arsenal of familiar and useful data structures (such as stacks, queues, lists, rings, etc.) can be implemented in genetic programming. In fact, this book can be summarized by what should be called Langdon's equation:

Genetic Programming + Data Structures = Automatic Programming.

John R. Koza
Consulting Professor, Computer Science Department,
Stanford University, January, 1998

Table of Contents

Table of Contents v
Preface xi
Acknowledgments xiii
Chapter 1. Introduction 1
Chapter 2. Survey 9
Chapter 3. Advanced Genetic Programming Techniques 43
Chapter 4. Evolving a Stack 61
Chapter 5. Evolving a Queue 81
Chapter 6. Evolving a List 123
Balanced bracket problem, Dyck Language, Evolving a four function calculator, Survey of GP and Evolvable memory
Chapter 7. Problems Solved Using Data Structures 143
Chapter 8. Evolution of GP Populations 167
Price's Theorem, Fisher's Theorem, Evolution of populations, Loss of Variety, Crossover's Effects
Chapter 9. Conclusions 209
Bibliography 309 References 213
Appendices
A Number of Fitness Evaluations Required 237
B Glossary 238
C Scheduling Planned Maintenance of the National Grid 242
Code Java demo South Wales Network
D Implementation Code (installation) 267
Index 822 entries 273

GECCO'2000 tutorial slides).

BibTeX citation

W.Langdon (last update 12 July 2013)