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

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

  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
  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
  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