Dreaming of Metaheuristics

Thoughts about metaheuristics for hard optimization

Go to the content | Go to the menu | Go to the search page

Sunday 10 September 2006

Confirmation of the biological foundations of particle swarm optimization

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/m2), the animals moves independently. When reaching 25 to 60 locusts/m2, they form collective groups, which direction can vary abruptly. Beyond 75 locusts/m2, 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.

Friday 1 September 2006

Finding references about metaheuristics (and computer science)

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.
  • 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: