Solving the Quadratic Assignment Problem with BOA

Genetic Algorithms have been used throughout the years for a large number of optimization problems. However, it has become ever more clear that these algorithms are powerful but not always very efficient. The biggest problem is that GAs often take a long time to find a near-optimal solution. Martin Pelikan has proposed an optimization technique called the Bayesian Optimization Algorithm (BOA). BOA uses the structure of the best solutions to model the data in a Bayesian Network, using the building blocks of these solutions. Then new solutions can be extracted from the network and proposed for evaluation. While Pelikan used this algorithm to solve simple, mostly binary, problems, we have used the same techniques for the Quadratic Assignment Problem, an NP-Hard problem. Our findings are that with BOA we get better solutions, more so for greater problem sizes.