Automating algorithm design within a general architecture for intelligence
David M. Steier · 1989
Turning the dream of programming into reality will involve, among other things, getting computers to design algorithms. For human algorithm designers, two abilities seem critical for success: (1) the ability to make design decisions based on diverse types of knowledge, and (2) the ability to improve performance by learning from experience. This thesis reports on three systems--all based on the Soar problem-solving and learning architecture--that advance the state of the art in automatic algorithm design along these two dimensions. Two non-Soar automatic algorithm designers were first partially reimplemented in Soar to produce Designer-Meets-Soar and Cypress-Soar. Features from these two systems were then combined in the current system, Designer-Soar, which designs several simple generate-and-test and divide-and-conquer algorithms. The thesis draws on the experiences in constructing these systems in developing a theory of the algorithm design process, summarized in the following propositions: (1) Design takes place in multiple problem spaces. A subset of these spaces embodies the target model of computation, and another set embodies the application domain model. (2) The task of design is to use knowledge of the application domain to build a procedure for computing the desired output in the computational spaces. (3) The computational spaces have functional operators corresponding to steps in an algorithm, at whatever level of abstraction is necessary for the design. (4) Means-end analysis on the results of execution drives the design, with the resulting series of execution passes in a design session exhibiting the pattern of progressive deepening. (5) Any part of the knowledge necessary for accomplishing the design task may be acquired by learning. The algorithm itself is represented as learned knowledge for navigating through the computational spaces. The purpose of the theory is to present a set of mechanisms that are sufficient to enable an intelligent agent (not necessarily a human) to design algorithms, assuming that it must cope with the diversity of the task environment and its own bounded rationality. Such assumptions hold not only in real algorithm design situations, but in any complex intellectual task, providing support for the claim that a general architecture such as Soar is an appropriate vehicle for this type of research.