SharpNEAT F.A.Q.

 

1. Introduction to NEAT

1.1 What is NEAT?

NEAT is Neuro-Evolution of Augmenting Topologies, a neuro-evolution technique devised by Kenneth Stanley while part of the Neural Networks Research Group, University of Texas at Austin. Go to http://www.cs.utexas.edu/users/kstanley/ for more info including research papers, links to software downloads, source code, a FAQ and an active discussion group. Apart from SharpNEAT a number of other implementations exist and are available for download, including Kenneth Stanley's original C/C++ source code and implementations in Java , C++/Windows, Delphi and Matlab.

1.2 What is Neuro-Evolution?

Very simply, neuro-evolution is the evolution of Artificial Neural Networks (ANN's), and in the case of NEAT this means the evolution of both connection weights and network structure, thus NEAT is a Topology and Weight Evolving Artificial Neural Network (TWEANN) strategy.

Traditionally the most common technique of devising a complete working neural network is to use back propagation, with this technique a fixed starting structure (some use the term topology or architecture) of neurons and their interconnections is pre-defined by a person, the back propagation algorithm is then applied to find a set of connection weights that describe whatever functionality is being sought. Back propagation (backprop for short) works very well but has some limitations, the first is that the experimenter must decide on a network structure before running the backprop algorithm, this is mostly done by researching the structures that others have used in the past, along with some trial and error - perhaps a lot depending on whether your problem domain is similar to domains that have already been investigated.

Another problem is that back propagation is what is known as a supervised training technique. This means that in order to run the backprop algorithm we must supply it with training data in the form of a set of input patterns - that we apply to the input nodes of a network - and a set of output patterns that are the 'correct' response for each input pattern. The backprop algorithm can then use the difference between the actual answer with the expected answer to modify the connection weights, hopefully towards describing the desired functionality. However, some problems do not lend themselves to this approach, e.g. consider trying to find a network that can play chess, with backprop we would need to supply a large set of board states and the 'correct' move to make for each state. The number of board states would probably have to be very large in order to instill in the network enough knowledge about chess, this problem can be alleviated by carefully selecting training data so that we only include one test case from a set of cases that are very similar. A more fundamental problem is producing a training set in the first place, in a game of chess it is not normally possible to say whether a move is wrong or right, it depends on the strategies that each of the players are using, and these strategies change throughout a game. So there exists a set of problem domains for which we cannot sensibly provide training data of the kind required to run back propagation, and in fact most real world problems fall into this category.

Neuro-evolution then, short-cuts the need to provide both training data or a pre-determined network structure. Typically a NEAT search will begin with a minimal network structure and use the process of evolution to search through different structures and connection weights. To evaluate a network's fitness or how good a network is at a problem task we now have a choice, we can use training sets in the same way as back propagation, or we can let the network perform the task it was designed for, e.g. play a game of chess, and evaluate how well it performs the task. So we might let the network play 10 games of chess and allocate it a score based on the number of wins, draws and losses. This same approach can be used in a wide range of problem domains including game playing, vehicle controllers, stock market prediction, artificial life simulations, etc.

Of course back propagation is not the only traditional technique that can be used to discover neural networks, however, neuro-evolution is the only truly general purpose approach that can be applied to any problem within reason, given enough CPU time and a means of evaluating the evolved networks. It is an extremely simple and potentially an extremely powerful technique.

1.3 What types of problem is NEAT applicable to?

There is no definitive answer here as research into NEAT is ongoing and there have been varying degrees of success reported. Significant problem domains that I know of for which good or near-perfect solutions have been found are; Single and Double Pole Balancing, Finless Rocket Control, Prey Capture, The 3/6 and 11-Multiplexer logic problems and Pattern classification. Note however that a significant number of problems do not have a 'perfect' solution as such, just good and bad solutions. E.g. in game playing experiments it is common to use co-evolution where fitness is evaluated by networks competing against each other, the fitness scores are therefore only indications of relative fitness not overall ability to play a game.

One very basic requirement when considering an experiment is that a fast method of evaluating fitness must be available for the problem at hand. This is so that NEAT can evaluate as many candidate networks as possible within a given time period. The more evaluations that can be performed the greater the probability of finding a good solution. e.g. if the fitness function is a mathematical equation or if it involves playing a short/fast game(such as tic-tac-toe) entirely within code, then we can evaluate networks very quickly and therefore evaluate a large number of networks in a given period. If however the fitness function requires interaction with a person or some physical system external to the CPU then the chances are that not enough evaluations can be performed for NEAT to be successful within a reasonable amount of time. However there may be exceptions to even this rule, if say a very simple topology is capable of solving a problem then it may be discoverable within very few evaluations.

To obtain a more full idea of what NEAT is capable of take a look at some of the published work from the Neural Networks Research Group at the University of Texas at Austin and more recently the Evolutionary Complexity Research Group at the University of Central Florida.

 

2. Introduction to SharpNEAT

2.1 What is SharpNEAT?

SharpNEAT is an implementation of NEAT written solely in C# (pronounced 'see sharp') and targeting the Microsoft dotNet Language runtime and class framework. Currently it consists of a library DLL and an executable/GUI front-end for easy starting and monitoring of experiments. There also exists seperate EXEs for viewing saved networks and for visualising the simulation of some of the experiments.

2.2 How did SharpNEAT come about? What are/were the design goals?

SharpNEAT came about as an educational exercise for myself, primarily in NEAT but also in C# and dotNet. However I have had a number of goals in mind during development which might help explain where SharpNEAT is coming from:

1) Provide a simple and minimal set of interfaces for implementing new experiments. If you are interested in how NEAT will perform on your own pet problem domain then you probably don't want to spend a lot of time learning about the inner workings of NEAT or a specific NEAT implementation. SharpNEAT [hopefully] delivers this by [normally] only requiring two very minimal interfaces to be implemented for a new experiment, once implemented the new code classes plug easily into SharpNEAT (currently requiring a recompile).

