| dc.description | This dissertation is submitted to the Graduate Programs in Engineering and Information Technologies in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Information Technologies and Communications, with a major in Intelligent Systems. This document describes and analyses the variable and value ordering problem in Constraint Satisfaction Problems (CSP), and proposes novel techniques to generate hyper-heuristics for such problem. Hyper-heuristics are methodologies that selectively apply low-level heuristics according to the features of the instance at hand, combining the strengths of these heuristics to achieve more general solution methods. The objective of this dissertation is contribute to the knowledge about variable and value ordering heuristics and the description of new techniques to produce hyper-heuristics that behave steadily competent on a wide range of instances when compared against those ordering heuristics. The CSP is a fundamental problem in Artificial Intelligence. It has many immediate practical applications which include vision, language comprehension, scene labelling, knowledge representation, scheduling and diagnosis. The complexity of CSP is in general, computationally intractable. Stated as a classic search problem, every CSP can be solved by going through a search tree associated to the instance. In this way, every variable represents a node in the tree. Every time a variable is instantiated, the constraints must be checked to verify that none of them is violated. When an assignment is in conflict with one or more constraints, the instantiation must be undone, and another value must be considered for that variable. If there are no other values available, the value of one previous instantiated variable must be changed. As we can see, when solving a CSP, the problem of the ordering in which the variables and their values are ordered affects the complexity of the search. Based on this, solving a CSP requires an efficient strategy to select the next variable, in other words, a form to assign priorities and decide which variable will be instantiated before the others and then, decide which value to use for it. Because an exhaustive search is impossible due to the exponential grow with the number of variables, the search is usually guided by heuristics. There are many heuristics exist to decide the ordering in which the variables and their values should be tried, but they have proved to be very specific and work well only on instances with specific features. In this dissertation we are interested in developing a solution model which is able to generate methods that show a good performance for different instances of CSP. Because hyperheuristics are able to adapt to the different problems or instances by dynamically choosing between low-level heuristics during the search, they seem suitable for being used to achieve the objective described. These hyper-heuristics should be able to give good-quality results for a wide set of different CSP instances. In other words, we are interested in developing a ix more flexible solution model than those presented in previous works. These hyper-heuristics can be produced through many strategies. We want to explore some of them and analyse their performance, in order to decide which one are more suitable than others according to some properties of the instances and the current needs in time and quality. In this dissertation, three approaches were used to generate the hyper-heuristics. The first approach uses a decision matrix hyper-heuristic, which contains information about the low-level heuristic to apply given certain features of the instances being solved. This approach is limited in scope because it was designed to work with a small set of features but it provided good results. Later, we studied an evolutionary approach to generate hyper-heuristics. This model is more general than the decision matrix approach and experiments suggest that it produces the hyper-heuristics with more quality among the three models described in this document. Nevertheless, the evolutionary approach requires a significant number of additional operations with respect to the other models to produce one hyper-heuristic. Finally, a neural network approach is introduced. The running time of this model proved that the approach is effective to produce good quality hyper-heuristics in a reasonable time. The general idea of this investigation is to provide a better understanding of the variable and value ordering heuristics for CSP and provide various models for hyper-heuristic generation for variable and value ordering within CSP. All the models described in this investigation generate hyper-heuristics that can be applied to a wider range of instances than the simple heuristics and still achieve acceptable results with respect to time and quality. | |
