- Adaptive Representation through Learning, 33
- ADF, 23-24, 33
- as evolving primitive, 102-106, 110
- as representation change, 207
- bracket problem, 144
- cache, 118
- call by reference, 125
- comparison with GLiB, 33
- constraining use, 118, 141
- dyck problem, 149
- FUNC, 128, 129
- in PADO, 164
- list problem, 124-127
- forwhile, 126
- syntax restrictions, 129

- pass by reference, 91
- list problem, 124
- queue problem, 107

- primitives, used in, 85, 101
- queue problem, 84, 90, 109
- RPN problem, 154, 158
- semantically constrained, 107
- support in GP-QUICK, 268
- treating rbp as ADF, 85, 90
- ADM, see Automatically Defined Macros
- ARG1
- dyck problem, 150
- list problem, 127, 128
- south wales problem, 255
- arg1
- bracket problem, 145
- dyck problem, 150
- list problem, 127, 128
- syntax restrictions, 129

- queue problem, 84
- syntax restrictions, 101

- RPN problem, 156
- stack problem, 66
- essential in, 179
- extinct, 179
- fitness covariance, 175, 179

- ARG2
- list problem, 128
- arg2
- dyck problem, 150
- RPN problem, 156
- ARL, see Adaptive Representation through Learning
- Automatically Defined Functions, see ADF
- Automatically Defined Macros, 23
- autonomous agents, 41, 47
- playing soccer, 47
- aux, 45, 128
- list problem, 125, 127
- initialised, 130
- queue problem, 85-87, 93, 95, 99, 108
- bug, 109
- differences between experiments, 118
- different from stack, 122
- harder than stack, 120-121
- initialised, 88
- syntax restrictions, 101
- use in shuffler, 94-95
- stack problem, 66-68
- deceptive, 180, 205
- essential in, 179
- extinct, 179
- fitness covariance, 175
- initialised, 69
- use in solutions, 71, 180
- auxiliary register, see aux
- BioX, 39
- bloat
- inherent in variable length representations, 77-78
- list problem, 131
- mutation experiments, 34
- RPN problem
- removal, 160

- stack problem, 76
- boids, 41
- boolean 6-multiplexer
- code growth, 76-77, 191
- effect of parsimony pressure, 30
- branch typing, 23
- in multi-tree crossover, 46
- Bruce, 140, 163, 205
- building block
- disruption, 180
- extinction, 180
- building blocks, 15
- introns, 119
- queue shuffler, 95, 119
- cache
- ancestor's fitness, 269-270
- bracket problem
- ADF evaluation, 145

- DAG, 27
- future work, 212
- loadflow, 266
- network connectivity, 266
- queue problem
- ADF evaluation, 118

- recommended, 211
- tree evaluation, 270
- calculator problem, see RPN problem
- call by reference, see ADF, call by reference
- case sensitive primitives names, 66
- cellular automata, 50
- clones, 184
- crossover
- binary tree model, 197-199
- leaf measurements, 201
- leaf model, 199-200
- measurements, 196, 197
- whole tree, 196-197
- disable reproduction operator, 205
- low variety, 195, 202
- closure, 21
- extended, 28
- indexed memory addresses, 67
- protected modulus, 84
- co-evolution
- 42 trees, 259
- queue problem, 82
- references, 29, 49, 180, 208
- representation, 207
- stack problem, 65
- ten operations, 123
- test case, 205
- contingencies
- electrical network, 262-265
- coroutine model, 32
- CPU
- complexity of problem, 64
- usage
- dyck problem, 153
- list problem, 132
- RPN problem, 159

- CPU complexity of scheduling heuristics, 266
- CPU limit, south wales problem, 260
- CPU penalty
- faster solutions
- list problem, 135
- RPN problem, 157, 160
- increased after solution
- dyck problem, 150, 152
- list problem, 131
- RPN problem, 155-157
- list problem, 123, 127
- pareto, 53, 131
- removal of introns, 141
- south wales problem, 256, 259, 262
- crossover, 2
- ADF, 23, 33
- asymmetric, 53
- between different implementations, 80
- bit string, 14
- bloat prevention, 120
- building block assembly, 15
- ADF, 33

