Project Title: Benchmarking Population Based Cooperative Heuristics for the Multidimensional Knapsack Problem
Student: Asna Seemab
Course: MSc Advanced Computing Science

Abstract:
The multi-dimensional knapsack problem is a variation of the famous np-hard knapsack problem that
has a lot of research to its credit. Because of the nature of the problem, various meta-heuristic
techniques have been devised to obtain optimal results. Past researches have attempted different
variations of tabu-search, simulated annealing, genetic mutation, ant colony optimization, etc but all
of them are single solution approaches. This report attempts to apply the population based approach to
iterative improvement algorithm, tabu-search algorithm, simulated annealing algorithm and hybrid
meta-heuristic algorithm and benchmark the results obtained against known results and their single
solution counterparts. To accomplish this, the single solution algorithms are extended using
cooperative approach which involves global memory sharing between member solutions of the
population. It was found that population based approach proves to be more consistent in giving the
best known results in comparison to single solution approach. Also, hybrid meta-heuristic algorithm
outperformed the other three, being a combination of iterative improvement, simulated annealing and
genetic mutation. This opens the door for implementation of population based approaches to more
problems to study their performance and further the results.