PSA, For Science! (Optimization Heuristics, part one)

One of my next assignments is to write a (rather short, by my standards) essay on artificial immune systems. In the meanwhile, I will probably dump some of the background information (in a readable fashion) on you, my dear reader. Mostly for Science, but otherwise just to give my explanation skills a try. As I am not allowed to disclose my essay before the deadline, I will write something not quite about the topic, but about some interesting things from the general context.

Optimization Heuristics, part one, or How to stop worrying and start relying on Nature

What do I mean by “optimization heuristics”? Or, better, what do I mean when I talk about “optimization”? Optimization is a problem from the vast domain of mathematics, where it is often needed to find some value x which causes a function f achieve its maximal value. This boring stuff suddenly becomes very exciting when f is your income. Or the efficiency of your car’s engine. Or something else, completely unrelated.

As you might still remember from school, optimization was this task of finding the extrema of some awfully boring function. And you had to derive once, twice, thrice to be able to talk about the behavior or the function in question. So, what is the point of researching things about optimization, if any schoolchild with some knowledge about calculus can do it? Surely it cannot be so easy.

The sad part is, not only it is not easy, it is also very, very, very complicated. Your income does not behave like a nice polynomial function (or otherwise you’d figure out how to optimize it into the skies) and neither do flow properties of the air in turbines. In some cases, we cannot even write down the function in question in a fashion such that we can analyze it on paper.

This leaves us with a heap of unresolved questions. Surely, we know that there is some function which dictates the behavior of, say, a turbine. We can simulate the turbine. We can try various configurations and compare them. And that is it. The general kind of problems is called black-box optimization, for the details of the function to optimize are unknown to us, f is said to be a black box.

What we can do now is to try different strategies for searching the optimal input for f. The most trivial is to randomly poke into the set of allowed input values (called search space for intuitive reasons) and compare the results. This works with humans, why should it not work with machines? The main problem: this kind of search strategy can lead to long waiting times for optimization. Imagine yourself searching for a book in your friend’s bookshelf. You can jump randomly around, sure, but there almost surely is some system in which the books are arranged, right? Why not just search from the beginning? Well, this might work, but the bookshelf is large, and you’ll expect to go through the half of it before you find the right book.

We have to keep in mind that we just faced an inherent problem: Any of search strategies in a black-box scenario might lead to long optimization times, because what we are doing here is basically just poking into the search space with some more or less smart strategy. But this is the problem of the scenario and there is nothing you can do about it once you confine yourself to no knowledge about the behavior of f whatsoever.

So, what can we do, if we face a difficult problem? We might try to seek for already existing and working solutions. One of the first things that comes to mind is that somewhere, somehow, something similar happened in nature. The main problem with it is that nature has no optimizing goals. But some natural processes behave like optimization goals. So we could try to copy strategies from nature just because they seem to work and hope that it will work for our problems, too.

(To be continued)

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.