A grammar-based technique for genetic search and optimization.

摘要

The genetic algorithm (GA) is a robust search technique which has been theoretically and empirically proven to provide efficient search for a variety of problems. Due largely to the semantic and expressive limitations of adopting a bitstring representation, however, the traditional GA has not found wide acceptance in the Artificial Intelligence community. In addition, binary chromosones can unevenly weight genetic search, reduce the effectiveness of recombination operators, make it difficult to solve problems whose solution schemata are of high order and defining length, and hinder new schema discovery in cases where chromosome-wide changes are required.;The research presented in this dissertation describes a grammar-based approach to genetic algorithms. Under this new paradigm, all members of the population are strings produced by a problem-specific grammar. Since any structure which can be expressed in Backus-Naur Form can thus be manipulated by genetic operators, a grammar-based GA strategy provides a consistent methodology for handling any population structure expressible in terms of a context-free grammar.;In order to lend theoretical support to the development of the syntactic GA, the concept of a trace schema--a similarity template for matching the derivation traces of grammar-defined rules--was introduced. An analysis of the manner in which a grammar-based GA operates yielded a Trace Schema Theorem for rule processing, which states that above-average trace schemata containing relatively few non-terminal productions are sampled with increasing frequency by syntactic genetic search. Schemata thus serve as the "building blocks" in the construction of the complex rule structures manipulated by syntactic GAs.;As part of the research presented in this dissertation, the GEnetic Rule Discovery System (GERDS) implementation of the grammar-based GA was developed. A comparison between the performance of GERDS and the traditional GA showed that the class of problems solvable by a syntactic GA is a superset of the class solvable by its binary counterpart, and that the added expressiveness greatly facilitates the representation of GA problems. To strengthen that conclusion, several experiments encompassing diverse domains were performed with favorable results.