Using Genetic Algorithms to Break Things • Hacker News Board

Re: Using Genetic Algorithms to Break Things

#41

Post by hershel » Sun, May 25, 2014, 3:25 PM UTC

j2kun wrote: post #39

srean wrote: post #9

A long time ago I had huge interest in genetic algorithms and on other soft optimization techniques. It is what inspired me to take up graduate studies in the first place. But very quickly I got thoroughly disillusioned by the community around it. What I am going to say is going to be very unpopular to the audience of this post. What turned me off and left a bad taste is the tendency for the community to push it as m…

I largely agree with you, but there are recent pushes to make the study of genetic algorithms (usually not stated this way) more palatable to the theory community. Look, for example, to the work of Christos Papadimitriou [1] (who is the anti snake-oil guy if I've ever seen one). He gave a talk last year at the Simons Institute on his ideas [2]. See also [3]. The essential argument of this new school is that GAs (and…

> balancing fitness and variation, so that if the environment changes drastically the entire population does not die off.

How can this property be advantageous for technological systems ?

Re: Using Genetic Algorithms to Break Things

#42

Post by j2kun » Sun, May 25, 2014, 4:05 PM UTC

srean wrote: post #40

j2kun wrote: post #39

Earlier quoted context omitted.

I largely agree with you, but there are recent pushes to make the study of genetic algorithms (usually not stated this way) more palatable to the theory community. Look, for example, to the work of Christos Papadimitriou [1] (who is the anti snake-oil guy if I've ever seen one). He gave a talk last year at the Simons Institute on his ideas [2]. See also [3]. The essential argument of this new school is that GAs (and…

Now, I am thoroughly confused. You provided (i) a link to Papadimitriou's dblp page, (ii) a link to an academic program to devise algorithms, data structures and mathematics to reconstruct and study evolution (nothing to do with GAs), a program in which Papadimitrou is involved and (iii) a survey paper on a classic optimization technique from the mid 80s known as exponentiated gradient method (alternatively called mi…

GA has nothing to do with evolution? Now I am thoroughly confused. GA is inspired by natural selection. If you program your algorithm to mimic natural selection then of course it's related to evolution, and if you don't then it's no longer a GA. Maybe your point is that the GA community has taken their snake oil so far away from this that they're not even using natural selection anymore?

If you want to study GAs, and you want to avoid the snake oil, what would you do? Selling it as studying the mathematics of natural selection seems like a good idea to me. I'm not saying that's Papadimitriou's motivation, but he does mention things like GAs in his talks.

The DBLP page has a handful of papers at the very beginning relating to this new direction. I didn't want to presume to choose one, so I linked there. But for those who don't have the time to read the titles and abstracts, here is one titled "Multiplicative updates in coordination games and the theory of evolution." [1]

Here is an excerpt:

> In this paper we provide such a demonstration; in doing so, we make some totally unexpected connections between Evolution and familiar concepts from Computation and Game Theory.

They go on to show that the natural selection occurring in some well accepted model of natural selection is equivalent to a multiplicative weight update in a coordination game. This would suggest that if we want to come up with provable guarantees for the convergence properties of GAs, we may fare better by relating their dynamics to these well-understood tools.

[1]: http://arxiv.org/abs/1208.3160

Re: Using Genetic Algorithms to Break Things

#43

Post by j2kun » Sun, May 25, 2014, 4:07 PM UTC

hershel wrote: post #41

j2kun wrote: post #39

Earlier quoted context omitted.

I largely agree with you, but there are recent pushes to make the study of genetic algorithms (usually not stated this way) more palatable to the theory community. Look, for example, to the work of Christos Papadimitriou [1] (who is the anti snake-oil guy if I've ever seen one). He gave a talk last year at the Simons Institute on his ideas [2]. See also [3]. The essential argument of this new school is that GAs (and…

> balancing fitness and variation, so that if the environment changes drastically the entire population does not die off. How can this property be advantageous for technological systems ?

If this is what GAs are doing then it would imply it's not a good technique for single-purpose optimization at all. It could be a good technique, for example, for designing robust agents to interact in some environment, such as robots walking or viruses in an unknown network.

Re: Using Genetic Algorithms to Break Things

#44

Post by fizwhiz » Sun, May 25, 2014, 7:56 PM UTC

platz wrote: post #18

fizwhiz wrote: post #10

Earlier quoted context omitted.

I definitely think that GAs can uncover a variety of bugs ranging from simple NPEs and more nuanced bugs like memory leaks (which would then required human dev intervention to investigate for a post-mortem) by dynamically generating the test-inputs. In addition to simply generating the input data, do you feel like GAs could broaden their span to essentially "mock" the states of other components in the system? I'm thi…

Also: "Genetic algorithms are not really an off-the-shelf black box that you can just plug your data into and get results." https://news.ycombinator.com/item?id=7712863

You post seems to be insinuating that we deem GAs as a panacea. No one here is saying that; to the contrary, we're just trying to see how we could use them for dynamically generating interesting test-input data. In addition to that, I'm just thinking out loud if you could possibly append to that functionality and see how to "prepare" more interesting test cases when multiple layers are involved.

No one is disputing the fact that you need an expert to tune these to get the desirable result for hard problems. I argue that having a "good enough" understanding of GAs (i.e. you don't need a PhD in the subject) should be sufficient for you to solve simpler problems such as the one we're discussing.

Do you have any counter-arguments to that? Can you cite any other examples where this view is challenged?

Re: Using Genetic Algorithms to Break Things

#45

Post by srean » Sun, May 25, 2014, 9:00 PM UTC

j2kun wrote: post #42

srean wrote: post #40

Earlier quoted context omitted.

Now, I am thoroughly confused. You provided (i) a link to Papadimitriou's dblp page, (ii) a link to an academic program to devise algorithms, data structures and mathematics to reconstruct and study evolution (nothing to do with GAs), a program in which Papadimitrou is involved and (iii) a survey paper on a classic optimization technique from the mid 80s known as exponentiated gradient method (alternatively called mi…

GA has nothing to do with evolution? Now I am thoroughly confused. GA is inspired by natural selection. If you program your algorithm to mimic natural selection then of course it's related to evolution, and if you don't then it's no longer a GA. Maybe your point is that the GA community has taken their snake oil so far away from this that they're not even using natural selection anymore? If you want to study GAs, and…

> GA has nothing to do with evolution ?

GA uses evolutionary analogies and metaphors, but that is about as much the similarity between large scale algorithms and models to explore gene and evolution data goes. So really little or no similarity between the two except for use of common words.

To put it differently that academic program is as related to GA as, imaging algorithms to explore FMRI data is related to training artificial neural networks.

However the specific paper that you point to now, and changing GA to follow the nature's model is indeed an interesting idea.