Probabilistic Incremental Program Evolution

[Rafal Salustowicz]

              PROBABILISTIC INCREMENTAL PROGRAM EVOLUTION

              Rafal Salustowicz       Juergen Schmidhuber

                          IDSIA, Switzerland

              To appear in  Evolutionary Computation 5(2)

Probabilistic Incremental Program Evolution (PIPE) is a novel technique
for automatic program synthesis.   We combine probability vector coding
of program  instructions,  Population-Based  Incremental Learning,  and
tree-coded  programs  like  those  used in  some  variants  of  Genetic
Programming (GP). PIPE  iteratively generates successive populations of
functional programs  according to an adaptive  probability distribution
over all possible programs.  Each iteration it uses the best program to
refine the distribution.   Thus, it stochastically generates better and
better programs. Since distribution refinements depend only on the best
program of the current population, PIPE can evaluate program populations
efficiently when the goal is to discover a program with minimal runtime.
We compare  PIPE to GP on a  function regression problem  and the 6-bit
parity problem. We also use PIPE to solve tasks in partially observable
mazes, where the best programs have minimal runtime.

              ftp://ftp.idsia.ch/pub/rafal/PIPE.ps.gz
              http://www.idsia.ch/~rafal/research.html

Short version:  Probabilistic Incremental Program Evolution: Stochastic
Search Through Program Space.   In van Someren, M., Widmer, G. editors,
Machine Learning:  ECML-97, pages 213-220,  Lecture Notes in Artificial
Intelligence 1224, Springer-Verlag Berlin Heidelberg.
(ftp://ftp.idsia.ch/pub/rafal/ECML_PIPE.ps.gz)


******************************************************************************
*  			     Rafal Salustowicz				     *
*     Istituto Dalle Molle di Studi sull'Intelligenza Artificiale (IDSIA)    *
*     Corso Elvezia 36 			 e-mail: rafal at idsia.ch	     	     *
*     6900 Lugano				 ==============	     	     *
*     Switzerland				 raf at cs.tu-berlin.de         *
*     Tel (IDSIA) : +41 91 91198-38		 raf at psych.stanford.edu      *
*     Tel (office): +41 91 91198-32		   			     *
*     Fax         : +41 91 91198-39	    WWW: http://www.idsia.ch/~rafal  *
******************************************************************************