计算智能导论

【实例截图】

【核心代码】

Contents
Page
Figures xxi
Tables xxiii
Algorithms xxvii
Preface xxix
Part I INTRODUCTION 1
1 Introduction to Computational Intelligence 3
1.1 Computational Intelligence Paradigms . . . . . . . . . . . . . . . . . . 4
1.1.1 Artificial Neural Networks . . . . . . . . . . . . . . . . . . . . . 5
1.1.2 Evolutionary Computation . . . . . . . . . . . . . . . . . . . . 8
1.1.3 Swarm Intelligence . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1.4 Artificial Immune Systems . . . . . . . . . . . . . . . . . . . . . 9
1.1.5 Fuzzy Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2 Short History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Part II ARTIFICIAL NEURAL NETWORKS 15
2 The Artificial Neuron 17
2.1 Calculating the Net Input Signal . . . . . . . . . . . . . . . . . . . . . 17
2.2 Activation Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Artificial Neuron Geometry . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Artificial Neuron Learning . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4.1 Augmented Vectors . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4.2 Gradient Descent Learning Rule . . . . . . . . . . . . . . . . . 24
2.4.3 Widrow-Hoff Learning Rule . . . . . . . . . . . . . . . . . . . . 25
2.4.4 Generalized Delta Learning Rule . . . . . . . . . . . . . . . . . 25
2.4.5 Error-Correction Learning Rule . . . . . . . . . . . . . . . . . . 25
2.5 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3 Supervised Learning Neural Networks 27
3.1 Neural Network Types . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.1 Feedforward Neural Networks . . . . . . . . . . . . . . . . . . . 28
3.1.2 Functional Link Neural Networks . . . . . . . . . . . . . . . . . 29
3.1.3 Product Unit Neural Networks . . . . . . . . . . . . . . . . . . 30
vii
viii CONTENTS
3.1.4 Simple Recurrent Neural Networks . . . . . . . . . . . . . . . . 32
3.1.5 Time-Delay Neural Networks . . . . . . . . . . . . . . . . . . . 34
3.1.6 Cascade Networks . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2 Supervised Learning Rules . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.1 The Supervised Learning Problem . . . . . . . . . . . . . . . . 36
3.2.2 Gradient Descent Optimization . . . . . . . . . . . . . . . . . . 38
3.2.3 Scaled Conjugate Gradient . . . . . . . . . . . . . . . . . . . . 45
3.2.4 LeapFrog Optimization . . . . . . . . . . . . . . . . . . . . . . 49
3.2.5 Particle Swarm Optimization . . . . . . . . . . . . . . . . . . . 49
3.3 Functioning of Hidden Units . . . . . . . . . . . . . . . . . . . . . . . . 49
3.4 Ensemble Neural Networks . . . . . . . . . . . . . . . . . . . . . . . . 51
3.5 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4 Unsupervised Learning Neural Networks 55
4.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2 Hebbian Learning Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.3 Principal Component Learning Rule . . . . . . . . . . . . . . . . . . . 58
4.4 Learning Vector Quantizer-I . . . . . . . . . . . . . . . . . . . . . . . . 59
4.5 Self-Organizing Feature Maps . . . . . . . . . . . . . . . . . . . . . . . 62
4.5.1 Stochastic Training Rule . . . . . . . . . . . . . . . . . . . . . . 62
4.5.2 Batch Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.5.3 Growing SOM . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.5.4 Improving Convergence Speed . . . . . . . . . . . . . . . . . . . 67
4.5.5 Clustering and Visualization . . . . . . . . . . . . . . . . . . . 69
4.5.6 Using SOM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.6 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5 Radial Basis Function Networks 73
5.1 Learning Vector Quantizer-II . . . . . . . . . . . . . . . . . . . . . . . 73
5.2 Radial Basis Function Neural Networks . . . . . . . . . . . . . . . . . 73
5.2.1 Radial Basis Function Network Architecture . . . . . . . . . . . 74
5.2.2 Radial Basis Functions . . . . . . . . . . . . . . . . . . . . . . . 75
5.2.3 Training Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 76
5.2.4 Radial Basis Function Network Variations . . . . . . . . . . . . 80
5.3 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6 Reinforcement Learning 83
6.1 Learning through Awards . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.2 Model-Free Reinforcement Learning Model . . . . . . . . . . . . . . . 86
6.2.1 Temporal Difference Learning . . . . . . . . . . . . . . . . . . . 86
6.2.2 Q-Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
CONTENTS ix
6.3 Neural Networks and Reinforcement Learning . . . . . . . . . . . . . . 87
6.3.1 RPROP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.3.2 Gradient Descent Reinforcement Learning . . . . . . . . . . . . 88
6.3.3 Connectionist Q-Learning . . . . . . . . . . . . . . . . . . . . . 89
6.4 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7 Performance Issues (Supervised Learning) 93
7.1 Performance Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.1.1 Accuracy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.1.2 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
7.1.3 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
7.2 Analysis of Performance . . . . . . . . . . . . . . . . . . . . . . . . . . 98
7.3 Performance Factors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
7.3.1 Data Preparation . . . . . . . . . . . . . . . . . . . . . . . . . . 99
7.3.2 Weight Initialization . . . . . . . . . . . . . . . . . . . . . . . . 106
7.3.3 Learning Rate and Momentum . . . . . . . . . . . . . . . . . . 107
7.3.4 Optimization Method . . . . . . . . . . . . . . . . . . . . . . . 109
7.3.5 Architecture Selection . . . . . . . . . . . . . . . . . . . . . . . 109
7.3.6 Adaptive Activation Functions . . . . . . . . . . . . . . . . . . 115
7.3.7 Active Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
7.4 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
Part III EVOLUTIONARY COMPUTATION 125
8 Introduction to Evolutionary Computation 127
8.1 Generic Evolutionary Algorithm . . . . . . . . . . . . . . . . . . . . . 128
8.2 Representation – The Chromosome . . . . . . . . . . . . . . . . . . . . 129
8.3 Initial Population . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
8.4 Fitness Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
8.5 Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
8.5.1 Selective Pressure . . . . . . . . . . . . . . . . . . . . . . . . . 135
8.5.2 Random Selection . . . . . . . . . . . . . . . . . . . . . . . . . 135
8.5.3 Proportional Selection . . . . . . . . . . . . . . . . . . . . . . . 135
8.5.4 Tournament Selection . . . . . . . . . . . . . . . . . . . . . . . 137
8.5.5 Rank-Based Selection . . . . . . . . . . . . . . . . . . . . . . . 137
8.5.6 Boltzmann Selection . . . . . . . . . . . . . . . . . . . . . . . . 138
8.5.7 (µ

, λ)-Selection . . . . . . . . . . . . . . . . . . . . . . . . . . 139
8.5.8 Elitism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
8.5.9 Hall of Fame . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
8.6 Reproduction Operators . . . . . . . . . . . . . . . . . . . . . . . . . . 139
x CONTENTS
8.7 Stopping Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
8.8 Evolutionary Computation versus Classical Optimization . . . . . . . 141
8.9 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
9 Genetic Algorithms 143
9.1 Canonical Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . 143
9.2 Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
9.2.1 Binary Representations . . . . . . . . . . . . . . . . . . . . . . 145
9.2.2 Floating-Point Representation . . . . . . . . . . . . . . . . . . . 146
9.3 Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
9.3.1 Binary Representations . . . . . . . . . . . . . . . . . . . . . . 154
9.3.2 Floating-Point Representations . . . . . . . . . . . . . . . . . . 155
9.3.3 Macromutation Operator – Headless Chicken . . . . . . . . . . 156
9.4 Control Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
9.5 Genetic Algorithm Variants . . . . . . . . . . . . . . . . . . . . . . . . 157
9.5.1 Generation Gap Methods . . . . . . . . . . . . . . . . . . . . . 158
9.5.2 Messy Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . 159
9.5.3 Interactive Evolution . . . . . . . . . . . . . . . . . . . . . . . . 161
9.5.4 Island Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . 162
9.6 Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
9.6.1 Niching Genetic Algorithms . . . . . . . . . . . . . . . . . . . . 165
9.6.2 Constraint Handling . . . . . . . . . . . . . . . . . . . . . . . . 169
9.6.3 Multi-Objective Optimization . . . . . . . . . . . . . . . . . . . 170
9.6.4 Dynamic Environments . . . . . . . . . . . . . . . . . . . . . . 173
9.7 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
9.8 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
10 Genetic Programming 177
10.1 Tree-Based Representation . . . . . . . . . . . . . . . . . . . . . . . . . 177
10.2 Initial Population . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
10.3 Fitness Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
10.4 Crossover Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
10.5 Mutation Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
10.6 Building Block Genetic Programming . . . . . . . . . . . . . . . . . . 184
10.7 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
10.8 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
11 Evolutionary Programming 187
11.1 Basic Evolutionary Programming . . . . . . . . . . . . . . . . . . . . . 187
11.2 Evolutionary Programming Operators . . . . . . . . . . . . . . . . . . 189
11.2.1 Mutation Operators . . . . . . . . . . . . . . . . . . . . . . . . 189
CONTENTS xi
11.2.2 Selection Operators . . . . . . . . . . . . . . . . . . . . . . . . 193
11.3 Strategy Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
11.3.1 Static Strategy Parameters . . . . . . . . . . . . . . . . . . . . 195
11.3.2 Dynamic Strategies . . . . . . . . . . . . . . . . . . . . . . . . . 195
11.3.3 Self-Adaptation . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
11.4 Evolutionary Programming Implementations . . . . . . . . . . . . . . 200
11.4.1 Classical Evolutionary Programming . . . . . . . . . . . . . . . 200
11.4.2 Fast Evolutionary Programming . . . . . . . . . . . . . . . . . 201
11.4.3 Exponential Evolutionary Programming . . . . . . . . . . . . . 201
11.4.4 Accelerated Evolutionary Programming . . . . . . . . . . . . . 201
11.4.5 Momentum Evolutionary Programming . . . . . . . . . . . . . 202
11.4.6 Evolutionary Programming with Local Search . . . . . . . . . . 203
11.4.7 Evolutionary Programming with Extinction . . . . . . . . . . . 203
11.4.8 Hybrid with Particle Swarm Optimization . . . . . . . . . . . . 204
11.5 Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
11.5.1 Constraint Handling Approaches . . . . . . . . . . . . . . . . . 206
11.5.2 Multi-Objective Optimization and Niching . . . . . . . . . . . 206
11.5.3 Dynamic Environments . . . . . . . . . . . . . . . . . . . . . . 206
11.6 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
11.6.1 Finite-State Machines . . . . . . . . . . . . . . . . . . . . . . . 207
11.6.2 Function Optimization . . . . . . . . . . . . . . . . . . . . . . . 208
11.6.3 Training Neural Networks . . . . . . . . . . . . . . . . . . . . . 209
11.6.4 Real-World Applications . . . . . . . . . . . . . . . . . . . . . . 210
11.7 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
12 Evolution Strategies 213
12.1 (1 1)-ES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
12.2 Generic Evolution Strategy Algorithm . . . . . . . . . . . . . . . . . . 215
12.3 Strategy Parameters and Self-Adaptation . . . . . . . . . . . . . . . . 216
12.3.1 Strategy Parameter Types . . . . . . . . . . . . . . . . . . . . . 216
12.3.2 Strategy Parameter Variants . . . . . . . . . . . . . . . . . . . 218
12.3.3 Self-Adaptation Strategies . . . . . . . . . . . . . . . . . . . . . 219
12.4 Evolution Strategy Operators . . . . . . . . . . . . . . . . . . . . . . . 221
12.4.1 Selection Operators . . . . . . . . . . . . . . . . . . . . . . . . 221
12.4.2 Crossover Operators . . . . . . . . . . . . . . . . . . . . . . . . 222
12.4.3 Mutation Operators . . . . . . . . . . . . . . . . . . . . . . . . 224
12.5 Evolution Strategy Variants . . . . . . . . . . . . . . . . . . . . . . . . 226
12.5.1 Polar Evolution Strategies . . . . . . . . . . . . . . . . . . . . . 226
12.5.2 Evolution Strategies with Directed Variation . . . . . . . . . . 227
xii CONTENTS
12.5.3 Incremental Evolution Strategies . . . . . . . . . . . . . . . . . 228
12.5.4 Surrogate Evolution Strategy . . . . . . . . . . . . . . . . . . . 229
12.6 Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
12.6.1 Constraint Handling Approaches . . . . . . . . . . . . . . . . . 229
12.6.2 Multi-Objective Optimization . . . . . . . . . . . . . . . . . . . 230
12.6.3 Dynamic and Noisy Environments . . . . . . . . . . . . . . . . 233
12.6.4 Niching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
12.7 Applications of Evolution Strategies . . . . . . . . . . . . . . . . . . . 235
12.8 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
13 Differential Evolution 237
13.1 Basic Differential Evolution . . . . . . . . . . . . . . . . . . . . . . . . 237
13.1.1 Difference Vectors . . . . . . . . . . . . . . . . . . . . . . . . . 238
13.1.2 Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
13.1.3 Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
13.1.4 Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
13.1.5 General Differential Evolution Algorithm . . . . . . . . . . . . 241
13.1.6 Control Parameters . . . . . . . . . . . . . . . . . . . . . . . . 241
13.1.7 Geometrical Illustration . . . . . . . . . . . . . . . . . . . . . . 242
13.2 DE/x/y/z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
13.3 Variations to Basic Differential Evolution . . . . . . . . . . . . . . . . 245
13.3.1 Hybrid Differential Evolution Strategies . . . . . . . . . . . . . 245
13.3.2 Population-Based Differential Evolution . . . . . . . . . . . . . 250
13.3.3 Self-Adaptive Differential Evolution . . . . . . . . . . . . . . . 250
13.4 Differential Evolution for Discrete-Valued Problems . . . . . . . . . . . 252
13.4.1 Angle Modulated Differential Evolution . . . . . . . . . . . . . 253
13.4.2 Binary Differential Evolution . . . . . . . . . . . . . . . . . . . 254
13.5 Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
13.5.1 Constraint Handling Approaches . . . . . . . . . . . . . . . . . 256
13.5.2 Multi-Objective Optimization . . . . . . . . . . . . . . . . . . . 256
13.5.3 Dynamic Environments . . . . . . . . . . . . . . . . . . . . . . 257
13.6 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
13.7 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
14 Cultural Algorithms 261
14.1 Culture and Artificial Culture . . . . . . . . . . . . . . . . . . . . . . . 261
14.2 Basic Cultural Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 262
14.3 Belief Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
14.3.1 Knowledge Components . . . . . . . . . . . . . . . . . . . . . . 264
14.3.2 Acceptance Functions . . . . . . . . . . . . . . . . . . . . . . . 265
CONTENTS xiii
14.3.3 Adjusting the Belief Space . . . . . . . . . . . . . . . . . . . . . 266
14.3.4 Influence Functions . . . . . . . . . . . . . . . . . . . . . . . . . 267
14.4 Fuzzy Cultural Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 268
14.4.1 Fuzzy Acceptance Function . . . . . . . . . . . . . . . . . . . . 269
14.4.2 Fuzzified Belief Space . . . . . . . . . . . . . . . . . . . . . . . 269
14.4.3 Fuzzy Influence Function . . . . . . . . . . . . . . . . . . . . . 270
14.5 Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
14.5.1 Constraint Handling . . . . . . . . . . . . . . . . . . . . . . . . 271
14.5.2 Multi-Objective Optimization . . . . . . . . . . . . . . . . . . . 272
14.5.3 Dynamic Environments . . . . . . . . . . . . . . . . . . . . . . 273
14.6 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
14.7 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
15 Coevolution 275
15.1 Coevolution Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
15.2 Competitive Coevolution . . . . . . . . . . . . . . . . . . . . . . . . . . 276
15.2.1 Competitive Fitness . . . . . . . . . . . . . . . . . . . . . . . . 277
15.2.2 Generic Competitive Coevolutionary Algorithm . . . . . . . . . 279
15.2.3 Applications of Competitive Coevolution . . . . . . . . . . . . 280
15.3 Cooperative Coevolution . . . . . . . . . . . . . . . . . . . . . . . . . . 281
15.4 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
Part IV COMPUTATIONAL SWARM INTELLIGENCE 285
16 Particle Swarm Optimization 289
16.1 Basic Particle Swarm Optimization . . . . . . . . . . . . . . . . . . . . 289
16.1.1 Global Best PSO . . . . . . . . . . . . . . . . . . . . . . . . . . 290
16.1.2 Local Best PSO . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
16.1.3 gbest versus lbest PSO . . . . . . . . . . . . . . . . . . . . . . . 292
16.1.4 Velocity Components . . . . . . . . . . . . . . . . . . . . . . . . 293
16.1.5 Geometric Illustration . . . . . . . . . . . . . . . . . . . . . . . 294
16.1.6 Algorithm Aspects . . . . . . . . . . . . . . . . . . . . . . . . . 296
16.2 Social Network Structures . . . . . . . . . . . . . . . . . . . . . . . . . 300
16.3 Basic Variations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
16.3.1 Velocity Clamping . . . . . . . . . . . . . . . . . . . . . . . . . 303
16.3.2 Inertia Weight . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
16.3.3 Constriction Coefficient . . . . . . . . . . . . . . . . . . . . . . 309
16.3.4 Synchronous versus Asynchronous Updates . . . . . . . . . . . 310
16.3.5 Velocity Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
16.4 Basic PSO Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . 312
xiv CONTENTS
16.5 Single-Solution Particle Swarm Optimization . . . . . . . . . . . . . . 314
16.5.1 Guaranteed Convergence PSO . . . . . . . . . . . . . . . . . . 316
16.5.2 Social-Based Particle Swarm Optimization . . . . . . . . . . . . 317
16.5.3 Hybrid Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 321
16.5.4 Sub-Swarm Based PSO . . . . . . . . . . . . . . . . . . . . . . 326
16.5.5 Multi-Start PSO Algorithms . . . . . . . . . . . . . . . . . . . 333
16.5.6 Repelling Methods . . . . . . . . . . . . . . . . . . . . . . . . . 337
16.5.7 Binary PSO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
16.6 Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
16.6.1 Constraint Handling Approaches . . . . . . . . . . . . . . . . . 342
16.6.2 Multi-Objective Optimization . . . . . . . . . . . . . . . . . . . 343
16.6.3 Dynamic Environments . . . . . . . . . . . . . . . . . . . . . . 346
16.6.4 Niching PSO . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
16.7 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354
16.7.1 Neural Networks . . . . . . . . . . . . . . . . . . . . . . . . . . 354
16.7.2 Architecture Selection . . . . . . . . . . . . . . . . . . . . . . . 356
16.7.3 Game Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
16.8 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
17 Ant Algorithms 359
17.1 Ant Colony Optimization Meta-Heuristic . . . . . . . . . . . . . . . . 360
17.1.1 Foraging Behavior of Ants . . . . . . . . . . . . . . . . . . . . . 360
17.1.2 Stigmergy and Artificial Pheromone . . . . . . . . . . . . . . . 363
17.1.3 Simple Ant Colony Optimization . . . . . . . . . . . . . . . . . 364
17.1.4 Ant System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
17.1.5 Ant Colony System . . . . . . . . . . . . . . . . . . . . . . . . . 372
17.1.6 Max-Min Ant System . . . . . . . . . . . . . . . . . . . . . . . 375
17.1.7 Ant-Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
17.1.8 Fast Ant System . . . . . . . . . . . . . . . . . . . . . . . . . . 379
17.1.9 Antabu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380
17.1.10AS-rank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380
17.1.11ANTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
17.1.12Parameter Settings . . . . . . . . . . . . . . . . . . . . . . . . . 383
17.2 Cemetery Organization and Brood Care . . . . . . . . . . . . . . . . . 384
17.2.1 Basic Ant Colony Clustering Model . . . . . . . . . . . . . . . 385
17.2.2 Generalized Ant Colony Clustering Model . . . . . . . . . . . . 386
17.2.3 Minimal Model for Ant Clustering . . . . . . . . . . . . . . . . 391
17.3 Division of Labor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
17.3.1 Division of Labor in Insect Colonies . . . . . . . . . . . . . . . 392
CONTENTS xv
17.3.2 Task Allocation Based on Response Thresholds . . . . . . . . . 393
17.3.3 Adaptive Task Allocation and Specialization . . . . . . . . . . 395
17.4 Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396
17.4.1 Continuous Ant Colony Optimization . . . . . . . . . . . . . . 396
17.4.2 Multi-Objective Optimization . . . . . . . . . . . . . . . . . . . 398
17.4.3 Dynamic Environments . . . . . . . . . . . . . . . . . . . . . . 402
17.5 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405
17.5.1 Traveling Salesman Problem . . . . . . . . . . . . . . . . . . . 406
17.5.2 Quadratic Assignment Problem . . . . . . . . . . . . . . . . . . 407
17.5.3 Other Applications . . . . . . . . . . . . . . . . . . . . . . . . . 411
17.6 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
Part V ARTIFICIAL IMMUNE SYSTEMS 413
18 Natural Immune System 415
18.1 Classical View . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
18.2 Antibodies and Antigens . . . . . . . . . . . . . . . . . . . . . . . . . . 416
18.3 The White Cells . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416
18.3.1 The Lymphocytes . . . . . . . . . . . . . . . . . . . . . . . . . 417
18.4 Immunity Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421
18.5 Learning the Antigen Structure . . . . . . . . . . . . . . . . . . . . . . 421
18.6 The Network Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422
18.7 The Danger Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422
18.8 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424
19 Artificial Immune Models 425
19.1 Artificial Immune System Algorithm . . . . . . . . . . . . . . . . . . . 426
19.2 Classical View Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
19.2.1 Negative Selection . . . . . . . . . . . . . . . . . . . . . . . . . 428
19.2.2 Evolutionary Approaches . . . . . . . . . . . . . . . . . . . . . 429
19.3 Clonal Selection Theory Models . . . . . . . . . . . . . . . . . . . . . . 431
19.3.1 CLONALG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
19.3.2 Dynamic Clonal Selection . . . . . . . . . . . . . . . . . . . . . 433
19.3.3 Multi-Layered AIS . . . . . . . . . . . . . . . . . . . . . . . . . 433
19.4 Network Theory Models . . . . . . . . . . . . . . . . . . . . . . . . . . 436
19.4.1 Artificial Immune Network . . . . . . . . . . . . . . . . . . . . 436
19.4.2 Self Stabilizing AIS . . . . . . . . . . . . . . . . . . . . . . . . . 438
19.4.3 Enhanced Artificial Immune Network . . . . . . . . . . . . . . 440
19.4.4 Dynamic Weighted B-Cell AIS . . . . . . . . . . . . . . . . . . 441
19.4.5 Adapted Artificial Immune Network . . . . . . . . . . . . . . . 442
xvi CONTENTS
19.4.6 aiNet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442
19.5 Danger Theory Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
19.5.1 Mobile Ad-Hoc Networks . . . . . . . . . . . . . . . . . . . . . 445
19.5.2 An Adaptive Mailbox . . . . . . . . . . . . . . . . . . . . . . . 446
19.5.3 Intrusion Detection . . . . . . . . . . . . . . . . . . . . . . . . . 448
19.6 Applications and Other AIS models . . . . . . . . . . . . . . . . . . . 448
19.7 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448
Part VI FUZZY SYSTEMS 451
20 Fuzzy Sets 453
20.1 Formal Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454
20.2 Membership Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 454
20.3 Fuzzy Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
20.4 Fuzzy Set Characteristics . . . . . . . . . . . . . . . . . . . . . . . . . 459
20.5 Fuzziness and Probability . . . . . . . . . . . . . . . . . . . . . . . . . 462
20.6 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463
21 Fuzzy Logic and Reasoning 465
21.1 Fuzzy Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465
21.1.1 Linguistics Variables and Hedges . . . . . . . . . . . . . . . . . 466
21.1.2 Fuzzy Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467
21.2 Fuzzy Inferencing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468
21.2.1 Fuzzification . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469
21.2.2 Inferencing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470
21.2.3 Defuzzification . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
21.3 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472
22 Fuzzy Controllers 475
22.1 Components of Fuzzy Controllers . . . . . . . . . . . . . . . . . . . . . 475
22.2 Fuzzy Controller Types . . . . . . . . . . . . . . . . . . . . . . . . . . 477
22.2.1 Table-Based Controller . . . . . . . . . . . . . . . . . . . . . . . 477
22.2.2 Mamdani Fuzzy Controller . . . . . . . . . . . . . . . . . . . . 477
22.2.3 Takagi-Sugeno Controller . . . . . . . . . . . . . . . . . . . . . 478
22.3 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
23 Rough Sets 481
23.1 Concept of Discernibility . . . . . . . . . . . . . . . . . . . . . . . . . . 482
23.2 Vagueness in Rough Sets . . . . . . . . . . . . . . . . . . . . . . . . . . 483
23.3 Uncertainty in Rough Sets . . . . . . . . . . . . . . . . . . . . . . . . . 484
23.4 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
CONTENTS xvii
References 487
A Optimization Theory 551
A.1 Basic Ingredients of Optimization Problems . . . . . . . . . . . . . . . 551
A.2 Optimization Problem Classifications . . . . . . . . . . . . . . . . . . . 552
A.3 Optima Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553
A.4 Optimization Method Classes . . . . . . . . . . . . . . . . . . . . . . . 554
A.5 Unconstrained Optimization . . . . . . . . . . . . . . . . . . . . . . . . 555
A.5.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . 555
A.5.2 Optimization Algorithms . . . . . . . . . . . . . . . . . . . . . 555
A.5.3 Example Benchmark Problems . . . . . . . . . . . . . . . . . . 559
A.6 Constrained Optimization . . . . . . . . . . . . . . . . . . . . . . . . . 560
A.6.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . 560
A.6.2 Constraint Handling Methods . . . . . . . . . . . . . . . . . . . 561
A.6.3 Example Benchmark Problems . . . . . . . . . . . . . . . . . . 566
A.7 Multi-Solution Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 567
A.7.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . 568
A.7.2 Niching Algorithm Categories . . . . . . . . . . . . . . . . . . . 568
A.7.3 Example Benchmark Problems . . . . . . . . . . . . . . . . . . 569
A.8 Multi-Objective Optimization . . . . . . . . . . . . . . . . . . . . . . . 570
A.8.1 Multi-objective Problem . . . . . . . . . . . . . . . . . . . . . . 570
A.8.2 Weighted Aggregation Methods . . . . . . . . . . . . . . . . . . 571
A.8.3 Pareto-Optimality . . . . . . . . . . . . . . . . . . . . . . . . . 572
A.9 Dynamic Optimization Problems . . . . . . . . . . . . . . . . . . . . . 575
A.9.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576
A.9.2 Dynamic Environment Types . . . . . . . . . . . . . . . . . . . 576
A.9.3 Example Benchmark Problems . . . . . . . . . . . . . . . . . . 578
Index 581
List of Figures
Figure Page
1.1 Computational Intelligence Paradigms . . . . . . . . . . . . . . . . . . 5
1.2 A Biological Neuron . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 An Artificial Neuron . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 An Artificial Neural Network . . . . . . . . . . . . . . . . . . . . . . . 7
2.1 An Artificial Neuron . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Activation Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3 Artificial Neuron Boundary . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4 Linear Separable Boolean Perceptrons . . . . . . . . . . . . . . . . . . 22
2.5 XOR Decision Boundaries . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.6 Gradient Descent Illustrated . . . . . . . . . . . . . . . . . . . . . . . . 24
3.1 Feedforward Neural Network . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 Functional Link Neural Network . . . . . . . . . . . . . . . . . . . . . 29
3.3 Elman Simple Recurrent Neural Network . . . . . . . . . . . . . . . . 32
3.4 Jordan Simple Recurrent Neural Network . . . . . . . . . . . . . . . . 33
3.5 A Single Time-Delay Neuron . . . . . . . . . . . . . . . . . . . . . . . 34
3.6 Cascade Neural Network . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.7 Product Unit Neural Network Search Space for f(z) = z 3 . . . . . . . 44
3.8 Feedforward Neural Network Classification Boundary Illustration . . . 51
3.9 Hidden Unit Functioning for Function Approximation . . . . . . . . . 52
3.10 Ensemble Neural Network . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.1 Unsupervised Neural Network . . . . . . . . . . . . . . . . . . . . . . . 56
4.2 Learning Vector Quantizer to Illustrate Clustering . . . . . . . . . . . 60
4.3 Self-organizing Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.4 Visualization of SOM Clusters for Iris Classification . . . . . . . . . . 70
5.1 Radial Basis Function Neural Network . . . . . . . . . . . . . . . . . . 74
6.1 Reinforcement Learning Problem . . . . . . . . . . . . . . . . . . . . . 84
7.1 Illustration of Overfitting . . . . . . . . . . . . . . . . . . . . . . . . . 96
7.2 Effect of Outliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
7.3 Sum Squared Error Objective Function . . . . . . . . . . . . . . . . . 101
7.4 Huber Objective Function . . . . . . . . . . . . . . . . . . . . . . . . . 102
7.5 Effect of Learning Rate . . . . . . . . . . . . . . . . . . . . . . . . . . 108
7.6 Adaptive Sigmoid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.7 Passive vs Active Learning . . . . . . . . . . . . . . . . . . . . . . . . . 119
8.1 Hamming Distance for Binary and Gray Coding . . . . . . . . . . . . 131
9.1 Crossover Operators for Binary Representations . . . . . . . . . . . . . 147
xix
xx LIST OF FIGURES
9.2 Illustration of Multi-parent Center of Mass Crossover Operators . . . . 151
9.3 Diagonal Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
9.4 Mutation Operators for Binary Representations . . . . . . . . . . . . . 155
9.5 An Island GA Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
10.1 Tree-Representation of XOR . . . . . . . . . . . . . . . . . . . . . . . . 178
10.2 Tree-Representation for Mathematical Expressions . . . . . . . . . . . 179
10.3 Genetic Programming Crossover . . . . . . . . . . . . . . . . . . . . . 181
10.4 Genetic Programming Mutation Operators . . . . . . . . . . . . . . . 183
11.1 Finite-State Machine [278] . . . . . . . . . . . . . . . . . . . . . . . . . 208
12.1 Illustration of Mutation Distributions for ES . . . . . . . . . . . . . . 219
12.2 Directed Mutation Operator for ES . . . . . . . . . . . . . . . . . . . . 225
12.3 Biased Mutation for Evolution Strategies . . . . . . . . . . . . . . . . 230
13.1 Differential Evolution Mutation and Crossover Illustrated . . . . . . . 243
13.2 Angle Modulation Illustrated . . . . . . . . . . . . . . . . . . . . . . . 254
14.1 Illustration of Population and Belief Spaces of Cultural Algorithms . . 263
14.2 Illustration of Belief Cells . . . . . . . . . . . . . . . . . . . . . . . . . 272
16.1 Geometrical Illustration of Velocity and Position Updates . . . . . . . 294
16.2 Multi-particle gbest PSO Illustration . . . . . . . . . . . . . . . . . . . 295
16.3 Illustration of lbest PSO . . . . . . . . . . . . . . . . . . . . . . . . . . 296
16.4 Example Social Network Structures . . . . . . . . . . . . . . . . . . . . 302
16.5 Effects of Velocity Clamping . . . . . . . . . . . . . . . . . . . . . . . . 305
16.6 Stochastic Particle Trajectory for w = 0.9 and c 1 = c 2 = 2.0 . . . . . . 315
17.1 Binary Bridge Experiment . . . . . . . . . . . . . . . . . . . . . . . . . 361
17.2 Shortest Path Selection by Forager Ants . . . . . . . . . . . . . . . . . 362
17.3 Graph for Shortest Path Problems . . . . . . . . . . . . . . . . . . . . 365
17.4 2-opt and 3-opt Local Search Heuristic . . . . . . . . . . . . . . . . . . 408
18.1 Antigen-Antibody-Complex . . . . . . . . . . . . . . . . . . . . . . . . 417
18.2 White Cell Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
18.3 Life Cycle of A Lymphocyte . . . . . . . . . . . . . . . . . . . . . . . . 418
18.4 B-Cell Develops into Plasma Cell, Producing Antibodies . . . . . . . . 419
18.5 Macrophage and NKTC . . . . . . . . . . . . . . . . . . . . . . . . . . 420
18.6 Co-Stimulation of T-Cell by an APC . . . . . . . . . . . . . . . . . . . 423
19.1 r-Continuous Matching Rule . . . . . . . . . . . . . . . . . . . . . . . 428
19.2 Adapted Negative Selection . . . . . . . . . . . . . . . . . . . . . . . . 430
20.1 Illustration of Membership Function for Two-Valued Sets . . . . . . . 455
20.2 Illustration of tall Membership Function . . . . . . . . . . . . . . . . . 455
20.3 Example Membership Functions for Fuzzy Sets . . . . . . . . . . . . . 458
20.4 Illustration of Fuzzy Set Containment . . . . . . . . . . . . . . . . . . 458
20.5 Illustration of Fuzzy Operators . . . . . . . . . . . . . . . . . . . . . . 460
LIST OF FIGURES xxi
20.6 Membership Functions for Assignments 1 and 2 . . . . . . . . . . . . . 463
21.1 Fuzzy Rule-Based Reasoning System . . . . . . . . . . . . . . . . . . . 468
21.2 Interpreting a Fuzzy Rule . . . . . . . . . . . . . . . . . . . . . . . . . 469
21.3 Defuzzification Methods for Centroid Calculation . . . . . . . . . . . . 473
21.4 Membership Functions for Assignments 2 and 3 . . . . . . . . . . . . . 474
22.1 A Fuzzy Controller . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476
23.1 Rough Set Illustration . . . . . . . . . . . . . . . . . . . . . . . . . . . 481
A.1 Types of Optima for Unconstrained Problems . . . . . . . . . . . . . . 553
A.2 Problem with Multiple Global Optima, with f(x) = sin 6 (5πx) . . . . . 554
A.3 Constrained Problem Illustration . . . . . . . . . . . . . . . . . . . . . 562
A.4 Illustration of the Effect of Penalty Functions . . . . . . . . . . . . . . 564
A.5 Illustration of Dominance . . . . . . . . . . . . . . . . . . . . . . . . . 572
A.6 Example Pareto-Optimal Fronts . . . . . . . . . . . . . . . . . . . . . . 574
A.7 Dynamic Parabola Objective Function . . . . . . . . . . . . . . . . . . 577
A.8 Dynamic Objective Function . . . . . . . . . . . . . . . . . . . . . . . 579