Abstract
Stochastic search techniques are used to solve NP-hard combinatorial optimization problems. Simulated annealing, genetic algorithms and hybridization of both, all attempt to find the best solution with minimal cost and time. Guided Evolutionary Simulated Annealing is one technique of such hybridization. It is based on evolutionary programming where a number of simulated annealing chains are working in a generation to find the optimum solution for a problem. Abduction is the problem of finding the best explanation to a given set of observations. In AI, this has been modeled by a set of hypotheses that need to be assumed to prove the observation or goal. Cost-Based Abduction (CBA) associates a cost to each hypothesis. It is an example of an NP-hard problem, where the objective is to minimize the cost of the assumed hypotheses to prove the goal. Analyzing the search space of a problem is one way of understanding its nature and categorizing it into straightforward, misleading or difficult for genetic algorithms. Fitness-Distance Correlation and Fitness-Distance plots are helpful tools in such analysis. This thesis examines solving the CBA problem using Simulated Annealing and Guided Evolutionary Simulated Annealing and analyses the Fitness-Distance landscape of some Cost-Based abduction problem instances.
School
School of Sciences and Engineering
Department
Computer Science & Engineering Department
Degree Name
MS in Computer Science
Date of Award
6-1-2005
Online Submission Date
3-14-2013
First Advisor
Abdelbar, Ashraf
Committee Member 1
Abdelbar, Ashraf
Document Type
Thesis
Extent
112 p.
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
IRB
Not necessary for this item
Recommended Citation
APA Citation
Amer, H. A.
(2005).Parallel versus iterated: comparing population oriented and chained sequential simulated annealing approaches to cost-based abduction [Thesis, the American University in Cairo]. AUC Knowledge Fountain.
https://fount.aucegypt.edu/retro_etds/2376
MLA Citation
Amer, Heba Abdallah. Parallel versus iterated: comparing population oriented and chained sequential simulated annealing approaches to cost-based abduction. 2005. American University in Cairo, Thesis. AUC Knowledge Fountain.
https://fount.aucegypt.edu/retro_etds/2376