Index

Adaptive Representations with Learning (ARL) 12
ADF 11,12
bloat 216
search space 127
alias problem 174
Altenberg's GP schema theory 38-43
ant problem 151-174
search space 124-126
symmetries 167
arity 9
ARL 12
Automatically Defined Functions see ADF
basin of attraction 18,19
bias 131-132,217
initialisation 109,170
one-point crossover
binary tree 106-107
size 105,106
ramped half-and-half 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 100-101
genetic operators 215
linear GP 204
none one-point crossover 193
Pareto 215
parsimony pressure 215
reduction techniques 214-216
schema analysis example 103-105
size limit 214
tentative schema analysis 101-103
Boolean functions, number of 114,115
Boolean search spaces 113-123
breed true 197
building blocks 36,107-109
Goldberg 36
Max problem 182
missing from ant 163-165,169
O'Reilly 45
one-point crossover 70
cartesian node reference systems 90
CFG-GP 45
code
gp-simple.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 CFG-GP
convergence
bloat 193-217
GA vs. GP 193
linear search space, proof 133,139
Markov analysis 27
Max problem 175,179-190,192
one-point 58-59,67
phenotype 198-199,211
population 110
schema analysis 73-83
tree search space
ADF 127
experimental 114-126
loops 128-129
memory 127-128
proof 133,139-144
shape 129-130
XOR 146-150
crossover 1-3,6,9-10
D'haeseleer 60
effect on reproduction rate 31
GA vs. GP 194-197
Koza see crossover, standard
one-point 55-60
effect on schemata 61
implementation 58
motivation 109
no bloat 193
Price's theorem 33
PADO 15
PDGP 14
Price's theorem 31-32,201
respectful, Radcliffe 59
size fair 200
smooth, motivation 109
standard 10,11
big trees 211
bloat 202-211
depth increase 216
depth limit 211-213
directed acyclic graph 217
exact schema theorem 92-93
protection from 200
removal bias 200
size change 199
size limit 211-213
strong context preserving 60
subtree swapping see crossover, standard
to reduce bloat 215
two-point 60
uniform 60,106,109
data mining 213
deception 110
ant problem 169
caused by adjusted fitness 98
Max problem 175
defining length
fixed-size-and-shape schema 53
O'Reilly's definition 43
depth
binary trees 129-130
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 49-51,55
subtree 52,77
variable arity schema 91,94
dynamical system models 3-5
edit distance 194
effective fitness 97-105
bit string GAs 97-98
exact 99-100
early GP 98-99
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 203-204
evolution of program shapes 203-204
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 4-6,17-26
ant problem 169
dynamic 103
effective 103-105
XOR parity problems 148-150
fixed-size-and-shape schema 51,53
fluff see introns
fractal trees 130-131
fragility
bit string GAs 34
of node composition 63
of shape 62,66,67
Rosca 51
generalisation 131-132
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 55-59
GP schema 51
defining length 53
definition 53
geometric interpretation 55
length 53
order 53
Rosca's definition 50
rooted tree 49-51
Rosca's 49-51
Whigham's definition 45
GP schema theorem
exact
macroscopic 82
microscopic 77
schema creation correction 80
survival-disruption version 65
GP schema theory
Altenberg's 38-43
O'Reilly's 43-45
pessimistic models 49
Rosca's 49-51
Whigham's 45-46
GPQUICK, maximum tree size 214
greedy search 5
grey code 25
hill climbing 17
ant problem 152,158-160,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 183-184
one-point crossover 59,66
full 67
ramped half-and-half 198,204,211,214
ramped uniform 214
ridge divide 213
uniform 214
instantiation 36-37
happy faces 35-37
Koza's 38
O'Reilly's 43-45
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,132-139
local optima 19
long-path problem 19
loops, effect on search space 128-129
machine code GP see linear genetic programming
macroscopic exact GP schema theorem 82
Markov analysis
big trees 141
GA 3-4,69
too detailed 27
long programs 135
Max problem 175-192
memory
search space 127-128
usage by GP 216-217
directed acyclic graph 217
microscopic exact GP schema theorem 77
Monte Carlo see random sampling
multi-cardinality GA 53
multi-objective fitness
ant problem 154
bloat reduction 215
problems with landscape metaphor 23
multiple tree programs 12
mutation 1-2
bloat 199
convergence, small trees 194
GA effective fitness 97-98
in GAs 33
included in schema transmission 71
non-convergence 193-197
point 9,55-59,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 8-9
ant problem 168-169
number of Boolean functions 114
O'Reilly
don't care symbol 55
GP schema theory 43-45
Occam's Razor 215
Ockham see Occam
one-point crossover
effect on schemata 61
in GAs 33
order
ant problem 162-165,169
fixed-size-and-shape schema 53
GP building blocks 70
GP schema 53
in binary GAs 33
O'Reilly's definition 43
Rosca's definition 50
PADO 14-15
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 118-119
4 bit 117-118
6 bit 119-123
with XOR 144-150
parsimony pressure 215
PDGP 14-15
ant problem 158
pessimistic GP schema theories 49
point mutation in GP 55-59
Poli and Langdon's GP schemata 51
population sizing 110
Price's theorem 28
genetic algorithms 31
Max problem 187-190
one-point crossover 33
proof 29
tournament selection 31
program component schema theories 27
program depths 203-204
program shapes 203-204
program size limit and Price's theorem 32-33
programs, number of 115
ramped half-and-half 113,130,198,204,211
ant problem 152,157-158
Max problem 176
low variety 183
one-point crossover 59,66
random
programs 132-133
initialisation bias 109
sextic polynomial 198
sampling 113,131,133
ant problem 152,154,157-159
big programs 131
convergence proof 133-144
effort 157
GP biases 213
limit to bloat 211
no free lunch 9,168-169
trees 113-126,154
XOR 144-150
solution
linear programs 139
tree 144
trees 129-131,203-204,214
walk 201,203,216
recombination see crossover
recursion, search space 128-129
register GP see linear genetic programming
removal bias 200
size fair crossover 200
respect, crossover, Radcliffe 59
rooted tree schemata 49-51
Rosca
Adaptive Representations with Learning 12
bloat 197,203,215
don't care symbol 55
GP schema theory 49-51
parity problem 119
population entropy 194
Santa Fe trail see ant problem
schema 7
Altenberg's 38-43
as subexpressions 42
bit string 33-35
components
position less 38
positioned 38
components, in binary GAs 35
creation 71-73
creation correction 80
disruption 35
disruption probability 34,44
extinction 72
fitness, in Altenberg's theorem 42
fixed-size-and-shape 51
fragility
bit string GAs 34
of node composition 63
of shape 62,66,67
Rosca 51
in CFG-GP 45
instantiations 36,37
Koza's 38
left and right parts 73-74
O'Reilly's 43-45
order
ant problem 162-165,169
fixed-size-and-shape 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 49-51
signal-to-noise ratio 71-73
transmission 71
Whigham's 45-46
schema theorem
Altenberg's 38-43
criticism 32,69-71
Holland's 33
generalisation 68
introduction 7,8
macroscopic, exact 82
microscopic, exact 42,77
O'Reilly's 43-45
pessimistic models 49
programs of fixed size and shape 74
Rosca's 49-51
schema creation correction 80
standard crossover 92-93
microscopic 42
Stephens and Waelbroeck's 73
survival-disruption version 65
Whigham's 45-46
schemata see schema
search and problem solving 2
search bias see bias
search space 2
3 bit parity 118-119
4 bit parity 117-118
6 bit parity 119-123
ADF 127
ant problem 124-126
Boolean 113-123
linear programs
convergence proof 133-139
random solution 139
loops 128-129
memory 127-128
parity, with XOR 144-150
recursion 128-129
symbolic regression 123-124
tree, convergence proof 139-144
XOR in random NAND gates 116-117
selection see fitness proportionate or tournament
sex see crossover
sextic polynomial
bloat 199
fitness covariance 202
phenotypic convergence 200
random programs 198
search space 123-124
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 186-190
tree
depth and size 129-130
depths 203-204
distribution of 204
fractal 130-131
number of 204
shape 130-131,203-204
tree fragment see schema
uniform crossover see crossover, uniform
variable arity hyperschema 90-92
Whigham's GP schema theory 45-46,55
wild card symbol see don't care symbol
XOR problem, search space 116-117



ucacbbl 2002-10-19