Global Optimization Algorithms– Theory and Application

相似文件 换一批

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

Global Optimization Algorithms _Theory and Application.pdf (12.61 MB, 需要: 10 个论坛币)

2010-9-12 10:49:50 上传

需要: 10 个论坛币  [购买]

Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Part I Global Optimization
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.1 A Classification of Optimization Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.1.1 Classification According to Method of Operation . . . . . . . . . . . . . . . . . . 22
1.1.2 Classification According to Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.2 What is an optimum? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.2.1 Single Objective Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.2.2 Multiple Objective Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.2.3 Constraint Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.2.4 Unifying Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.3 The Structure of Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.3.1 Spaces, Sets, and Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.3.2 Fitness Landscapes and Global Optimization . . . . . . . . . . . . . . . . . . . . . 47
1.3.3 Gradient Descend . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
1.3.4 Other General Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
1.4 Problems in Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
1.4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
1.4.2 Premature Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
1.4.3 Ruggedness and Weak Causality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
1.4.4 Deceptiveness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
1.4.5 Neutrality and Redundancy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
1.4.6 Epistasis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
1.4.7 Noise and Robustness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
1.4.8 Overfitting and Oversimplification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
1.4.9 Dynamically Changing Fitness Landscape . . . . . . . . . . . . . . . . . . . . . . . . 76
1.4.10 The No Free Lunch Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
1.4.11 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
1.5 Formae and Search Space/Operator Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
1.5.1 Forma Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
1.5.2 Genome Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
1.6 General Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
1.6.1 Areas Of Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
1.6.2 Conferences, Workshops, etc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
8 CONTENTS
1.6.3 Journals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
1.6.4 Online Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
1.6.5 Books . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
2 Evolutionary Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
2.1.1 The Basic Principles from Nature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
2.1.2 The Basic Cycle of Evolutionary Algorithms . . . . . . . . . . . . . . . . . . . . . . 96
2.1.3 The Basic Evolutionary Algorithm Scheme . . . . . . . . . . . . . . . . . . . . . . . 98
2.1.4 From the Viewpoint of Formae . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
2.1.5 Does the natural Paragon Fit? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
2.1.6 Classification of Evolutionary Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 100
2.1.7 Configuration Parameters of evolutionary algorithms . . . . . . . . . . . . . . . 104
2.2 General Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
2.2.1 Areas Of Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
2.2.2 Conferences, Workshops, etc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
2.2.3 Journals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
2.2.4 Online Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
2.2.5 Books . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
2.3 Fitness Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
2.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
2.3.2 Weighted Sum Fitness Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
2.3.3 Pareto Ranking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
2.3.4 Sharing Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
2.3.5 Variety Preserving Ranking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
2.3.6 Tournament Fitness Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
2.4 Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
2.4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
2.4.2 Truncation Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
2.4.3 Fitness Proportionate Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
2.4.4 Tournament Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
2.4.5 Ordered Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
2.4.6 Ranking Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
2.4.7 VEGA Selection. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
2.4.8 Clearing and Simple Convergence Prevention (SCP) . . . . . . . . . . . . . . . 134
2.5 Reproduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
2.5.1 NCGA Reproduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
2.6 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
2.6.1 VEGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：Optimization Application Algorithms Algorithm Global Theory Optimization Application Algorithms Global

薄利多销额~