2) Provide a clear, easy to use code base that can form the basis of future experimentation with the overall NEAT strategy. SharpNEAT is a full implementation of the NEAT strategy, however there may be extensions and refinements that can be made. SharpNEAT's simple OO design can expedite investigations in this area. To date SharpNEAT has a had a few modifications made to it in the form of extra search parameters, and one major extension in the form of phased pruning [see 3.5 What is Phased Searching?].

3) Provide an optimized code base. Many NEAT experiments are extremely CPU hungry, therefore it is important that the code base runs as efficiently as possible so that we don't eat into CPU and memory resources that are at a premium. To date a number of fairly significant performance improvements have been implemented and this process has been driven by the profiling of existing code and focusing on optimization of the most CPU hungry sections.

4) Provide an easy to use GUI for controlling and monitoring experiments. Currently SharpNEAT includes a basic window for controlling experiments, modifying experimental parameters and displaying progress statistics. There are also seperate windows for best network visualization, species monitoring and progress monitoring graphs. One notable absence currently is a proper graphical representation of the number of species, their relative sizes, fitness, range of fitness etc.

2.3 Why C#/.Net?

Firstly, at SharpNEAT's inception I had been using C# and dotNet commercially for some months and was keen to base the project on the same platform for my own education. Having said that there are actually a number of sound pragmatic reasons for using C# and targeting dotNet:

1) Targeting dotNet provides an extensive, stable and OS independent[see www.mono-project.com] runtime platform and class framework. Although compilation to target Mono has not yet been performed, there are only a few small steps required to make the SharpNEAT core library run on Mono. [see 2.7 Does SharpNEAT run on Mono™?]

2) Using a managed language such as C# simplifies code, reduces the incidence of bugs and therefore has been a factor in expediting development and allowing more time to focus on developing the NEAT strategy itself rather than hunting down difficult bugs or trying to keep up with changing code libraries.

3) Some have expressed concern about the performance of dotNet executables in comparison to native binaries compiled with an optimizing compiler. It is true to say that a typical algorithm ported from C++ [compiled to native machine code] to C# will generally perform slower. However, the performance difference is not as great as might be expected, in my own tests algorithms typically performed at 80% of the speed under C#/dotNet. Most of this performance loss can actually be attributed to the use of dotNet's container classes that must perform casting and boxing since dotNet 1.x lacks an equivalent of C++ templates [Note. dotNet 2.0 Generics solves this problem, but SharpNEAT does not yet use Generics]. However, some performance critical sections of SharpNEAT utilise strongly typed sort and search algorithms to overcome this problem where it is most noticable.

In fact if code is carefully written with performance in mind then most algorithms can be made to run at about the same speed in C# as in C++, this is because dotNet employs a Just-In-Time (JIT) compiler to compile Microsoft Intermediate Language (MSIL) into native machine code prior to execution, thus dotNet is able to perform some of the compiler optimizations that C++ compilers do, and can actually perform some extra optimizations because compilation is occurring at runtime - e.g. virtual method lookup tables can sometimes be discarded or partially collapsed if they are not actually used, and CPU specific optimisations can be made since the JIT compiler knows the exact type of CPU that will be executing the code.

Another factor affecting performance is memory management and garbage collection. Memory managed environments typically generate some overhead in tracking both memory allocations and when objects have gone out of scope, however there is a plus side to this which is that in-scope objects can actually be moved around in physical memory thus allowing the memory management system to prevent memory fragmentation - limiting physical RAM usage and speeding up new memory allocations. In fact dotNet's heap allocation routine is almost as fast as allocating space on the stack since there is no linked list of free blocks to scan as is normally the case with non-managed environments.

.Net also now supports for 64bit execution environments by way of an alternative 64bit CLR. In tests this executed the same C# code about 20% faster than the 32bit CLR.

2.4 Does SharpNEAT differ significantly from the original 'canonical' NEAT implementation?

