A Sampling-Based Heuristic for Tree Search Applied to
Grammar Induction
Proceedings of the Fifteenth National Conference on
Artificial Intelligence (AAAI-98) Tenth Conference on
Innovative Applications of Artificial Intelligence
(IAAI-98), Madison, Wisconsin, USA, AAAI Press Books, (26-30 July 1998)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.