多选择背包问题的人工蜂群算法

摘要

Multi-choice knapsack problem( MCKP) is NP hard as one of combinatorial optimization. This paper proposed a new intelligent optimization algorithm-artificial bee colony ( ABC) algorithm to solve MCKP. The algorithm obtained global optimum through the local search of the employed bees, follower bees and scout bees. It presented the main idea of the algorithm for MCKP and implemented on microcomputer by MATLAB. Through a kind of computational instances, it compared with other algorithms, and it obtains the satisfactory results, which shows the feasibility and effectiveness of the proposed algorithm, expanding the applications of ABC.%多选择背包问题是组合优化中的NP难题之一,采用一种新的智能优化算法——人工蜂群算法进行求解.该算法通过雇佣蜂、跟随蜂和侦察蜂的局部寻优来实现全局最优.基于算法实现的核心思想,用MATLAB编程实现,对参考文献的算例进行仿真测试.与其他算法进行了比较,获得了满意的结果.这说明了算法在解决该问题上的可行性与有效性,拓展了人工蜂群算法的应用领域.