Clever Algorithms NatureInspired Programming Recipes

Jason Brownlee

Clever Algorithms

Nature-Inspired Programming Recipes

ii

Jason Brownlee, PhD

Jason Brownlee studied Applied Science at Swinburne University in Melbourne,

Australia, going on to complete a Masters in Information Technology focusing on

Niching Genetic Algorithms, and a PhD in the field of Artificial Immune Systems.

Jason has worked for a number of years as a Consultant and Software Engineer

for a range of Corporate and Government organizations. When not writing books,

Jason likes to compete in Machine Learning competitions.

Cover Image

© Copyright 2011 Jason Brownlee. All Reserved.

Clever Algorithms: Nature-Inspired Programming Recipes

© Copyright 2011 Jason Brownlee. Some Rights Reserved.

First Edition. LuLu. January 2011

ISBN: 978-1-4467-8506-5

This work is licensed under a Creative Commons

Attribution-Noncommercial-Share Alike 2.5 Australia License.

The full terms of the license are located online at

http://creativecommons.org/licenses/by-nc-sa/2.5/au/legalcode

Webpage

Source code and additional resources can be downloaded from the books

companion website online at http://www.CleverAlgorithms.com

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

iii

iv Contents

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

v

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

vi Contents

Foreword

I am delighted to write this foreword. This book, a reference where one

can look up the details of most any algorithm to find a clear unambiguous

description, has long been needed and here it finally is. A concise reference

that has taken many hours to write but which has the capacity to save vast

amounts of time previously spent digging out original papers.

I have known the author for several years and have had experience of his

amazing capacity for work and the sheer quality of his output, so this book

comes as no surprise to me. But I hope it will be a surprise and delight to

you, the reader for whom it has been written.

But useful as this book is, it is only a beginning. There are so many

algorithms that no one author could hope to cover them all. So if you know

of an algorithm that is not yet here, how about contributing it using the

same clear and lucid style?

Professor Tim Hendtlass

Complex Intelligent Systems Laboratory

Faculty of Information and Communication Technologies

Swinburne University of Technology

Melbourne, Australia

2010

vii

viii Foreword

Preface

About the book

The need for this project was born of frustration while working towards my

PhD. I was investigating optimization algorithms and was implementing

a large number of them for a software platform called the Optimization

Algorithm Toolkit (OAT)1

. Each algorithm required considerable effort

to locate the relevant source material (from books, papers, articles, and

existing implementations), decipher and interpret the technique, and finally

attempt to piece together a working implementation.

Taking a broader perspective, I realized that the communication of

algorithmic techniques in the field of Artificial Intelligence was clearly a

difficult and outstanding open problem. Generally, algorithm descriptions

are:

ˆ Incomplete: many techniques are ambiguously described, partially

described, or not described at all.

ˆ Inconsistent: a given technique may be described using a variety of

formal and semi-formal methods that vary across different techniques,

limiting the transferability of background skills an audience requires

to read a technique (such as mathematics, pseudocode, program code,

and narratives). An inconsistent representation for techniques means

that the skills used to understand and internalize one technique may

not be transferable to realizing different techniques or even extensions

of the same technique.

ˆ Distributed: the description of data structures, operations, and pa￾rameterization of a given technique may span a collection of papers,

articles, books, and source code published over a number of years, the

access to which may be restricted and difficult to obtain.

For the practitioner, a badly described algorithm may be simply frus￾trating, where the gaps in available information are filled with intuition and

1OAT located at http://optalgtoolkit.sourceforge.net

ix

x Preface

‘best guess’. At the other end of the spectrum, a badly described algorithm

may be an example of bad science and the failure of the scientific method,

where the inability to understand and implement a technique may prevent

the replication of results, the application, or the investigation and extension

of a technique.

The software I produced provided a first step solution to this problem: a

set of working algorithms implemented in a (somewhat) consistent way and

downloaded from a single location (features likely provided by any library of

artificial intelligence techniques). The next logical step needed to address this

problem is to develop a methodology that anybody can follow. The strategy

to address the open problem of poor algorithm communication is to present

complete algorithm descriptions (rather than just implementations) in a

consistent manner, and in a centralized location. This book is the outcome

of developing such a strategy that not only provides a methodology for

standardized algorithm descriptions, but provides a large corpus of complete

and consistent algorithm descriptions in a single centralized location.

The algorithms described in this work are practical, interesting, and

fun, and the goal of this project was to promote these features by making

algorithms from the field more accessible, usable, and understandable.

This project was developed over a number years through a lot of writing,

discussion, and revision. This book has been released under a permissive

license that encourages the reader to explore new and creative ways of

further communicating its message and content.

I hope that this project has succeeded in some small way and that you

too can enjoy applying, learning, and playing with Clever Algorithms.

Jason Brownlee

Melbourne, Australia

2011

Acknowledgments

This book could not have been completed without the commitment, passion,

and hard work from a large group of editors and supporters.

A special thanks to Steve Dower for his incredible attention to detail

in providing technical and copy edits for large portions of this book, and

for his enthusiasm for the subject area. Also, a special thanks to Daniel

Angus for the discussions around the genesis of the project, his continued

support with the idea of an ‘algorithms atlas’ and for his attention to detail

in providing technical and copy edits for key chapters.

In no particular order, thanks to: Juan Ojeda, Martin Goddard, David

Howden, Sean Luke, David Zappia, Jeremy Wazny, and Andrew Murray.

Thanks to the hundreds of machine learning enthusiasts who voted on

potential covers and helped shape what this book became. You know who

you are!

Finally, I would like to thank my beautiful wife Ying Liu for her unre￾lenting support and patience throughout the project.

xi

xii Acknowledgments

Part I

Background

1

Chapter 1

Introduction

Welcome to Clever Algorithms! This is a handbook of recipes for com￾putational problem solving techniques from the fields of Computational

Intelligence, Biologically Inspired Computation, and Metaheuristics. Clever

Algorithms are interesting, practical, and fun to learn about and implement.

Research scientists may be interested in browsing algorithm inspirations in

search of an interesting system or process analogs to investigate. Developers

and software engineers may compare various problem solving algorithms

and technique-specific guidelines. Practitioners, students, and interested

amateurs may implement state-of-the-art algorithms to address business or

scientific needs, or simply play with the fascinating systems they represent.

This introductory chapter provides relevant background information on

Artificial Intelligence and Algorithms. The core of the book provides a large

corpus of algorithms presented in a complete and consistent manner. The

final chapter covers some advanced topics to consider once a number of

algorithms have been mastered. This book has been designed as a reference

text, where specific techniques are looked up, or where the algorithms across

whole fields of study can be browsed, rather than being read cover-to-cover.

This book is an algorithm handbook and a technique guidebook, and I hope

you find something useful.

1.1 What is AI

1.1.1 Artificial Intelligence

The field of classical Artificial Intelligence (AI) coalesced in the 1950s

drawing on an understanding of the brain from neuroscience, the new

mathematics of information theory, control theory referred to as cybernetics,

and the dawn of the digital computer. AI is a cross-disciplinary field

of research that is generally concerned with developing and investigating

3