Optimization Heuristics, part III: The bitter pill

I have previously told you that the ways in which Nature works lead to surprising and wonderful results: Evolution produces human biochemistry, thermodynamics produces beautiful crystals etc.

I did not, however, tell you that it happens fast. Because it does not.

Homo sapiens took several million years to evolve. The thermodynamic processes are overly complex and happen on a vastly stretched time scale. And even then, the results are far from the optimum. Because, seriously, four blood types? The whole mammalian biochemistry? The blind spot? It is impossible to engineer that.

The main problem in the heuristics business is that even the most sophisticated nature-inspired process is just another clever strategy to randomly poke around in the search space. Because the problems (especially the complicated, we-have-no-idea-how-to-solve-it ones) have that rather bad habit of behaving not the way you want them to behave (because, otherwise, you’d just solve them in a traditional fashion). There is a famous result, called the No Free Lunch Theorem, which states that on average, all algorithms on all problems are equally bad. Bad means here exponentially bad, the kind of bad you do not want to mess with. One may argue that this result is a bit overrated, because we do not want to consider all problems; but even in the case when we restrict ourselves to “sane” problems with exactly one local maximum, it can still be shown that bad performance may occur, which makes “hard” guarantees on optimization time rather complicated. There are promising results for fluffy toy problems where the probabilistic machinery is not too awful. Still, for any real problem (like optimizing antenna designs) there are no theoretic bounds; but then again, any solution strategy that works for this kind of problems where there is little knowledge about the problem structure is better than none.

Leave a Reply

Your email address will not be published.

Time limit is exhausted. Please reload CAPTCHA.

This site uses Akismet to reduce spam. Learn how your comment data is processed.