 Adaptive Representations with Learning (ARL) 12
 ADF 11,12
 bloat 216
 search space 127
 alias problem 174
 Altenberg's GP schema theory 3843
 ant problem 151174
 search space 124126
 symmetries 167
 arity 9
 ARL 12
 Automatically Defined Functions see ADF
 basin of attraction 18,19
 bias 131132,217
 initialisation 109,170
 onepoint crossover
 binary tree 106107
 size 105,106
 ramped halfandhalf 157
 removal 200
 required 201
 size 170,215
 standard crossover
 local search 106
 removal 200
 size 105
 uniform crossover
 global 106
 bloat
 ADF 216
 code editing 216
 depth limit 214
 effective fitness explanation 100101
 genetic operators 215
 linear GP 204
 none onepoint crossover 193
 Pareto 215
 parsimony pressure 215
 reduction techniques 214216
 schema analysis example 103105
 size limit 214
 tentative schema analysis 101103
 Boolean functions, number of 114,115
 Boolean search spaces 113123
 breed true 197
 building blocks 36,107109
 Goldberg 36
 Max problem 182
 missing from ant 163165,169
 O'Reilly 45
 onepoint crossover 70
 cartesian node reference systems 90
 CFGGP 45
 code

gpsimple.c
11

ntrees.cc
113

