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 of Sciences and Engineering
Computer Science & Engineering Department
MS in Computer Science
Date of Award
Online Submission Date
Committee Member 1
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
Not necessary for this item
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.
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.