- clones, 184, 188
- binary tree model, 197-199
- leaf measurements, 201
- leaf model, 199-200
- measurements, 196, 197
- run time reduction, 206
- stack problem, 184-186, 192, 195

- closure, 21
- context preserving, 35
- depth based, 34
- directed, see directed crossover
- disruption, 24, 180
- diverse individuals
- fitness niches, 129, 141

- effect on reproduction rate, 52, 170
- four node problem, 249
- introns, 78
- length restriction
- stack problem, 70

- measurements
- stack problem, 200-202

- multi-tree, 46-47
- 42 trees, 259
- list problem, 124
- queue problem, 84
- RPN problem, 154
- stack problem, 65

- no code sharing between different tree types, 91, 172
- offspring same fitness, 74
- one offspring, 184
- one point, 36
- program length limit, 268
- protected from by encapsulation, 33
- random
- Price's theorem, 170-171

- run out of steam, 206
- scheduling representations, 248-249
- self
- demes, 53

- semantically constrained, 107
- short fit programs, 78
- solution rediscovery, 207
- STGP, 28
- successful
- stack problem, 202-204

- tree, 3
- unique offspring, 206
- variety, 189
- constant model, 190-191
- quadratic model, 191-195
- stack problem, 195-197

- whole trees reduces variety, 196-197
- cultural transmission, 69
- DAG
- Storing population in, 27
- data mining, 39
- Dec_Aux
- queue problem, 85-87, 93, 95, 99
- different from stack, 122
- harder than stack, 120-121
- syntax restrictions, 101
- stack problem, 66-68
- deceptive, 180, 205
- essential in, 179
- extinct, 179
- fitness covariance, 175, 179
- use in solutions, 180
- deception, 6, 21
- co-evolution, 205
- deme, 205
- dyck problem
- static program, 154

- future work, 211
- list problem, 141
- mutation rate to escape, 205
- niches, 141, 205
- novel genetic operators, 207
- queue problem, 121
- RPN problem, 160
- stack problem, 180, 205, 207
- deme, 49-53
- beneficial, 49
- bracket problem, 145, 146
- deceptive problems, 205
- defocusing search, 207
- diversity, 141, 211
- dyck problem, 146, 150, 152
- elitism, 56
- genetic similarity, 55
- queue problem, 103-104
- references, 37
- speed of convergence, 52
- Directed Acyclic Graph, see DAG
- directed crossover, 133
- error location, 132
- list problem, 127
- software maintenance, 140
- survey, 47-49
- distributed artificial intelligence (DAI), 41
- divide by zero, 21
- Effort, 75, 237
- elitism
- demic populations, 56
- list problem, 127
- multi-objective fitness function, 57
- required if random removal, 211
- south wales problem, 256
- steady state population, 56
- end nodes, 20
- error location guiding crossover, 132
- error trapping not required
- list problem, 130
- queue problem, 81, 88
- stack problem, 64, 69
- error, memory address
- abort
- queue problem, 95
- stack problem, 67
- continuing on
- queue problem, 86, 122
- options, 67
- error, recursion
- abort
- queue problem, 92
- error, stack
- continuing on, 145
- external nodes, 20
- extinction
- critical stack primitives, 178
- list primitives, 135
- feature films, 41
- Fisher's fundamental theorem, 177
- fitness, 9, 21-22
- avoid evaluation of clones, 206
- avoiding excess resource consumption, 94
- cache, see cache
- deceptive, see deception
- diversity, 183
- dynamic, 29-30
- evaluations required, see effort
- future work
- reduce test case, 102

