mlpack  blog
Neural Evolution Algorithms for NES games - Summary

Neural Evolution Algorithms for NES games - Summary

Kartik Nighania, 29 August 2017

My Google Summer of Code project was to create neural evolution algorithms for NES games. under which:

  • CNE: Conventional Neural Evolution.
  • CMAES: Covariance Matrix Adaptation Evolution Strategy.
  • NEAT: Neural Evolution through Augmented Topologies.

and HyperNEAT which is exactly same as NEAT but the genomes go through a substrate layer to get the links has to be implemented. All the evolutionary algorithm as planned before was supposed to be neural network optimization algorithms. But we later switched to using it as a generalized optimizer which can be used with other functions and machine learning methods, like logistic regression class implemented in mlpack as well. Therefore CMAES and CNE were designed as an optimizer.

CMAES Implementation

  • My working PR (ready): This PR is all set to get merged 938
  • References: The research paper that I referred for this algorithm is: The CMA Evolution Strategy: A Tutorial by Nikolas Hansen.
  • Medium Blog Post: I have a medium blog describing how this algorithm works followed by describing mlpack open source library and a full code tutorial showing the optimization in action: CMAES algorithm in C++ using mlpack
  • Test Cases: CMA-ES algorithm works by using clever probability distribution (using a modifiable Gaussian distribution) and moving the mean to minima and updating the covariance matrix in the process. Unlike other derivative methods for optimization, this method is great for discontinuous and ill conditioned functions. Therefore one of the performance tests was done using Rosenbrock function and that too iteratively for up to 50 dimensions. A change in 1e-5 in values leads to a very different result. A lot of time was spent to make the algorithm better and removing some major bugs. I can confidently present the optimizer now which works perfectly giving accurate results each time.
  • Tutorial: A full descriptive tutorial on using CMAES has been added in the documentation covering step by step:
    1. The CMAES optimizer class in short.
    2. Making the function Class.
    3. Setting up the constructor.
    4. Complete code example.
    5. Using as optimizer with other models.

This PR was very challenging for me. The time I decided was way too much less than actually needed. Also during this time, I was new to armadillo library for which my mentor came to the rescue. I made a lot of modifications to the PR and also spend a lot more in debugging. This PR was indeed a bit scary learning experience. But finally, this PR got completed after optimization, improvements and bug fixes.

CNE Implementation

  • PR (merged): 1088
  • Divided into three sections: Optimizer, Test Cases, Tutorial
  • Optimizer: Conventional Neural Evolution implemented in mlpack is an optimizer that works like biological evolution in nature which selects best candidates based on their fitness scores and creates new generation by mutation and crossover of the population. This then keeps on repeating iteratively till several generations after which healthy candidates are found which perform well in getting the desired output.
  • References: The research paper and reference code that I used to learn CNE were: Training Feedforward Neural Networks Using Genetic Algorithms, Evolving Artificial Neural Networks, Multineat, PR 753
  • Test Cases: Test cases were written for three very different scenarios.
    1. Optimizing a given function: XOR function.
    2. Optimizing a vanilla network: It worked for both iris dataset and the thyroid dataset. But for making the test case faster only iris dataset is used.
    3. Testing with mlpack existing model: Logistic regression model was given the optimizer to learn a dataset.
  • Tutorial: A full descriptive tutorial on using CNE has been added in the documentation covering step by step:
    1. The CNE optimizer class in short.
    2. The constructor parameters.
    3. Creating a model using mlpack's ANN Class.
    4. Complete code example.
    5. Logistic regression using CNE as an optimizer.

This is my first merged PR for any open source project which now rests peacefully in mlpack servers.CNEwas not as painful asCMAES` and as always my mentor provided his valuable suggestions and code reviews. I loved working on it completely.

NEAT Implementation

This class is already made by previous GSoC 2016 participant Bang Lui and so rather than reinventing the wheel my work was to make it live again and fix an important bug.

Reading his code was really a nice experience and I think it is one of those best ones in which u can see classes for neurons, links and using them a new class genomes (which is a neural network having links and neurons) and then species as a cluster of genomes and finally population as a cluster of species. To see the true essence of classes and object oriented programming so beautifully implemented.

Some of my time went on to make this one-year-old PR live and working again. I made more than 270 indentation fixes and other code optimization and style fixes that do not get caught by the cppCheck bot. A tutorial for documentation is also under process. I was able to find some errors which created some critical changes in evolution. Also, changes are under testing and debugging for now.

Future work

My future work is to complete NEAT till it gets merged successfully. Looking at the work done by Bang Lui the code is worth fixing and pushing to the codebase. For HyperNEAT which is a small extension to NEAT, a new PR will follow which is not a major task.

I loved the idea of adding Gaussian process implementation to mlpack in one of the issues. I would love to contribute for this later.

Conclusion

I would like to thank mlpack for giving me a chance to contribute to this beautiful library. I have a very different perspective for open source now. Big thanks to my mentor Marcus Edel for tolerating me. There were multiple times I asked for his help and he always responded in no time and with a lot of patience. Also, the detailed code review and improvements that he suggested were unmatched and clearly ensure that good quality code gets in the main codebase. Thanks to Ryan for the code review and final edits. Lastly Google for encouraging open source contribution. Looking forward to more contributions from my side and becoming a better engineer.