A new ant colony optimization algorithm for the multidimensional Knapsack problem |
| |
Authors: | Min Kong Peng Tian Yucheng Kao |
| |
Affiliation: | 1. Shanghai Jiaotong University, Shanghai, PR China;2. Tatung University, Taipei, Taiwan, ROC |
| |
Abstract: | 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. |
| |
Keywords: | Ant colony optimization Binary ant system Combinatorial optimization Multidimensional Knapsack problem |
本文献已被 ScienceDirect 等数据库收录! |
|