- author = "Hugues Juille",
- title = "Methods for Statistical Inference: Extending the Evolutionary Computation Paradigm",
- school = "Department of Computer Science, Brandeis University",
- year = "1999",
- address = "USA",
- 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 adaptability.
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 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 races.",
-
notes = "2 Jan 2013 discussed by Broken March 2021
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",
