Methods for Statistical Inference: Extending the Evolutionary Computation Paradigm

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

  author =       "Hugues Juille",
  title =        "Methods for Statistical Inference: Extending the
                 Evolutionary Computation Paradigm",
  school =       "Department of Computer Science, Brandeis University",
  year =         "1999",
  month =        may,
  keywords =     "genetic algorithms, genetic programming,
                 Coevolutionary Learning, Stochastic Search, Cellular
  URL =          "",
  size =         "221 pages",
  abstract =     "In many instances, Evolutionary Computation (EC)
                 techniques have demonstrated their ability to tackle
                 ill-structured and poorly understood problems against
                 which traditional Artificial Intelligence (AI) search
                 algorithms fail. The principle of operation behind EC
                 techniques can be described as a statistical inference
                 process which implements a sampling-based strategy to
                 gather information about the state space, and then
                 exploits this knowledge for controlling search.
                 However, this statistical inference process is
                 supported by a rigid structure that is an integral part
                 of an EC technique. For instance, {\em schemas} seem to
                 be the basic components that form this structure in the
                 case of Genetic Algorithms (GAs). Therefore, it is
                 important that the encoding of a problem in an EC
                 framework exhibits some regularities that correlate
                 with this underlying structure. Failure to find an
                 appropriate representation prevents the evolutionary
                 algorithm from making accurate decisions. This
                 dissertation introduces new methods that exploit the
                 same principles of operation as those embedded in EC
                 techniques and provide more flexibility for the choice
                 of the structure supporting the statistical inference
                 process. The purpose of those methods is to generalize
                 the EC paradigm, thereby expanding its domain of
                 applications to new classes of problems.

                 Two techniques implementing those methods are described
                 in this work. The first one, named SAGE, extends the
                 sampling-based strategy underlying evolutionary
                 algorithms to perform search in trees and directed
                 acyclic graphs. The second technique considers
                 coevolutionary learning, a paradigm which involves the
                 embedding of adaptive agents in a fitness environment
                 that dynamically responds to their progress.
                 Coevolution is proposed as a framework in which
                 evolving agents would be permanently challenged,
                 eventually resulting in continuous improvement of their
                 performance. After identifying obstacles to continuous
                 progress, the concept of an ``Ideal'' trainer is
                 presented as a paradigm which successfully achieves
                 that goal by maintaining a pressure toward

                 The different algorithms discussed in this dissertation
                 have been applied to a variety of difficult problems in
                 learning and combinatorial optimization. Some
                 significant achievements that resulted from those
                 experiments concern: (1) the discovery of new
                 constructions for 13-input sorting networks using fewer
                 comparators than the best known upper bound, (2) an
                 improved procedure for the induction of DFAs from
                 sparse training data which ended up as a co-winner in a
                 grammar inference competition, and (3) the discovery of
                 new cellular automata rules to implement the majority
                 classification task which outperform the best known

                 By describing evolutionary algorithms from the
                 perspective of statistical inference techniques, this
                 research work contributes to a better understanding of
                 the underlying search strategies embedded in EC
                 techniques. In particular, an extensive analysis of the
                 coevolutionary paradigm identifies two fundamental
                 requirements for achieving continuous progress. Search
                 and machine learning are two fields that are closely
                 related. This dissertation emphasises this relationship
                 and demonstrates the relevance of the issue of
                 generalisation in the context of coevolutionary
  notes =        "2 Jan 2013 discussed by
                 Says coevolution majority CA better than GKL, Das and
                 ABK \cite{andre:1996:GKL} (Table 6.2).

                 GP, eg starting on page 169",

Genetic Programming entries for Hugues Juille