Machine Learning plus Intelligent Optimization.pdf

【实例简介】机器学习与智能优化

【实例截图】

【实例目录】

Contents
1 Introduction 1
1.1 Learning and Intelligent Optimization: a prairie fire . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Searching for gold and for partners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 All you need is data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Beyond traditional business intelligence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5 Implementing LION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.6 Teaching and learning in Internet times . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.7 A “hands on” community approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Lazy learning: nearest neighbors 9
2.1 Nearest Neighbors Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 From brute-force to smarter lookups: Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Locality-sensitive Hashing (LSH) and approximated nearest neighbors . . . . . . . . . . . . . . . . . 15
2.4 Space-partitioning data structure: k-d trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 Learning requires a method 21
3.1 Learning from labeled examples: minimization and generalization . . . . . . . . . . . . . . . . . . . 23
3.2 Learn, validate, test! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3 Errors of different kinds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
I Supervised learning 33
4 Linear models 35
4.1 Linear regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.2 A trick for nonlinear dependencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3 Linear models for classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.4 How does the brain work? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.5 Why are linear models popular and successful? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.6 Minimizing the sum of squared errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.7 Numerical instabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5 Mastering generalized linear least-squares 47
5.1 Goodness of fit and and chi-square . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.2 Least squares and maximum likelihood estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.2.1 Hypothesis testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.2.2 Cross-validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.3 Bootstrapping your confidence (error bars) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
iii
iv CONTENTS
6 Rules, decision trees, and forests 59
6.1 Building decision trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.2 Democracy and decision forests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
7 Ranking and selecting features 69
7.1 Selecting features: the context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
7.2 Correlation coefficient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
7.3 Correlation ratio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
7.4 Chi-square test to deny statistical independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
7.5 Heuristic relevance based on nearest neighbors: Relief . . . . . . . . . . . . . . . . . . . . . . . . . 74
7.6 Entropy and mutual information (MIFS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.6.1 Entropy and Mutual Information for continuous variables . . . . . . . . . . . . . . . . . . . . 78
8 Models based on matrix factorization 81
8.1 Combining ratings by similar users . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
8.2 Models based on matrix factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
8.2.1 A more refined model: adding biases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
9 Specific nonlinear models 87
9.1 Logistic regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
9.2 Locally-Weighted Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
9.2.1 Bayesian LWR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
9.3 LASSO to shrink and select inputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
10 Neural networks: multi-layer perceptrons 95
10.1 Multilayer Perceptrons (MLP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
10.2 Learning via backpropagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
10.2.1 Batch and “Bold Driver” Backpropagation . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
10.2.2 On-Line or stochastic backpropagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
10.2.3 Advanced optimization for MLP training . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
11 Deep and convolutional networks 103
11.1 Deep neural networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
11.1.1 Auto-encoders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
11.1.2 Random noise, dropout and curriculum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
11.2 Local receptive fields and convolutional networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
12 Statistical Learning Theory and Support Vector Machines (SVM) 115
12.1 Empirical risk minimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
12.1.1 Linearly separable problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
12.1.2 Non-separable problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
12.1.3 Nonlinear hypotheses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
12.1.4 Support Vectors for regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
13 Least-squares and robust kernel machines 125
13.1 Least-Squares Support Vector Machine Classifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
13.2 Robust weighted least square SVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
13.3 Recovering sparsity by pruning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
13.4 Algorithmic improvements: tuned QP, primal versions, no offset . . . . . . . . . . . . . . . . . . . . 130
CONTENTS v
14 Structured Machine Learning, Text and Web Mining 133
14.1 Bayesian networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
14.2 Markov networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
14.3 Inductive logic programming (ILP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
14.4 Text and web mining: the context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
14.5 Retrieving and organizing information from the web . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
14.5.1 Crawling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
14.5.2 Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
14.6 Information retrieval and ranking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
14.6.1 From Documents to Vectors: the Vector-Space Model . . . . . . . . . . . . . . . . . . . . . . 145
14.6.2 Relevance feedback . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
14.6.3 More complex similarity measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
14.7 Using the hyperlinks to rank web pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
14.8 Identifying hubs and authorities: HITS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
14.9 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
15 Democracy in machine learning 157
15.1 Stacking and blending . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
15.2 Diversity by manipulating examples: bagging and boosting . . . . . . . . . . . . . . . . . . . . . . . 160
15.3 Diversity by manipulating features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
15.4 Diversity by manipulating outputs: error-correcting codes . . . . . . . . . . . . . . . . . . . . . . . . 161
15.5 Diversity by injecting randomness during training . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
15.6 Additive logistic regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
15.7 Gradient boosting machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
15.8 Democracy for better accuracy-rejection compromises . . . . . . . . . . . . . . . . . . . . . . . . . 167
16 Recurrent networks and reservoir computing 171
16.1 Recurrent neural networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
16.2 Energy-minimizing Hopfield networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
16.3 RNN and backpropagation through time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
16.4 Reservoir learning for recurrent neural networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
16.5 Extreme learning machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
II Unsupervised learning and clustering 183
17 Top-down clustering: K-means 185
17.1 Approaches for unsupervised learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
17.2 Clustering: Representation and metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
17.3 K-means for hard and soft clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
18 Bottom-up (agglomerative) clustering 195
18.1 Merging criteria and dendrograms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
18.2 A distance adapted to the distribution of points: Mahalanobis . . . . . . . . . . . . . . . . . . . . . . 197
18.3 Visualization of clustering and parallel coordinates . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
19 Self-organizing maps 203
19.1 An artificial cortex to map entities to prototypes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
19.2 Using an adult SOM for classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
vi CONTENTS
20 Dimensionality reduction by projection 211
20.1 Linear projections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
20.2 Principal Components Analysis (PCA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
20.3 Weighted PCA: combining coordinates and relationships . . . . . . . . . . . . . . . . . . . . . . . . 216
20.4 Linear discrimination by ratio optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
20.4.1 Fisher discrimination index for selecting features . . . . . . . . . . . . . . . . . . . . . . . . 218
20.5 Fisher’s linear discriminant analysis (LDA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
20.6 Projection Pursuit: searching for interesting structure guided by an explicit index . . . . . . . . . . . 220
20.6.1 Normal Gaussian distributions are non-interesting: sphering or whitening . . . . . . . . . . . 220
20.6.2 Index to measure non-normality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
21 Feature extraction and Independent Component Analysis 225
21.1 Simple preprocessing for feature extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
21.2 Independent Component Analysis (ICA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
21.2.1 ICA and Projection Pursuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
21.3 Feature Extraction by Mutual Information Maximization . . . . . . . . . . . . . . . . . . . . . . . . 232
22 Visualizing graphs and networks by nonlinear maps 235
22.1 Multidimensional Scaling (MDS) Visualization by stress minimization . . . . . . . . . . . . . . . . . 236
22.2 A one-dimensional case: spectral graph drawing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
22.3 Complex graph layout criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
23 Semi-supervised learning 245
23.1 Learning with partially unsupervised data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
23.1.1 Separation in low-density areas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
23.1.2 Graph-based algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
23.1.3 Learning the metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
23.1.4 Integrating constraints and metric learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
III Optimization: basics 253
24 Greedy and Local Search 255
24.0.1 Case study: the Traveling Salesman Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 257
24.1 Greedy constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
24.1.1 Greedy algorithms for minimum spanning trees . . . . . . . . . . . . . . . . . . . . . . . . . 258
24.2 Local search based on perturbations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
24.3 Local search and big valleys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
24.3.1 Local search and the TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
25 Stochastic global optimization 269
25.1 Stochastic Global Optimization Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
25.2 A digression on Lipschitz continuity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
25.3 Pure random search (PRS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
25.3.1 Rate of Convergence of Pure Random Search . . . . . . . . . . . . . . . . . . . . . . . . . . 275
25.4 Statistical inference in global random search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
25.5 Markov processes and Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
25.6 Simulated Annealing and Asymptotics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
25.6.1 Asymptotic convergence results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
25.7 The Inertial Shaker algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
CONTENTS vii
26 Derivative-Based Optimization 287
26.1 Optimization and machine learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
26.2 Derivative-based techniques in one dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
26.2.1 Derivatives can be approximated by the secant . . . . . . . . . . . . . . . . . . . . . . . . . 294
26.2.2 One-dimensional minimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
26.3 Solving models in more dimensions (positive definite quadratic forms) . . . . . . . . . . . . . . . . . 295
26.3.1 Gradient or steepest descent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
26.3.2 Conjugate gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
26.4 Nonlinear optimization in more dimensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
26.4.1 Global convergence through line searches . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
26.4.2 Cure for indefinite Hessians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
26.4.3 Relations with model-trust region methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
26.4.4 Secant methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
26.4.5 Closing the gap: second-order methods with linear complexity . . . . . . . . . . . . . . . . . 304
26.5 Constrained optimization: penalties and Lagrange multipliers . . . . . . . . . . . . . . . . . . . . . . 305
IV Learning for intelligent optimization 311
27 Reactive Search Optimization (RSO): Online Learning Methods 313
27.1 RSO: Learning while searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
27.2 RSO based on prohibitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
27.3 Fast data structures for using the search history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
27.3.1 Persistent dynamic sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
28 Adapting neighborhoods and selection 327
28.1 Variable Neighborhood Search: Learning the neighborhood . . . . . . . . . . . . . . . . . . . . . . . 328
29 Iterated local search 333
30 Online learning in Simulated Annealing 339
30.1 Combinatorial optimization problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
30.2 SA for global optimization of continuous functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 341
31 Dynamic landscapes and noise levels 343
31.1 Guided local search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
31.2 Adapting noise levels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
32 Adaptive Random Search 349
32.1 RAS: adaptation of the sampling region . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
32.2 Repetitions for robustness and diversification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
V Special optimization problems and advanced topics 355
33 Linear and Quadratic Programming 357
33.1 Linear Programming (LP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
33.1.1 An algebraic view of linear programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
33.2 Integer Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363
33.3 Quadratic Programming (QP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363
viii CONTENTS
34 Branch and bound, dynamic programming 365
34.1 Branch and bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
34.2 Dynamic programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
35 Satisfiability 373
35.1 Satisfiability and maximum satisfiability: definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 374
35.1.1 Notation and graphical representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
35.2 Resolution and Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
35.2.1 Resolution and backtracking for SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
35.2.2 Integer programming approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377
35.3 Continuous approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
35.4 Approximation algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
35.4.1 Randomized algorithms for MAX W–SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384
35.5 Local search for SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
35.5.1 Quality of local optima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
35.5.2 Non-oblivious local optima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
35.5.3 Local search satisfies most 3–SAT formulae . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
35.5.4 Randomized search for 2–SAT (Markov processes) . . . . . . . . . . . . . . . . . . . . . . . 394
35.6 Memory-less Local Search Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
35.6.1 Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
35.6.2 GSAT with “random noise” strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396
35.6.3 Randomized Greedy and Local Search (GRASP) . . . . . . . . . . . . . . . . . . . . . . . . 397
35.7 History-sensitive Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
35.7.1 Prohibition-based Search: TS and SAMD . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
35.7.2 HSAT and “clause weighting” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
35.7.3 The Hamming-Reactive Tabu Search (H-RTS) algorithm . . . . . . . . . . . . . . . . . . . . 399
35.8 Models of hardness and threshold effects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 400
35.8.1 Hardness and threshold effects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 400
36 Design of experiments, query learning, and surrogate model-based optimization 403
36.1 Design of experiments (DOE) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
36.1.1 Full factorial design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406
36.1.2 Randomized design: pseudo Montecarlo sampling . . . . . . . . . . . . . . . . . . . . . . . 406
36.1.3 Latin hypercube sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
36.2 Surrogate model-based optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
36.3 Active or query learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
37 Measuring problem difficulty in local search 413
37.1 Measuring and modeling problem difficulty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
37.2 Phase transitions in combinatorial problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
37.3 Empirical models of fitness surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
37.4 Tunable landscapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
37.5 Measuring local search components: diversification and bias . . . . . . . . . . . . . . . . . . . . . . 418
37.5.1 A conjecture: better algorithms are Pareto-optimal in D-B plots . . . . . . . . . . . . . . . . 422
VI Cooperation and multiple objectives in optimization 425
38 Cooperative Learning And Intelligent Optimization (C-LION) 427
38.1 Intelligent and reactive solver teams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
CONTENTS ix
38.2 Portfolios and restarts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430
38.3 Predicting the performance of a portfolio from its component algorithms . . . . . . . . . . . . . . . . 431
38.3.1 Parallel processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
38.4 Reactive portfolios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435
38.5 Defining an optimal restart time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437
38.6 Reactive restarts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438
38.7 Racing: Exploration and exploitation of candidate algorithms . . . . . . . . . . . . . . . . . . . . . . 439
38.7.1 Racing to maximize cumulative reward by interval estimation . . . . . . . . . . . . . . . . . 440
38.7.2 Aiming at the maximum with threshold ascent . . . . . . . . . . . . . . . . . . . . . . . . . 442
38.7.3 Racing for off-line configuration of heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . 444
38.8 Gossiping Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448
38.8.1 Epidemic communication for optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . 448
38.9 Intelligent coordination of local search processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450
38.10C-LION: a political analogy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
38.11A C-LION example: RSO cooperating with RAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453
38.12Other C-LION algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
39 Genetics, evolution and nature-inspired analogies 459
39.1 Genetic algorithms and evolution strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
40 Multi-Objective Optimization 467
40.1 Multi-objective optimization and Pareto optimality . . . . . . . . . . . . . . . . . . . . . . . . . . . 469
40.2 Pareto-optimization: main solution techniques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470
40.3 MOOPs: how to get missing information and identify user preferences . . . . . . . . . . . . . . . . . 473
40.4 Brain-computer optimization (BCO): the user in the loop . . . . . . . . . . . . . . . . . . . . . . . . 474
41 Conclusion 479
Bibliography 481
Index 503