Book Review: Essentials of Metaheuristics

Getting the book: http://www.cs.gmu.edu/~sean/book/metaheuristics/

I picked up a copy of this book from the man himself, Sean Luke at the IEEE CEC 2011. I was “aware” of this book from a while back, so I thought it might be a good idea to pick a print copy for light readings during my travels post-conference. Here is a brief review of the book:

Synopsis:

As the author states, the book is a compilation of undergraduate lectures notes on Metaheuristics. It focuses on the applications of Metaheuristics to optimization problems including Multi-objective optimization, Combinatorial optimization and Policy optimization. Depending on your experience with Metaheuristics, this book will serve a different purpose for you:

1. If you are quite well versed with them, this book will be a nice light reading, with interesting bits and pieces throughout
2. If you are starting with them, or want to start with Metaheuristics, this book gives a nice well rounded view of the state-of-the art

Review

The book starts with an overview of gradient based optimization methods in Chapter 1 gradually moving to stochastic methods such as randomized hill-climbing, tabu search, simulated annealing in Chapter 2.

Chapter 3 introduces population methods — Evolution Strategies, Genetic Algorithms, Differential Evolution and Particle Swarm Optimization.

Over the last three chapters, the author introduces some fundamental concepts: the choice of representation of solutions, issues of exploration v$ exploitation and local optima traps.

Chapters 4-10 each discuss one specific topic. For example,  Chapter 4 is dedicated to representation of solutions — vectors, direct encoded graphs, program trees and rulesets.  Chapter 5 discussess parallel methods for metaheuristics and Chapter 7 talks about Multi-objective optimization. Chapter 8 and 10 talks about combinatorial optimization and policy optimization respectively. So, if you are looking for anything specific, you can directly jump to the relevant chapter (assuming, of course that you have the pre-requisite knowledge). As you can see in the ToC, most of the chapters from 4-10 depends on Chapters 3 & 4.

The book finally concludes with some descriptions of test problems and statistical tests that researchers often use to test their algorithms. The very important issue of selecting a proper random number generator is discussed in this chapter.

Conclusion

This book along with Evolutionary Computation: A Unified Approach (You may be interested in my review) is great for getting a holistic view of the Meta-heuristic methods, especially if you are more experienced with only one of them.

Getting the book: http://www.cs.gmu.edu/~sean/book/metaheuristics/

Advertisement

Book Review: Evolutionary Computation: A Unified Approach

My background: I am currently working full time on research problems in Genetic Algorithms. My current work is in using GAs for multi-modal optimization. My experience in this field is 6 months, my interest infinite :)

Evolutionary Computation: A Unified Approach brings together a summarized view of three distinct fields of Evolutionary Computing (EC)- Evolutionary Strategies (ES), pioneered by Rechenberg and Schwefel, Evolutionary Programming (EP), pioneered by Fogel and Genetic Algorithms (GA) pioneered by John Holland. A fundamental book such as this one helps the EA researcher to sit back and identify the fundamental principles of these different algorithms. Throughout the book, a unified view of the fields is presented and thus this book is a must read for the evolutionary computing researcher- novice, like me or the experienced. This book explores a very experimental approach to the study of these algorithms and is thus easy to follow, almost like reading a novel for the EA researcher.

In Chapter 1, fundamental characteristics of a simple evolutionary system are presented. EV, a simple evolutionary system is presented and sample runs over a 1-dimensional and 2-dimensional landscape is presented. First ideas of evolutionary systems as problem solvers are presented in this chapter. A key idea presented in this chapter is that simulated evolutionary systems try to draw inspiration from the biological evolutionary system to design better algorithms to solve complex computational problems, and not mimic them. The graphical plots of the results demonstrates the ideas of convergence, and though not explicitly mentioned, the EC researcher easily identifies this as a useful way to demonstrate the progress of a Evolutionary algorithm.

In Chapter 2, a step is taken back to look at the historical development of the three fields of ES, EP and GA. This chapter puts the three research communities into perspective of their historical development.

In Chapter 3, the simple EV system introduced in Chapter 1 is extended to the generic EV(m,n) system of m parent population, and an offspring population of size n. What this generalization does is that it allows talking about the canonical EP, ES and GA in one common framework.

Chapter 4 presents a first detailed unified treatment of the three algorithms. The following common pattern of evolutionary dynamics are presented:

1. a fixed size population, m is evolved over time,
2. the current population is used as a parent population to produce n offspring, and
3. the expanded population size is reduced from m+n to m

Its apparent that the EA researchers have several design choices to make: a correct value of m and n, the selection of the parent population that takes part in the process to generate offspring, and selecting the m population size from the m+n population. These questions are addresses in the rest of this chapter by the discussions on population sizing, selection mechanisms, reproductive mechanism and representation issues.

So far, the book has addressed the ideas of simulating simple evolutionary systems and their temporal dynamics. How can such systems be used to solve computational and engineering problems is addressed in chapter 5. Using EAs for search, optimization-single objective and multi-objective, machine learning and automatic programming are discussed here. This is a chapter that will be useful to readers beyond the EA research community, since they provide insights into using EA for practical problem solving, which can be useful in complex, high-dimensional search spaces and not much information is available about the problem at hand.

Chapter 6 is of utmost importance and interest for the EA researcher as it describes some of the ways that EAs can be theoretical analyzed. Depending on the property of a EA you are analyzing, the tools for analysis also vary:

• EA population dynamics -> dynamical systems tools
• Stochastic properties of EAs -> Markov processes
• Aggregate properties of EAs -> Statistical mechanics tools
• Computational complexity  of EAs -> Algorithmic Analysis tools
• Optimization properties of EAs -> Mathematical tools

I am yet to grok this chapter in its full capacity and power, so I shall get back to it after a detailed reading.

The second last chapter of the book, Chapter 7 takes a look at some of the advanced EA topics such as self-adaptive EAs, Multi-objective EAs, memetic EAs, EAs applied to dynamic landscapes and others.

The book concludes in Chapter 8 by urging more work in the quest the book started with- more unification of the different fields in Evolutionary computation.

Book Review: The War of the Worlds

I just finished reading a work of Scientific Romance– The War of the Worlds, H.G.Wells. In approx 200 pages, this book is a enriching read, taking you to a time when Earth is under attack from Mars, the utter destruction that ensues, the protagonist’s (also the narrator’s) journey across the cities, witnessing death, demoralisation and finally, the martians’ termination by Earth’s bacteria.

There are symbolic meanings attached to the events that take place. For eg: (in Book One, Chapter One- http://publicliterature.org/books/war_of_the_worlds/xaa.php)

Yet so vain is man, and so blinded by his vanity, that no writer,
up to the very end of the nineteenth century, expressed any idea that
intelligent life might have developed there far, or indeed at all,
beyond its earthly level.

and many such are vivid throughout the book. The wikipedia page has got great matter on the book. A definite checkout for the Science fiction loving reader!