A Sampling-Based Heuristic for Tree Search Applied to Grammar Induction

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

@InProceedings{juille:1998:shtsgi,

• author = "Hugues Juille and Jordan B. Pollack",
• title = "A Sampling-Based Heuristic for Tree Search Applied to Grammar Induction",
• booktitle = "Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI-98) Tenth Conference on Innovative Applications of Artificial Intelligence (IAAI-98)",
• year = "1998",
• address = "Madison, Wisconsin, USA",
• month = "26-30 " # jul,
• publisher = "AAAI Press Books",
• keywords = "genetic algorithms, genetic programming, search, massively parallel systems, inductive learning, DFA induction",
• URL = "http://www.demo.cs.brandeis.edu/papers/aaai98.pdf",
• URL = "http://www.demo.cs.brandeis.edu/papers/aaai98.ps.gz",
• URL = "http://www.demo.cs.brandeis.edu/papers/aaai98.ps",
• URL = "http://www.cs.brandeis.edu/~hugues/papers/AAAI_98.ps.gz",
• abstract = "In the field of Operation Research and Artificial Intelligence, several stochastic search algorithms have been designed based on the theory of global random search (Zhigljavsky, 1991). Basically, those techniques iteratively sample the search space with respect to a probability distribution which is updated according to the result of previous samples and some predefined strategy. Genetic Algorithms (GAs) (Goldberg, 1989) or Greedy Randomised Adaptive Search Procedures (GRASP) (Feo & Resende, 1995) are two particular instances of this paradigm. we present SAGE, a search algorithm based on the same fundamental mechanisms as those techniques. However, it addresses a class of problems for which it is difficult to design transformation operators to perform local search because of intrinsic constraints in the definition of the problem itself. For those problems, a procedural approach is the natural way to construct solutions, resulting in a state space represented as a tree or a DAG. The aim of this paper is to describe the underlying heuristics used by SAGE to address problems belonging to that class. The performance of SAGE is analysed on the problem of grammar induction and its successful application to problems from the recent Abbadingo DFA learning competition is presented.",

}

Genetic Programming entries for Hugues Juille Jordan B Pollack

Citations