Using Genetic Algorithms to Break Things
westleyargentum.github.io
westleyargentum.github.io
You want to evolve a controller for a robot that walks far, it will find exploits in the physics engine that defy gravity or somehow catapult the robot through the air (this sort of exploit is the bane of those doing research in virtual creatures [1]). You want to evolve a talented player for an atari game like beamrider, and evolution will find an infinite score-loop exploit [2]. It's meeting the letter of the law in maximizing your measure, but it's missing the forest for the trees.
This kind of problem has led some in the community to look at driving evolution by other means -- e.g. my dissertation was on evolving neural network controls for robots by choosing the most novel behaviors instead of those that performed the best by the fitness measure [3].
[1] https://archive.org/details/sims_evolved_virtual_creatures_1...
You had something particular in mind when you set the objective function for your biped robot to be distance travelled before it falls. Finding an exploit in the underlying physics engine that allows the biped to explode and travel quite far -- while indeed excelling at the function, is far from what you had in mind. Yet it does reveal a vulnerability in your physics engine, which while unexpected, may be valuable in its own right, as the application the post's author argues.
This isn't entirely unique to EAs -- but it seems to happen more frequently in the kinds of domains EAs are often applied to -- complex simulations where the gradient of an objective function is difficult or impossible to calculate.
if validation were performed the population would not evolve into the cracks of unlikely physics loop holes.
So those are "overfitting" for the exact quirks of the engine. I agree, it's a stretch, but not unlike in ML, it shows that optimizing too much will show quirks if your 'objective function/simulation' pair is not exactly equal to the 'desired objective function/reality', or if there is an innumerable ensemble of situations you might expect the solution to behave well.
That means we're getting there. This sounds like any toddler that I've ever met!
The reason why this stuff works, is that there are almost always lots of bugs out there, and that RNGs aren't subject to the misconceptions programmers are subject to. It's also why fuzzing works.
I could see GAs doing very well with this.
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 thinking of a case where you have some set of services deployed on different machines that communicate with each other. In theory, could we have the GA "mock/simulate" a network jitter sporadically (thus intercepting a request from ServiceA to ServiceB and deliberately dropping it)? This extends beyond the input data for some entry point at ServiceA, and instead encapsulates some sort of an "ether" surrounding all the components. Every permutation and combination of the subsytem state could in theory be controlled by the governing GA.
If someone actually built a DSL/library that handled these things I'm sure it would benefit everybody in a remarkable way.
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?
Skiena in The Algorithm Design Manual, at the end of the three-paragraph blurb where he talks about them.
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 magic, much like what a shady snake oil salesmen would do.
Rather than building the theory on analysis, classification and measurable properties and definitions of objective functions for which GA with specific mutation and crossover operators are a good solution, the way of the community is to push it as snake oil. Often taking examples of cooked up functions that arent really important to globally optimize over and totally ignoring speed of optimization with other competing tools.
The method of choice of the community seemed to impress the audience, not with how fast and effective the methods are compared to the traditional, but with colorful analogies. Heck, a bead of perspiration rolling down an armpit optimizes a function, that does not mean that is how we should optimize any function on a computer that way.
This is really unfortunate, because if one goes back to GA's genesis, classifying and characterizing functions that yield themselves to GA was a big part of David Goldberg's book. There are indeed functions that are very amenable to GA and other such methods. Characterize them mathematically, rather than what seems to me, cook up two adhoc operations name them 'crossover' and 'mutation' and look cool.
That is hardly progress.
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.
I will give you a specific example of what I think is a better way. Consider the clustering algorithm K-means. Obtaining its global minimum is an NP hard problem and has been a target for GA, ant colony, swarm optimization and what have you. All of them are blown way off the park by simply better initialization of the standard K-means algorithm. For example just initialize it with a set of furthest first points and it will give good results. Not only that, it will provably be very close to the global optimization, but people did not know that in the beginning. Some people had to say to themselves "I am going to find out more about the structure of the problem so that I can find efficient methods". These make progress.
Take another example, non-negative matrix factorization: another objective function that is NP hard to optimize. I will make a different point with this example (although the same point could be made with the k-means example). The cases where the simple local algorithm for NMF does not converge to near global optimization are provably uninteresting to begin with. Even if the global optimum was indeed found, it would serve no purpose.
Another example global optimization of low rank matrix factorization models for recommender system, same problem again, optimal solution NP hard to obtain. Again simple methods do provably well if you utilize the structure of the problem.
Often the difficult function that one is trying to optimize can be entirely circumvented by modeling the phenomena with a better behaved function, model the problem differently so that better techniques apply. This not always possible, but I see people not even trying, apparently it is easier to publish a few papers when you spray it with colorful analogies. An example: protein folding. It is an misguided effort to find the globally optimized shape, nature does not fold proteins optimally.
Another example: consider classifiers. Misclassification as a function is the worst nightmare, non differentiable, nonconvex, with huge swaths of zero gradient. So what do people in machine learning do, bound it on top by a well behaved function and optimize that function. They dont stop there. They first validate empirically that optimizing the surrogate has good performance and then prove theoretically that this comes with guarantees on performance.
I am more convinced that analyzing important objective functions (that are important to optimize), studying their properties and motivating performant optimizations schemes is a far better contribution than coming up with colorful analogies of genetics, evolution, swarms etc without characterizing precisely what it is that makes it work and when. Demystify the problem and the technique rather than mystify and please compare running times and resources with more traditional optimization.
Again, I am not saying that GA, or swarm optimization methods are wrong to use. There are indeed cases where it is exactly the correct thing to use. Consider gene/dna assembly, here GA is indeed the right thing to use. GA works well when the optimal solution looks like assembly of small good solutions. Swarm works well when the optimization function looks like a smooth well behaved function overlayed with a high frequency fluctuation. I wish this is what the community focused on.
In my opinion, EAs are most useful when you don't have a more specific human-fit algorithm to solve a problem, and particularly when a gradient to your objective function cannot be calculated. For example, when you are trying to create a controller for a many-jointed robot in a complex simulation with a high-level objective function.
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 want to optimize. I want them to offer principled guidelines that would allow generalizing the techniques beyond anecdotes. I have no problems with communities pushing their technique, to the contrary, my disenchantment is with them not doing this.
I want the community to produce re-usable pieces of interesting/novel information that I can use when I am faced with optimizing a function.
You mentioned non-differentiable functions. Now lets take a look at a subclass of these functions: convex non-differentiable functions. There are very efficient methods for these.
Consider another class, lets throw away convexity, consider functions that are non-differentiable and very rough locally but when filtered with a low pass filter is well behaved. Then again we know what to do.
Consider functions that are difference of potentially non differentiable convex functions (this is a Huge class. The difference need neither be differentiable, nor be convex), then again we have good ideas about what to do.
I think building this decision function: Problem_type -> preferred_algorithm is a very useful exercise. What annoys me is that GA community seems not to be interested in this, and take cheap shots by presenting anecdotes.
Prove properties, of your techniques, I will buy them by the bagful.
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."
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.
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 random numbers.
But this kind of totally random functions pretty much do not exist in the real world. So if out objective function came from the real application (and not from a random number generator), we already know enough about it that we can say that the NFL theorems don't apply to it.
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.
> 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.
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)
>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.
EDIT: replaced 'you' with 'proponent' lest it gives the impression that I meant it personally.
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.
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
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.
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.
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.
How can this property be advantageous for technological systems ?
I highly recommend the hard copy
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.)
An aside, for things like unit tests where in most cases the result of the test is binary i.e fail/pass. How do you think about and ultimately represent the fitness criteria.