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!