Using Genetic Algorithms to Break Things • Hacker News Board

Re: Using Genetic Algorithms to Break Things

#31

Post by Dn_Ab » Sun, May 25, 2014, 9:52 AM UTC

srean wrote: post #27

sampo wrote: post #24

Earlier quoted context omitted.

> If nothing is known about the objective function What that "nothing is known" means, in the context of NFL theorems, is that values at each point are random, and independent of values at other points. For example, if our domain is a 100-by-100 grid, and we fill the grid with random numbers, now we have such a function. And indeed, no optimization function is of any help in trying to find the largest of the 10 000 r…

Sure, no particular instance of a function will be so utterly random, but I think you are probably missing the point of the parent comment. All that NFL says is that if you fix an optimization algorithm and average its performance over all possible measurable functions, no algorithm will be better than the other. The average is with respect to the distribution you described. However, if you skew the distribution so t…

The bias is not magical at all if it is against complexity - it's what underpins occam's razor.

Re: Using Genetic Algorithms to Break Things

#32

Post by sampo » Sun, May 25, 2014, 10:47 AM UTC

srean wrote: post #27

sampo wrote: post #24

Earlier quoted context omitted.

> If nothing is known about the objective function What that "nothing is known" means, in the context of NFL theorems, is that values at each point are random, and independent of values at other points. For example, if our domain is a 100-by-100 grid, and we fill the grid with random numbers, now we have such a function. And indeed, no optimization function is of any help in trying to find the largest of the 10 000 r…

Sure, no particular instance of a function will be so utterly random, but I think you are probably missing the point of the parent comment. All that NFL says is that if you fix an optimization algorithm and average its performance over all possible measurable functions, no algorithm will be better than the other. The average is with respect to the distribution you described. However, if you skew the distribution so t…

> All that NFL says is that if you fix an optimization algorithm and average its performance over all possible measurable functions, no algorithm will be better than the other.

> Therefore, trying to design a fully generic optimization algorithm is a fool's errand.

I don't think we have any factual disagreement. In pure mathematical context, what you say is absolutely true.

I just wish to emphasize, that "all possible measurable functions" and "fully generic optimization algorithm" have very specific mathematical meanings here, and those meaning are probably different than what a casual reader might expect.

In a set of "all possible functions" an overwhelming majority are functions that are indistinguishable from random noise. They are e.g. not continuous, not even remotely like continuous, they have no structure at all whatsoever.

On an intuitive level, everybody understands that it is a fool's errand to try to design an optimization algorithm to find the maximum from an array of random numbers. But when you just say "trying to design a fully generic optimization algorithm", people may not realize that the "fully generic" contains the requirement that it should also work on random noise.

The No Free Lunch Theorem does not say anything about the feasibility of fully generic optimization algorithms, if we restrict the "fully generic" to mean anything that can be expected to appear in any real world application. A lot of people might agree that an algorithm that performs well in any real world problem is "fully generic", even though it may not perform well in all imaginable abstract mathematical settings (which mostly means settings of random noise).

To your last comment: I also agree with you on this front. Also my understanding is that for every or almost every type of problem there are other optimization algorithms that drastically outperform genetic algorithms. I also like your "snake oil" metaphor, and I was happy to see your top comment on this topic.

Re: Using Genetic Algorithms to Break Things

#33

Post by [deleted] » Sun, May 25, 2014, 11:05 AM UTC

srean wrote: post #27

sampo wrote: post #24

Earlier quoted context omitted.

> If nothing is known about the objective function What that "nothing is known" means, in the context of NFL theorems, is that values at each point are random, and independent of values at other points. For example, if our domain is a 100-by-100 grid, and we fill the grid with random numbers, now we have such a function. And indeed, no optimization function is of any help in trying to find the largest of the 10 000 r…

Sure, no particular instance of a function will be so utterly random, but I think you are probably missing the point of the parent comment. All that NFL says is that if you fix an optimization algorithm and average its performance over all possible measurable functions, no algorithm will be better than the other. The average is with respect to the distribution you described. However, if you skew the distribution so t…

[deleted]

Re: Using Genetic Algorithms to Break Things

#34

Post by rainforest » Sun, May 25, 2014, 11:28 AM UTC

kordless wrote: post #22

stcredzero wrote: post #4

Thomas Ray, who wrote the A-Life program Tierra found that genetic algorithms were really good at finding bugs in his code and exploiting them. One bug where that happened was a register he forgot to clear between simulated viruses. A virus evolved to exploit the data and use it to attack other viruses.

We should put them to work finding bugs in code. Breed one to click buttons and fill in webforms...and it gets to replicate when it breaks things.

EvoSuite springs to mind for that one [1]. Java only though, but their publications describe how it works well enough to port the ideas from what I can tell.

[1]: http://www.evosuite.org

Re: Using Genetic Algorithms to Break Things

#35

Post by kriro » Sun, May 25, 2014, 12:02 PM UTC

