Key Word Index

A

a posteriori classification 109
Adaptive Distributed Database Management Problem (ADDMP) 3, 7, 8, 22
ANOVA 55

B

backbone (frozen variable set) 119
basin of attraction 22, 23, 92, 93, 105, 233, 238, 298, 322, 330
best action only maps.  See maps
birth-death process 244
blind exploration.  See exploration
breeder G A 9, 26
building-blocks 8, 26, 49, 69–90, 143, 145, 150, 154–159, 162, 163, 248
hypothesis 71
interdependency 8, 26, 69–90, 128
monotonically increasing number of correct 87 See also epistasis; linkage; schema; schema theorem
building-block problem 
hierarchical 14
separable 70, 71, 72, 75, 76, 79

C

Chernoff bounds 148, 161, 285
classical genetical algorithm 227, 236
classifiers 
accuracy-based fitness 167, 168, 173, 176–179, 181–184
action selection 166–169, 174, 176
fit overgeneral 174–176, 183
fitness 165–168, 171–175, 178–184
greedy creation 166
learning systems 165
overgeneral 166, 170-183
standard ternary language 167
strength 167, 168, 171, 172, 174, 176–183
strength-based fitness 167–169, 171–175, 179–184
strong overgeneral 166, 174–183
unbiased reward function 175, 180, 183
coefficient of variation 9
communication cost 232, 237
competing schemata 76, 81, 84
complementary crossover.  See recombination
complexity 
GA-easy 76, 103, 160
GA-friendly 76, 160
GA-hard/difficult 69–90
problem 41, 42, 47–67, 175
concatenate trap functions 78
convergence 5–7, 12, 26, 29, 42, 43, 85, 103, 143, 213, 224, 227, 230, 236, 246, 256, 300, 321, 322, 324
analysis 162, 261, 300
conditional 147, 156
GA 143, 145, 150
rate, finite-time 246, 256
connectivity 296, 306, 308
cooling schedule 236, 277 See also simulated annealing
crossover 9, 10, 12, 15, 22, 30, 49, 69–90, 187, 210, 211, 222, 223, 316, 323–325, 330 See also recombination
crossover mask 73–75, 78, 80, 81, 83, 222
crowding, deterministic 85, 86
cyclic behavior 7, 18, 24

D

decoder (genotype-to-phenotype) 313, 314, 316-318, 321–324, 326, 327, 329, 330
decomposition 
hierarchically decomposable problems 69–90
of mutation vectors 131
recursive 76
delivery phase 9
density of states (DOS) 109
transformation with respect to 109
dependency, non-linear 76, 77 See also epistasis; linkage
differential equation analysis 244, 247, 249, 251
dimensional reduction 78, 185, 194, 201
diploidy 313, 315–320, 322–330
distributions 
limiting, mutation 242, 257
limiting, recombination 245, 257
peak distribution characteristics 49, 50, 55–57
stationary probability 229, 230
steady-state 243
diversity 22, 77, 84, 85, 313, 316, 321, 324–328, 330
maintenance 29, 30, 77, 84, 85, 324, 330
dynamical system 209, 21l, 216
continuous-time 209, 216
discrete-time 211, 233, 238
random perturbations of 238, 231

E

ES (evolution strategy) 119, 128, 183, 214
(1+1) 127
EA (evolutionary algorithm) 5, 109, 128, 165, 183, 186, 275, 313
(1+1) 276
efficiency 135
eigenvalue 221, 246
elitist 9
empirical tests 6, 22
encodings 
binary versus Gray 298
fixed-length binary strings 9, 22, 227, 228
Gray 197, 297
shifting Gray 298 See also Gray codes
energy 
barrier 234, 236
function 230, 232, 236
entropy 325
epistasis 27, 47, 77, 84, 85, 77, 84, 85, 92, 102, 205 See also linkage
ergodic 243
Euler method 216
existence of solutions 217, 218, 224
expected run time 69–90, 278, 284, 287
exploration 182, 330
blind 229, 313, 328–330 See also search
exponential decrease rate of mutation 
probability 230, 234

F

fitness 
accuracy-based classifier 167, 168, 173, 176–179, 181–184
advantage 130
barrier 5, 9, 18, 23
biased reward function 175, 18l, 183
contributions 48, 70, 80, 82
distribution 7, 15
gain 130
ideal 130
landscape 47, 70, 80, 82, 91, 92, 102–105, 183, 189
neutral 18, 20
noise 130, 229
perceived 130
sharing 172
selection 166, 167, 174, 175, 181–183
fixed point 92
fixed-length binary strings.  See encodings
Freidlin-Wentzell theory 228, 233, 236

