Representation Schemes for Evolutionary Automatic Programming

Created by W.Langdon from gp-bibliography.bib Revision:1.3872

  author =       "Taro Yabuki",
  title =        "Representation Schemes for Evolutionary Automatic
  school =       "Department of Frontier Informatics, Graduate School of
                 Frontier Sciences, The University of Tokyo",
  year =         "2004",
  address =      "Japan",
  note =         "In Japanese",
  keywords =     "genetic algorithms, genetic programming",
  URL =          "",
  abstract =     "We propose a new representation scheme for Genetic
                 Programming (GP). It is a recurrent network consisting
                 of functions (Recurrent Network consisting of Trees,
                 RTN). GP is a type of evolutionary computing (EC). EC
                 is a framework of automatic optimisation or

                 Features of EC are:

                 * Representation scheme for solution candidates and
                 variation operators for them. * Fitness function that
                 shows a quality of the solution candidate.

                 * Selection method that selects prospective solution
                 candidates from a set of them. Usually, these features
                 are defined independently. Although it is interesting
                 to rethink this model completely, we reconsider only
                 the representation scheme for GP.

                 We use GP to generate a program automatically. The
                 program is represented by RTN. RTN can represent any
                 algorithms, in other words, Turing-complete. Thus, a
                 user of RTN need not worry about whether a solution of
                 a given problem can be described by RTN. On the other
                 hand, the expressiveness of solution candidates of
                 standard GP, which is the most popular GP, is strongly
                 restricted. A solution candidate of standard GP is
                 represented by a single parse tree. The parse tree
                 consists of terminals and non-terminals. If all
                 non-terminals are pure functions and we treat an
                 evaluated value of the parse tree as an output (or
                 behaviour) of the solution candidate, the repertoire of
                 this representation is smaller than the one of finite
                 state machine.",
  abstract =     "This does not matter if we know that the restricted
                 expressiveness is sufficient to describe the solution
                 of a given problem in advance of evolutionary
                 computation. However, in case that we do not know that
                 and the search should fail, it will be impossible to
                 find out whether it is attributable to evolutionary
                 computing or the representation scheme. For example,
                 suppose we try to generate a classifier for the
                 language $ \{ww\vert w\in\{0,1\}*\}$. If we use a
                 representation whose repertoire is the same as one of
                 the pushdown automaton, then we will never succeed,
                 because it is proved that any pushdown automaton cannot
                 decide this language.

                 One conceivable approach is to introduce an ideally
                 infinite indexed memory and non-terminals to access to
                 it. It is proved that if the solution candidate is
                 represented by a parse tree consisting of these
                 non-terminals and we can repeat the evaluation of the
                 parse tree until the data stored in the memory meets a
                 halting condition, then the expressiveness is
                 equivalent to the one of a Turing machine, i.e.
  abstract =     "However, the representation scheme for GP must satisfy
                 other conditions except Turing-completeness. These are
                 as follows:

                 * User can specify the input-output scheme.

                 * Useful components can be introduced easily.

                 * The program is modularised and hierarchised.

                 We will discuss necessity of them in detail in this

                 We propose another representation scheme, RTN. It
                 satisfies above conditions. It is a natural extension
                 of standard GP. Standard GP uses a single parse tree to
                 represent a solution candidate. On the other hand, RTN
                 is a recurrent network consisting of plural nodes. Each
                 node consists of a value and a pure function
                 represented by a parse tree. The parse tree consists of
                 non-terminals and terminals. Special non-terminals are
                 not needed. Terminal set consists of four variables and
                 constants. In case of standard GP, the input data bind
                 variables. On the other hand, they bind the values of
                 the RTN nodes.",
  abstract =     "This is an example of RTN consisting of two nodes. The
                 functions of each node are $\displaystyle \char93 1$
                 $\displaystyle : (c-P[c])/2,$ $\displaystyle \char93 2$
                 $\displaystyle : P[a] d,$ where $ P$ is a procedure
                 which returns a remainder of its argument divided by $
                 2$. The function has at most four parameters, i.e. $
                 a$, $ b$, $ c$, and $ d$. These parameters are bound to
                 the value of nodes. In this case, the binding rule is
                 expressed as follows: Links of $ \char93 1$ and $
                 \char93 2$ are $ \{*, *, 1, *\}$ and $ \{1, *, *, 2\}$,
                 respectively. The third parameter of $ \char93 1$, i.e.
                 $ c$ and the first parameter of $ \char93 2$, i.e. $ a$
                 are bound to the value of $ \char93 1$, because both
                 the third link of $ \char93 1$ and the first link of $
                 \char93 2$ are $ 1$. The fourth parameter of $ \char93
                 2$, i.e. $ d$ is bound to the value of $ \char93 2$,
                 because the fourth link of $ \char93 2$ is $ 2$.",
  abstract =     "The program is executed according to the discrete time
                 steps. Define the function and the value of the $
                 \char93 n$ at time $ t$ as $ f_n$ and $ v[[n, t]]$,
                 respectively, the number of parameters as $ k_n$, and
                 let $ i$-th parameter be bound to the value of $
                 \char93 l_{n,i}$. The value at $ t+1$ will be
                 $\displaystyle v[[n, t+1]]=f_n[v[[l_{n,1},t]],\ \cdots\
                 ,v[[l_{n,k_{n}},t]]]. $ Suppose the value of $ \char93
                 1$ is bound to the input data and the value of $
                 \char93 2$ is $ 1$ at $ t=0$. For example, when the
                 input data is a binary digit $ 1011$, the transition of
                 RTN will be as follows: Value of $ \char93 1$ $ 1011$ $
                 101$ $ 10$ $ 1$ 0 Value of $ \char93 2$ $ 1$ $ 1$ $ 1$
                 0 0 When the value of $ \char93 1$ becomes 0, the value
                 of $ \char93 2$ is 0 if and only if the inputted binary
                 digit contains 0.

                 It is straightforward to prove that RTN can simulate
                 any Turing machine, in other words, RTN can represent
                 any algorithms. We give the proof in this paper.",
  abstract =     "We use RTN to generate language classifiers. These are
                 the tasks that GP has failed to solve. GP using RTN
                 succeeds to solve them. We also apply the
                 representation scheme using indexed memory to these
                 tasks. However, it does not succeed. This comparison
                 implies that our approach is effective and

                 Various representations for GP have been proposed so
                 far. We discuss differences between RTN and other
                 representation scheme. We also discuss the criteria
                 used in comparing various approaches. For example, No
                 Free Lunch Theorem does not matter.",
  notes =        "

                 email Thu, 01 Sep 2005 16:45:44 +0900 No English
                 translation available, but, the essential part of it,
                 i.e. details of proposed representation scheme and
                 results of its application, is described in
                 \cite{yabuki04genetic}. There are many topics not
                 included \cite{yabuki04genetic} but discussed in the

                 - In \cite{yabuki04genetic}, we said that the
                 repertoire of single S-expression is the same as the
                 one of finite state automaton (FSA). In the thesis, I
                 showed it is usual that the repertoire of single
                 S-expression is smaller than the one of FSA.

                 - Drawbacks of describing strategies of iterated
                 prisonerB!Gs dilemma by means of tables or strings of

                 - Requirements for the representation for GP were
                 discussed concretely in the thesis.

                 - Drawbacks of automatically defined functions and
                 recursive non-terminal.

                 - The way how to simulate multi-tape Turing machine
                 directly by means of our representation scheme.

                 - Successful result of our method applied to a problem
                 that cannot be solved by FSA.",

Genetic Programming entries for Taro Yabuki