Adaptive Aspects of Heuristic Search

In this thesis we investigate methods by which GT4, a revised and extended version of the Doran-Michie Graph Traverser, might in the course of its problem-solving activity learn about the domain in which it is searching and thereby improve its performance. We study first the problem of automatically optimizing the parameters of GT4' s evaluation function. In particular, we investigate the distance estimator method proposed by Doran and Michie. Using two sliding-block puzzles and the algebraic manipulation problems of Quinlan and Hunt we demonstrate experimentally the feasibility of this method of parameter optimization. An interesting feature of the work is that optimization is implemented by recursive call of GT4, the algorithm acting for this purpose as a pattern search numerical optimizer. A theoretical analysis of several factors affecting the success of the distance estimator method is then carried out and alternative approaches to parameter optimization are proposed and discussed. In Chapter 8 we describe the results of our experiments in automatic operator selection. We investigate, in particular, a promotional scheme for re-ordering ┌', the global operator list used by GT4, so that operators of proven utility are given preference in the order of application. Our results demonstrate that the scheme successfully improves the ordering of a list of 48 Eight-puzzle macro-operators