incorporating EANT and CMA-ES into breve
There is a neural net class included with breve in the SDK which lets you use a standard feed forward perceptron network.. The problem is, cool behavior with this is hard to find as the backprop learning algorithm can't deal with noisy input and gets stuck in local maxima very easily. In addition, you must figure out the structure of your neural net in advance, or else devise some method of generating and testing out populations of randomly generated structures.
EANT and CMA-ES are two recent developments that make neural nets super effective at solving controller problems- MUCH MUCH better than the standard GA used in brevecreatures, while also automating the process and generalizing it so it can be applied to a huge set of problem domains.
EANT, which was published a couple years ago by Kassahun and Siebel, evolves the structure of a neural net dynamically, using an evolutionary algorithm; then when it has a population of different structures it "exploits" each one using CMA-ES, which is a very powerful evolution strategy that works exceptionally well with noisy sensor data and high dimensionality, while simultaneously avoiding the pitfalls of local maxima/minima.
I'm posting this thread to beg JK to incorporate these into breve. It would basically make breve functional as a tool for generating robot-locomotion AI automatically. There is source code available for L-CMA-ES (a newer variant) which is very general and allows a fitness function to be dropped in. While there exists no free implementation of EANT that I can find, a description of the algorithm is available from the published papers and I'd be happy to try my shot at writing a breve class for it, although I have no development experience myself. The main distinction that EANT has to other neuroevolution methods is a linear encoding of neural nets, the ordering of which implicitly defines the shape of the network.
Combining these concepts with the automatic generation of morphology in brevecreatures would be interesting, and would make breve relevant and current with respect to advances in evolutionary algorithms and machine learning.
Thank you
Ever heard of NEAT (another
Ever heard of NEAT (another great neuroevolution algorithm)?
I've managed to bind Breve and NEAT (with arbitrary recurrent networks!). It's still a work in progress and not released yet.
It works basically making a system call to Breve and passing as parameter a neural network to be evaluated in some experiment (actually the network is dumped to a file and Breve unpickles it). An external python program (implementing NEAT) controls the genetic algorithm, so Breve is called from the inside of a fitness function.
I don't know EANT, is it efficient? Are there any papers comparing its performance against other methods?
Yes, I am familiar with
Yes, I am familiar with NEAT. Theres a comparison between NEAT and EANT in this paper: http://www.ks.informatik.uni-kiel.de/~vision/doc/Publications/nts/SiebelKassahun2006-HIS06.pdf
NEAT is good, but as a general neuroevolution method it fails on two fronts; one, the training of the weights takes place at the same time as the evolution of the net structure/topology.In this way, NEAT is a greedy search because it might pick needlessly complex, less functional and more computationally demanding organisms more than it would need to (if it instead optimized the weights first).
You can change this by changing one of the 13 parameters you need to give NEAT in every experiment, but that means theres no clear way to see which parameters fit which experiments. In contrast, EANT uses an evolution strategy that automatically adapts the parameters while evolution is in progress; this maximizes its speed while making it MUCH more general and requiring less work in picking parameters that fit your experiment.
The second way it fails is that its computationally very inefficient. On non-markovian (AKA no velocity sensor) double pole balancing, EANT is about 2-5 times as fast as NEAT in general, and the subalgorithm it uses to optimize weights (CMA-ES) is so fast it can find solutions in 1/8th the amount of CPUtime given a fixed topology.
So to conclude; its very good that you are working on NEAT and breve, but I think your efforts would be better used now adapting what you've made to incorporate some of the features of EANT, since EANT is a newer variation of neuroevolution which directly addresses the pitfalls of neat.
Other HUGE benefits of EANT
Other HUGE benefits of EANT that I can think of: the linear genome and mutation operators are PROVEN to only be capable of producing working neural nets. Not only that, but every neural net capable of existing is capable of being encoded by the linear genome. NEAT can't say the same thing and one benefit is that you don't have to put a block of code in the form of:
.
.
load sensors into net
attempt activation function
if (the net successfully relaxed to some output values)
// Good stuff
else
// uh oh we just wasted cpu time making a nonfunctional net
.
.
.
Also, CMA-ES, the component of EANT which optimizes net weights, is much more robust at traversing lumpy, rough and discontinuous fitness landscapes. It is far FAR less likely to get stuck on a local optimum and additionally it works with noisy sensor data. Speciation isn't handled with a set of additional rules, but is an inherent part of EANT's selection algorithm which operates in the structural exploration loop. Theres many many reasons to switch over.
great thread
Hey guys,
great thread. I've looked at NEAT before, but this was the first I've heard of EANT and CMA-ES.
I just read up a bit on it and it seems pretty interesting. It looks like it's hard to argue with the speed of the network training using CMA-ES, but I have to admit that from an alife perspective, I was kind of fond of the straightforward evolution in the NEAT method.
I would love to see either of these methods integrated into breve and to replace the (crappy) neural network implementation I've got now.
Cesar -- can you provide additional details on your NEAT implementation?
- jon
Hi Jon, I have a working
Hi Jon,
I have a working Python NEAT implementation at Google Code: http://code.google.com/p/neat-python
It follows from the original C++ version (but much less lines of code - thanks to Python). I hope to get it finished and released soon, so there's not documentation yet. The source code has some comments and I think that it's pretty easy to follow.
Do you remember that video I posted here last year? It was from a neat-Breve simple experiment.
I'm accepting opinions on what sort of experiments it would be nice to evolve using neat-Breve :-)
Cesar
I look forward to seeing
I look forward to seeing your completed implementation.
As far as integration with the breve engine is concerned (at least as far as official support is concerned), I'd be inclined to try the C++ version so that it can be used from all language frontends.
As far as neat-Breve experiments, I think there are a bunch! First would be to replicate something similar to Ken Stanley's NERO Game, where the game agents evolve in realtime. I'd also really like to see how NEAT-controlled agents behave in SwarmEvolve (perhaps a neural-network vs. GP matchup!?). Finally, as tripwire mentioned, it would be great to see how neural networks can be used in virtual creatures and how they compare to the (overly simple) controllers in some of the breve demos.
- jon
NEAT-Creatures
Hi Cesar,
I'm doing a class project in which I have to improve breveCreatures. One of the things that I want to do is to change breveCreatures 'brain' to a more biologically realistic approach, using for example neuroevolution. As I read the NEAT algorithm is quite interesting and I think that merging creatures with it can emerge surprising results.
Your project can actually be used to this? If not I can try to help..
Best regards,
Rui Costa
Hi Rui, Yes, that's
Hi Rui,
Yes, that's possible. We can continue our conversartion in private (got your e-mail) and if anything interesting comes out of that we can "publish" it here.
[]'s
Cesar
Hi tripwire, The paper you
Hi tripwire,
The paper you recommended does not compare NEAT and EANT actually, it only uses NEAT as a reference :-)
Although NEAT doesn't solve the conventions problem entirely, it greatly minimizes it using "valid" crossover and mutation operators. I need to know more about "linear genomes" and the operators EANT applies in order to compare.
But what do you mean by "successfully relaxed to some output"? Are you requiring the network to stabilize in some state?
Another point the authors of EANT count as an advantage over previous method is the activation of the network. In my opinion (and as far as I understand) activating the network without decoding the genome is just a question of good programming practice. Since NEAT uses direct encoding, the genotype and the phenotype represents the very same thing. You could have a method to "activate" a genotype without much effort. It is just not modular enough.
Since you mentioned the double pole balancing, do you know where I can find a published comparison? I'd really like to know more about it because I'm finishing a paper showing that when evolving CTRNNs (Continuous-time recurrent neural networks) with NEAT, it solves the double pole balancing (non-markovian) problem in significantly fewer generations than using traditional neuron models (much better than the AGE method, for instance).
When I decided to use NEAT (a while ago) it was because there were tons of information available on the Internet and lots of published papers and comparisons. In addition, NEAT has been implemented in several programming languages and has a really nice and active discussion list [1]. You could subscribe and join the discussion arguing on EANT. I'm not sure they are aware of it and that would be interesting.
But your excitement got my attention. I'm going to spend some time reading about EANT. Thanks for bringing it up.
Cesar
[1] http://www.cs.ucf.edu/~kstanley/neat.html#group
Sorry if I'm coming off as
Sorry if I'm coming off as overly preachy in regards to one neuroevolution approach over another; I was initially very interested in NEAT for the reasons cesar mentions; the depth of existing experiments and resources, papers and the numerous implementations in different languages. I tried to adapt JNEAT to a virtual controller task in an actual ragdoll physics game as I thought it would simply be a matter of plugging in some sensor values; it turns out that JNEAT was written entirely for classification problems and needed to be rewritten to work with controller problems. When I was doing this I noticed many more problems and issues with the code and doing research to try and minimize the work I was doing, I came to discover that many of the difficulties with NEAT could be bypassed with some of the features of EANT; I feel the way forward is definitely combining some of the recent advancedments in neat (for example CPPNs and HYPERNEAT) with the linear genome/cma-es optimization from EANT.
In regards to the question about a non-markovian pole balancing comparison, there is a benchmark using the original incarnation of EANT against NEAT and a couple of other methods; its from 2005 when EANT was using a standard evolution strategy for the weight adjusting; for CMA-ES, the evaluations required to reach a solution on a predefined network was dramatically lower than other methods which evolved the structure and weights simultaneously.
http://www.informatik.uni-kiel.de/reports/2005/2005_tr08.pdf
In general, EANT seems to be at least 50%
When I mentioned that a drawback to NEAT was that it can generate nets which fail; to my knowledge, the crossover and mutate operators do not guarantee that a created neural net will necessarily settle to one fixed set of output values within a reasonable timeframe; hence somewhere between 5 and 14% of a new population might have be to discarded without getting anything for them.
I'm not sure what you meant by comment about direct genome encodings being good programming practice; the linear genome in EANT could easily be adopted into NEAT and hyperNEAT since its capable of direct and indirect encodings.
I'm very interested in the idea of ragdoll physics simulations using EANT as we could actually have an automated lifelike human locomotion generator.
I am intrigued by your
I am intrigued by your description of EANT, but am not clear on some of the issues on how to get it into breve. First of all, the lack of an existing open-source implementation certainly complicates the prospect of getting it integrated into breve, even for evaluation.
Also, the "double evolution" aspect of EANT/CMA-ES seems a bit harder to fit in. Doesn't it mean lots, lots more fitness evaluations of each network for the evolving weights? For some problems these extra fitness evaluations might not be a big deal, but when dealing with simulations which may take a little while to run, it seems like it could add up.
Can you fill in some of the details of how the integration might look? Maybe using the creatures simulation as an example, you could explain how the EANT genomes would be integrated with the body genomes and how the fitness test execution would change compared to the current system.
- jon
Looking at the structure of
Looking at the structure of the breveCreatures class, I think a class which works similarly the the GeneticAlgorithm class would be the way to go. Segmentation of the EANT algorithm into subclasses seems like a good idea because of how well that works in the various implementations of NEAT. It's a pity this Nils guy isn't responding to my email about EANT because I'd kill for some source code. There is a few good CMA-ES implementations, including a C++ version called L-CMA-ES which can be computationally faster, although slightly less robust. The C++ version is very easy to plug in your own fitness functions in, so maybe its possible to have that working with breve through callbacks or something.
The way that eant needs to interface with breve is that it needs to be initialized with some starting values; it will then issue requests for the fitness value of specific organisms (genomes in this case) as per its algorithm until some end of run condition is reached (timeout or perhaps happening upon a winning solution). It's easier for me the visualize this without bothering with the evolved morphology yet, but I'll work that in, in due time.
Every time CMA-ES is called, it requires some parameters from EANT; these are the list of parameters to optimize (the connection weights), the dimensionality/number of elements in previous list (in order to calculate the required cma-es population size), and finally, the initial step size for the mutation operator.
Because of the linear genome encoding, each connection weight that we want to optimize in CMA-ES is a gene, with an associated age value that EANT tracks during the outer loop. The inverse of this age value is passed to CMA-ES as the initial mutation step size; this is to ensure that older genes are less frequently optimized which is apparently better for some reason.
Now, the paper I was reading on CMA-ES said to be aware that on multimodal functions with many dimensions, the probability of finding the global optimum in a given generation will increase sharply as the population size increases. As an example, on an 80 dimensional Rastrigin function, a population size of at least 1000 is required to ensure an 80% probability of finding a solution. In contrast, a population of 300 is required when we are dealing with 10 dimensions, and a population of 55 is required with 2 dimensions. It looks like this increase is dictated by a natural logarithmic relationship, at least from the way the one java implementation of CMA-ES calculates the required population size from the number of dimensions.
Since the dimensionality of our search space is actually the same as the size of the linear genome we are optimizing, as our genomes get bigger, the required evaluations will also increase nonlinearly; this effect will taper off as the structural exploration progresses, doubly so as structural exploration tends to decrease in speed later on anyway. In order to avoid having to find the right population value for each problem, CMAES calculates an initial population size equal to the integer value of 4+3 * the number of parameters. When a certain amount of generations have passed without any reduction in fitness, CMAES can be told to restart with double the population size. By doubling the population size every failure, there is an upper bound on the number of restarts required to find the global optimum a given percentage of the time, if it exists. Ideally, with a bit of testing or some prior experience with the problem at hand, the population size can be picked to suit the dimensionality and landscape of the problem; this might require more work but would reduce wasted time spent on evaluations during runs that uselessly plateau. Some 100-dimensional multimodal functions need populations in the thousands in order to guarantee high likelihood of finding the global optimum, but I think interesting behavior could be achieved in breve with child populations of much less, perhaps maximum 100 and favoring amounts closer to 10.
Lets assume the computationally worst scenario: for every CMAES call, the genomes were of the maximum size specified for consideration on our experiment (lets say a reasonable number here is 100 genes). The population size would initialize to 18 and it would likely double to 36, then 72, and maybe 144 as well, if our problem was complex enough. To simplify our estimate of how many evaluations we need, lets just fix the internal population size at 100. The limit on generations for CMAES used in the EANT visual servoing task presented in the previously linked paper was established at 500. The outer population size used was 30. Additionally, EANT was configured to perform 2 parallel CMAES optimizations for each genome and pick the better. Finally, for each parent organism in the outer loop, 2 child organisms are created through though mutate operator (and subsequently evaluated).
Thus an upper bound on the number of evaluations (individual breve fitness tests) required to find a global optimum to a locomotion problem using similar parameters as established in the previously linked paper can be given as:
(outerPopulationSize)(#ofOuterGenerations)(#ofOffspring)(#ofParallelEvaluations)(innerPopulationSize)(max#ofInnerGenerations)
= (#ofOuterGenerations)(30)(2)(2)(100)(500)
= 6 million evaluations for every structural exploration generation.
I realize this is a pretty intimidating number, but hopefully theres other ways to speed it up as well.
What we REALLY need is some way to make this process distributable so that work can be farmed out to hundreds of computers on a network, or to internet suscribers asynchronously as a screensaver, ala electric sheep.
The only reason why breveCreatures showed improvement in the comparative short term (perhaps a few hours of running) is because its search space was very constrained; it didn't show any improvement in the longterm because the mutate/crossover operators did not produce children with comparable fitness to their parents- there was only a very weak gradient descent method being applied to a problem space which was dramatically altering every step as morphology changed. In all my many many many trials of tweaking and running it I've always had it hit local optima, exploit granularity/inaccuracy in the physics engine to get cheating solutions, or bug out and fly into the void, getting a fitness of NaN. Granted, 50 000 fitness tests is a damn sight short of some multiple of 6 million, but the results are not going to be comparable either.
I'm really tired; sorry for rampant spelling mistakes/abandoned sentence fragments
googling for CMA-ES
Hi all
By googling on cma-es I have fund this
http://www.bionik.tu-berlin.de/user/niko/cmaesintro.html
It has a lot of links to the subject you are discussing.
Costas
Nice!
Hi tripwire,
I've just read the main points about EANT (from that technical report) and it seems to be really interesting.
Although the report is from 2005, they used an outdated result from NEAT's double-pole experiment (from 2002). In 2003 Gomez (as described in Stanley's thesis) showed that it's actually better.
It deserves more attention and I should take a closer look at it later.
Thanks,
Cesar
Note about reversed fitness conventions
Word up: for some reason, all these different genetic/evo algorithms use different conventions for fitness; in EANT/CMAES the fitness gets better as it gets closer to 0; in the standard breveCreatures GA fitness gets better as it gets higher.
This might clear up some confusion.
I heard back from Nils Siebel (worked on EANT)
He said that the EANT codebase is currently undergoing some refactoring and cleanup, and that they won't be releasing the current version of EANT because they feel it isn't much use to the community (apparently a lot of the code was for testing purposes and is unlikely to be used by people other than the original eant developers).
This is a pity because I'd really like to get cracking on trying to adapt cesarg's python code to incorporate some EANT features- theres nothing really stopping me from doing this now except reluctance to spend a huge amount of time developing, testing, and refining a product from scratch when someone has spent years perfecting this same product.
Keep us up to date with
Keep us up to date with their progress, and feel free to mention to them how powerful it would be to get their code (in whatever condition) integrated into breve -- that might entice them to release whatever they have.
- jon