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.
Computer Science & Engineering Department
MS in Computer Science
Date of Award
Online Submission Date
Committee Member 1
Committee Member 2
Committee Member 3
Ismail Amr Ismail
Library of Congress Subject Heading 1
Iterative methods (Mathematics)
Library of Congress Subject Heading 2
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 firstname.lastname@example.org
(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.
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.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.