Abstract:
Knapsack problems (KP) and variants thereof are classic problems in computer science with
diverse applications. The knapsack problem has been used to model various decision making
processes. Industrial applications find the need for satisfying additional constraints and these
necessities lead to the variants and extensions of knapsack problems which are complex to
solve. All variants of KP require a subset of given items to be chosen with the aim of maximizing
the total profit without exceeding the capacity of the knapsack(s). In the Multidimensional
Knapsack Problem (MKP) the resources are multidimensional whereas in the Multiple Choice
Knapsack Problem (MCKP) the picking criteria for items are restricted. Multiple-choice Multidimensional
Knapsack Problem (MMKP) is a combination of MKP and MCKP. Finding exact
solutions for most KP variants, including MCKP, MKP and MMKP is NP-hard. There exist
a number of heuristics in the literature for 0-1 KPs, MKPs and MMKPs. Another direction
to solve these variants is to apply various meta-heuristic techniques. Examples of such metaheuristics
include tabu search, simulated annealing, genetic algorithms, bee colony optimization,
artificial immune system and ant colony optimization.
This research focuses on MKP and MMKP, two complex variants of the knapsack problem.
It involves an empirical analysis of the existing state of the art heuristics with respect to problem
structure especially in constraint correlation and constraint slackness settings. The main focus
of this research is to develop improved metaheuristic algorithms for MKP and MMKP. As
for the meta-heuristic tools, we are mainly interested in Ant Colony Optimization (ACO) and
Artificial Immune System (AIS). Another objective of this research is to develop improved
heuristic approaches to initialize searches and to improve local search neighborhoods.
The main contribution of this thesis work is the design of a number of good meta-heuristic
algorithms based on ACO and AIS. We have also devised some very effective local search techniques which reduces the scalability and slow convergence problem of the meta-heuristic
techniques. Our ACO algrithms not only produces near-optimal solutions but also greatly enhances
convergence speed. A comparative analysis with other state-of-the-art heuristic algorithms
based on public MMKP dataset shows that, in all cases our approaches outperform others.
We have also shown that our algorithms find near optimal (within 3% of the optimal value)
solutions within milliseconds, which makes our approach very attractive for large scale real time
systems. Also our AIS algorithms produces quality solutions within reasonable time boundary.
Though AIS algorithms take longer time than ACO algorithms to find good solutions, they produce
better result than our ACO algorithms for public datasets of MKP and MMKP. Infact our
AIS algorithms beats all other meta-heuristic approaches in terms of solution quality.