2# raymond009
3 Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
3.2 General Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
3.2.1 Areas Of Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
3.2.2 Conferences, Workshops, etc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
3.2.3 Online Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
3.2.4 Books . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
3.3 Genomes in Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
3.4 Fixed-Length String Chromosomes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
3.4.1 Creation: Nullary Reproduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
3.4.2 Mutation: Unary Reproduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
3.4.3 Permutation: Unary Reproduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
3.4.4 Crossover: Binary Reproduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
3.5 Variable-Length String Chromosomes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
CONTENTS 9
3.5.1 Creation: Nullary Reproduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
3.5.2 Mutation: Unary Reproduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
3.5.3 Crossover: Binary Reproduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
3.6 Schema Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
3.6.1 Schemata and Masks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
3.6.2 Wildcards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
3.6.3 Holland’s Schema Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
3.6.4 Criticism of the Schema Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
3.6.5 The Building Block Hypothesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
3.7 The Messy Genetic Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
3.7.1 Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
3.7.2 Reproduction Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
3.7.3 Splice: Binary Reproduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
3.7.4 Overspecification and Underspecification . . . . . . . . . . . . . . . . . . . . . . . . . 154
3.7.5 The Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
3.8 Genotype-Phenotype Mappings and Artificial Embryogeny . . . . . . . . . . . . . . . . 155
4 Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
4.1.1 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
4.2 General Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
4.2.1 Areas Of Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
4.2.2 Conferences, Workshops, etc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
4.2.3 Journals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
4.2.4 Online Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
4.2.5 Books . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
4.3 (Standard) Tree Genomes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
4.3.1 Creation: Nullary Reproduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
4.3.2 Mutation: Unary Reproduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
4.3.3 Recombination: Binary Reproduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
4.3.4 Permutation: Unary Reproduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
4.3.5 Editing: Unary Reproduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
4.3.6 Encapsulation: Unary Reproduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
4.3.7 Wrapping: Unary Reproduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
4.3.8 Lifting: Unary Reproduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
4.3.9 Automatically Defined Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
4.3.10 Automatically Defined Macros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
4.3.11 Node Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
4.4 Genotype-Phenotype Mappings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
4.4.1 Cramer’s Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
4.4.2 Binary Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
4.4.3 Gene Expression Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
4.4.4 Edge Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
4.5 Grammars in Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
4.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
4.5.2 Trivial Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
4.5.3 Strongly Typed Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
4.5.4 Early Research in GGGP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
4.5.5 Gads 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
4.5.6 Grammatical Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
4.5.7 Gads 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
4.5.8 Christiansen Grammar Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
4.5.9 Tree-Adjoining Grammar-guided Genetic Programming . . . . . . . . . . . . 187
4.6 Linear Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191

2# raymond009
10 CONTENTS
4.6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
4.6.2 Advantages and Disadvantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
4.6.3 The Compiling Genetic Programming System . . . . . . . . . . . . . . . . . . . . . 193
4.6.4 Automatic Induction of Machine Code by Genetic Programming . . . . 193
4.6.5 Java Bytecode Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
4.6.6 Brameier and Banzhaf: LGP with Implicit Intron removal . . . . . . . . . . 194
4.6.7 Homologous Crossover: Binary Reproduction. . . . . . . . . . . . . . . . . . . . . . 195
4.6.8 Page-based LGP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
4.7 Graph-based Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
4.7.1 Parallel Algorithm Discovery and Orchestration . . . . . . . . . . . . . . . . . . . 196
4.7.2 Parallel Distributed Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . 196
4.7.3 Genetic Network Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
4.7.4 Cartesian Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
4.8 Epistasis in Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
4.8.1 Forms of Epistasis in Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . 202
4.8.2 Algorithmic Chemistry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
4.8.3 Soft Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
4.8.4 Rule-based Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
4.9 Artificial Life and Artificial Chemistry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
4.9.1 Push, PushGP, and Pushpop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
4.9.2 Fraglets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
4.10 Problems Inherent in the Evolution of Algorithms . . . . . . . . . . . . . . . . . . . . . . . 219
4.10.1 Correctness of the Evolved Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
4.10.2 All-Or-Nothing? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
4.10.3 Non-Functional Features of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
5 Evolution Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
5.2 General Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
5.2.1 Areas Of Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
5.2.2 Conferences, Workshops, etc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
5.2.3 Books . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
5.3 Populations in Evolution Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
5.3.1 (1 + 1)-ES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
5.3.2 (μ + 1)-ES. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
5.3.3 (μ + λ)-ES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
5.3.4 (μ, λ)-ES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
5.3.5 (μ/ρ, λ)-ES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
5.3.6 (μ/ρ + λ)-ES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
5.3.7 (μ′, λ′(μ, λ)γ)-ES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
5.4 One-Fifth Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
5.5 Differential Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
5.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
5.5.2 General Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
6 Evolutionary Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
6.2 General Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
6.2.1 Areas Of Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
6.2.2 Conferences, Workshops, etc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
6.2.3 Books . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

