Genetic Programming and Data Structures: Genetic Programming + Data Structures = Automatic Programming!Computers that `program themselves' has long been an aim of computer scientists. Recently genetic programming (GP) has started to show its promise by automatically evolving programs. Indeed in a small number of problems GP has evolved programs whose performance is similar to or even slightly better than that of programs written by people. The main thrust of GP has been to automatically create functions. While these can be of great use they contain no memory and relatively little work has addressed automatic creation of program code including stored data. This issue is the main focus of Genetic Programming, and Data Structures: Genetic Programming + Data Structures = Automatic Programming!. This book is motivated by the observation from software engineering that data abstraction (e.g., via abstract data types) is essential in programs created by human programmers. This book shows that abstract data types can be similarly beneficial to the automatic production of programs using GP. Genetic Programming and Data Structures: Genetic Programming + Data Structures = Automatic Programming! shows how abstract data types (stacks, queues and lists) can be evolved using genetic programming, demonstrates how GP can evolve general programs which solve the nested brackets problem, recognises a Dyck context free language, and implements a simple four function calculator. In these cases, an appropriate data structure is beneficial compared to simple indexed memory. This book also includes a survey of GP, with a critical review of experiments with evolving memory, and reports investigations of real world electrical network maintenance scheduling problems that demonstrate that Genetic Algorithms can find low cost viable solutions to such problems. Genetic Programming and Data Structures: Genetic Programming + Data Structures = Automatic Programming! should be of direct interest to computer scientists doing research on genetic programming, genetic algorithms, data structures, and artificial intelligence. In addition, this book will be of interest to practitioners working in all of these areas and to those interested in automatic programming. |
Contents
INTRODUCTION | 1 |
12 Motivation | 5 |
SURVEY | 9 |
21 Introduction | 10 |
22 Genetic Algorithms | 13 |
23 Genetic Programming | 19 |
24 GP Research | 26 |
25 GP Applications | 36 |
610 Discussion | 140 |
611 Conclusions | 141 |
PROBLEMS SOLVED USING DATA STRUCTURES | 143 |
71 Balanced Bracket Problem | 144 |
72 Dyck Language | 149 |
73 Evaluating Reverse Polish Expressions | 154 |
74 Work by Others on Solving Problems with Memory | 160 |
75 Summary | 164 |
26 Conclusions | 42 |
ADVANCED GENETIC PROGRAMMING TECHNIQUES | 43 |
32 Tournament Selection | 44 |
33 Steady State Populations | 45 |
36 Multitree programs | 46 |
37 Directed Crossover | 47 |
38 Demes | 49 |
39 Pareto Optimality | 53 |
310 Conclusions | 57 |
EVOLVING A STACK | 61 |
42 Architecture | 65 |
44 Fitness Function | 68 |
45 Parameters | 70 |
46 Results | 71 |
47 Summary | 78 |
EVOLVING A QUEUE | 81 |
52 Architecture | 84 |
54 Fitness Functions | 87 |
55 Parameters | 89 |
56 Automatically Defined Functions | 90 |
57 Evolved Solutions Caterpillar | 92 |
58 Evolved Programs Shuffler | 94 |
59 Circular Buffer Given Modulus Increment | 95 |
510 Circular Bugger Evolving Modulus Increment | 102 |
Building Blocks and Introns | 119 |
512 Summary | 120 |
EVOLVING A LIST | 123 |
62 Architecture | 124 |
64 Choice of Primitives | 125 |
65 Fitness Function | 129 |
66 Directed Crossover | 133 |
69 Software Maintenance | 139 |
EVOLUTION OF GP POPULATIONS | 167 |
81 Prices Selection and Covariance Theorem | 168 |
82 Fishers Fundamental Theorem of Natural Selection | 177 |
83 Evolution of Stack Problem Populations | 178 |
84 Loss of Variety | 183 |
85 Measurements of GP Crossovers Effects | 200 |
86 Discussion | 202 |
87 Summary | 207 |
CONCLUSIONS | 209 |
91 Recommendations | 210 |
92 Future work | 211 |
References | 213 |
Number of Fitness Evaluations Required | 237 |
Glossary | 238 |
Scheduling Planned Maintenance of the National Grid | 242 |
C3 The South Wales Region of the UK Electricity Network | 244 |
C4 Approximating Replacement Generation Costs | 246 |
C6 The Chromosome | 248 |
C7 Greedy Optimisers | 250 |
C8 South Wales Problem without Contingencies | 251 |
C9 South Wales and Genetic Programming | 253 |
C10 South Wales Problem with Contingencies | 262 |
C11 Conclusions | 265 |
C13 Using QGAME | 266 |
Implementation | 267 |
D2 Coding Changes to GPQUICK21 | 268 |
D4 Network Running | 269 |
D6 Caches | 270 |
D9 Code | 272 |
| 273 | |
Other editions - View all
Genetic Programming and Data Structures: Genetic Programming + Data ... W.B. Langdon No preview available - 1998 |
Common terms and phrases
adf1 adfl Advances in Genetic Angeline arg1 arg1 arg1 arguments Automatically Defined Functions aux2 chapter contain convergence CPU penalty crossover data structures demes dequeue Dyck language editors empty enqueue evaluated evolution Evolutionary Computation evolving programs experiments Figure fitness function fitness test Fogel Genetic Algorithms genetic operators genetic programming Genetic Programming 1996 Goldberg GP population GP run GP-QUICK implementation Inc_Aux2 indexed memory Individuals Created initial population integer International Conference introns Koza Langdon loop maintenance makenull modulus increment Morgan Kaufmann mutation nodes Number of Individuals offspring parameters parents Pareto partial solutions Price's Theorem primitives Proceedings push pushdown automaton QROG2 QRQG2 queue random read SUB Riolo schedule search space Set Aux1 shows solve South Wales stack data structure stack populations stack problem stack runs subtree Table techniques test sequences tests passed tournament selection tree write zero