Using Genetic Algorithms to Break Things

If nothing is known about the objective function, no optimization algorithm can possibly be said to be better than any other. This is the no free lunch theorem.

http://en.wikipedia.org/wiki/No_free_lunch_theorem

So there is absolutely no sense in talking about optimization algorithms in isolation from the problems they're meant to solve. An intelligent appraisal of genetic algorithms would talk about the types of objective functions they seem to be able to find good answers for.

>On the other hand if you prove a theorem stating that for this types of problems, if you let GA run for this amount of time you are going to be close to the optimum with high probability. That would be phenomenally useful.

>At its basic, GA is a parallelized and randomized exploration of the space. Tell me why is that particular way of randomization and parallelization the right thing to do, or for what classes of problems is it the right thing to do. Without this, they are anecdotes.

That's pretty much impossible. If you already know so much about the problem space to the point of being able to prove theorems about it, then you don't need metaheuristics.

Therefore, trying to design a fully generic optimization algorithm is a fool's errand. On the contrary, a specific objective function will have specific properties and in that case it would be valuable to use specific algorithms suited to its properties. To follow the argument forward, it would be very useful if it was characterized what is exactly the class of objective functions that EA, GA, swarms, ant colon algorithms handle well. Under what assumptions is their specific randomization and parallel evaluation the right thing to do. These are resource intensive procedures, so such a characterization will tell us when is that effort well spent.

One uncharitable but plausible way to read the tail end of your comment is that just because a particular function is not random, it will violate NFL and magically make EA, GA style algorithms appropriate, that is not true. Glad that you were able to reword it before the edit window closed.

Edit: replying here because this thread is becoming nested too deep.

Hi @Dn_Ab I think we may have talked passed each other, so clarifying. Of course a bias / preference will naturally get induced over algorithms when you select objective functions non-uniformly. No magic there. But that is not going to make a particular choice of an algorithm (in this case EA, GA et al) magically appropriate for whatever specific nonuniform distribution over the objective function chosen. The choice either has to be deliberate (in which case we would need to know a measurable description of the class where these algorithms work better) or one has wait to get wildly lucky, the latter is about as productive as playing lottery except that the tickets are pretty expensive when we play EA, GA etc.

@sampo > have very specific mathematically defined meanings here, and those meaning are probably very different than what a casual reader might expect.

Good point, upvoted, now I understand your previous comment better.

@sampo > I also like your "snake oil" metaphor, and I was happy to see your top comment on this topic.

I expected it to be downvoted out of existence given a few snarks that I yielded to.

The No Free Lunch Theorem is also one of those limit statements that rarely impinges on reality. We are not interested in all possible functions - the majority of which will be of such complexity as to be indistinguishable from random - only those with exploitable structure. It's much the same reason for why, although kmeans is NP-hard, failing to find a good clustering is very often suggestive of an ill-posed problem with no interesting structure. If kmeans didn't find a good cluster, very possibly a good one does not exist (e.g. Clustering is difficult only when it does not matter; http://arxiv.org/abs/1205.4891)