rand_tree.cc
113
 solutions to ant problem 154
 code editing for bloat prevention 216
 competing conventions 170
 component
 analysis 6
 instantiations 36
 position less 38
 positioned 38
 schema 35
 context free grammar GP see CFGGP
 convergence
 bloat 193217
 GA vs. GP 193
 linear search space, proof 133,139
 Markov analysis 27
 Max problem 175,179190,192
 onepoint 5859,67
 phenotype 198199,211
 population 110
 schema analysis 7383
 tree search space
 ADF 127
 experimental 114126
 loops 128129
 memory 127128
 proof 133,139144
 shape 129130
 XOR 146150
 crossover 13,6,910
 D'haeseleer 60
 effect on reproduction rate 31
 GA vs. GP 194197
 Koza see crossover, standard
 onepoint 5560
 effect on schemata 61
 implementation 58
 motivation 109
 no bloat 193
 Price's theorem 33
 PADO 15
 PDGP 14
 Price's theorem 3132,201
 respectful, Radcliffe 59
 size fair 200
 smooth, motivation 109
 standard 10,11
 big trees 211
 bloat 202211
 depth increase 216
 depth limit 211213
 directed acyclic graph 217
 exact schema theorem 9293
 protection from 200
 removal bias 200
 size change 199
 size limit 211213
 strong context preserving 60
 subtree swapping see crossover, standard
 to reduce bloat 215
 twopoint 60
 uniform 60,106,109
 data mining 213
 deception 110
 ant problem 169
 caused by adjusted fitness 98
 Max problem 175
 defining length
 fixedsizeandshape schema 53
 O'Reilly's definition 43
 depth
 binary trees 129130
 linear growth 205
 DGPC, maximum tree size 214
 Discipulus 132
 maximum program length 214
 disruption probability 34,44
 don't care symbol
 in binary GAs 33,52
 left and right 73
 lower and upper schema 75,76
 O'Reilly 43,55
 one node 52,53,55,77
 polymorphic 53
 Rosca 4951,55
 subtree 52,77
 variable arity schema 91,94
 dynamical system models 35
 edit distance 194
 effective fitness 97105
 bit string GAs 9798
 exact 99100
 early GP 9899
 exact GP 100
 high 100
 standard crossover 100
 effort
 ant problem 174
 random search 157
 elitism
 tournament selection 187
 entropy
 during bloat 216
 population 194
 evolution of program depths 203204
 evolution of program shapes 203204
 evolution vs.\ optimisation 199
 evolvability 121
 exact schema theorem
 for standard crossover 42
 macroscopic 82
 exhaustive search 17
 ant problem 154
 false peaks 19
 ant problem 169,171
 feature selection 213
 fitness 9
 deceptive see deception
 evaluations required see effort
 offspring fitness correlation 32
 primitive covariance see Price's theorem
 program size see parsimony
 proportionate selection 34,60
 test set 9
 fitness landscapes 46,1726
 ant problem 169
 dynamic 103
 effective 103105
 XOR parity problems 148150
 fixedsizeandshape schema 51,53
 fluff see introns
 fractal trees 130131
 fragility
 bit string GAs 34
 of node composition 63
 of shape 62,66,67
 Rosca 51
 generalisation 131132
 generational model 9
 genetic drift 32,149
 Price's theorem 30
 geometric interpretation of GP schemata 55
 geometric interpretation of GP hyperplanes 55
 GLib 11
 global vs.\ local search tradeoff 21
 GP as evolutionary process 199
 GP easy 110
 GP point mutation 5559
 GP schema 51
 defining length 53
 definition 53
 geometric interpretation 55
 length 53
 order 53
 Rosca's definition 50
 rooted tree 4951
 Rosca's 4951
 Whigham's definition 45
 GP schema theorem
 exact
 macroscopic 82
 microscopic 77
 schema creation correction 80
 survivaldisruption version 65
 GP schema theory
 Altenberg's 3843
 O'Reilly's 4345
 pessimistic models 49
 Rosca's 4951
 Whigham's 4546
 GPQUICK, maximum tree size 214
 greedy search 5
 grey code 25
 hill climbing 17
 ant problem 152,158160,171
 with restarts 21
 Holland's schema theorem 33
 generalisation 68
 hyperplanes 55
 hyperschema 77
 variable arity
 hyperspace 55
 implicit parallelism
 hypothesis 54
 Max problem 182
 ineffective code 199
 information in test set 139
 initialisation 109
 Max problem 176
 variety 183184
 onepoint crossover 59,66
 full 67
 ramped halfandhalf 198,204,211,214
 ramped uniform 214
 ridge divide 213
 uniform 214
 instantiation 3637
 happy faces 3537
 Koza's 38
 O'Reilly's 4345
 Rosca 50
 Whighams's 45
 introns 199
 ant problem 167
 ant solution 166,168
 effective fitness 98,101
 none in Max problem 176
 inviable code 199
 junk code 199
 karst landscape 169
 Koza's schema 38
 Levenshtein distance 194
 linear genetic programming 13,132139
 local optima 19
 longpath problem 19
 loops, effect on search space 128129
 machine code GP see linear genetic programming
 macroscopic exact GP schema theorem 82
 Markov analysis
 big trees 141
 GA 34,69
 too detailed 27
 long programs 135
 Max problem 175192
 memory
 search space 127128
 usage by GP 216217
 directed acyclic graph 217
 microscopic exact GP schema theorem 77
 Monte Carlo see random sampling
 multicardinality GA 53
 multiobjective fitness
 ant problem 154
 bloat reduction 215
 problems with landscape metaphor 23
 multiple tree programs 12
 mutation 12
 bloat 199
 convergence, small trees 194
 GA effective fitness 9798
 in GAs 33
 included in schema transmission 71
 nonconvergence 193197
 point 9,5559,65
 ant problem neighbour operator 158
 convergence 67
 schema theorem 65
 Price's theorem 32
 size fair 217
 to reduce bloat 215
 Whigham's 45
 natural selection 1
 neutral network 174,201
 ant problem 152,169
 no free lunch 89
 ant problem 168169
 number of Boolean functions 114
 O'Reilly
 don't care symbol 55
 GP schema theory 4345
 Occam's Razor 215
 Ockham see Occam
 onepoint crossover
 effect on schemata 61
 in GAs 33
 order
 ant problem 162165,169
 fixedsizeandshape schema 53
 GP building blocks 70
 GP schema 53
 in binary GAs 33
 O'Reilly's definition 43
 Rosca's definition 50
 PADO 1415
 Parallel Distributed Genetic Programming see PDGP
 Pareto fitness bloat reduction 215
 parity
 number of solutions 147
 number of solutions using XOR 147
 search space
 3 bit 118119
 4 bit 117118
 6 bit 119123
 with XOR 144150
 parsimony pressure 215
 PDGP 1415
 ant problem 158
 pessimistic GP schema theories 49
 point mutation in GP 5559
 Poli and Langdon's GP schemata 51
 population sizing 110
 Price's theorem 28
 genetic algorithms 31
 Max problem 187190
 onepoint crossover 33
 proof 29
 tournament selection 31
 program component schema theories 27
 program depths 203204
 program shapes 203204
 program size limit and Price's theorem 3233
 programs, number of 115
 ramped halfandhalf 113,130,198,204,211
 ant problem 152,157158
 Max problem 176
 low variety 183
 onepoint crossover 59,66
 random
 programs 132133
 initialisation bias 109
 sextic polynomial 198
 sampling 113,131,133
 ant problem 152,154,157159
 big programs 131
 convergence proof 133144
 effort 157
 GP biases 213
 limit to bloat 211
 no free lunch 9,168169
 trees 113126,154
 XOR 144150
 solution
 linear programs 139
 tree 144
 trees 129131,203204,214
 walk 201,203,216
 recombination see crossover
 recursion, search space 128129
 register GP see linear genetic programming
 removal bias 200
 size fair crossover 200
 respect, crossover, Radcliffe 59
 rooted tree schemata 4951
 Rosca
 Adaptive Representations with Learning 12
 bloat 197,203,215
 don't care symbol 55
 GP schema theory 4951
 parity problem 119
 population entropy 194
 Santa Fe trail see ant problem
 schema 7
 Altenberg's 3843
 as subexpressions 42
 bit string 3335
 components
 position less 38
 positioned 38
 components, in binary GAs 35
 creation 7173
 creation correction 80
 disruption 35
 disruption probability 34,44
 extinction 72
 fitness, in Altenberg's theorem 42
 fixedsizeandshape 51
 fragility
 bit string GAs 34
 of node composition 63
 of shape 62,66,67
 Rosca 51
 in CFGGP 45
 instantiations 36,37
 Koza's 38
 left and right parts 7374
 O'Reilly's 4345
 order
 ant problem 162165,169
 fixedsizeandshape 53
 GP building blocks 70
 in binary GAs 33
 O'Reilly's definition 43
 Rosca's definition 50
 Poli and Langdon's 51
 Rosca's 4951
 signaltonoise ratio 7173
 transmission 71
 Whigham's 4546
 schema theorem
 Altenberg's 3843
 criticism 32,6971
 Holland's 33
 generalisation 68
 introduction 7,8
 macroscopic, exact 82
 microscopic, exact 42,77
 O'Reilly's 4345
 pessimistic models 49
 programs of fixed size and shape 74
 Rosca's 4951
 schema creation correction 80
 standard crossover 9293
 microscopic 42
 Stephens and Waelbroeck's 73
 survivaldisruption version 65
 Whigham's 4546
 schemata see schema
 search and problem solving 2
 search bias see bias
 search space 2
 3 bit parity 118119
 4 bit parity 117118
 6 bit parity 119123
 ADF 127
 ant problem 124126
 Boolean 113123
 linear programs
 convergence proof 133139
 random solution 139
 loops 128129
 memory 127128
 parity, with XOR 144150
 recursion 128129
 symbolic regression 123124
 tree, convergence proof 139144
 XOR in random NAND gates 116117
 selection see fitness proportionate or tournament
 sex see crossover
 sextic polynomial
 bloat 199
 fitness covariance 202
 phenotypic convergence 200
 random programs 198
 search space 123124
 tree shapes 204
 shape
 evolution of 205
 simulated annealing 21
 ant problem 152,158
 bloat 199
 smooth crossover see crossover, smooth
 stack based GP 14
 steady state model 9
 Stephens and Waelbroeck's GA schema theory 73
 symbolic regression see sextic polynomial
 syntax trees 9
 tabu search 21
 test set, information content 139
 tournament selection pressure
 elite fraction 187
 Max problem 186190
 tree
 depth and size 129130
 depths 203204
 distribution of 204
 fractal 130131
 number of 204
 shape 130131,203204
 tree fragment see schema
 uniform crossover see crossover, uniform
 variable arity hyperschema 9092
 Whigham's GP schema theory 4546,55
 wild card symbol see don't care symbol
 XOR problem, search space 116117
ucacbbl
20021019