An Ant Colony Optimization Algorithm Based on Mutation and Pheromone Diffusion for the Multidimensional Knapsack Problems

Ant colony optimization (ACO) algorithm is a metaheuristic and stochastic search technology, which has been one of the effective tools for solving discrete optimization problems. The multidimensional knapsack problem (MKP) is a classical combinatorial optimization problem, whose goal is to find a subset of objects that maximizes the total profit while satisfying some resource constraints. There are many algorithms to effectively solve MKPs, where ACO algorithm is a new and robust method. However, there are two bottlenecks in which the ACO algorithm takes too much time and solves imprecisely for large-scaled MKP. In this paper, a novel ACO algorithm with high performance is proposed, which syncretizes the improvements of the pheromone updating and the stochastic search scheme. Firstly, in light of the preference to better solutions, the association distances among objects are mined in each cycle with a Top-k strategy. Then a pheromone diffusion model based on information fountain of an object is established, which strengthens the collaborations among ants. Finally, a simple mutation scheme is employed to optimize the evolution results of each step. The experimental results on the benchmark testing set of MKPs show that the proposed algorithm can not only get much more optimal solutions but also greatly enhance convergence speed compared with the latest improved algorithms.