Analysis of a Feature-independent Hyper-heuristic Model for Constraint Satisfaction and Binary Knapsack Problems

Abstract

This document describes and analyzes empirical results of an evolutionary-based hyper-heuristic model applied to Binary Knapsack Problems (0/1 KP) and Constraint Satisfaction Problems (CSP). Hyper-heuristics are high-level methodologies that either select among existing algorithms or generate new ones for solving complex problems. The objective of this dissertation is to contribute to the knowledge about hyper-heuristics and propose a model which is feature-independent in order to obtain competing solutions on a variety of fields. The CSP is a classical example of a complex problem where the solution is a valid assignment of variables in order to satisfy a set of constraints It has many applications including knowledge representation, scheduling and optimization. Although there could be many solutions to a single CSP instance, finding them could represent a hard challenge—its complexity is, in general terms computationally intractable. With many real-life applications like allocation and cargo loading, the 0/1 KP is another example of complex problems, and is one of the most studied in the optimization branch. Its description can be summarized as finding a selection of items packed in a container which yields the highest profit without violating a capacity constraint. Both KPs and CSPs can be stated as classical search problems, undergoing through a search tree associated to a problem instance. Each node in the search tree is a decision point—a variable in CSP or an item in KP. For each of these decision points many different heuristics can be used. Finding the right heuristics at the right decision points requires of efficient strategies, since an exhaustive search may be impossible due to the exponential growth of the variables involved in the problem. Many heuristics that are feasible and efficient exist for both CSPs and KPs. Nevertheless, these methods usually require delicate setup and constant monitoring as it may be necessary to adjust some parameters in order to get a solution within an acceptable time frame. The concept of hyper-heuristics holds high relevance in this context since new solutions can come up from already known heuristic methods. In order for the hyper-heuristic to appropriately map a method to a state of the search problem, it needs some criteria. Usually problem characterization is useful in this process—two problem instances with similar features are very likely to be solved efficiently in the same manner. However, problem characterization may be especially difficult in some cases, as most real-life situations usually feature hyper-dimensional search spaces which are non-calculus friendly. In this dissertation we are interested in developing a solution model able to come up with general methods that show good performance even when dealing with no problem characterization whatsoever. Having a more flexible solution model allows for an easier adaptation of the framework to other domains, where problem characterization may be somewhat difficult. This document explores an evolutionary approach to generate hyper-heuristic from a pool of already known heuristics. Experiments suggest that the model is able to find and exploit key decision points in both KP and CSP. The model can also find better solutions from mixing heuristics that perform poorly on their own. However, the method is prone to overfitting under certain conditions. The general idea of this dissertation is to provide a better understanding on the generality aspect of hyper-heuristics and provide a feature-independent model to generate hyper-heuristics in order to tackle a variety of combinatorial optimization problems.

Xavier F. C. Sánchez Díaz

PhD candidate in Artificial Intelligence

PhD candidate in Artificial Intelligence at the Department of Computer Science (IDI) of the Norwegian University of Science and Technology