Index

A

absorption, 221, 236

absurdity, 409, 411

ACL, 459

acoustic signal classification, 326

adaptability, 396

adaptive crossover, 259

adaptive destruction, 263

adaptive Occam method, 429

ADATE, 268, 276

adder problems, 307

affinity, 359

agent communication language, 459

AIM-GP, 275-299

aligned homologous crossover, 275, 290-291

analog lowpass filter, 119

and-or query problem, 135, 156-158

angle criterion, 49

annotation array, 286

anti-idiotype excitation, 360

antigens, 357

applicative order genetic programming, 19

artificial ant, 175-177, 199, 378, 382, 389-392

artificial life, 425

artificial neural networks, 326, 351

ASHRAE Competition, 415-416, 418

atom mode, 18-25

auto-parallelization, 15

automatic programming, 276

automatically defined functions, 219, 233, 265, 292

B

basis functions

definition, 405

determination by GP, 403, 406

integration into a regression model, 406

selection, 407, 409

update or timely renewal, 421

beowulf-style computer, 15, 123

bias, removal, 183, 266

bias-variance dilemma, 267

binary trees

distribution of, 167, 185

number of, 167, 185

bloat, 7-8, 10, 163, 243, 266, 384, 389

as protection, 179

continuous fitness function, 176

despite stability penalty, 185

in dynamic problems, 185

reducing operators, 187

with variable length chromosomes, 168

Boolean classification problems, 301

breeding strategies, 451-452

bucket-brigade, 325

building block hypothesis, 245, 246

building blocks, 8, 218, 248, 377, 381, 391, 396

biological, 233

in genetic algorithms, 217-218

in genetic programming, 217-219, 233-235

stable, 265

building numerical constants, 233, 236

C

CAD, 6, 41

CAD expression, 45

cart centering problem, 199

catchments, 89

CFG-GP, 90

character recognition problem, 9, 310

circuit synthesis, 7, 105

circuit-constructing functions, 110-113

code growth, 7-8, 163

coevolution, 266

coevolutionary fitness switching, 10, 425-443

combination problem, 69-78

COMBINE, 69-78

communication, 448

compiling genetic programming system, 275

compositionality, 68-69

computational basis vector, 137

computational effort, 413-414, 419

computer-aided design, 6, 41

conceptual dependency theory, 67

conditional phase gate, 141, 154

construction engineer, 42

construction operator, 47

constructive solid geometry, 42, 47

context-free grammar, 89-90

context-preserving mutation, 362

controlled NOT gate, 139-140, 154

cooperation, 447

cooperative behaviour, 425, 429-431, 433-434, 440, 443, 447

cosmetics, 63

covariance theorem, 170, 246

credit assignment, 325

credit-blame map, 332

cross structure, 59

crossover

adaptive, 259

applying a credit-blame map, 340-341

cut and splice, 362

depth-dependent, 377-399

graph, 325

self-tuning depth-dependent, 10, 377-399

CSG

primitive, 47

sequence, 47

tree, 47

curvature type criterion, 50

D

dash-and-dribble problem, 439-440

data dependency analysis, 16-18

data driven model building, 401

data manipulation, 410

data modelling, 220

data reduction, 43

data regions, 410

database search, 136, 154-156

deadlock, 394

decompilation, 286, 288-289

delay lag vector, 401

delay time, 401

depth selection probability, 378, 380, 396

depth-dependent crossover, 377-399

derived terminal set, 412, 416

design, 105

destruction, adaptive, 263

development-controlling functions, 118

developmental genetic programming, 108

DGPC, 4

digitising, 42

directed data dependency analysis, 16-34

Discipulus, 9, 283, 303

distance criterion, 48

diversity, 51, 363, 366

division-by-zero, 409

DNA transcription, 164, 165

drift, 243

dynamic fitness function, 358

E

early promise problem, 149-152

early stopping policy, 410

efficiency, 67-68, 83-85

electrical circuits, 7, 105-134

11-bit multiplexer problem, 382-389

elimination, 221, 236

elitism, 409

elliptic (Cauer) filter, 121

embedding dimension, 401, 416-417, 421

embryo, 18, 108-110

English grammar, 67-88

entertainment, 63

ephemeral random constant, 8, 220-227, 233-241

