Hill-Climbing and Genetic Algorithms coded using OR-Parallel
Logic plus Meta-Control
P. Kefalas
and T.J.Reynolds
Abstract: Brave plus Meta-Brave is a parallel
logic programming system. Brave is a minimal Prolog designed for OR-parallel
execution. We choose OR-parallelism because we believe that many Artificial
Intelligence problems exhibit large search spaces suitable for OR-parallel
exploration. OR-parallelism also leads to large independent computations
which seldom need to communicate. Brave lacks the cut, assert and retract
of Prolog because we believe they compromise parallel execution. However,
in common with other workers, we believe we need replacements, in particular
to code parallel versions of search algorithms, where guidance of the search
in one subtree requires information from another subtree. Rather than include
this meta-contol in Brave itself, we provide a meta language in which we
may express guidance of search as a separate declarative programming activity.
We believe this separation leads to clearer programs, without inhibiting
the free exploitation of parallelism. Meta-Brave can guide search using
three main mechanisms: partial results are selectively remembered (lemmas),
conditions for early failure of subtrees are stated (pruning), the style
of search is altered (strategies). We show how this combination of
features makes the Brave system specially suited to writing clear programs
for example search algorithms taken from Artificial Intelligence. In previous
work results were presented for the application of Brave to the branch
and bound algorithm and alpha-beta pruning of game trees. In this paper
we present results for hill-climbing and genetic algorithms.
Keywords: Hill-Clibing Search, Genetic Algorithms,
OR-Parallelism, Prolog
Appeared in: Proc. of the 1st Intern. Workshop on Parallel Processing
for AI, held in association with Intern. Conference in AI, IJCAI-91, Sydney,
Australia, 1991
Available: Hardcopy on request from the authors. .
Back
to Dept. of Computer Science, CITY Liberal Studies
Back
to Petros Kefalas home page