Exploring Hyper-Heuristic Approaches for Solving Constraint Satisfaction Problems

Hdl Handle:
http://hdl.handle.net/11285/572560
Title:
Exploring Hyper-Heuristic Approaches for Solving Constraint Satisfaction Problems
Issue Date:
01/12/2011
Abstract:
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.
Keywords:
Heuristic; Constraint Satisfaction
Degree Program:
Doctoral Program Information Technologies and Communications
Advisors:
Dr. Hugo Terashima Marin
Committee Member / Sinodal:
Dr. Ender �zcan; Dr. Andrew J. Parkes; Dr. Manuel Valenzuela Rendón; Dr. Santiago Enrique Conant Pablos
Degree Level:
Doctor of Philosophy in Information Technologies and Communications.
School:
School Of Engineering And Information Technologies
Campus Program:
Campus Monterrey
Discipline:
Ingeniería y Ciencias Aplicadas / Engineering & Applied Sciences
Appears in Collections:
Ciencias Exactas

Full metadata record

DC FieldValue Language
dc.contributor.advisorDr. Hugo Terashima Marines
dc.creatorOrtiz Bayliss, José C.en
dc.date.accessioned2015-08-17T11:35:17Zen
dc.date.available2015-08-17T11:35:17Zen
dc.date.issued01/12/2011-
dc.identifier.urihttp://hdl.handle.net/11285/572560en
dc.description.abstractThis 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.en
dc.language.isoenen
dc.rightsOpen Accessen
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.titleExploring Hyper-Heuristic Approaches for Solving Constraint Satisfaction Problemsen
dc.typeTesis de Doctoradoes
thesis.degree.grantorInstituto Tecnológico y de Estudios Superiores de Monterreyes
thesis.degree.levelDoctor of Philosophy in Information Technologies and Communications.en
dc.contributor.committeememberDr. Ender �zcanes
dc.contributor.committeememberDr. Andrew J. Parkeses
dc.contributor.committeememberDr. Manuel Valenzuela Rendónes
dc.contributor.committeememberDr. Santiago Enrique Conant Pabloses
thesis.degree.disciplineSchool Of Engineering And Information Technologiesen
thesis.degree.nameDoctoral Program Information Technologies and Communicationsen
dc.subject.keywordHeuristicen
dc.subject.keywordConstraint Satisfactionen
thesis.degree.programCampus Monterreyes
dc.subject.disciplineIngeniería y Ciencias Aplicadas / Engineering & Applied Scienceses
All Items in REPOSITORIO DEL TECNOLOGICO DE MONTERREY are protected by copyright, with all rights reserved, unless otherwise indicated.