1. UKM Learning and Research Repository
2. PHD Thesis / Tesis PHD
3. Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat

Title:	Hyper-Heuristics For Combinatorial Optimization Problems
Authors:	Nasser R Sabar (P54811)
Supervisor:	Masri Ayob, Assoc. Prof. Dr.
Keywords:	Hyper-Heuristics For Combinatorial Optimization Hyper-Heuristics Combinatorial Optimization Problems Combinatorial Optimization Problems In Hyper-Heuristics Combinatorial optimization-Data processing
Issue Date:	12-Jun-2013
Description:	Hyper-heuristics (HH) were introduced to raise the level of generality of search methodologies. HH operate over a search space of heuristics, rather than directly search the solution space. The main components of a perturbative HH to choose heuristics are the selection mechanism and the acceptance criteria. Hence, many researchers are looking for an intelligent selection mechanism (to select the most suitable low level heuristic) and an adaptive acceptance criterion (to guide the search towards promising regions). The effectiveness of different heuristics may vary significantly depending on the problem domain or instance. Thus, if several heuristics can be combined intelligently, or heuristics can be generated during the problem solving, then they may perform better than those that were manually designed by human experts. Indeed, if the high level heuristic components (selection mechanism and acceptance criteria) can influence the performance of a HH, then we will have a HH framework that is capable of working well across different problem domains if we employ automatic program generation methods to either intelligently combine existing components or generate the high level heuristic components. This thesis proposes three different HH frameworks: (i) A grammatical evolution HH framework (GE-HH) to intelligently combine heuristic components. It takes several heuristic components as input and automatically generates a perturbation local search template by selecting the appropriate combination of these heuristic components. The generated local search template starts with an initial solution and then attempts to iteratively improve it. (ii) A HH framework that uses the dynamic multi-armed bandit-extreme value based rewards as an online heuristic selection mechanism, and gene expression programming algorithm to automatically generate the acceptance criteria during the solving process (DM-GEP). (iii) An on-line gene expression programming framework to automatically generate the high level heuristic components (heuristic selection mechanism and the acceptance criteria) of the HH framework (GEP-HH). GEP-HH iteratively generates a population of high level heuristic components which are used to decide which heuristic should be selected and the acceptance or rejection of the resultant solution. To enhance the effectiveness of the proposed HH frameworks, we embed them with a memory component, which contains a collection of both high quality and diverse solutions, and are dynamically updated. To test the generality, consistency and performance of the proposed HH frameworks, eight combinatorial optimization problems are considered: exam timetabling, dynamic vehicle routing, boolean satisfiability, one dimensional bin packing, permutation flow shop, personnel scheduling, travelling salesman and vehicle routing with time windows. Results demonstrate that the proposed HH frameworks obtain competitive results (if not best results for some instances), on all problem domains when compared to the best known methods in the scientific literature. This demonstrates that the use of a population of solutions, within a HH, along with an automatic program generation method to either intelligently combine existing components or generate the high level heuristic components, produces an effective HH framework that generalizes well across a wide variety of combinatorial optimization problems.,PhD
Pages:	349
Call Number:	QA402.5 .S229 2013 3
Publisher:	UKM, Bangi
Appears in Collections:	Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.