Evolvable Substrate

[Scott H.]

Great news about adding the Novelty Search. I had put my own together but it was very solution dependent. I'll check this one out.

I've also been reading on Evolvable Substrates (http://eplex.cs.ucf.edu/ESHyperNEAT/). Their implementation is based on an older version SharpNeat but I'm having a bit of time trying to port it to the current version. Has anyone else already done this? If so, would you share?

Thanks,

Scott

[Keith Nelson]

Hi Scott,
   A couple of months ago I talked with Sebastian Risi about converting his code located (at http://eplex.cs.ucf.edu/ESHyperNEAT/#implementations) to the current version and releasing it for SharpNeat users to play with, and he was quite happy to see that happen. Unfortunately I have not had much spare time to dedicate to the task (as I am sure your finding out, it requires a bit of time to convert). 
If you have any specific conversion tasks/problems perhaps post them here, I know I´d try and help out anyway I could. It would be great to have a HyperNeat Evolvable Substrate implementation for SN to play with!

Cheers,
Keith

[Scott H.]

Hi, Keith,

Thanks for the note. I've made good progress creating an EvolvableSubstrate class (and its dependents), adapting Sebastian's code to return an INetworkDefinition. Basically, my goal was to create a class that resembles the one in Substrate.cs except that it would create the hidden layer's substrate via the ES-HyperNeat algorithm instead of specifying it explicitly as HyperNeat requires. I should finish up shortly but have a questions/issues:

1. Sebastian's code do not make use of a bias node. This may be by design but I thought I'd check to make sure. 

2. The Substrate.cs definition has a public property, NodeSetList. This property makes sense for HyperNeat where all substrate nodes are known from the start. In ESHyperNeat the hidden layer's substrate nodes would be created in the call to CreateNetworkDefinition. If EvolvableSubstrate is to support that property then either it must throw an InvalidOperationException (since the actual NodeSetList cannot be known generically) or it should return a NodeSetList with just the input and output layers' substrate nodes. Do you have a preference?

3. The CreateNetworkDefinition method takes as a parameter lengthCppnInput. Since this doesn't map to a set of coordinates I'm not sure how to include that in the ESHyperNeat version. 

-Scott

[Keith Nelson]

Hi Scott,
   Excellent news your port is going well. The 2012/2010 papers on ES-HyperNeat method show a bias node being used, so it is strange it is not in the code; perhaps Sebastian can weigh in on what is happening there (I sent him a heads up to this thread). On #2 I would lean towards InvalidOperationException unless there was some good reason not to. #3 LengthCppnInput certainly appears to make a big difference on the boxes test domain, but if there is no clear way to include it perhaps it is not worth worrying too much at this point.

Sorry I can´t be more help!

Look forward to help testing out the code.

Regards,
Keith

[Sebastian Risi]

Hi Scott,

I'm excited to hear that you're porting ES-HyperNEAT to the new SharpNEAT and would be happy to answer any questions that you might have. About questions 1 and 3:

1. Sebastian's code do not make use of a bias node. This may be by design but I thought I'd check to make sure. 

- Do you mean a bias for the CPPN or the substrate (i.e ANN)? Keith is correct that the CPPN has a bias but the current implementation doesn't make use of a bias node for the ANN. It didn't seem necessary for the task but it was definitely something I wanted to add at some point. You could add bias values by node-centric CPPN queries with the location of the discovered hidden neurons (e.g. CPPN(x, y, 0, 0)). This is similar to the way we normally do it in HyperNEAT (http://eplex.cs.ucf.edu/hyperNEATpage/HyperNEAT.html). Or you could add an additional ANN bias input that would be located somewhere on the substrate.

3. The CreateNetworkDefinition method takes as a parameter lengthCppnInput. Since this doesn't map to a set of coordinates I'm not sure how to include that in the ESHyperNeat version

- In the queryCPPN function in EvolvableSubstrate.cs you could add the length of the connection as an additional parameter (e.g  coordinates[4] = length of connection). Does that clarify your question?

I hope that helps. Please let me know if you have any other questions.

Sebastian

[Scott H.]

Hi, Sebastian (and everyone else),

I've had quite a bit of fun moving your code into the SharpNEAT 2 framework. I've attached the files of my attempt to get the group's feedback. I've plugged it into the WalkerBox2DExperiment and saw some improvement. But I think I've looked at it too closely for too long to see any remaining errors. Here are the big changes:

• Changed the datatypes from float to double. This required creating a PointD struct to mimic your use of PointF (quite a clever appropriation of that struct, btw).
• Employing your algorithm within the public method's of Collin's Substrate class. In other words, having the same method signatures (used an interface) returning an INetworkDefinition instead of passing back out a ConnectionGeneList. Most things fit nicely, some had to be changed a bit more.
• Use of an IDictionary<PointD, NetworkNode> collection to keep the network nodes associated with the position of the substrate node. Your ConnectionGene stores the position internally.

I appreciate Keith's and your feedback to my questions but I chose to leave the ANN's bias node and the lengthCppnInput out of this version. Probably best to make sure it does what you expect for expanding it to match Substrate.cs.

Two more notes:

• The pseudo code in the paper has a comment about removing connections that are not part of a path from input to output. Your algorithm prevents the case where the input to hidden connection could be orphaned but does allow for some hidden nodes to never connect to a path to an output node. Everything runs fine of course, just maybe a few more calculations that never get used. I put in a method that removes these connections but it was such a performance hit that I commented out the method call.
• I have begun working on a version that moves beyond a QuadPoint (divides into squares) to a multi-dimensional one, MDPoint, (divides into squares, cubes, etc.). It compiles but I haven't had a chance to swap it out with the EvolvableSubstrate and test it. Still, I'm attaching it (EvolvableSubstrateMD.cs) to get your feedback.

-Scott

[Scott H.]

Earlier I had asked a question (#3) about using the lengthCppnInput parameter and my solution was to ignore it. The problem is that I completely missed the point of that parameter when I first read the Substrate.cs code and then never looked back. Short version: I took it to be part of the ANN instead of the CPPN. Anyway, here's a new version of the EvolvableSubstrate (and EvolvableSubstrateMD) classes which use the lengthCppnInput like the original Substrate.cs code does. Sorry for the confusion.

[Sebastian Risi]

Hi Scott,

I'm glad that converting the code wasn't to painful. Do you already have a way of visualizing the resulting substrates? I think that would help a lot in debugging the system. If you load the same genome in both systems, the substrates it produces should look identical (given that both systems use the same bias setup and CPPN input setup).

About the connection pruning. In the method "generateHomogeneousGenomeES" in the SubstrateDescription class, the algorithm actually performs some band pruning. At some point I planned to also move that method to the EvolvableSubstrate class but haven't gotten around to it yet.

Making the class more general with the potential to move beyond QuadPoints sounds like a very interesting idea.  I will take a look at the EvolvableSubstrateMD class and see if I have some useful feedback.

Sebastian

[Keith Nelson]

Hi Scott,
   Excellent work on the EvolvableSubstrate port - just getting a chance to play with it now (just back from vacations). Will post any feedback if I find anything to comment on. Colin, is there any chance this will find it´s way into the main release?

Keith

[Colin Green]

Hi all,

Regarding merging Scott's code into the main SharpNeat code. It's
certainly something I'm happy to do, it's just a matter of finding the
time to read the code, make sure I understand it fully and deciding
where it fits in structurally with everything else, both existing and
going forward. Right now I have very limited time to work on
SharpNeat, so I'm just happy for everyone to share code here and
elsewhere for now. But yes I am intending to 'hoover up' other's work
as and when I get time.

Thanks.

BTW I noticed a comment in a previous email about using dictionaries
of points and wanted to point out that performance of dictionaries
using cartesian points as a key can be poor. You may get a boost in
performance by switching the hash function to:

hash = x.GetHashCode() + (y.GetHashCode() * 17)

Instead of the existing:

hash = x.GetHashCode() + y.GetHashCode()


I could go into detail, or you could just me on this one :)

Colin.

[Keith Nelson]

Hello All,
    I finally got a chance to play properly with Scott's code and have posted some code additions below. I decided to post the whole solution as there are a lot of little changes but have included subversion folders so it is easy to diff for the changes.

ES Hyperneat related Additions:
    - Visualise Hyperneat Substrates via Menu "View -> Best Genome Substrate". Uses new IGuiNeatExperiment::CreateSubstrateView(); interface. I tested on 2D and 3D substrates but should work (more or less) in higher dimensions as well.
    - Added Bias node to substrates generated by ES Hyperneat/MD (see two loops below comment "// Additionally we create connections from each hidden and output node to a bias node").

Scott I noticed that your code did not filter connections out if (weightAbs > _weightThreshold).  Not sure if this is by design? I threw the filters back in for testing so if it should not be there please let me know.

Novelty Search related additions:
    I hijacked the EvaluationInfo.AuxFitnessArr to store actual "traditional" fitness values (as opposed to EvaluationInfo.Fitness which is the novelty score).  To maintain a list of best actual traditional fitness scoring genomes over all generations, I slightly modified AbstractGenerationalAlgorithm and NeatEvolutionAlgorithm to maintain "_genomeListAlternative" (related properties "CurrentAlternativeChampGenome" and "GenomeListAlternativeChamps") which store actual highest fitness genomes.
    For an experiment to support novelty searches I have added two new NeatEvolutionAlgorithmParameters "UseAltFitness" bool and "AlternativeCount" int. In addition a Novelty project must also define "delegate(int _selectCount, IList<NeatGenome> _genomeListAlternative, IList<NeatGenome> _genomeListCurrent)" passed into the NeatEvolutionAlgorithm constructor. This delegate is where the experiment specific code goes to maintain the genomeListAlternative best traditional fitness genomes after every generation.
    When novelty search project is running, the main interface "Current Stats" -> "Alternative Best Fitness" field shows the CurrentAlternativeChampGenome AuxFitnessArr[0] value, which is more useful to watch than the scrolling textbox bestFitness novelty score values. View Best Genome/Substrate and problem domain forms also display the CurrentAlternativeChampGenome.
    Overall probably not the most elegant solution but it seemed to be the easiest way to implement Novelty searches in SharpNeat with very minimal changes. Have had some success using Novelty search it does look promising method to bypass local maximum fitness traps altogether.

All the above code changes are demonstrated in four new experiments under SharpNeatDomainsExtra/WalkerBox2d, where I also added my NoveltyKNN class which works fairly well for 1-3 dimensional novelty behaviours and can adaptively adjust it´s archive rates as more evaluations are performed.

Comments and feedback appreciated. Colin I am happy for any or all parts of the code to be rolled into SharpNeat as you see fit. Almost forgot, there is also a box2D cleanup bug fix: "openGlControl.DestroyContexts()" - one of my two computers blue screened unless this was in the code for some unknown reason - probably graphics card related.

Regards,
Keith