Many science and engineering applications require finding solutions to optimization problems by satisfying a set of constraints. These problems are typically ill-structured and intractable. They are formalized as constraint problems (CPs). Evolutionary algorithms (EAs) are known to be good solvers for optimization problems ubiquitous in various problem domains. EAs have also been used to solve CPs, however traditional EAs are ‘blind’ to constraints as they do not extract and exploit information from the constraints to better ‘inform’ search for solutions. In this thesis, the constraint problems are investigated and characterized. A variation of EA is studied and proposed which extracts information from constraints to better guide the search process. A novel computational model is developed as a prototype and validated with several benchmark problems. The model is called ICHEA (for Intelligent Constraint Handling Evolutionary Algorithm) and it is developed to work on domains with both quantitative and qualitative data and constraints. ICHEA modelling is designed to be independent of problem parameters and mostly focuses on maximally utilizing information from constraint in its search. It takes the divide and conquer approach for search through incrementally taking a sequence of constraints to solve CPs. It models constraints preferences and constraints strengths and exploits their relationships in search. The computational model developed allows for what-if analysis for exploring search spaces and for revising solution paths. Incrementality is a requisite feature as it models solving dynamic CPs where constraints arrive at run time or where constraints change over time. The challenge undertaken is to maximally utilize solutions already developed to a point in time to process any new, arriving sub-sequence of constraints rather than search for a solution anew each time a constraint changes or a new constraint arrives. The experimental results from ICHEA from benchmark test problems demonstrate improvements on efficiency for the continuous domain and also produce competitive results for discrete domains. The main objective is not only to outperform other algorithms and approaches in efficiency and efficacy but also to provide a generic (i.e. problem independent) computational model that is suitable for constraint handling and solving. Several experiments have been conducted to benchmark ICHEA with other models. The results from these experiments are encouraging. ICHEA can be extended to support mixed data (continuous and discrete) domains of CPs. It can also be designed based to benefit from a multi-agent environment where each subsequence of constraints clustered on constraint relationships and hierarchies is handled by autonomous agent to get more efficient results. Several future extensions to the current investigation are proposed to address some remaining research gaps from the reflections, and new research questions that emerged from the current work.
Information discovery from constraints for evolutionary computational model
Sharma, A. (Author). 2014
Student thesis: Doctoral Thesis