neuro-evolution software, papers, web demos available

[risto@cs.utexas.edu]

The JavaSANE software package for evolving neural networks with genetic
algorithms is available from the UTCS Neural Networks Research Group
website, http://www.cs.utexas.edu/users/nn. The SANE method has been
designed as part of our ongoing research in efficient neuro-evolution.
This software is intended to facilitate applying neuro-evolution to new
domains and problems, and also as a starting point for future research
in neuro-evolution algorithms.

Abstracts of recent papers on eugenic evolution, on-line evolution, and
non-Markovian control are also included below. Demos of these
systems as well as other neuroevolution papers are available at
http://www.cs.utexas.edu/users/nn/pages/research/neuroevolution.html.

-- Risto

Software:
-----------------------------------------------------------------------
JAVASANE: SYMBIOTIC NEURO-EVOLUTION IN SEQUENTIAL DECISION TASKS
http://www.cs.utexas.edu/users/nn/pages/software/abstracts.html#javasane
Cyndy Matuszek, David Moriarty

The JavaSANE package contains the source code for the Hierarchical SANE
neuro-evolution method, where a population of neurons is evolved
together with network blueprints to find a network for a given task.
The method has been shown effective in several sequential decision tasks
including robot control, game playing, and resource optimization.
JavaSANE is designed especially to make it possible to apply SANE to new
tasks with minimal effort. It is also intended to be a platform-independent
and parsimonious implementation of SANE, so that can serve as a starting
point for further research in neuro-evolution algorithms. (This package is
written in Java; an earlier C-version is also available).



Papers and Demos:
-----------------------------------------------------------------------
SOLVING NON-MARKOVIAN CONTROL TASKS WITH NEUROEVOLUTION

Faustino Gomez and Risto Miikkulainen
To appear in Proceedings of the International Joint Conference on Artificial 
Intelligence (IJCAI-99, Stockholm, Sweden) (6 pages).

http://www.cs.utexas.edu/users/nn/pages/publications/abstracts.html#gomez.ijcai99.ps.gz

The success of evolutionary methods on standard control learning tasks
has created a need for new benchmarks.  The classic pole balancing
problem is no longer difficult enough to serve as a viable yardstick for
measuring the learning efficiency of these systems.  The double pole
case, where two poles connected to the cart must be balanced
simultaneously is much more difficult, especially when velocity
information is not available.  In this article, we demonstrate a
neuroevolution system, Enforced Sub-populations (ESP), that is used to
evolve a controller for the standard double pole task and a much harder,
non-Markovian version.  In both cases, our results show that ESP is
faster than other neuroevolution methods.  In addition, we introduce an
incremental method that evolves on a sequence of tasks, and utilizes a
local search technique (Delta-Coding) to sustain diversity.  This method
enables the system to solve even more difficult versions of the task
where direct evolution cannot.

A demo of ESP in the 2-pole balancing task can be seen at
http://www.cs.utexas.edu/users/nn/pages/research/neuroevolution.html.


-----------------------------------------------------------------------
REAL-TIME INTERACTIVE NEURO-EVOLUTION

Adrian Agogino, Kenneth Stanley, and Risto Miikkulainen
Technical Report AI98-266, Department of Computer Sciences,
The University of Texas at Austin, 1998 (16 pages).

http://www.cs.utexas.edu/users/nn/pages/publications/abstracts.html#agostan.ine.ps.Z

In standard neuro-evolution, a population of networks is evolved in the
task, and the network that best solves the task is found. This network
is then fixed and used to solve future instances of the
problem. Networks evolved in this way do not handle real-time
interaction very well. It is hard to evolve a solution ahead of time
that can cope effectively with all the possible environments that might
arise in the future and with all the possible ways someone may interact
with it. This paper proposes evolving feedforward neural networks online
to create agents that improve their performance through real-time
interaction. This approach is demonstrated in a game world where
neural-network-controlled individuals play against humans. Through
evolution, these individuals learn to react to varying opponents while
appropriately taking into account conflicting goals. After initial
evaluation offline, the population is allowed to evolve online, and its
performance improves considerably. The population not only adapts to
novel situations brought about by changing strategies in the opponent
and the game layout, but it also improves its performance in situations
that it has already seen in offline training. This paper will describe
an implementation of online evolution and shows that it is a practical
method that exceeds the performance of offline evolution alone.

