An ant colony optimization approach for the multidimensional knapsack problem

Ant colony optimization is a metaheuristic that has been applied to a variety of combinatorial optimization problems. In this paper, an ant colony optimization approach is proposed to deal with the multidimensional knapsack problem. It is an extension of Max Min Ant System which imposes lower and upper trail limits on pheromone values to avoid stagnation. In order to choose the lower trail limit, we provide a new method which takes into account the influence of heuristic information. Furthermore, a local search procedure is proposed to improve the solutions constructed by ants. Computational experiments on benchmark problems are carried out. The results show that the proposed algorithm can compete efficiently with other promising approaches to the problem.