Clever Algorithms


Clever Algorithms: Nature-Inspired Programming Recipes (2011) .. by Jason Brownlee @jbrownlee


Contents

Foreword vii

Preface ix

I Background 1

1 Introduction 3

1.1 What is AI . . . 3

1.2 Problem Domains . . . 9

1.3 Unconventional Optimization . . . 13

1.4 Book Organization . . . 16

1.5 How to Read this Book . . . 19

1.6 Further Reading . . . 20

1.7 Bibliography . . . 21

II Algorithms 27

2 Stochastic Algorithms 29

2.1 Overview . . . 29

2.2 Random Search . . . 30

2.3 Adaptive Random Search . . . 34

2.4 Stochastic Hill Climbing . . . 39

2.5 Iterated Local Search . . . 43

2.6 Guided Local Search . . . 49

2.7 Variable Neighborhood Search . . . 55

2.8 Greedy Randomized Adaptive Search . . . 60

2.9 Scatter Search . . . 66

2.10 Tabu Search . . . 73

2.11 Reactive Tabu Search . . . 79

3 Evolutionary Algorithms 87

3.1 Overview . . . 87

3.2 Genetic Algorithm . . . 92

3.3 Genetic Programming . . . 99

3.4 Evolution Strategies . . . 108

3.5 Differential Evolution . . . 114

3.6 Evolutionary Programming . . . 120

3.7 Grammatical Evolution . . . 126

3.8 Gene Expression Programming . . . 134

3.9 Learning Classifier System . . . 141

3.10 Non-dominated Sorting Genetic Algorithm . . . 152

3.11 Strength Pareto Evolutionary Algorithm . . . 160

4 Physical Algorithms 167

4.1 Overview . . . 167

4.2 Simulated Annealing . . . 169

4.3 Extremal Optimization . . . 175

4.4 Harmony Search . . . 182

4.5 Cultural Algorithm . . . 187

4.6 Memetic Algorithm . . . 193

5 Probabilistic Algorithms 199

5.1 Overview . . . 199

5.2 Population-Based Incremental Learning . . . 203

5.3 Univariate Marginal Distribution Algorithm . . . 208

5.4 Compact Genetic Algorithm . . . 212

5.5 Bayesian Optimization Algorithm . . . 216

5.6 Cross-Entropy Method . . . 224

6 Swarm Algorithms 229

6.1 Overview . . . 229

6.2 Particle Swarm Optimization . . . 232

6.3 Ant System . . . 238

6.4 Ant Colony System . . . 245

6.5 Bees Algorithm . . . 252

6.6 Bacterial Foraging Optimization Algorithm . . . 257

7 Immune Algorithms 265

7.1 Overview . . . 265

7.2 Clonal Selection Algorithm . . . 270

7.3 Negative Selection Algorithm . . . 277

7.4 Artificial Immune Recognition System . . . 284

7.5 Immune Network Algorithm . . . 292

7.6 Dendritic Cell Algorithm . . . 299

8 Neural Algorithms 307

8.1 Overview . . . 307

8.2 Perceptron . . . 311

8.3 Back-propagation . . . 316

8.4 Hopfield Network . . . 324

8.5 Learning Vector Quantization . . . 330

8.6 Self-Organizing Map . . . 336

III Extensions 343

9 Advanced Topics 345

9.1 Programming Paradigms . . . 346

9.2 Devising New Algorithms . . . 356

9.3 Testing Algorithms . . . 367

9.4 Visualizing Algorithms . . . 374

9.5 Problem Solving Strategies . . . 386

9.6 Benchmarking Algorithms . . . 400

IV Appendix 411

A Ruby: Quick-Start Guide 413

A.1 Overview . . . 413

A.2 Language Basics . . . 413

A.3 Ruby Idioms . . . 417

A.4 Bibliography . . . 419

Index 421