SANE neurogenetic algorithm

David Moriarty and Professor Risto Miikkulainen of the Neural Networks Research Group at the University of Texas at Austin wrote several papers about SANE (Symbiotic Adaptive Neuro-Evolution), a genetic algorithm that operates on neural networks. There has also been some follow-on work to improve the idea.

The papers can be found, along with others, on the group’s publications page (you may have to click the weird “also show archived” checkbox). The group is friendly to game research, so there’s a bunch of cool stuff there.

the algorithm

SANE addresses the problem of premature convergence that genetic algorithms are prone to. Instead of evolving a population of complete networks, it evolves a population of individual neurons. Each neuron specifies its connections to the input and output layers. Its fitness is determined by its average performance in a sample of random networks.

The random networks are formed by choosing a fixed-size subset of the population of neurons. Each network is evaluated on the target task, and credit or blame for its performance is divided evenly among its neurons.

This method of evaluation has two benefits. First, the population remains diverse. If too many neurons do the same thing, threatening premature convergence, then on average they combine into less-effective networks and suffer lower fitness, which tends to reduce their numbers. Second, because neurons are evaluated according to how well they cooperate with other neurons in the population, the neurons tend to specialize into subpopulations, each subpopulation taking a different role in the overall solution. Thus SANE has implicit niching, making it similar to (for example) fitness sharing methods.

The population is automatically balanced. It’s an ingenious idea, though I find it a counterintuitive one.

results

Performance results show that SANE works well, at least on a few problems.

The papers below apply SANE to several domains, concluding that it’s effective and efficient. One result, in the “Learning sequential decision tasks” paper, is for the game of othello. SANE learned a “focus network” for search control, the same problem tackled by the marker-based method in “Evolving neural networks to focus minimax search” by the same authors. Unlike the marker-based genetic algorithm, SANE was able to correct weaknesses in Bill’s evaluation function by guiding the search away from them. That’s fairly impressive, because Bill’s evaluator was sophisticated for its day.

my opinion

The strong results mean that SANE is promising, but somebody else needs to get good results before it’ll be fully convincing.

I have a lot of questions. Why does it work so well on the tested tasks? Is it better than other implicit niching methods? And the big question: Are there tasks for which all the good networks include neurons which do not work well in random networks? If so, then apparently SANE must perform weakly on these tasks.

references

Efficient reinforcement learning through symbiotic evolution (1996, 23 pages)
David Moriarty and Risto Miikkulainen
Abstract and paper. It describes SANE and compares it to a couple other methods on the pole-balancing task.

Learning sequential decision tasks (1995, 14 pages)
David Moriarty and Risto Miikkulainen
Abstract and paper. It applies the algorithm to two search control domains, including one in the game of othello.

Learning sequential decision tasks (1997)
David Moriarty
Abstract and PhD thesis. The long treatment.

Applying ESP And Region Specialists To Neuro-Evolution For Go (2001)
Andres Santiago Perez-Bergquist
Abstract and undergraduate honors thesis. A follow-on algorithm based on SANE was applied to the game of go, though it did not scale to useful board sizes.

Co-Evolving A Go-Playing Neural Network (2001)
Alex Lubberts and Risto Miikkulainen
Abstract and paper. Further follow-on work, still doesn’t scale.