- identical from different programs, 183
- manual, 41
- multi-objective, see pareto
- novelty reward, 259
- offspring fitness correlation, 170
- primitive covariance, see Price's theorem
- program size, see parsimony
- queue problem
- harder than stack, 120
- run time, 269

- rank based, 44
- redesign, 208
- rediscovery, 202
- reducing test case, 151
- rescaling, 44
- sharing, see niches
- sufficient testing, 132
- test case, 22
- Flockton, 54
- fluff, see introns
- for
- south wales problem, 256
- syntax restriction, 254
- forwhile, 126, 128
- bracket problem, 145, 165
- list problem, 127
- CPU penalty, 131
- CPU usage, 160
- in ADF only, 126
- iteration limit, 126
- syntax restriction, 126

- functions, 20
- Gathercole, 29, 30, 32, 89
- generation equivalent, 45
- genetic drift, 55
- Price's theorem, 170
- genetic programming, origins, 17
- Gordon, 248, 249
- GP-QUICK, 267
- support for ADFs, 23, 268
- halting problem, 31
- Inc_Aux
- queue problem, 85-87, 93, 95, 99
- different from stack, 122
- harder than stack, 120-121
- syntax restrictions, 101
- stack problem, 66-68
- deceptive, 180, 205
- essential in, 179
- extinct, 179
- fitness covariance, 175
- use in solutions, 180
- indefinite loops, 31
- indexed memory, 45
- avoiding deception, 205
- greedy solutions, 94
- penalty, 94, 118, 131
- increased after solution, 131

- south wales problem, 253
- survey, 160-164
- information theory
- queue problem, 121
- size of test case, 210
- stack problem, 80
- initialisation
- aux
- bracket problem, 145
- dyck problem, 151
- queue problem, 88
- RPN problem, 155
- stack problem, 69
- indexed memory
- bracket problem, 145
- dyck problem, 151
- GEMS, 161
- list problem, 130
- queue problem, 88
- references, 131
- RPN problem, 155
- south wales problem, 254
- stack problem, 69
- internal nodes, 20
- introns, 48
- avoiding fitness evaluation, 270
- building blocks, 119
- concealing convergence, 7
- hiding building block, 103
- inherent in variable length representations, 77-78
- loss of variety, 183
- removal by CPU penalty, 141
- some references, 37
- stack problem, 76
- useful with mutation, 35
- wetware, 144
- iteration, see for, forwhile
- constrained, 161
- CPU usage, 22, 31-32
- little research, 31, 43
- Koza, 1-272
- length, see program size
- loop, see for, forwhile
- machine code
- RISC, 27, 161
- Z80, 161
- Maze
- Solving with a stack, 63
- MDL, 30-31
- biasing search, 49
- general programs, shorter, 210
- MInc
- implementation, 87
- queue problem, 85, 87, 95, 99
- harder than stack, 120-121
- syntax restrictions, 101

- minimum description length, see MDL
- mod
- implementation, 85
- queue problem, 84
- south wales problem, 256
- models of loss of variety, 188
- modulus, see mod
- modulus increment, see MInc
- multi-tree programs, 46-47
- mutation, 2
- artificial life, 41
- background primitive frequency, 208
- bit string, 13
- defocusing search, 207
- possible benefit, 141, 211
- restore diversity, 205
- south wales problem, 254
- survey, 34-35
- neutral crossovers, 74
- NFL, see No Free Lunch
- niches, 54-57
- deception, 205
- defocusing search, 207
- diversity, 141, 211
- dyck problem, 150
- future work, 142, 211
- genetic similarity, 55
- list problem, 123, 129-130
- RPN problem, 156
- south wales problem, 259
- No Free Lunch, 16
- object oriented programming
- Bruce, 163
- PADO, 28, 164
- anytime algorithm, 31
- run time in fitness, 131
- panmictic population, 49
- fast convergence, 211
- Parallel Distributed Genetic Programming, see PDGP
- pareto, 53-57
- avoiding loss of improvements, 102
- CPU penalty, 53
- dyck problem, 150, 152
- future work, 211
- list problem, 123, 129
- memory penalty, 53
- queue problem, 102
- RPN problem, 155, 156
- south wales problem, 259
- parsimony, 30, 131
- biasing search, 49
- pass by reference, see ADF, pass by reference
- PDGP, 28
- permutation of trees, 35
- permutation, GA chromosome, 248-250, 260, 266, 267
- PGA, 250
- PIPE, 36
- point typing, 205
- popcorn, indefinite loops, 31
- prefix jump table, 70
- efficient, 26
- GP-QUICK, 268
- premature convergence, 49
- change representation, 207
- demes, 103
- niches, 152
- offspring selection, 101
- short test case, 130
- Price's theorem, 168
- genetic algorithms, 170
- proof, 168
- Probabilistic Incremental Program Evolution, see PIPE
- program size, see bloat, MDL, parsimony
- boolean 6-multiplexer, 76-77
- CPU penalty
- list problem, 135

