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

Call Number

Thesis 2006/88

Location

mgfth

Share

COinS