A new ant colony optimization algorithm for the multidimensional Knapsack problem

作者：Kong, Min^*; Tian, Peng; Kao, Yucheng

来源：Computers & Operations Research, 2008, 35(8): 2672-2683.

DOI：10.1016/j.cor.2006.12.029

• ant colony optimization
• binary ant system
• combinatorial optimization
• multidimensional Knapsack problem

The paper proposes a new ant colony optimization (ACO) approach, called binary ant system (BAS), to multidimensional Knapsack problem (MKP). Different from other ACO-based algorithms applied to MKP, BAS uses a pheromone laying method specially designed for the binary solution structure, and allows the generation of infeasible solutions in the solution construction procedure. A problem specific repair operator is incorporated to repair the infeasible solutions generated in every iteration. Pheromone update rule is designed in such a way that pheromone on the paths can be directly regarded as selecting probability. To avoid premature convergence, the pheromone re-initialization and different pheromone intensification strategy depending on the convergence status of the algorithm are incorporated. Experimental results show the advantages of BAS over other ACO-based approaches for the benchmark problems selected from OR library.

• 出版日期2008-8
• 单位上海交通大学