改进二进制人工蜂群算法求解多维背包问题

王志刚()、夏慧明

中国工程科学 ›› 2014, Vol. 16 ›› Issue (8) : 106-112.

PDF(1012 KB)
PDF(1012 KB)
中国工程科学 ›› 2014, Vol. 16 ›› Issue (8) : 106-112.

改进二进制人工蜂群算法求解多维背包问题

  • 王志刚()、夏慧明

作者信息 +

Modified Binary Artificial Bee Colony Algorithm forMultidimensional Knapsack Problem

  • Wang Zhigang、Xia Huiming

Author information +
History +

摘要

针对二进制人工蜂群算法收敛速度慢、易陷入局部最优的缺点,提出一种改进的二进制人工蜂群算法。新算法对人工蜂群算法中的邻域搜索公式进行了重新设计,并通过Bayes 公式来决定食物源的取值概率。将改进后的算法应用于求解多维背包问题,在求解过程中利用贪婪算法对进化过程中的不可行解进行修复,对背包资源利用不足的可行解进行修正。通过对典型多维背包问题的仿真实验,表明了本文算法在解决多维背包问题上的可行性和有效性。

Abstract

The binary artificial bee colony algorithm has the shortcomings of slower convergence speed and falling into local optimum easily. According to the defects, a modified binary artificial bee colony algorithm is proposed. The algorithm redesign neighborhood search formula in artificial bee colony algorithm, the probability of the food position depends on the Bayes formula. The modified algorithm was used for solving multidimensional knapsack problem, during the evolution process, it uses the greedy algorithm repairs the infeasible solution and rectify knapsack resources with insufficient use. The simulation results show the feasibility and effectiveness of the proposed algorithm.

关键词

人工蜂群算法 / 多维背包问题 / 贪婪算法 / 组合优化

Keywords

artificial bee colony algorithm / multidimensional knapsack problem / greedy algorithm / combinatorial optimization

引用本文

导出引用
王志刚,夏慧明. 改进二进制人工蜂群算法求解多维背包问题. 中国工程科学. 2014, 16(8): 106-112

参考文献

基金
南京师范大学泰州学院资助项目(Q201232)
PDF(1012 KB)

Accesses

Citation

Detail

段落导航
相关文章

/