Optimal Ordered Problem Solver

title = "Optimal Ordered Problem Solver",

institution = "IDSIA",

year = "2002",

number = "IDSIA-12-02",

month = "31 " # jul,

keywords = "genetic algorithms, genetic programming, OOPS, bias-optimality, incremental optimal universal search, metasearching, metalearning, self-improvement",

URL = "

ftp://ftp.idsia.ch/pub/juergen/oops.ps.gz",

abstract = "We extend principles of non-incremental universal search to build a novel, optimally fast, incremental learner that is able to improve itself through experience. The Optimal Ordered Problem Solver (OOPS) searches for a universal algorithm that solves each task in a sequence of tasks. It continually organises and exploits previously found solutions to earlier tasks, efficiently searching not only the space of domain-specific algorithms, but also the space of search algorithms.

The initial bias is embodied by a task-dependent probability distribution on possible program prefixes (pieces of code that may continue). Prefixes are self-delimiting and executed in online fashion while being generated. They compute the probabilities of their own possible continuations. Let p^n denote a found prefix solving the first n tasks. It may exploit previous solutions p^i (i In illustrative experiments, our self-improver becomes the first general system that learns to solve all n disk Towers of Hanoi tasks (solution size 2^n-1) for n up to 30, profiting from previously solved, simpler tasks involving samples of a simple context free language.",

notes = "GP is a heuristic method with little or no theoretical justification (http://www.idsia.ch/~juergen/gp.html); most existing GP implementations do not even allow for loops and recursion. The following method, however, performs optimal incremental search in general program space. http://www.idsia.ch/~juergen/oops.html

arXiv:cs.AI/0207097 v1;