7 Learning Classifier Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
7.2 General Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
7.2.1 Areas Of Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
7.2.2 Conferences, Workshops, etc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
7.2.3 Books . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
7.3 The Basic Idea of Learning Classifier Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
7.3.1 A Small Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
7.3.2 Messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
7.3.3 Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
7.3.4 Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
7.3.5 Classifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
7.3.6 Non-Learning Classifier Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
7.3.7 Learning Classifier Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
7.3.8 The Bucket Brigade Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
7.3.9 Applying the Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
7.4 Families of Learning Classifier Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
8 Ant Colony Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
8.2 General Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
8.2.1 Areas Of Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
8.2.2 Conferences, Workshops, etc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
8.2.3 Journals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
8.2.4 Online Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
8.2.5 Books . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
8.3 River Formation Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
9 Particle Swarm Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
9.2 General Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
9.2.1 Areas Of Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
9.2.2 Online Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
9.2.3 Conferences, Workshops, etc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
9.2.4 Books . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
10 Hill Climbing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
10.2 General Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
10.2.1 Areas Of Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
10.3 Multi-Objective Hill Climbing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
10.4 Problems in Hill Climbing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
10.5 Hill Climbing with Random Restarts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
10.6 GRASP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
10.6.1 General Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
10.7 Raindrop Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
11 Random Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
11.2 General Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
11.2.1 Areas Of Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260

12 Simulated Annealing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
12.2 General Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
12.2.1 Areas Of Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
12.2.2 Books . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
12.3 Temperature Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
12.4 Multi-Objective Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
13 Extremal Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
13.1.1 Self-Organized Criticality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
13.1.2 The Bak-Sneppens model of Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
13.2 Extremal Optimization and Generalized Extremal Optimization . . . . . . . . . . . 270
13.3 General Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
13.3.1 Areas Of Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
14 Tabu Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
14.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
14.2 General Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
14.2.1 Areas Of Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
14.2.2 Books . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
14.3 Multi-Objective Tabu Search. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
15 Memetic and Hybrid Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
15.1 Memetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
15.2 Lamarckian Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
15.3 Baldwin Effect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
15.4 Summary on Lamarckian and Baldwinian Evolution . . . . . . . . . . . . . . . . . . . . . 280
15.5 General Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
15.5.1 Areas Of Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
15.5.2 Online Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
15.5.3 Books . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
16 Downhill Simplex (Nelder and Mead) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
16.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
16.2 General Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
16.2.1 Areas Of Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
16.2.2 Online Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
16.2.3 Books . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
16.3 The Downhill Simplex Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
16.4 Hybridizing with the Downhill Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
17 State Space Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
17.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
17.2 General Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
17.2.1 Areas Of Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
17.2.2 Books . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
17.3 Uninformed Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
17.3.1 Breadth-First Search. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
17.3.2 Depth-First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
17.3.3 Depth-limited Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
17.3.4 Iterative Deepening Depth-First Search . . . . . . . . . . . . . . . . . . . . . . . . . . 294
17.3.5 Random Walks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
17.4 Informed Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295

17.4.1 Greedy Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
17.4.2 A⋆ search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
17.4.3 Adaptive Walks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
18 Parallelization and Distribution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
18.1 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
18.2 Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
18.2.1 Client-Server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
18.2.2 Island Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
18.2.3 Mixed Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
18.3 Cellular Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
19 Maintaining the Optimal Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
19.1 Updating the Optimal Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
19.2 Obtaining Optimal Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
19.3 Pruning the Optimal Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
19.3.1 Pruning via Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
19.3.2 Adaptive Grid Archiving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
Part II Applications
20 Experimental Settings, Measures, and Evaluations . . . . . . . . . . . . . . . . . . . . . 315
20.1 Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
20.1.1 The Optimization Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
20.1.2 The Optimization Algorithm Applied . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
20.1.3 Other Run Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
20.2 Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
20.3 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
20.3.1 Simple Evaluation Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
20.3.2 Sophisticated Estimates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
20.4 Verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
20.4.1 Confidence Intervals or Statistical Tests . . . . . . . . . . . . . . . . . . . . . . . . . . 324
20.4.2 Factorial Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
21 Benchmarks and Toy Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
21.1 Real Problem Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
21.1.1 Single-Objective Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
21.1.2 Multi-Objective Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
21.1.3 Dynamic Fitness Landscapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
21.2 Binary Problem Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
21.2.1 Kauffman’s NK Fitness Landscapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
21.2.2 The p-Spin Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
21.2.3 The ND Family of Fitness Landscapes . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
21.2.4 The Royal Road . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
21.2.5 OneMax and BinInt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
21.2.6 Long Path Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
21.2.7 Tunable Model for Problematic Phenomena . . . . . . . . . . . . . . . . . . . . . . . 341
21.3 Genetic Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354
21.3.1 Artificial Ant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354
21.3.2 The Greatest Common Divisor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357

