CAJ | 학술논문

多背包问题是出现在现实世界中许多领域的一个NP-hard组合优化问题.提出一种基于人工鱼觅食,追尾、聚群等行为的求解多背包问题的优化算法.针对多约束导致大量非可行解的产生而使算法性能劣化的问题,采用基于启发式规则的调整算子,使人工鱼始终在可行解域中寻优.数值实验结果表明,提出的算法能够快速搜索到最优解.算法对其他有约束组合优化问题也具有应用价值.
다배포문제시출현재현실세계중허다영역적일개NP-hard조합우화문제.제출일충기우인공어멱식,추미、취군등행위적구해다배포문제적우화산법.침대다약속도치대량비가행해적산생이사산법성능열화적문제,채용기우계발식규칙적조정산자,사인공어시종재가행해역중심우.수치실험결과표명,제출적산법능구쾌속수색도최우해.산법대기타유약속조합우화문제야구유응용개치.
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.