Metaheuristic algorithms for some knapsack variants

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.