Explainer: Evolutionary Algorithms

Whenever you undertake an activity that seeks to minimise or maximise a well-defined quantity such as distance or the vague notion of the right amount of sleep, you are optimising.

Like I have mentioned elsewhere, I like to introduce complex (and not so complex) concepts in a popular science fashion – for consumption by even the high-school kid. Hence, when I was contacted by Bella from The Conversation, I was excited to write about Evolutionary Algorithms and optimization and what we as a group work on.

The article is now live here. Hope you enjoy the read. Many thanks to the team at The Conversation for the final touches on the article.

Snowy, your support in various ways is always appreciated.

Link: http://theconversation.edu.au/explainer-evolutionary-algorithms-3580

Advertisement

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/

IEEE CEC 2011: Post-conference Thoughts

I am currently sitting by the window of my 10th floor of my hotel room and New Orleans looks beautiful at this time of the night. The neon glows of the hotels and shops around and the lights of those huge wooden/steel bodies on the mighty Mississippi is quite a spectacle for my bespectacled eyes. The IEEE Congress on Evolutionary Computation 2011 concluded today.  Over three days of paper and poster presentations, plenary lectures, cruise dinner on the steamboat Natchez and the sumptuous banquet last night, it was an awesome conference. Thank you Dr. Alice Smith and congratulations on the wonderful conference, which must have given you a lot of sleepless nights.

Here are some rough notes/thoughts/rants on the conference:

Plenary lectures

Each of the three days of the conference began with a plenary lecture. Natalio Krasnagor delivered the lecture on the first day talking about his work at the confluence of Natural sciences and Evolutionary Algorithms. Holger Hoos delivered the lecture on the 2nd day  where he had a lot of interesting things to talk about his research and mostly on topics of automating software development, having more degrees of freedom in software and algorithm selecting algorithms. Hod Lipson delivered the last of the plenary lectures and demonstrated his work on Evolutionary robotics and his super work, Eureqa. A lot to take home from each of these lectures. Enlightening and inspiring.

Interesting ideas/papers presented

• A lot of work is being done on Genetic Programming, mainly as tools — in varied domains, from edge detection to blog network modeling. Once the IEEE CEC proceedings are indexed by IEEExplore, it would be very interesting to go through these papers. Available here.
• Multi-view classification
• Representation plays a key role in EAs and Daniel Ashlock‘s tutorial on this topic was (or supposed to be) quite enlightening, but I think I was busy doing something else. However, I intend to go through the slides he used and get an idea of the variety of representation schemes for different applications.

Rants

I usually tend to set high standards for myself and more often than not fail to achieve them, which ofcourse doesn’t deter me in setting them in the first place. Seeing a lot of “well known” people in this field presenting trivial works at a premier conference was quite disheartening. One good thing it does is that it makes me feel that may be I should be a little gentle to myself.

I wanted to change the world, but they lied to us

I don’t know about you, but I almost always think myself to be the cover page of the major world news papers or its nearest domain equivalent, whenever I do something cool/nice/interesting (according to myself, ofcourse). I thought writing up a paper titled “How does the good old GA perform at Real World Optimization?” would irk a lot of people and elicit reactions out of them. I guess nothing really matters. Sigh.

Well, anyway I am taking back a lot from this conference at the Big Easy. Good bye Poboy’s and Gumbo!