An Adaptive Hybrid Genetic-Annealing Approach for Solving the MAP Problem on Belief Networks

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.