Learning a Mixture of Search Heuristics

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