A Sampling-Based Heuristic for Tree Search Applied to Grammar Induction   [TS] [GI]

by

Juillé, H. and Pollack, J., B.

Literature search on Evolutionary ComputationBBase ©1999-2013, Rasmus K. Ursem
     Home · Search · Adv. search · Authors · Login · Add entries   Webmaster
Note to authors: Please submit your bibliography and contact information - online papers are more frequently cited.

Info: Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI-98) Tenth Conference on Innovative Applications of Artificial Intelligence (IAAI-98) (Conference proceedings), 1998
Keywords:genetic algorithms, genetic programming, search, massively parallel systems, inductive learning
Abstract:
In the field of Operation Research and Artificial Intelligence, [AI] several stoch astic search algorithms [SA] have been designed based on the theory of global random search [RS] (Zhigljavsky, 1991). Basically, those techniques iteratively sample the s earch space with respect to a probability distribution which is updated accordin g to the result of previous samples and some predefined strategy. Genetic Algori thms (GAs) (Goldberg, 1989) or Greedy Randomized Adaptive Search Procedures (GRA SP) (Feo & Resende, 1995) are two particular instances of this paradigm. In this paper, we present SAGE, a search algorithm based on the same fundamental me chanisms as those techniques. However, it addresses a class of problems for whic h it is difficult to design transformation operators to perform local search [LS] bec ause of intrinsic constraints in the definition of the problem itself. For those problems, a procedural approach is the natural way to construct solutions, resu lting 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 analyzed on the problem of grammar in duction and its successful application to problems from the recent Abbadingo DFA learning competition is presented.
URL(s):(G)zipped postscript

Review item:

Mark as doublet (will be reviewed)

Print entry



BibTex:
@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",
  URL =          "http://www.cs.brandeis.edu/~hugues/papers/AAAI_98.ps.gz",
  abstract =     "In the field of Operation Research and Artificial
                 Intelligence, several stoch astic search algorithms
                 have been designed based on the theory of global random
                 search (Zhigljavsky, 1991). Basically, those techniques
                 iteratively sample the s earch space with respect to a
                 probability distribution which is updated accordin g to
                 the result of previous samples and some predefined
                 strategy. Genetic Algori thms (GAs) (Goldberg, 1989) or
                 Greedy Randomized Adaptive Search Procedures (GRA SP)
                 (Feo & Resende, 1995) are two particular instances
                 of this paradigm. In this paper, we present SAGE, a
                 search algorithm based on the same fundamental me
                 chanisms as those techniques. However, it addresses a
                 class of problems for whic h it is difficult to design
                 transformation operators to perform local search bec
                 ause of intrinsic constraints in the definition of the
                 problem itself. For those problems, a procedural
                 approach is the natural way to construct solutions,
                 resu lting 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
                 analyzed on the problem of grammar in duction and its
                 successful application to problems from the recent
                 Abbadingo DFA learning competition is presented.",
}