Applications of Bee Colony Optimization

Abstract

Many computationally difficult problems are attacked using non-exact algorithms, such as approximation algorithms and heuristics. This thesis investigates an ex- ample of the latter, Bee Colony Optimization, on both an established optimization problem in the form of the Quadratic Assignment Problem and the FireFighting problem, which has not been studied before as an optimization problem. Bee Colony Optimization is a swarm intelligence algorithm, a paradigm that has increased in popularity in recent years, and many of these algorithms are based on natural pro- cesses.
We tested the Bee Colony Optimization algorithm on the QAPLIB library of Quadratic Assignment Problem instances, which have either optimal or best known solutions readily available, and enabled us to compare the quality of solutions found by the algorithm. In addition, we implemented a couple of other well known algorithms for the Quadratic Assignment Problem and consequently we could analyse the runtime of our algorithm.
We introduce the Bee Colony Optimization algorithm for the FireFighting problem. We also implement some greedy algorithms and an Ant Colony Optimization al- gorithm for the FireFighting problem, and compare the results obtained on some randomly generated instances.
We conclude that Bee Colony Optimization finds good solutions for the Quadratic Assignment Problem, however further investigation on speedup methods is needed to improve its performance to that of other algorithms. In addition, Bee Colony Optimization is effective on small instances of the FireFighting problem, however as instance size increases the results worsen in comparison to the greedy algorithms, and more work is needed to improve the decisions made on these instances.