Evolutionary Computation Comic Strip... Well, at least it seems one!
I found a Power Point presentation (named Just What Are "Building Blocks" - How do (should) Evolutionary Algorithms “work”?), by Chris Stephens, upon some critiques related to Building Block Hypothesis and, also, on the Building Blocks itself. That presentation was held at FOGA 2007. I paid attention to four slides, I guess they speak by themselves. It's so intelligent and funny! :)
Stephens made interesting question on the Building Block Hypothesis, see below:
The good old Building Block Hypothesis! I remember that, once, at a evolutionary computation class, I asked the professor how someone could guarantee that the unknown solution of a problem could be achieved through short, low order, above average schemata, if the solution itself is unknown?! What if the solution is neither short nor has low order? Could a genetic algorithm get the optimum also working through strings with below average fitnesses? The professor was so categoric and said that the Building Block Hypothesis really explains the way genetic algorithms work.
Well, when the problem has to do with decomposable/separable fitness functions, it should work fine, however put some dependencies among variables and you will see what happens - even for EDAs the dependencies can represent a frightening nightmare, since, when dealing with strong dependencies, the probability distribution that samples the strings can be almost computationally unfeasible to calculate.
Stephens made interesting question on the Building Block Hypothesis, see below:
"Building Block" Hypothesis:
A GA works by combining short, low-order,
highly fit schemata (“building blocks”) into
fitter higher order schemata.
- But how would we recognise one if we saw one?
- Building what?
- How many of them are there?
- Just how are they combined together?
- When is recombination beneficial?
- How does the effect of recombination depend on the fitness landscape (and on other operators/parameters)?
The good old Building Block Hypothesis! I remember that, once, at a evolutionary computation class, I asked the professor how someone could guarantee that the unknown solution of a problem could be achieved through short, low order, above average schemata, if the solution itself is unknown?! What if the solution is neither short nor has low order? Could a genetic algorithm get the optimum also working through strings with below average fitnesses? The professor was so categoric and said that the Building Block Hypothesis really explains the way genetic algorithms work.
Well, when the problem has to do with decomposable/separable fitness functions, it should work fine, however put some dependencies among variables and you will see what happens - even for EDAs the dependencies can represent a frightening nightmare, since, when dealing with strong dependencies, the probability distribution that samples the strings can be almost computationally unfeasible to calculate.
posted by Marcelo at 9:24 PM
2 Comments:
It seems old Goldbergs Building Blcok hypothesis has moved from theory to truth. Wish some people would realise it is still a theory, albeit interesting one which does explain some of the reasons for GA success.
Speaking of EDAs, i used a simple one for solving the protein structure prediciton problem for my MSc. Usefull little buggers they are :)
Regards Wolfe
Regards Wolfe
Hi, Wolfe! :)
When you said that BBH is "still a theory" it means that the BBH is well established taking into account that view, that is, theory. What is not true. :)
The Building Block Hypothesis, as the name itself suggests, is a hypothesis. :)
Theory would mean:
"a well-substantiated explanation of some aspect of the natural world; an organized system of accepted knowledge that applies in a variety of circumstances to explain a specific set of phenomena; 'theories can incorporate facts and laws and tested hypotheses'; 'true in fact and theory'"
What is not the current situation of the BBH. :)
But I think that you used the word theory through a colloquial manner. :)
I consider the BBH one of the first attempts to explain the way GAs work, despite the fact that I do not consider it the real working of GAs.
Let's expect that no person comes soon to declare genetic algorithms too complex to be explained through equations and mathematics! What would be very funny! Albeit it is a possibility... :)
Até Mais!
Marcelo
Post a Comment
<< Home