View Full Document

Learning a Mixture of Search Heuristics



View the full content.
View Full Document
View Full Document

5 views

Unformatted text preview:

Learning a Mixture of Search Heuristics Smiljana Petrovic1 Susan L Epstein1 2 and Richard J Wallace3 1 Department of Computer Science The Graduate Center The City University of New York NY USA 2 Department of Computer Science Hunter College of The City University of New York NY USA 3 Cork Constraint Computation Centre and Department of Computer Science University College Cork Cork Ireland spetrovic gc cuny edu susan epstein hunter cuny edu r wallace 4c ucc ie Abstract Problem solvers have at their disposal many heuristics that may support effective search The efficacy of these heuristics however varies with the problem class and their mutual interactions may not be well understood The long term goal of our work is to learn how to select appropriately from among a large body of heuristics and how to combine them into a weighted mixture that works well on a specific class of problems During learning search heuristics weights are used to solve a problem and then updated based on their subsequent performance This paper proposes and demonstrates a variety of ways to gauge and adapt search performance and shows how their application can improve subsequent search performance Keywords search learning mixture of experts 1 Introduction A program that uses the results of its own search experience to modify its subsequent behavior does adaptive search Such an approach permits the program to tailor its algorithm to the task at hand In particular given a set of search heuristics of unknown quality and a class of putatively similar hard problems our goal is to learn to solve those problems well The thesis of our work is that adaptive search for a class of constraint satisfaction problems can provide improved performance This paper describes several techniques that gauge search performance on constraint satisfaction problems and learn to improve it Machine learning experiments require both training examples and performance criteria Given a set of problems an autonomous learner



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Learning a Mixture of Search Heuristics and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Learning a Mixture of Search Heuristics and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?