- limit, 89-90
- bracket problem, 145
- crossover, 46
- dyck problem, 150
- GP-QUICK, 268
- list problem, 127, 133
- loss of diversity, 89
- Price's theorem, 170-171
- queue problem, 93, 95, 99, 108
- random individuals, 90
- RPN problem, 156
- south wales problem, 256
- stack problem, 66, 70

- list problem, 137
- mutation rate, 254
- part of diversity, 184
- queue problem, 89, 117
- random trees, 89
- south wales problem, 259
- stack problem, 76-77, 79
- initial fall, 78

- protected functions, 21
- protected modulus, see mod
- pUnRestrictWt, 47
- effect in full binary trees, 197
- random search, ineffective, 75
- rank selection, 44
- rankone, 266
- Rational Allocation of Trials, 30
- recursion
- CPU usage, 22, 31-32
- little research, 43
- prevented
- list problem, 125
- queue problem, 91

- references, 91
- Red Queen, 180
- rheological models, 39
- Ross, 29, 30, 32, 89, 249, 250
- scalar memory, see aux
- scoping rules, 125
- future work, 211
- SDRS2, 266
- search space
- automatic program generation, 17
- explore v.\ exploit, 205, 207
- impact of primitives and fitness, 20
- indexed memory, 210
- multiple solutions, 80, 120
- poorly behaved, 42
- program length, 210
- scheduling problem, 253, 260, 265-266
- size, 266

- stack problem
- size, 16

- STGP, 49
- techniques, 15-16
- seeding
- references, 140
- software maintenance, 139
- south wales, 254
- semantic constraints
- queue problem, 107
- Set_Aux, 128
- list problem, 127
- queue problem, 85-87, 93, 95, 99, 108
- different from stack, 122
- harder than stack, 120-121
- syntax restrictions, 101

- size of random trees, 77, 89
- structured population, 49
- sufficiency, 20
- swap, 45
- bracket problem, 145
- definition, 166
- list problem, 127
- south wales problem, 256
- swap, genetic operator, see permutation of trees
- syntax restrictions
- list problem, 126, 129
- queue problem, 90
- tableau, 68
- terminals, 20
- tournament selection, 44
- steady state, 187
- transmission function, 20
- tree leafs, 20
- tree size limit, 268
- dyck problem, 150
- list problem, 127, 133
- RPN problem, 156
- Turing complete, 27, 43
- virtual reality, 41
- wrapper, 68
- bracket problem, 145
- dyck problem, 150
- queue problem, 88, 93, 95, 99, 108
- empty, 122

- RPN problem, 156
- south wales problem, 256
- stack problem, 66, 68
- write_Aux
- queue problem
- different from stack, 122
- not used, 86-87
- stack problem, 66-68
- deceptive, 180, 205
- essential in, 179
- extinct, 179
- fitness covariance, 175
- use in solutions, 180
- Yang, 54

Bill LANGDON 2001-08-19