Saturday, December 23, 2006

David²




I found some months ago two very interesting audio presentations from David Fogel and other from David E. Goldberg. According to Fogel (hear here the presentation or download it), what works best is the synergistic effect obtained by combining simulated evolutionary learning with human learning. As an example of this latter approach he tells the story of Blondie24, a checkers program supplied with only minimal information that was able to reach high levels of expertise thanks to the application of genetic algorithms. Fogel looks at other real-world applications in industry, medicine, and defense, as well as speculating on the future capabilities offered by these combined learning mechanisms. It is a nice example of evolutionary computation application.

Goldberg's presentation is about the evolution of genetic algorithms through the 1990s, when GAs had their Warhol 15 minutes of fame, and where they are today. It is an interesting overview of genetic algorithms (although I disagree on some parts of his presentation), why they did not solve some classes of problems (maybe this paper here and this other here can help to understand that why), the results got by the first generation of genetic algorithms and, of course, the results obtained through new generation GAs, such as hBOA (Hierarchical Bayesian Optimization Algorithm). He also talks on the comparison made between a Simple Genetic Algorithm (or SGA) and hBOA on an antenna design problem. There is, of course, Goldberg's famous quote which he uses to ask why when the subject is conceptual machines, such as genetic algorithms, persons often want to see proof and rigor, while other machines, such as airplanes and toasters, are frequently used and persons do not ask for rigor and proof, here you are the quote:


"Nobody has ever formally proven that an airplane flies, but we all entrust our lives to them/it."


Yes, I agree that no one has ever proven mathematically/formally that an airplane can fly (or a toaster can toast), but an airplane (or toaster, fan, towel, shoes, etc) is not an algorithm! When we talk about evolutionary algorithms, we are also talking about algorithms (I guess it is clear) and we cannot disconnect an algorithm from its natural features, such as convergence proof and complexity analysis. If we disconnect them, the situation tends to get worse, because we need to consider those inherent features/characteristics to make a rigorous analysis of the algorithms' behaviour (it is valid for genetic algorithms too). Inevitably, that task needs rigor and proof. I suppose that would be difficult to convince people, mainly computer scientists, to use an algorithm which does not have all those stuffs I said. (If you want to read a more detailed version of that quote, please, see here.)

3 Comments:

Blogger Togelius said...

I didn't know about that quote, but I think it's excellent.

I don't really understand your argument though. Or course we can talk about (and use, and trust) evolutionary algorithms without mentioning convergence proofs and complexity analysis. Further, I don't see such theoretical constructs as "natural features" of evolutionary algorithms - rather, they're just theoretical constructs.

This is not too say that I don't think theoretical analysis of EA's is interesting. It definitely is. Interesting. As for its usefulness, I don't know just yet...

23 December, 2006 14:40  
Anonymous SoloGen said...

Do you believe that people do not prove that planes can fly?! I thought that mechanical/aerospace engineers exactly do this kind of jobs!

05 January, 2007 16:32  
Blogger Nosophorus said...

Hi, Friends! :)

It's an honour to myself for your presence and comments here in my relatively obscure blog, The Genetic Argonaut. :)

Well, I know that no one should answer a question through another question, but, if you permit me, I would like to ask you some ones which are, if not interesting, at least funny! :)

Here you are:

Fist, the quote:

"Nobody has ever formally proven that an airplane flies, but we all entrust our lives to it."

Now, the questions:

1 - Have you ever seen a Turing Machine that matches an airplane?

2 - Or an airplane which has computable features?

3 - What is the complexity of an airplane according to the Big-O notation?

4 - Could we put an algorithm inside the wind tunnel and do some CFD simulations with it?

5 - Could you give me, please, the Reynolds Number of your Genetic Algorithm?

6 - It would be interesting to look for some kind of implicit parallelism in airplanes, wouldn't it?

Thanks heavens that my toaster
never goes into infinite loop, otherwise I would have unhealthy toasts to my breakfast! :)

And remember next time when you get aboard an airplane:

"Nobody has ever formally proven that an airplane flies, but we all entrust our lives to it."

And the passenger beside you could say:

"Of course! Even my bomb does not need that!

:)

See You!

Marcelo

P.S: I am writing a post to more formally reply your questions. So, stay tuned! :)

02 March, 2007 21:02  

Post a Comment

Links to this post:

Create a Link

<< Home

Charles Darwin Has A Posse Check Google Page Rank