The success of a genetic algorithm when applied to an optimization problem depends upon several features present or absent in the problem to be solved, including the quality of the encoding of data, the geometric structure of the search space, deception or epistasis. This book deals essentially with the latter notion, presenting for the first time a complete state-of-the-art research on this notion, in a structured completely self-contained and methodical way. In particular, it contains a refresher on the linear algebra used in the text as well as an elementary introductory chapter on genetic algorithms aimed at readers unacquainted with this notion. In this way, the monograph aims to serve a broad audience consisting of graduate and advanced undergraduate students in mathematics and computer science, as well as researchers working in the domains of optimization, artificial intelligence, theoretical computer science, combinatorics and evolutionary algorithms.
Author(s): M. Iglesias B. Naudts C. Vidal
Edition: 1
Year: 2005
Language: English
Pages: 309
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
