Аннотация
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.
Пользователи данного ресурса
Пожалуйста,
войдите в систему, чтобы принять участие в дискуссии (добавить собственные рецензию, или комментарий)