I think the best use of GAs is sort of rapid prototyping. Throw them at the problem to get a better feel for the search space then think about it deeper and find the best algorithm you can come up with.

With the appropriate disclaimers that there's usually better algorithms I think they are pretty valuable from a pedagogical point of view (actually I'm thinking more of nature inspired algorithms in general not just GAs). It helps if you can relate an algorithm to something in nature because most algorithms are very abstract and hard to grasp. I also think nature inspired algorithms can help people think about problem solving in creative ways (just wander through your garden and see if you can replicate some of the stuff in algorithmic form etc.)

Re: Using Genetic Algorithms to Break Things

#36

Post by tripzilch » Sun, May 25, 2014, 12:42 PM UTC

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…

Thank you for writing this. I'm upvoting the story in hopes that more people read this comment :)

Re: Using Genetic Algorithms to Break Things

#37

Post by unstabilo » Sun, May 25, 2014, 1:51 PM UTC

srean wrote: post #15

jal278 wrote: post #12

Earlier quoted context omitted.

I'm not sure that the phenomenon you've encountered is unique to the evolutionary computation community: If you go to an academic conference dedicated to specific methodology, because the attendees have a vested interest in that methodology (they may have built their career on it), that hammer will certainly end up finding many questionable 'nails'. In my opinion, EAs are most useful when you don't have a more specif…

Thank you for your comment, hope I am not being too harsh, I just have been very peeved by my experience. The downvotes are already here, not unexpected. From my experience, and this was a while ago so I will be glad if this has changed, it seems that the community prefers to push their techniques as snake oil and not try to nail down the characteristics of their techniques and show how to match it with a function I…

Maybe not exactly what you want, but this book has some useful information: http://cleveralgorithms.com/nature-inspired/index.html .

Check out the "Heuristics" subtitle of the algorithms. For example,

"Differential evolution was designed for nonlinear, non-differentiable continuous function optimization."

"NSGA was designed for and is suited to continuous function multiple objective optimization problem instances."

Re: Using Genetic Algorithms to Break Things

#38

Post by Houshalter » Sun, May 25, 2014, 1:58 PM UTC

srean wrote: post #30

Houshalter wrote: post #25

Earlier quoted context omitted.

Metaheuristics are blind methods that make very few assumptions about the structure of the solution space. If you already know some of the structure of course you can find a better optimization algorithm. Better yet, you can find a better representation or mutation function that will massively shrink the search space. Or a fitness function more likely to lead evolution through the correct path. Or even seed solutions…

With apologies, if a proponent of an algorithm cannot tell me under what circumstances the proposed algorithm would do better, the proponent is selling me snake oil. There has to be some quantitative statements about their properties, not necessarily proof of convergence to the global optimum. Otherwise it is not science, (yet). Its not an understanding of the space of an arbitrary problem that I desire, it is a meas…

We do know what kinds of situations genetic algorithms do well at (though generally other metaheuristics like hillclimbing do slightly better.) The fitness landscape has to be as smooth as possible and not have bad local optima. You want as few variables as possible. And you want them to be independently correlated with fitness. If an improvement requires multiple things to mutate all at once it's unlikely to happen.

There are various other heuristics. But you definitely need to have an understanding of the solution space (as well as the alternative) to know for sure.

Re: Using Genetic Algorithms to Break Things

#39

Post by j2kun » Sun, May 25, 2014, 2:46 PM UTC

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 evolution in general) do not try to find the optimal individual. Here is a reader's digest argument as to why: say you had actually achieved the perfect individual, then sex would result in imperfect children while the parents die off. So if evolution isn't optimizing fitness, what is it optimizing? One hypothesis is that it's balancing fitness and variation, so that if the environment changes drastically the entire population does not die off.

[Edit: another note to add] And there is a common adage in CS theory that for every problem, a focused gradient descent algorithm (using knowledge about the optimization function, domain, etc.) will always outperform GA. So this is a sort of meta-theorem that says asexual reproduction is better at finding the optimal individual than sexual reproduction.

There are concrete techniques being analyzed in this context, for example the "Multiplicative Weights Update Algorithm," which has been proven to perform well against adversarial manipulations of the environment. See [4] for a long and detailed reference of its applications to classical CS problems.

[1]: http://www.informatik.uni-trier.de/~ley/pers/hd/p/Papadimitr... [2]: https://www.youtube.com/watch?v=cWv-s6KuDlM [3]: http://simons.berkeley.edu/programs/evolution2014 [4]: https://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf

Re: Using Genetic Algorithms to Break Things

#40

Post by srean » Sun, May 25, 2014, 3:23 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…

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 mirror descent, Bregman proximal gradient method, multiplicative update method), again nothing to do with GAs. Apparently it all connects to GAs, but how it does so totally eludes me :)

GA is not natural evolution, GA does whatever it is programed to do by whoever wrote the code for it. The program that you pointed to is about using CS techniques to analyze huge amounts of natural evolution related data (by the terrabytes) to make sense out of it.

I have not watched the video yet, so it is possible I am missing something, I must be.