# Methods for Statistical Inference: Extending the Evolutionary Computation Paradigm

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

@PhdThesis{hugues_thesis,
author =       "Hugues Juille",
title =        "Methods for Statistical Inference: Extending the
school =       "Department of Computer Science, Brandeis University",
year =         "1999",
month =        may,
keywords =     "genetic algorithms, genetic programming,
Coevolutionary Learning, Stochastic Search, Cellular
Automata",
URL =          "http://www.demo.cs.brandeis.edu/papers/hugues_thesis.pdf",
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
rules.

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
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
races.",
notes =        "2 Jan 2013 discussed by
http://tech.groups.yahoo.com/group/genetic_programming/message/6014
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

Citations