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

@PhdThesis{hugues_thesis, 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 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 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