Hill-Climbing and Genetic Algorithms coded using OR-Parallel Logic plus Meta-Control

 P. Kefalas and T.J.Reynolds 
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