A demo of on-line evolution in the real-time gaming task is at
http://www.cs.utexas.edu/users/nn/pages/research/neuroevolution.html.


-----------------------------------------------------------------------
EUGENIC EVOLUTION FOR COMBINATORIAL OPTIMIZATION

John W. Prior
Master's Thesis, Technical Report AI98-268, Department of Computer
Sciences, The University of Texas at Austin, 1998 (126 pages).

http://www.cs.utexas.edu/users/nn/pages/publications/abstracts.html#prior.eugenic-thesis.ps.Z

In the past several years, evolutionary algorithms such as simulated
annealing and the genetic algorithm have received increasing recognition
for their ability to optimize arbitrary functions. These algorithms rely
on the process of Darwinian evolution, which promotes highly successful
solutions that result from random variation. This variation is produced
by the random operators of mutation and/or recombination. These
operators make no attempt to determine which alleles or combinations of
alleles are most likely to yield overall fitness improvement.  This
thesis will explore the benefits that can be gained by utilizing a
direct analysis of the correlations between fitness and alleles or
allele combinations to intelligently and purposefully design new
highly-fit solutions.

An algorithm is developed in this thesis that explicitly analyzes
allele-fitness distributions and then uses the information gained from
this analysis to purposefully construct new individuals ``bit by
bit''. Explicit measurements of ``gene significance'' (the effect of a
particular gene upon fitness) allows the algorithm to adaptively decide
when conditional allele-fitness distributions are necessary in
order to correctly track important allele interactions.  A new
operator---the ``restriction'' operator---allows the algorithm to simply
and quickly compute allele selection probabilities using these
conditional fitness distributions.  The resulting feedback from the
evaluation of new individuals is used to update the statistics and
therefore guide the creation of increasingly better individuals. Since
explicit analysis and creation is used to guide this evolutionary
process, it is not a form of Darwinian evolution. It is a pro-active,
contrived process that attempts to intelligently create better
individuals through the use of a detailed analysis of historical
data. It is therefore a eugenic evolutionary process, and thus
this algorithm is called the ``Eugenic Algorithm'' (EuA).

The EuA was tested on a number of benchmark problems (some of which are
NP-complete) and compared to widely recognized evolutionary optimization
techniques such as simulated annealing and genetic algorithms. The
results of these tests are very promising, as the EuA optimized all the
problems at a very high level of performance, and did so much more
consistently than the other algorithms. In addition, the operation of
EuA was very helpful in illustrating the structure of the test problems.
The development of the EuA is a very significant step to statistically
justified combinatorial optimization, paving the way to the creation of
optimization algorithms that make more intelligent use of the
information that is available to them. This new evolutionary paradigm,
eugenic evolution will lead to faster and more accurate combinatorial
optimization and to a greater understanding of the structure of
combinatorial optimization problems.


-----------------------------------------------------------------------
FAST REINFORCEMENT LEARNING THROUGH EUGENIC NEURO-EVOLUTION

Daniel Polani and Risto Miikkulainen
Technical Report AI99-277, Department of Computer Sciences, University
of Texas at Austin, 1999 (7 pages).

http://www.cs.utexas.edu/users/nn/pages/publications/abstracts.html#polani.eusane-99.ps.gz

In this paper we introduce EuSANE, a novel reinforcement learning
algorithm based on the SANE neuro-evolution method. It uses a global
search algorithm, the Eugenic Algorithm, to optimize the selection of
neurons to the hidden layer of SANE networks.  The performance of EuSANE
is evaluated in the two-pole balancing benchmark task, showing that
EuSANE is significantly stronger than other reinforcement learning
methods to date in this task.