G

GA (genetic algorithm) 47, 69–90, 110, 128, 165, 209, 211, 316, 319
classical 227, 236
generational 9, 29, 145, 209–211, 222–224, 227, 229, 316
steady-state 9, 22, 86, 103, 111, 209–213, 222, 224
Geiringer’s theorem 241, 245, 258
genetic linkage.  See epistasis linkage
genetic repair 135
Genitor 211
genotype 314
GIGA/Gene lnvariant GA 72, 73, 76, 80, 84, 85
Gray codes 197, 297
high precision 299
neighborhood structure 299
standard binary reflected 297
unique shifts 299
guaranteed path to solution 79, 319, 321

H

Hamming 
cliffs 203, 298
distance 39, 41, 103, 189, 203, 231, 289
distance-1 neighborhood 103, 297, 299
space 57, 305
hardness measure 92, 120
heuristics 315, 316
hierarchies, default 169, 170, 184
H-IFF (hierarchical-if-and-only-if), 7–9, 14, 18, 22, 23, 69, 72, 76
shuffled 77
higher-order schemata 71, 76
hill climbing 9, 18, 24, 27–46, 49, 69–90, 319, 328
macro-mutation 88
random mutation 18, 79
hyperplanes 7, 16, 72, 187, 196, 249, 252, 255, 258 See also schema

I

infinite temperature approximation 115

J

juxtapositional characteristics 49

K

knapsack problem 314–316, 322, 324, 333 See also problems
landscape generator 47
landscapes 7, 9, 19, 20, 24, 27–46, 47, 88, 91, 92, 102, 103, 188, 189, 319, 322
NK 7, 18, 20, 23, 27, 47, 48, 49, 72, 102–105
NKP 47, 49
NKPSR 54
structure of 47–67, 91, 92, 105, 189, 314, 318–322 See also fitness
large deviations 227, 229
learning.  See reinforcement learning
linear function 285
linkage 71, 72, 77, 78, 88
disequilibrium 71, 77, 252, 258
genetic 71, 72, 77, 78, 88, 205, 261
tight genetic 71, 78, 88
poor 77 See also epistasis
Lipschitz condition 216, 217, 219
local performance 130
long path 88, 291

M

macro-mutation 71, 78, 79, 80, 313, 328–330
hill climbing 88
maps 
best action only 172, 175, 179
complete 173, 175
Markov chain 222, 230, 242, 278
Markov inequality 281, 283
max-ones problem.  See problems
MAX3SAT 120
mean evaluations used/exploited 6, 14, 20
Mendelian segregation 246
Metropolis algorithm 115, 276, 277
mixing rate 261
models, 
finite population 214, 247
infinite population 209–211, 216, 218–220, 222, 247
macroscopic vs. microscopic 144
sphere 119, 128, 130
multimodal functions 18, 20, 22
multimodal performance profile 9, 22
multimodality 7
multistep tasks (sequential tasks) 169, 184
mutation 5, 7, 8, 11, 12, 14, 22, 23, 69, 129, 210, 211, 214, 221–223, 229, 233, 242, 316, 318–322
event 5, 8, 9, 11, 23, 24
k-gene/bit 8, 12, 23
limiting distributions 242, 257
neutral 313, 318, 319, 322–324, 330
New Random Allele (NRA) 9, 12, 20, 22
optimal rates 7, 23
probability 111, 230, 233, 276, 284, 316, 319–321, 328
rescaled 135
selection algorithm 227, 276
space 72
strength 130
total used 9, 11, 14
vector decomposition 131

N

neutral networks 318, 321–323
next ascent 302
NK landscapes.  See landscapes
No Free Lunch 91, 297
noise strength 131
noise-to-signal ratio 132, 135
non-separable 69–90
normalization 109, 131
normalized progress rate 119, 133
normalizing constant 115

O

one-point crossover.  See recombination
OneMax.  See problems
optimal performance 22, 134
optima 
best fitness found 6, 15, 18, 24
collapse of local 305
convergence to 300
expected number of 69, 88, 91–105, 297
exponential number of local 69, 79, 88
global 47, 92, 188, 213, 221, 224, 229, 296, 324
local 5, 8, 9, 12, 22–24, 27–46, 55, 79, 91, 103–105, 188, 296, 312, 318–322, 328, 330
path to 69–90, 120, 319, 321 See also convergence

P