equivalence class, 236

ERC, 220

ERC-centric, 222, 226

error-correcting mechanisms, 221, 236

even-10 parity problem, 316

even-5 parity problem, 318

evolution of program shapes, 184-185

evolution strategies, 6, 45

evolution vs. optimisation, 172

evolutionary algorithm, 46

evolutionary programming, 196

evolutionary stable strategy, 232

example dynamics, 358

execution probability, 46

exon, 164-165

expected improvement, 193

explicit credit assignment, 326

explicit credit scores, 333

exploration vs. exploitation, 337-338

extra-grammaticality, 67-68

F

factoring, 135-136

fair crossover, 187

fair subtree mutation, 174

fast evaluation of fitness cases, 315

fast GP implementation, 317

features, functional, 248

Fibonacci series, 329 50%-150%

fair mutation, 175

filter, 119

finite quadric, 47

first difference transformation, 422

fitness causes bloat, 168

fitness correlation coefficient, 192-193

fitness distribution, 191-216

fitness function, 2, 55, 120-122, 148, 408

dynamic, 358

MDL-based, 363

fitness landscape, 192, 356

analysis, 192

fitness penalty, 225

probability distribution function, 229-232, 235

strategies, 236

fitness switching, 425-426, 428, 430-431, 434, 443

fitness-centric, 222-223

floating point arithmetic, 291-292

flow of control, 327

flow of data, 327

forecasting

on-line or real-time, 415, 421

runaway extension, 415, 418, 420, 422

update extension, 415, 418, 420

formal grammar, 90

foveation, 330

function identification, 220

function sensitivity approximation, 334

function set, 2, 47

functional features, 248

future time, 401

G

Gaussian curvature, 44

Gaussian mutation, 192

gene, 233-234

generality testing, 171

genetic programming

basic procedure, 2

books, journals, conference

proceedings, 3

on-line resources, 3-4

public domain implementations, 4-5

genotype, 51, 218, 219, 233-235

Glan Teifi catchment, 96

GLR* parser, 75, 83

glue, 287

GMDH, 362

golden mean, 329

GP as evolutionary process, 172

GPQUICK/GPdata, 4

graph crossover, 325

greedy, 381

Grover's algorithm, 136

growth in program size, 163

GRR (Genetic Recursive Regression), 402, 420

GSR (Genetic Symbolic Regression), 401-402

H

Hadamard gate, 141, 153

Hamming distance, 192

herding, 431, 433-436, 439

hill climbing bloat, 173

hill climbing mutation, 92

homing, 431, 433-436, 439

human blood flow, 411

hydrograph, 89

hydrological model, 89

I

ICGA, 1

idiotypic networks, 357

iGP, 356, 359-360, 364, 366, 369, 372

IHACRES model, 93

image processing, 345-347

immune system dynamics, 357

immune version of genetic programming, 356, 362-372

impact step, 411, 413, 421

implementation in C, 318

incorporation, 236

indexed memory, 325

induction, 255

inductive genetic programming, 356, 359-360, 364, 366, 369, 372

inoperative code, 165

instantaneous unit hydrograph, 92

interactive evolution, 58

internal reinforcement, 9, 325, 331

intron, 164-165, 230-231, 237, 266

invention machine, 7, 131-132

inviable code, 165

IRNP, 326

J

JANUS, 68

Java byte code, 286

Java implementation of GP, 5

junk DNA, 165

K

ket vector, 137

L

lag vector, 403

language interfaces, 67-68

language understanding, 67-68

lazy evaluation, 19

lilgp, 4, 222-223

limiting bloat, 166

Linda, 15

Lisp implementation of GP, 5

locally optimal solutions, 80-82

locally successful sub-models, 406

loop fusion, 26-28

loop mode, 19, 26-33

loop shrinking, 28-29

lowpass filter, 7, 119

lymphocyte clones, 357

M

machine code genetic programming, 9, 275-299

machine learning, 364-366

machine translation, 68, 83-85

Mackey-Glass equation, 411-412

macromutation, 265

majority-on problem, 152

Mathematica, 5

maximum entropy bloat, 169

MDL-based fitness function, 363

mean squared error, 408

measurement

of crossover, 177

of mutation, 177

