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

摘要： 多背包问题是出现在现实世界中许多领域的一个NP-hard组合优化问题。提出一种基于人工鱼觅食，追尾、聚群等行为的求解多背包问题的优化算法。针对多约束导致大量非可行解的产生而使算法性能劣化的问题，采用基于启发式规则的调整算子，使人工鱼始终在可行解域中寻优。数值实验结果表明，提出的算法能够快速搜索到最优解。算法对其他有约束组合优化问题也具有应用价值。

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