Abstract
In this thesis we analyze the search space characteristics of Cost Based Abduction, through investigating fitness-distance correlation for local minima and landscape ruggedness. Our results indicate that stochastic local search (SLS) techniques would be promising on this problem given the fitness distance correlation values that we compute early on. We design three greedy solution construction heuristics in order to improve the quality of the solutions we achieve through our ILS search heuristic. We go on to present an iterated local search algorithm based on hill-climbing, tabu search and compare it to a simulated annealing technique. This algorithm combines two SLS methods that have been used very successfully for solving a variety of other hard combinatorial optimization problems; Iterated Local Search (ILS) and Robust Tabu Search (RoTS) modified to fit CBA problems. We finally compare the performance of our algorithm to simulated annealing through Run Length analysis (Run length distributions). The Iterated local search algorithm outperforms the simulated annealing algorithm on most occasion, we augmented it with a repetitive simulated annealing algorithm and the result was superiority of the hybrid ILS technique over the simulated annealing algorithm for all of our testing CBA instances.
Department
Computer Science & Engineering Department
Degree Name
MS in Computer Science
Date of Award
2-1-2007
Online Submission Date
7-25-2006
First Advisor
Ashraf Abdelbar
Committee Member 1
Amr Goneid
Committee Member 2
Ahmed Rafea
Committee Member 3
Ismail Amr Ismail
Document Type
Thesis
Extent
93 leaves
Library of Congress Subject Heading 1
Iterative methods (Mathematics)
Library of Congress Subject Heading 2
Cost control.
Rights
The American University in Cairo grants authors of theses and dissertations a maximum embargo period of two years from the date of submission, upon request. After the embargo elapses, these documents are made available publicly. If you are the author of this thesis or dissertation, and would like to request an exceptional extension of the embargo period, please write to thesisadmin@aucegypt.edu
Recommended Citation
APA Citation
Gheita, S.
(2007).Exploring the fitness landscape and the run-time behavior of an iterated local search algorithm for cost-based abduction [Thesis, the American University in Cairo]. AUC Knowledge Fountain.
https://fount.aucegypt.edu/retro_etds/2039
MLA Citation
Gheita, Sarah M Hossam Ali. Exploring the fitness landscape and the run-time behavior of an iterated local search algorithm for cost-based abduction. 2007. American University in Cairo, Thesis. AUC Knowledge Fountain.
https://fount.aucegypt.edu/retro_etds/2039
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Call Number
Thesis 2006/88
Location
mgfth