Solving the Quadratic Assignment Problem with BOA

Bie, A.M. van der (2011) Solving the Quadratic Assignment Problem with BOA. Bachelor's Thesis, Artificial Intelligence.

Preview	Text Bachelorproject_Alex_van_der_Bie.pdf - Published Version Download (130kB) | Preview
	Text akkoord.pdf - Other Restricted to Registered users only Download (30kB)

Abstract

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.

Item Type:	Thesis (Bachelor's Thesis)
Degree programme:	Artificial Intelligence
Thesis type:	Bachelor's Thesis
Language:	English
Date Deposited:	15 Feb 2018 07:46
Last Modified:	15 Feb 2018 07:46
URI:	https://fse.studenttheses.ub.rug.nl/id/eprint/9765

Actions (login required)

View Item