of point mutation, 177

mechanical engineering, 41

medicine, 63

Mersenne Twister, 222, 235

Message Passing Inter face, 15

meta-individual, 55

micro-behaviour, 427-428, 430-431, 434, 443

migration between evolving

populations, 408

minimum description length principle, 255, 267, 430

minimum distance parsing, 68, 83-85

modules, 266, 268

MPI, 15

multi-agent

cooperation, 426

learning, 447-466

reinforcement learning, 464

team, 407, 409

multiobjective fitness measure, 120

multivariate

forecasting, 416

trees, 361

mutation, 50

adaptive, 259

applying a credit-blame map, 339-340

block, 286

context-preserving, 362

data, 286

Gaussian, 192

hill climbing, 92

instruction, 286

tailored, 268

mutation only bloat, 173

N

naive evolution, 430, 434, 440

Namoi River catchment, 99

natural image classification, 326

natural language processing, 6, 67-88

navigation task, 449

nearest k neighbours, 421

negotiation, 459

neural networks, 326, 351

neural programming, 325, 327

NMSE (Normalised Mean Squared Error), 408

node participation, 325

noise terms, 420

non-destructive crossover, 180

non-uniform rational B-splines, 42

normal curvature, 44

normal order, 19

normal plane, 44

normal vector, 43

normalisation, 422

null structure, 226, 230, 237

NURBS, 42

O

Occam's razor, 79, 267

on-line visualisation, 59

operative code, 165

operators, 325

optimisation

incremental, 56

multi-criterion, 48

parameter, 45

oracle, 149, 152-154

orthogonal function, 407

over-training, 410

over fitting, 171, 410

overflow, 409

P

Pac-Man problem, 9, 262

PADO, 9, 344

Paragen, 5-6, 15-39

parallel distributed genetic programming, 302

parallel evaluation of fitness cases, 315, 318

parallel programming, 5-6, 15, 301, 406, 413

Parallel Virtual Machine, 15

Parameterised Signal Primitive, 327

parasites

biological, 232

genetic programming, 232

parity problem, 316, 318

parse repair, 67-88

parsimony, 8, 254-256, 260-262

criterion, 50

parsing, 6, 67-68, 75-77, 83-85

grammar, 67-68, 83

partial parsing, 68, 75-77, 83-85

patents, 7, 131-132

pattern recognition, 42

penalty, 409

performance measures, 408

person identification, 63

perturbation theory, 420

phenotype, 51, 218-219, 233-235

physical object, 41, 42

approximated, 43

PIPE, 276

placement, 105

point cloud, 42

point mutation, 178

predator-prey problem, 425

preprocessing, 43

Price's covariance theorem, 8, 170, 246

probability amplitude, 136

probability density function, 221, 229-232

probability of improvement, 193

problem

11-bit multiplexer, 382-389

6-bit multiplexer, 199

acoustic signal classification, 326

adder, 307

and-or query, 135, 156-158

artificial ant, 175-177, 199, 378, 382, 389-392

cart centering, 199

character recognition, 9, 310

cross-structure reconstruction, 59-63

dash-and-dribble, 439-440

database search, 136, 154-156

dowel reconstruction, 54-59

early promise, 149-152

even-10 parity, 316

even-5 parity, 318

image classification, 345-347

majority-on, 152

navigation, 449

Pac-Man, 9, 262

parity, 9, 316, 318

predator-prey, 425

robot, 392

scaling majority-on, 152-153

sextic polynomial, 170

sunspot modeling, 199

symbolic regression, 170, 220, 234

table transport, 425, 431, 433, 439, 443

program

bottom-up refinement, 264

complexity, 243

dynamics, 358

landscapes, 182, 184

search spaces, 47, 167

shapes, 7-8, 184-185

size, 163, 243

top-down refinement, 265, 268

Prolog, 5

protective code theories of bloat, 166

proteins, 164, 165

PSP, 327

PVM, 15

Q

Q-learning, 10, 447, 462

quality measure, 48

quantum

computers, 7, 135-160

gates, 137-141

mechanics, 135, 420

qubit, 136

R

rainfall-runoff

grammar, 92

models, 6, 89-104

random number generator, 222

random seeds, 412

ranking selection, 430

