Contents
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . XV
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .XVII
List of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .XIX
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Research Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Road Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Genetic Algorithms and Genetic Linkage . . . . . . . . . . . . . . . . . . 5
2.1 Overview of Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.1 Representation, Fitness, and Population . . . . . . . . . . . . . . 6
2.1.2 Selection, Crossover, and Mutation . . . . . . . . . . . . . . . . . . 7
2.2 Goldberg’s Design Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Population-Sizing Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Competent Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.5 Genetic Linkage and the Linkage Problem . . . . . . . . . . . . . . . . . . 17
2.5.1 What Is Genetic Linkage? . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.5.2 Linkage Learning as an Ordering Problem . . . . . . . . . . . . 20
2.5.3 Why Is Genetic Linkage Learning Iportant? . . . . . . . . . 20
2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3 Genetic Linkage Learning Techniques . . . . . . . . . . . . . . . . . . . . . . 23
3.1 Unimetric Approach vs. Multimetric Approach . . . . . . . . . . . . . . 24
3.2 Physical Linkage vs. Virtual Linkage . . . . . . . . . . . . . . . . . . . . . . . 26
3.3 Distributed Model vs. Centralized Model . . . . . . . . . . . . . . . . . . . 28
3.4 LLGA: Precursors and Ancestors . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.5 LLGA: Unimetric, Physical Linkage, and Distributed Model . . 32
3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4 Linkage Learning Genetic Algorithm. . . . . . . . . . . . . . . . . . . . . . . 35
4.1 Chromosome Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2 Exchange Crossover. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3 Linkage Definition and Two Linkage Learning Mechanisms. . . . 38
4.3.1 Quantifying Linkage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3.2 Linkage Skew . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.3.3 Linkage Shift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.4 Accomplishments of the LLGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.5 Difficulties Faced by the LLGA. . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5 Preliminaries: Assumptions and the Test Problem . . . . . . . . . 45
5.1 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.2 Test Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6 A First Improvement: Using Promoters. . . . . . . . . . . . . . . . . . . . 51
6.1 A Critique of the Original LLGA . . . . . . . . . . . . . . . . . . . . . . . . . . 52
6.1.1 Test Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
6.1.2 What Is the LLGA Supposed to Do?. . . . . . . . . . . . . . . . . 52
6.1.3 How Does the LLGA Fail?. . . . . . . . . . . . . . . . . . . . . . . . . . 53
6.1.4 Separation Inadequacy: Key Deficiency of the LLGA . . . 54
6.2 Improve Nucleation Potential with Promoters . . . . . . . . . . . . . . . 56
6.2.1 How Do Promoters Work? . . . . . . . . . . . . . . . . . . . . . . . . . . 56
6.2.2 Modified Exchange Crossover . . . . . . . . . . . . . . . . . . . . . . . 57
6.2.3 Effect of the Modifications . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
7 Convergence Time for the Linkage Learning
Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
7.1 Experimental Settings. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
7.2 Sequentiality for Exponentially Scaled BBs . . . . . . . . . . . . . . . . . 65
7.2.1 Time to Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
7.2.2 Building-Block Propagation. . . . . . . . . . . . . . . . . . . . . . . . . 66
7.2.3 Time to Tighten the First Building Block . . . . . . . . . . . . 67
7.3 Sequentiality for Uniformly Scaled BBs . . . . . . . . . . . . . . . . . . . . . 67
7.3.1 Time to Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
7.3.2 Building-Block Propagation. . . . . . . . . . . . . . . . . . . . . . . . . 69
7.3.3 Time to Tighten the First Building Block . . . . . . . . . . . . 72
7.4 Macro View: Sequential Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . 72
7.5 Extending Linkage Learning Mechanisms . . . . . . . . . . . . . . . . . . . 74
7.5.1 Extending the Linkage-Skew Model . . . . . . . . . . . . . . . . . . 76
7.5.2 Extending the Linkage-Shift Model . . . . . . . . . . . . . . . . . . 78
7.6 Micro View: Tightness Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
7.7 From One Building Block to m Building Blocks . . . . . . . . . . . . . 84
7.7.1 Genetic Material from the Donor . . . . . . . . . . . . . . . . . . . . 86
7.7.2 Genetic Material on the Recipient . . . . . . . . . . . . . . . . . . . 86
7.7.3 Tightness Time for m Uniformly Scaled Building Blocks 86
7.8 Convergence Time Model for the LLGA . . . . . . . . . . . . . . . . . . . . 87
7.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
8 Introducing Subchromosome Representations . . . . . . . . . . . . . . 91
8.1 Limit to Competence of the LLGA . . . . . . . . . . . . . . . . . . . . . . . . 91
8.2 Subchromosome Representations . . . . . . . . . . . . . . . . . . . . . . . . . . 92
8.2.1 Chromosome Representation . . . . . . . . . . . . . . . . . . . . . . . . 92
8.2.2 Exchange Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
8.3 Empirical Verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
8.3.1 Experimental Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
8.3.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
8.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
9 Conclusions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
9.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
9.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
9.3 Main Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
Another Genetic Algorithm Books
Download
No comments:
Post a Comment