关键词: 人工鱼群算法, 多背包问题, 组合优化, 约束, 启发式规则

Abstract: The Multiple Knapsack Problem (MKP) is a NP-hard combinatorial optimization problem in many real-word applications. An algorithm with the behaviors of preying, following and swarming of artificial fish for searching optimal solution was proposed in this paper. With regard to the problem that infeasible solutions are largely produced in the process of initializing individuals and implementing the behaviors of artificial fish due to the multiple constraints, which undermines the algorithm performance, an adjusting operator based on heuristic rule was designed to ensure all the individuals in the feasible solution areas. Computational results show that the algorithm can quickly find optimal solution. The proposed algorithm can also be applied to other constrained combinatorial optimization problems.

Key words: Artificial Fish Swarm Algorithm (AFSA), Multiple Knapsack Problem (MKP), combinatorial optimization, constraint, heuristic rule