Show simple item record

dc.contributor.advisor Abdelbar, Ashraf Hosny, Manar 2013-02-03T08:29:05Z 2013-02-03T16:00:08Z 2000 Spring en 2013-02-03
dc.description.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. en
dc.format.extent 193 p. en
dc.format.medium theses en
dc.language.iso en en
dc.rights Author retains all rights with regard to copyright. en
dc.subject MAP (Computer program language) en
dc.subject Genetic algorithms en
dc.subject.lcsh Thesis (M.A.)--American University in Cairo en
dc.title An adaptive hybrid genetic-annealing approach for solving the map problem on belief networks en
dc.type Text en
dc.subject.discipline Computer Science en
dc.rights.access This item is available en
dc.contributor.department American University in Cairo. Dept. of Computer Science and Engineering en
dc.description.irb American University in Cairo Institutional Review Board approval is not necessary for this item, since the research is not concerned with living human beings or bodily tissue samples. en
dc.contributor.committeeMember Abdelbar, Ashraf
dc.contributor.committeeMember Goneid, Amr
dc.contributor.committeeMember Sameh, Ahmed
dc.contributor.committeeMember Salem, Abd El Badie

Files in this item


This item appears in the following Collection(s)

  • Theses and Dissertations [1807]
    This collection includes theses and dissertations authored by American University in Cairo graduate students.

Show simple item record