Abstract
Genetic algorithms (GAs) and simulated annealing (SA) are two important search methods that have been used successfully in solving difficult problems such as combinatorial optimization problems. Genetic algorithms are capable of wide exploration of the search space, while simulated annealing is capable of fine tuning a good solution. Combining both techniques may result in achieving the benefits of both and improving the quality of the solutions obtained. Several attempts have been made to hybridize GAs and SA. One such attempt was to augment a standard GA with simulated annealing as a genetic operator. SA in that case acted as a directed or intelligent mutation operator as opposed to the random, undirected mutation operator of GAs. Although using this technique showed some advantages over GA used alone, one problem was to find fixed global annealing parameters that work for all solutions and all stages in the search process. Failing to find optimum annealing parameters affects the quality of the solution obtained and may degrade performance. In this research, we try to overcome this weakness by introducing an adaptive hybrid GA - SA algorithm, in which simulated annealing acts as a special case of mutation. However, the annealing operator used in this technique is adaptive in the sense that the annealing parameters are evolved and optimized according to the requirements of the search process. Adaptation is expected to help guide the search towards optimum solutions with minimum effort of parameter optimization. The algorithm is tested in solving an important NP-hard problem, which is the MAP (Maximum a-Posteriori) assignment problem on BBNs (Bayesian Belief Networks). The algorithm is also augmented with some problem specific information used to design a new GA crossover operator. The results obtained from testing the algorithm on several BBN graphs with large numbers of nodes and different network structures indicate that the adaptive hybrid algorithm provides an improvement of solution quality over that obtained by GA used alone and GA augmented with standard non-adaptive simulated annealing. Its effect, however, is more profound for problems with large numbers of nodes, which are difficult for GA alone to solve.
School
School of Sciences and Engineering
Department
Computer Science & Engineering Department
Degree Name
MS in Computer Science
Date of Award
5-1-2000
Online Submission Date
5-2000
First Advisor
Abdelbar, Ashraf
Committee Member 1
Goneid, Amr
Committee Member 2
Sameh, Ahmed
Committee Member 3
Salem, Abd el Badie
Document Type
Thesis
Extent
193 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
Hosny, M.
(2000).An adaptive hybrid genetic-annealing approach for solving the map problem on belief networks [Thesis, the American University in Cairo]. AUC Knowledge Fountain.
https://fount.aucegypt.edu/retro_etds/2331
MLA Citation
Hosny, Manar. An adaptive hybrid genetic-annealing approach for solving the map problem on belief networks. 2000. American University in Cairo, Thesis. AUC Knowledge Fountain.
https://fount.aucegypt.edu/retro_etds/2331
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License