Learning to combine heuristics to solve constraint satisfaction problems.
Item
-
Title
-
Learning to combine heuristics to solve constraint satisfaction problems.
-
Identifier
-
AAI3310605
-
identifier
-
3310605
-
Creator
-
Petrovic, Smiljana.
-
Contributor
-
Adviser: Susan L. Epstein
-
Date
-
2008
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer Science
-
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. This research is on machine-learning techniques to select appropriately from among a large body of heuristics, and combine them into a weighted mixture that works well on a specific class of constraint satisfaction problems.;The learning used here is a form of self-supervised reinforcement learning. The training instances come from the solver's own (likely imperfect) successful searches. As a result, learning lacks reliable information on how much any individual decision or mutual interaction of heuristics influenced overall search performance.;A pre-existing learner has weights for heuristics learned from the size of the search space explored. The new algorithms proposed and tested here use different ways to gauge and adapt search performance; they learn from the accuracy, intensity, frequency and distribution of heuristics' preferences. Stochastic methods address challenges for that learner on hard problems under limited resources and with large and contradictory set of heuristics.;This work is an important step toward automated problem solving. The resultant solver is effective, robust and self-adaptive. It thereby relieves the user of the burden of providing domain specific knowledge for a solver. Although the experimental work is done on constraint satisfaction problems, the machine learning techniques presented here are general, and therefore applicable to many other domains.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
