The NFL Theorems in a nutshell

Last Friday I tried to explain the other members the famous Wolpert & Macready paper “No Free Lunch Theorems for Optimization”. I said “I tried” because I was beaten by a lot of bravely formulas with their invincible Sigma Squadron. I get obfuscated with such all mathematical things and I decided to face up to the problem with sense: searching a summary in the Internet. It looks like that anybody has read the article, because I haven’t found any useful (and understable for my person) information. But I’ll try to explain what I’ve learned:

The NFL Theorems says that for each pair of algorithms, A and B, without human behaviour, the half of problems in the world, the universe and all, will be more efficient in the algorithm A than the B.

Well, not bad.

But, imagine you have programmed the “Super Wonderful Algorithm To Do All With The Powers of the Cristal Skull”, the best algorithm ever made, and you are proud of it, working since you started your MsC, using it for your PhD and now you are an ancient professor you are finally writing the greatest paper of Universe. So you take all problems of the world, the universe and all, and compare with another algorithm. For example, the random search.

Damm! Your algorithm is worse in the half of problems.

So this paper is a pessimist way to those than are searching that “super wonderful algorithm to do all”.

The most interesting part is the philosophical sense. I’ve asked in the last GeNeura weekly meeting if we are part of a super-evolutionary algorithm and we can adapt the algorithms A or B to increase the performance over the other then the super-evolutionary algorithm that have created us breaks with the theorems. But JJ said that the universe is not computable, even at microatomic scale. So we all talked about metaphysics the rest of the meeting.

After that I suggested the Craig Evan’s book “Permutation City”. It’s about human virtual copies, meta-universes and a lot of cyberpunk cliches. And it’s quite cool.

That’s all, I guess. All comments about NFL theorems and/or computable universes are welcome!

New paper on multiobjective ant colony optimization available online

This is the paper we presented at the ECAL 2007 conference. Its title is Comparing ACO Algorithms for Solving the Bi-criteria Military Path-Finding Problem, and it deals with one of our lines of work, using ant-colony algorithms to show the way to a (peaceful and unarmed) military unit.


Long time before coming back here. This Friday has been devoted to talking about XMPP and its research possibilities. It’s already a distributed infrastructure, so it wouldn’t be too difficult to turn it into a distributed computing infrastructure, which we are about to do.
We also got kind of lucky in our latest paper submissions, and got 5 papers accepted for CEC (within WCCI), plus two papers in EvoStar. We’ll be in Napoli to present them come late March.