27 Set Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455
27.1 Set Membership . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455
27.2 Relations between Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455
27.3 Special Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
27.4 Operations on Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
27.5 Tuples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458
27.6 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459
27.7 Binary Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461
27.7.1 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462
27.7.2 Order Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463
27.7.3 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464
28 Stochastic Theory and Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465
28.1 General Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465
28.1.1 Books . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465
28.2 Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466
28.2.1 Probabily as defined by Bernoulli (1713) . . . . . . . . . . . . . . . . . . . . . . . . . 467
28.2.2 The Limiting Frequency Theory of von Mises . . . . . . . . . . . . . . . . . . . . . 468
28.2.3 The Axioms of Kolmogorov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469
28.2.4 Conditional Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469
28.2.5 Random Variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470
28.2.6 Cumulative Distribution Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470
28.2.7 Probability Mass Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
28.2.8 Probability Density Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472
28.3 Stochastic Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472
28.3.1 Count, Min, Max and Range . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472
28.3.2 Expected Value and Arithmetic Mean . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
28.3.3 Variance and Standard Deviation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474
28.3.4 Moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475
28.3.5 Skewness and Kurtosis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476
28.3.6 Median, Quantiles, and Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476
28.3.7 Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
28.3.8 The Law of Large Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
28.4 Some Discrete Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
28.4.1 Discrete Uniform Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
28.4.2 Poisson Distribution πλ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
28.4.3 Binomial Distribution B(n, p) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483
28.5 Some Continuous Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484
28.5.1 Continuous Uniform Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
28.5.2 Normal Distribution N
􀀀
μ, σ2


. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486
28.5.3 Exponential Distribution exp(λ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
28.5.4 Chi-square Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 490
28.5.5 Student’s t-Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494
28.6 Example – Throwing a Dice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
28.7 Estimation Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499
28.7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499
28.7.2 Likelihood and Maximum Likelihood Estimators . . . . . . . . . . . . . . . . . . 500
28.7.3 Confidence Intervals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503
28.7.4 Density Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
28.8 Statistical Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 508
28.8.1 Non-Parametric Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509
28.9 Generating Random Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526
28.9.1 Generating Pseudorandom Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526
28.9.2 Random Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528

28.9.3 Converting Random Numbers to other Distributions . . . . . . . . . . . . . . . 528
28.10List of Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532
28.10.1Gamma Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532
28.10.2Riemann Zeta Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532
29 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535
29.1 Distance Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537
29.1.1 Distance Measures for Strings of Equal Length . . . . . . . . . . . . . . . . . . . . 537
29.1.2 Distance Measures for Real-Valued Vectors . . . . . . . . . . . . . . . . . . . . . . . 537
29.1.3 Elements Representing a Cluster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539
29.1.4 Distance Measures Between Clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539
29.2 Clustering Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540
29.2.1 Cluster Error . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540
29.2.2 k-means Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540
29.2.3 nth Nearest Neighbor Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541
29.2.4 Linkage Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541
29.2.5 Leader Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543
30 Theoretical Computer Science . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547
30.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547
30.1.1 Algorithms and Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547
30.1.2 Properties of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549
30.1.3 Complexity of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 550
30.1.4 Randomized Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 552
30.2 Distributed Systems and Distributed Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 553
30.2.1 Network Topologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554
30.2.2 Some Architectures of Distributes Systems . . . . . . . . . . . . . . . . . . . . . . . . 556
30.3 Grammars and Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 561
30.3.1 Syntax and Formal Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562
30.3.2 Generative Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562
30.3.3 Derivation Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563
30.3.4 Backus-Naur Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564
30.3.5 Extended Backus-Naur Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565
30.3.6 Attribute Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565
30.3.7 Extended Attribute Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567
30.3.8 Adaptive Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568
30.3.9 Christiansen Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 569
30.3.10Tree-Adjoining Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 569
30.3.11S-expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571

免费下载网址：
http://www.it-weise.de/projects/book.pdf