ABSTRACT vi
List of Figures xiii
List of Equations xvi
List of Tables xvi
Chapter 1 - Accretive
and compositional change in natural and
artificial evolution 1
1.1 Exchange between evolutionary biology and evolutionary computation 2
1.1.1 Gradualism and the probability of large adaptive changes 2
1.1.2 Evolutionary adaptation and artificial optimisation methods 3
1.2 Accretive and compositional mechanisms 4
1.3 Complex systems with modular interdependency 7
1.3.1 Evolvability and algorithmic paradigms 7
1.3.2 Modular interdependency 10
1.4 The (un)evolvability of systems with modular interdependecy 14
1.5 Conditions for the adaptive advantage of composition 17
1.5.1 Composition based on sexual recombination 18
1.5.2 Composition based on symbiotic encapsulation 20
1.6 Impact for evolutionary biology and evolutionary computation 22
1.7 Related issues 26
1.7.1 Related issues in Evolutionary Biology 26
1.7.2 Related issues in Evolutionary Computation 28
1.8 Summary 32
1.8.1 Motives, research questions, and claims 32
1.8.2 Approach and outline of models 33
1.8.3 Contributions 35
1.8.4 Scope 36
1.8.5 Dissertation structure 37
Chapter 2 - Accretion and Composition in Evolutionary Biology 40
2.1 The accretive model 40
2.1.1 Successive slight modifications/ gradualism 40
2.1.2 Evolutionary difficulty under accretion 42
2.1.3 Consequences of the accretive model 47
2.2 Compositional mechanisms 48
2.2.1 A spectrum of compositional mechanisms 48
2.2.2 Sexual recombination 49
2.2.3 Interspecific genetic integration 52
2.2.4 Compositional evolution 56
2.2.5 Is gradualism necessary and/or sufficient? 57
2.3 Other related mechanisms 59
2.3.1 Large phenotypic changes from small genotypic changes: ontogenesis 60
2.3.2 Mechanisms for large genetic changes within a lineage: Gene duplication 61
2.3.3 Large changes within a lineage and self-similarity 61
2.3.4 Within a lineage vs between parallel lineages 62
2.4 Evolutionary difficulty under composition 63
2.4.1 Transferring concepts of accretive difficulty (where possible) 63
2.5 Discussion 68
2.5.1 Single inheritance and multiple-inheritance 68
2.5.2 The rest of the genotype as a ‘backdrop’ vs important epistasis 71
2.5.3 Selection on interaction systems: Shifting Balance Theory 72
2.5.4 Other species as a ‘backdrop’ vs important interspecific relationships 74
2.5.5 Intragenomic dependencies and intergenomic dependencies 75
2.6 Summary 75
Chapter 3 - Accretion and Composition in Evolutionary Computation 76
3.1 Evolutionary Algorithms 76
3.1.1 Evolutionary algorithm basics 76
3.1.2 The Simple Genetic Algorithm 78
3.1.3 EAs as Evolutionary Models 80
3.2 Evolutionary difficulty for the Simple EA 82
3.3 Compositional mechanisms in EAs 83
3.3.1 The operation of crossover 84
3.3.2 The Building block Hypothesis, BBH 86
3.3.3 Algorithmic Principles - Divide-and-Conquer Problem Decomposition 89
3.3.4 Mechanisms of encapsulation in EAs 93
3.3.5 Other related divide and conquer methods 94
3.3.6 Explicit symbiosis/symbiogenesis models 96
3.3.7 Summary of existing methods 100
3.4 Evolutionary difficulty under compositional mechanisms 101
3.4.1 Difficulties of building block processing under recombination 101
3.4.2 Schema
disruption: genetic linkage, partial specification, and competing
conventions. 101
3.4.3 Evaluation of parts 105
3.4.4 Selection on parts: The credit assignment problem 106
3.4.5 Coevolution
of parts: premature convergence/competitive exclusion and
fitness sharing. 107
3.4.6 The multi-dimensional interpretation of fitness and ‘Pareto coevolution’ 108
3.5 Test problems 110
3.5.1 Building block problems 111
3.5.2 Interdependency 112
3.5.3 Other test problems for EAs 113
3.5.4 Modularity and interdependency: non-separable modules 114
3.6 Summary 115
3.7 Accretion and composition in evolutionary biology and evolutionary computation 116
Chapter 4 - Defining Modular Interdependency 119
4.1 Philosophical provisos: The ‘problem’ for an evolving entity 120
4.2 Pairwise interactions 120
4.2.1 Pairwise interactions and fitness saddles 120
4.2.2 Defining ‘interdependency’ 123
4.3 Large-Scale interdependency structure 124
4.3.1 Separability and decomposability to modular interdependency 126
4.3.2 An example non-separable but decomposable system of four variables 130
4.4 Generalised models 134
4.4.1 Aggregate effects of modules: dimensional reduction 134
4.4.2 Hierarchy and scaling-up 137
4.4.3 General recursive form 139
4.4.4 Hierarchical consistency 140
4.4.5 Alternate base functions 141
4.5 Hierarchical-Equality and Hierarchical-if-and-only-if (HIFF) 143
4.6 Discussion 146
4.6.1 Symmetries and variations 146
4.6.2 The HIFF landscape and natural hierarchy 146
4.6.3 Other hierarchical modular interdependency functions 147
4.6.4 Comparison with Royal Roads, concatenated trap functions, and NKC landscapes 147
4.6.5 Modular interdependency as a hierarchical cooperation problem 149
4.6.6 How changes in Module A affect the fitness landscape for Module B 150
4.6.7 Relation to philosophical provisos 151
4.7 Summary 151
Chapter 5 - Mutation on Modular Interdependency 153
5.1 Cross-sections through the fitness landscape 153
5.2 Difficulty of modular interdependency for accretive mechanisms 157
5.2.1 Ruggedness 157
5.2.2 Width of fitness saddles 158
5.2.3 Irreducibility - HIFF appears to be irreducibly complex (but is not) 159
5.2.4 HIFF appears to have low epistasis (but does not) 161
5.3 Expected time to solution for accretive mechanisms 162
5.3.1 Preliminary Comparison with compositional mechanisms 163
5.4 Simulation results for mutation 164
5.5 Summary 166
Chapter 6 - Sexual Recombination on Modular Interdependency 168
6.1 Overview of models 170
6.2 Basic Model: Single panmictic population—Simple GA 170
6.2.1 Simulation results 171
6.2.2 Discussion 173
6.3 Diversity: Subdivided/niched population—GA with crowding 174
6.3.1 Mutation is not essential 180
6.3.2 Gradualism is neither sufficient nor required 181
6.4 Genetic linkage 181
6.4.1 No genetic linkage: ‘Free recombination’ or ‘uniform crossover’ 182
6.4.2 Re-ordered linkage: Shuffled gene positions 186
6.4.3 Convergence controlled variation 190
6.4.4 Linkage learning 192
6.5 Summary of simulation results 193
6.6 Analysis of sexual recombination on HIFF 197
6.6.1 Analysis on separable problems 199
6.6.2 Analyses on HIFF 203
6.6.3 Analyses for a recombinative hill-climber 205
6.6.4 From a recombinative hill-climber to a recombinative population 211
6.7 Empirical illustration of analytic results 213
6.7.1 Simulation
for Theorem 4: Recombinative Hill-climber with one-point
crossover on HIFF. 213
6.7.2 Simulation for Theorem 5: GA with two-point crossover applied to H-IFF2 214
6.7.3 Summary of analysis section 217
6.8 Summary of sexual recombination on hierarchically modular problems 217
Chapter 7 - Symbiotic Encapsulation on Modular Interdependency 219
7.1 Overview of symbiotic encapsulation model 219
7.2 Integration model: Entities and their encapsulation 221
7.2.1 Mutually exclusive characters and the ‘overlap’ of feature sets 221
7.2.2 A model of entities and their encapsulation 225
7.2.3 Consequences for adaptation 227
7.3 Evaluation and selection model 228
7.3.1 Evaluating an entity in different contexts 229
7.3.2 Pareto dominance 230
7.3.3 Building environmental contexts: Group evaluation 232
7.4 The Symbiogenic Evolutionary Adaptation Model (SEAM) 233
7.5 Simulation results 234
7.5.1 Control experiments 235
7.5.2 Simulation results for SEAM and control experiments 236
7.5.3 Summary of main simulation experiments using SEAM and GA. 239
7.6 Discussion 241
7.6.1 Coevolution and SEAM 241
7.6.2 Canalisation of successful groups 242
7.6.3 Scale-invariant evolutionary processes 243
7.7 Analysis of SEAM on Shuffled HIFF 245
7.7.1 Idealised-SEAM 245
7.7.2 From idealised-SEAM to SEAM 250
7.7.3 Summary of analytic results 255
7.8 Summary 256
Chapter 8 - Implications for Evolutionary Biology 258
8.1 Impact for evolutionary biology 258
8.1.1 Evolutionary difficulty and gradualism 258
8.1.2 Symbiosis as source of evolutionary innovation 259
8.1.3 Multiple-inheritance allows large non-random genetic changes 260
8.1.4 Assumptions concerning genetic systems 261
8.2 Related results 261
8.2.1 Hierarchical encapsulation, the Baldwin effect, and symbiotic scaffolding 261
8.3 Future research 263
8.3.1 The relationship of accretive and compositional mechanisms 263
8.3.2 The open-endedness of evolutionary processes 266
8.3.3 The
inherent tension of innovation and reproductive fidelity (change and
non-change) 267
8.3.4 Selfish genes and the evolution of cooperation 268
8.3.5 Modular interdependency in natural systems 269
8.3.6 The ubiquity of compositional mechanisms 271
Chapter 9 - Implications for Evolutionary Computation 272
9.1 Impact for Evolutionary Computation 272
9.1.1 Building Block Hypothesis 272
9.1.2 Building blocks and modules - genetic linkage vs. interdependency 272
9.1.3 GA-easiness 273
9.1.4 Interdependency and NK landscapes 274
9.1.5 Module acquisition and linkage learning 275
9.1.6 Crossover is not just macro-mutation 275
9.1.7 Competing conventions problem 275
9.1.8 Credit assignment 275
9.1.9 Separation of the Building Block Hypothesis from the Schema Theorem 276
9.1.10 Evolution and coevolution in the GA with crossover 276
9.1.11 Optimisation at several scales vs. optimisation at any one scale 277
9.2 Understanding modularity 280
9.2.1 Modular interdependency, Ising models, and renormalisation groups 280
9.2.2 Simon and nearly decomposable systems 282
9.2.3 Deception 284
9.2.4 Relationship of HIFF to some related concepts of problem difficulty 286
9.3 Understanding composition 287
9.3.1 Recombining versus combining 288
9.3.2 Problems with partial evaluation, bloat, and diversity 288
9.3.3 Template differencing 290
9.3.4 The pressure to fill-in missing features 291
9.3.5 The Baldwin effect and ‘stochastic lookahead’ 292
9.3.6 Stochastic lookahead avoids need for ‘backtracking’ in greedy optimisation 293
9.3.7 Pareto Coevolution 295
9.3.8 Relationship of SEAM to some other algorithmic methods 297
9.4 Future research 298
9.4.1 Theoretical 298
9.4.2 Possible applications of SEAM 299
9.4.3 Extensions of SEAM 300
Chapter 10 - Summary and Conclusions 303
Subject Index 308
References 311