Dreaming of Metaheuristics

Particle swarm optimization (PSO) is based on biological (and theorical physic) work concerning self-organizaton in animals groups. Up to now, theory explained that animals must adjust their direction in order to set up a group. PSO use this concept to build a set of vectors that will exlpore the search space of an optimization problem, while converging on an optimum.

One key prediction of the theory is a transition between the recruitment of the individuals and the collective motion. This transition "from disorder to order" has been proved in situ by biologists, while studying locusts. They have filmed during 8 hours a group of 5 to 120 desert locusts, in a circular cockpit, and analysed the motions datas. The study shows that, at low density (under 25 individuals/m²), the animals moves independently. When reaching 25 to 60 locusts/m², they form collective groups, which direction can vary abruptly. Beyond 75 locusts/m², the coordinated marching is homogen.

While this should not change the use of PSO, which is a simplified model, it is always interesting to consider works talking about this transition between order and chaos, in self-organized systems. Indeed, this transition can also occurs in metaheuristics, and is perhaps interesting for further research, like in dynamical optimization.

From Disorder to Order in Marching Locusts, Buhl et al., Science, Vol. 312. no. 5778, pp. 1402 - 1406, 2 june 2006.

The Internet is rapidly becoming the first place to search for scientific papers. But the number of places gathering ressources becomes really high. Here is a list of web sites with free access. These are places where you can find some stuff about metaheuristics, I have not include all the available databases (nor journals web pages), despite the fact that metaheuristics are often apply to a wide range of fields.

• Online collective bibliography managers are really usefull for picking references when surfing on journal sites, they permits to automatically gather the reference's informations, tag them, share your list with others and export it in your local reference manager.
  • CiteUlike: really intersting for computer science, see my user page, the metaheuristics group, the evolutionary computation group and the optimization group. With watchlist and syndication based on RSS.
  • Connotea, more aim at clinicians and biologist.
• digital libraries or paper databases:
  • CiteSeer, search for citations and papers, show citations inside each papers, permits corrections on items, really interesting for computer science.
  • ScienceDirect, database, require registration, make available a watchlist based on email alerts.
  • arXiv, an e-print service, well formated ressources, RSS syndication.
  • Springer Links, books & papers database, RSS syndication, watchlist for registered users.
  • ACM portal, digital library, no syndication or free watchlist for registered users.
  • IEEE Xplore, database, no syndication, no watchlist, email alerts at field level only.
  • The Collection of Computer Science Bibliographies, database, RSS syndication.
  • PubMed, database, emails alerts for registered users.
  • Backwell Synergy, database, RSS/Atom syndication, email alerts.
  • Optimization Online, e-print about optimization, monthly email alerts.
  • Scitation, database, no syndication, no free email alerts.
  • Wiley InterScience, database, no syndication, emails alerts for registerd users.
• generalistic search-engines:
  • Scirus
  • Google Scholar

Springer has published a new book in their Studies in Computational Intelligence series.

Edited by Abraham, Grosan and Ramos, it covers "Stigmergic Optimization". Looking at the table of content, one can see that we talk about Ant Colony Optimization.

Of course, it also get onto the so-called swarm intelligence and self-organization, but also onto Particle Swarm Optimization, which is a method that gather more and more researchers these months.

Note that this bibliography is quite old (2003) and aim french students.

If you need only one reference, this is (of course, because I'm one of the authors) this one :

• Dréo, J. ; Petrowski, A. ; Taillard, E. ; Siarry, P. ; Metaheuristics for Hard Optimization Methods and Case Studies, Springer, 2006, XII, 369 p., 140 illus., Hardcover. ISBN: 3-540-23022-X

General

Books

• Glover, F. W. ; Kochenberger, G. A. ; 2003 : Handbook of Metaheuristics, Kluwer Academic Publishers, International series in operations research and management science, Boston Hardbound.

• Teghem, J. ; Pirlot, M. ; 2002 : Optimisation approchée en recherche opérationnelle. Recherches locales, réseaux neuronaux et satisfaction de contraintes, Hermès.

• Pham, D.T. ; Karaboga, D. ; 2000 : Intelligent optimisation techniques. Genetic Algorithms, Tabu Search, Simulated Annealing and Neural Networks, Springer.

• Saït, S.M. ; Youssef, H. ; 1999 : Iterative computer algorithms with applications in engineering, IEEE Computer Society Press.

• Reeves, C.R., 1995 : Modern Heuristic Techniques for Combinatorial Problems, Mc Graw-Hill, Advances topics in computer science.

Algorithms

Simulated Annealing

Books

• Siarry, P.; Dreyfus, G. ; 1989 : La méthode du recuit simulé : théorie et applications, ESPCI -- IDSET, 10 rue Vauquelin, 75005 Paris.

Tabu Search

Books

• Glover, F. ; Laguna, M. ; 1997 : Tabu search, Kluwer Academic Publishers, Dordrecht.

Articles

• Glover, F. ; 1989 : Tabu search --- part I, ORSA Journal on Computing, vol. 1, 190--206.

• Glover, F. ; 1990 : Tabu search --- part II, ORSA Journal on Computing, vol. 2, 4--32.

Evolutionary Algorithms (aka Genetic Algorithm)

Books

• Baeck, T. ; Fogel, D. B. ; Michalewicz, Z. ; 2000 : Evolutionary computation 1: basic algorithms and operators, Institute of Physics Publishing.

• Baeck, T. ; Fogel, D. B. ; Michalewicz, Z. ; 2000 : Evolutionary computation 2: advanced algorithms and operators, Institute of Physics Publishing.

• Goldberg, D. E. ; 1994 : Algorithmes génétiques. exploration, optimisation et apprentissage automatique, Addison-Wesley France.

• Koza, J. R. ; 1992 : Genetic programming I: on the programming of computers by means of natural selection, MIT Press.

• Koza, J. R. ; 1994 : Genetic programming II: automatic discovery of reusable programs, MIT Press.

Ant Colony Algorithms

Books

• Bonabeau, E. ; Dorigo, M. ; Theraulaz, G. ; 1999 : Swarm Intelligence, From Natural to Artificial Systems, Oxford University Press.

Greedy Randomized Adaptive Search Procedure (GRASP)

Tech Reports

• Resende, M.G.C. ; 2000 : Greedy randomized adaptive search procedures (GRASP), AT&T Labs-Research, TR 98.41.1.

Partical Swarm Optimization

Books

• Eberhart, R.C. ; Kennedy, J. ; Shi, Y. ; 2001 : Swarm Intelligence, Morgan Kaufmann, Evolutionnary Computation.

Estimation of Distribution Algorithms

Books

• Larranaga, P. ; Lozano, J.A. ; 2002 : Estimation of Distribution Algorithms, A New Tool for Evolutionnary Computation, Kluwer Academic Publishers, Genetic Algorithms and Evolutionnary Computation.

Related Topics

Multi-Objective Optimization

Books

• Collette, Y. ; Siarry, P. ; 2002 : Optimisation multiobjectif, Eyrolles.

• Deb, K. ; 2001 : Multi-objective optimization using evolutionary algorithms, John Wiley and sons.

Constrainted Optimization

Books

• Michalewicz, Z. ; 1996 : Genetic algorithms + data structures = evolution programs, Springer Verlag, troisième édition révisée.

Self-Organization

Books

• Camazine, S. ; Deneubourg, J.L. ; Franks, N. ; Sneyd, J. ; Theraulaz, G. ; Bonabeau, E. ; 2000 : Self-Organization in Biological Systems, Princeton University Press.