parameter 
control 275
optimization problem 298
sensitivity 5, 6
passive solution 328
path-to-jump 288
path-with-trap 291
performance profiles 5, 6, 7, 20, 24
perturbations, asymptotically vanishing 231, 232
phase transition 114
phased behavior 7, 18, 20, 23, 24
population 
equi-fitness 234
mean curve 109
finite model 214, 247
infinite model 209–211, 216, 218–220, 222, 247
multiset 210
sizing 6, 9, 12, 14, 15, 20, 22, 128
uniform 224, 229, 236
vector 103, 210
potential associated to a communication 
cost function 233
problems 
Adaptive Distributed Database Management Problem (ADDMP) 3, 7, 8, 22
knapsack 314–316, 322, 324, 333
leading ones 114, 285
longest path 299
max-ones (OneMax) 7, 9, 18, 22, 72, 113, 279
NK landscapes.  See landscapes
Royal Road 76, 88
Royal Staircase 7, 18, 20, 22
test 7, 71, 76, 88, 113, 223
progress coefficient, c_((/(I, (( 133
progress rate 130

Q

quality of service 6, 25
radioactive decay 244, 245

R

Random Bit Climber (RBC) 27-46, 304
random walk 14, 20, 22, 24, 284, 319, 321
ranking deletion 211–213, 220
real-world problems 5, 6 See also problems
recombination 
complementary 80
distributions 241, 246, 258
global 129
intermediate 129
landscape/space 71, 72, 77
limiting distributions 245, 257
mask 73–75, 78, 80, 81, 83, 222
neutral 313, 323, 324, 326, 327, 330
one-point (single-point) 9, 15, 27–46, 71, 72, 77, 145, 187, 188, 250, 265
two-point 30, 72, 78, 88, 189, 267, 316
uniform 9, 22, 27–46, 189, 223, 250, 252, 255, 258, 264
recombinative 69–90, 27–46
algorithm, upper bound for 69–90
hill-climber 69, 80
redundancy 313–343
degree of 317
reinforcement learning 167, 173
repairing of individuals 315
representable domain values 304
representation 9, 167, 172, 173, 183, 188, 296, 313 See also encodings
reproduction 9, 18, 166, 167, 174, 175, 181–183
repulsive, attractive sets 233, 238
Robbins’ equilibrium 246, 250, 252, 254, 256–258
Royal Road 76, 88 See also problems

S

schema 71, 76, 78, 80, 143–145, 151, 155, 160, 163, 318, 323, 324
analysis 241, 248, 252
competing 76, 81, 84
construction 248, 249, 258
disruption 248, 249, 258, 323
higher-order 71, 76
schema theorem 143–164, 187
conditional 143, 148, 152, 158, 162
exact 145, 162
without expectation operator for finite populations 162
prediction over multiple generations 144
recursive 152, 156–159
search 
blind 229, 313, 328–330
evolutionary 7, 8, 12, 23, 24
search plateau 313, 318, 319, 321–323, 327, 330
search space, reduction of 317, 322
selection 9, 18, 166, 167, 174, 175, 181–183
Boltzmann 114, 128, 227
fitness-based 166, 167, 174, 175, 181–183
pressure 12, 14, 120, 166, 227, 233, 236, 323, 324, 328
schedule 9, 18, 277
tournament 9, 22
worst-element deletion 211, 212, 214, 220, 221, 224
simplex 210, 213, 216, 217, 219–221, 223
simulated annealing 92, 115, 227, 236, 276, 277
generalized 228
single step (non-sequential) tasks 167, 169
single-point crossover.  See recombination
spanning tree 237
sphere functions 128, 130, 203, 302
stability 209, 221, 222
asymptotic 209, 221
stationary probability distribution.  See distributions
steady-state distribution.  See distributions
steepest ascent 302 See also hill climbing
structure of landscape.  See landscapes
summary statistics 109
symmetric function 277

T

temperature parameter 115 See also simulated annealing
trajectory 211, 216, 220
transient behavior 169, 182, 241, 244, 247, 258
transition phase 11, 20
transition matrices 231
tuning phase 8, 11
two-point crossover.  See recombination

U

unbiased reward function.  See classifiers
uniform crossover.  See recombination
uniform equilibrium 242, 257, 258
unimodal functions 18, 20, 22, 23, 24, 300 See also problems
unitation function 223

V

valley 105, 279
velocity 109

W

Walsh coefficients 50, 51, 92, 190, 191, 196
Walsh transform 50, 51, 185, 190
worst-element deletion.  See selection
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.138.204.186