Efficient reinforcement learning through symbiotic evolution
(1996, 23 pages)David Moriarty and Risto Miikkulainen
Compressed postscript. It describes SANE and compares it to a couple other methods on the pole-balancing task.
David Moriarty and Professor Risto Miikkulainen of the UTCS Neural Networks Research Group at the University of Texas wrote several papers about SANE (Symbiotic Adaptive Neuro-Evolution), a genetic algorithm that operates on neural networks.
| Jay : game learning : GA : SANE |
The papers can be found, along with others, on this neuro-evolution publications page, which points ultimately to this ftp archive.
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.
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.
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.
Efficient reinforcement learning through symbiotic evolution
(1996, 23 pages)
David Moriarty and Risto Miikkulainen
Compressed postscript. 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
Compressed postscript. It applies the algorithm to two
search control domains, including one in the game of othello.