An ant colony optimization approach for solving the Multidimensional Knapsack Problem

Ant Colony Optimization (ACO) is a metaheuristic that has been used to solve variety of optimization problems. In this paper, an ACO approach is proposed to solve the Multidimensional Knapsack Problem (MKP). The algorithm proposed in this paper is called preference-list ACO algorithm with mutation (PACOM). A preference-list is introduced to determine the number of items that should be considered by an ant. In addition, infeasible solutions are allowed to be constructed to reduce the time complexity to generate a solution. We compare the proposed algorithm with several ACO algorithms applied on the MKP. The experimental results of the benchmark problems show PACOM outperforms other ACO algorithms.