Yes and no, bare in mind that SharpNEAT has been completely written from scratch and is not a port, the original NEAT source was used only as a reference point for details about how the genome comparison, crossover, mutation, speciation, etc. techniques work. There are a number of areas where SharpNEAT differs from Ken's NEAT code, e.g. there are slight variations in how connection weight mutation and genome crossover occurs. In essence though all of the fundamental parts of the original NEAT algorithm such as fitness sharing, speciation, the mutation and crossover techniques and the functioning of the underlying neural network code are all in place, so although SharpNEAT doesn't emulate original NEAT exactly, experimental results can be expected to be similar but not exactly the same.

One important difference is the addition of phased searching within SharpNEAT. [See 3.5 What is Phased Searching?]

2.5 What are the hardware and OS platform requirements?

The basic requirements are those for hosting the dotNet 2.x environment. So Windows XP or Windows 2000, a 600Mhz CPU and 128Mb of memory. Back in the real world you really want the fastest CPU available to increase the evaluations/sec rate and thus the chances of finding a good solution for a given problem. Therefore I would recommend at least a 1Ghz CPU, and 256Mb of memory. The specific system requirements for dotNet can be seen here [http://msdn2.microsoft.com/en-us/netframework/aa497338.aspx] or search for ".net framework minimum requirements" in google.

2.6 What software dependencies are there?

ZedGraph is used for rendering the progress graphs. Other graphs are usign my own built in graph cntrol called RubyGraph - however, the source for this graph is part of the SharpNEAT release. RubyGraph usage is beign phased out in favur of the much better ZedGraph. Apart from this the only dependency is the .Net frameowrk itself, currently I develop against.Net 2.x.

2.7 Does SharpNEAT run on Mono™?

Having just tried this on Mono 1.2.6 (December 2007) I can say that it does work but there appear to be stability problems. e.g. the Reset button causes the application to quit (probably via some exception). So yes you can get an experiment runnign but some bug fixing will be required to improve stability. I suspect the problems areas are in the GUI (System.Windows.Forms) stuff and possibly threading and the interaction between the worker thread and the GUI thread. It's possible that Mono is being more strict about certain cases than Microsofts CLR, and throwing exceptions.

 

3. Using SharpNEAT

3.1 What is an experiment module?

Each experiment in SharpNEAT is represented by an implementation of the IExperiment interface, such an implementation is what I call an experiment module since it aggregates everything needed to run an experiment in SharpNEAT into one 'module' that can be plugged into SharpNEAT. The most notable property on IExperiment is PopulationEvaluator which returns an IPopulationEvaluator that is used to evaluate genomes within the population. Apart from this there are properties for specifying the number of input/ouput nodes the experiment requires, default search parameters, explanatory text for the experiment, etc.

3.2 What experiment modules are provided with SharpNEAT as standard?

1. XOR
2. 3-Multipler
3. 6-Multiplexer
4. 11-Multiplexer
5. Prey Capture
6. Pole Balancing(Single Pole)
7. Pole Balancing(Double Pole)
8. Pole Balancing(Double Pole, No velocity Inputs)
9. Pole Balancing(Double Pole, No velocity Inputs + Alternative Anti-Wiggle evaluation function)
10. Simple-OCR (Technically a pattern classification problem, not OCR proper)
11. Multiplication
12. Vector Cross Product
13. Tic-Tac-Toe (A co-evolution experiment)
14. Physical Travelling Salesperson Controller
15. Function Regression(Single Parameter)
16. WaveGenerator.

An explanation for each experiment is available within the SharpNEAT GUI, just select an experiment in the drop-down combobox and click the button marked '?'.

3.3 How do I perform an experimental run using one of the existing experiment modules?

1. Run the SharpNEAT GUI executable (SharpNEAT.exe)
2. Select an experiment in the drop-down list.
3. Click the button marked 'Load Default Search Parameters'.
4. Select one of the 'Initialize Population' menu options. For starters just click 'Auto Generate' and 'OK'.
5. Click the 'Start/Continue' button.

You should now see progress information being written to the log window, there are also some extra monitor windows available via the 'Visualization' Menu.

3.4 How do I create a new experiment module?

Implement IExperiment in a new class and add the experiment to the combo-box in the SharpNEAT GUI - within the Form1.PopulateDomainCombo() method.

In the absence of a more complete explanation of how to implement IExperiment take a look at the existing classes that implement IExperiment classes. Hopefully it's straightforward to see what's going on.

3.5 What is Phased Searching?

Within the SharpNEAT GUI, on the 2nd tab page there is a checkbox with the label 'Enable Pruning' which is checked by default. This enables a process whereby the average complexity of genomes in the population is tracked, and if it passes some threshold then the search switches to a 'pruning' mode. In pruning mode the search continues as normal but additive mutations are disabled and deletion mutation rates are increased, this causes the structural complexity of genomes in the population to fall but without loosing the best genomes. This can give rise to new bursts of improvement in fitness and also a speedup of the search, since more complex genomes take longer to evaluate. For a more complete explanation see the experimental write-up - Phased Searching with NEAT: Alternating Between Complexification And Simplification.

3.6 What is the development status of SharpNEAT? What development plans are there?

See the roadmap page.