Index

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