Foundations of Generic Optimization: Volume 1: A Combinatorial Approach to Epistasis

1402036663......Page 1
Contents......Page 8
O Genetic algorithms: a guide for absolute beginners......Page 13
1 Basic concepts......Page 32
2 The GA in detail......Page 36
3 Describing the GA dynamics......Page 40
4 Tools for GA design......Page 42
5 On the role of toy problems.........Page 44
5.2 One needle, two needles......Page 45
5.3 Unitation functions......Page 47
5.4 Crossover-friendly functions......Page 49
6 . . . and more serious search problems......Page 55
7.1 Fitness–distance correlation......Page 57
7.2 Interactions......Page 58
7.3 The epistasis measure......Page 60
1 Introduction......Page 62
2.1 Epistasis variance......Page 63
2.2 Normalized epistasis variance......Page 65
3.1 The matrices G[sub(l)] and E[sub(l)]......Page 66
3.2 The rank of the matrix G[sub(l)]......Page 71
4 Examples......Page 74
5.1 The minimal value of normalized epistasis......Page 76
5.2 The maximal value of normalized epistasis......Page 82
III Examples......Page 87
1.1 Generalized Royal Road functions of type I......Page 88
1.2 Generalized Royal Road functions of type II......Page 97
1.3 Some experimental results......Page 102
2.1 Generalities......Page 103
2.2 Matrix formulation......Page 104
2.3 The epistasis of a unitation function......Page 105
2.4 The matrix B[sub(l)]......Page 106
2.5 Experimental results......Page 110
3.1 Basic properties......Page 113
3.2 Epistasis of template functions......Page 120
3.3 Experimental results......Page 126
IV Walsh transforms......Page 128
1.1 Walsh functions......Page 129
1.2 Properties of Walsh functions......Page 130
1.3 The Walsh matrix......Page 133
2 Link with schema averages......Page 136
3 Link with partition coefficients......Page 141
4 Link with epistasis......Page 145
5.1 Some first, easy examples......Page 150
5.2 Amore complicated example: template functions......Page 154
6 Minimal epistasis and Walsh coefficients......Page 160
1 Multary representations......Page 163
2 Epistasis in the multary case......Page 165
2.2 Matrix representation......Page 166
2.3 Comparing epistasis......Page 174
3 Extreme values......Page 176
3.1 Minimal epistasis......Page 177
3.2 Maximal epistasis......Page 180
4 Example: Generalized unitation functions......Page 189
4.1 Normalized epistasis......Page 190
4.2 Extreme values of normalized epistasis......Page 204
1 Generalized Walsh transforms......Page 212
1.1 First generalization to the multary case......Page 213
1.2 Second generalization to the multary case......Page 225
2 Examples......Page 231
2.1 Minimal epistasis......Page 232
2.2 Generalized camel functions......Page 235
2.3 Generalized unitation functions......Page 236
2.4 Second order functions......Page 238
3 Odds and ends......Page 243
3.2 Balanced sum theorems......Page 244
3.3 Partition coefficients revisited......Page 246
3.4 Application: moments of schemata and fitness function......Page 249
3.5 Application: summary statistics for binary CSPs......Page 251
A The schema theorem (variations on a theme)......Page 255
1 A Fuzzy Schema Theorem......Page 256
2 The schema theorem on measure spaces......Page 261
1.1 Generalities......Page 267
1.2 Invertible matrices......Page 271
1.3 Generalized inverses......Page 273
2.1 Generalities......Page 274
2.2 Linear independence, generators and bases......Page 275
2.3 Euclidean spaces......Page 279
3.1 Definition and examples......Page 281
3.2 Linear maps and matrices......Page 282
3.3 Orthogonal projections......Page 283
4.1 Eigenvalues and eigenvectors......Page 284
4.2 Diagonalizable matrices......Page 286
Bibliography......Page 288
L......Page 300
W......Page 301