rapid prototyping, 41

recombination, 51

reconstruction

cross-structure, 59

dowel, 54

surface, 41, 42

recursive regression, 404, 414

redesign, 41

reinforcement learning, 453-455, 464

removal bias, 183, 266

repair hypothesis, 79

reuse, 266

RMSE, 95

RNA translation, 164-165

RoboCup, 438

robot, 392

robotic soccer, 426, 443

root finding, 236

rooted-tree schema

disruption, 258

growth, 251

independence, 265

ROSE, 6, 67-88

rotation matrix, 141

routing, 105

S

sample average, 408

sample variance, 408

Santa Fe Competition, 415, 418

Santa Fe Institute, 415

Santa Fe trail, 199

scaling majority-on problem, 152-153

scheduling, 37

schema

in genetic algorithms, 218, 245

in genetic programming, 219, 233, 247

independence, 246

rooted-tree, 8, 243, 249

schema theorem, 7, 245

in genetic algorithms, 218

in genetic programming, 217

search operator, 46

search space, 7, 47, 167

size, 70-71

selection, 52, 199

comma-, 53

elitist, 52

fitness-proportional, 52

plus-, 53

ranking, 52

tournament, 52

selection pressure, 53

self crossover, 177

self tuning

with parameter crossover, 380

without parameter crossover, 379

self-tuning depth-dependent crossover, 10, 377-399

semantic replication, 409

sensor, 43

sequential evolution, 430, 434, 437, 440, 443

series expansion, 402, 405

sextic polynomial problem, 170

SGPC, 4

Shor's algorithm, 135-136

short-term forecasters, 415

silent variation, 195

simulated annealing bloat, 172

single-node, 219, 234

6-bit multiplexer problem, 199

size, genotypic, 55

Smalltalk, 5

smoothness, 43

software re-engineering, 15

speedup techniques, 302, 315

spurious information, 410

square root of not, 137-138

stack-based genetic programming, 135, 146-147

stackless linear genome genetic programming, 135, 147-148

state space, 402-403

coordinate variable, 407-408, 410

dense and coarse, 418, 421

stereometrical primitive, 47

stochastic iterative hillclimbing search, 82

stochastic modelling, 420

strict non-destructive crossover, 182, 183

STROGANOFF, 356, 364-366, 369, 372

structure evolution, 56

sub-machine-code genetic programming, 301-323

subroutine discovery, 268

subtree

content, 223, 226, 234

context, 226, 230, 233, 235

rooted, 218

subtree fair mutation, 175

sunspot modelling problem, 199

super population, 408-409

surface

approximating, 43

curved, 42, 46

geometrical, 42

physical, 42

surface oriented CAD system, 42

surface reconstruction, 6

SURREAL, 6, 42

symbiosis

biological, 232, 238

in genetic algorithms, 238

in genetic programming, 232, 238

symbol space, 402, 406

symbolic form

absurd, 409

attributes, 408

integration, 406

symbolic regression, 170, 220, 234, 401, 402

T

table transport problem, 425, 431, 433, 439, 443

terminal set, 2, 47

termination conditions, 410, 412

Tetris, 234

three-dimensional object, 41

Tile World, 447, 450

time series

ASHRAE Competition, 415

chaotic, 411-420

characterisation technologies, 421

deterministic and stochastic, 401, 404, 416-417, 420-421

non-stationary, 417

residual, 401, 404, 421

time series prediction, 6, 10, 90, 367-368, 370

topological information, 43

topology preservation, 43

topology-modifying functions, 114-118

trained approximate fitness evaluation, 78-80

translation systems, 67-88

tree shapes, 167, 184-185

tree-based homologous crossover, 291

tree-like polynomials, 361, 364

tree-schema, 249

triangulation, 42

gridded, 43

Tschebyshev function, 408, 422

U

underflow, 409

univariate forecasting, 416-417

V

vanishing z-value, 49

variable complexity representations, 249

variation operator, 46

vector

computational basis, 137

delay lag, 401

ket, 137

lag, 403

normal, 43

viable code, 165

virtual quantum computer, 136-143

volume oriented CAD system, 42

W

weakly-structured data, 41

Y

year 2000 problem, 15

Z

zoom-in regression, 404, 421