改进二进制人工蜂群算法求解多维背包问题
2014-09-25王志刚夏慧明
中国工程科学 2014年8期
关键词:优化
王志刚,夏慧明
(南京师范大学泰州学院数学科学与应用学院,江苏泰州 225300)
改进二进制人工蜂群算法求解多维背包问题
王志刚,夏慧明
(南京师范大学泰州学院数学科学与应用学院,江苏泰州 225300)
针对二进制人工蜂群算法收敛速度慢、易陷入局部最优的缺点,提出一种改进的二进制人工蜂群算法。新算法对人工蜂群算法中的邻域搜索公式进行了重新设计,并通过Bayes公式来决定食物源的取值概率。将改进后的算法应用于求解多维背包问题,在求解过程中利用贪婪算法对进化过程中的不可行解进行修复,对背包资源利用不足的可行解进行修正。通过对典型多维背包问题的仿真实验,表明了本文算法在解决多维背包问题上的可行性和有效性。
人工蜂群算法;多维背包问题;贪婪算法;组合优化
1 前言
人工蜂群[1~4](artificial bee colony,ABC)算法是由Karaboga于2005年提出的一种基于群体智能的仿生优化算法。实验表明,ABC算法比遗传算法(GA)、差分进化算法(DE)、粒子群优化算法(PSO)具有更好的优化性能。由于其具有收敛速度快、控制参数少、易于实现等优点,已引起越来越多的学者关注,并在很多优化问题中取得了成功的应用[5~9]。传统的ABC算法主要用于求解连续空间的优化问题,对于一些采用二进制编码的0~1整数规划问题却难以处理,这已成为限制其发展的一个瓶颈。为此,Marinakis等在2009年提出了一种二进制人工蜂群(binary artificial bee colony,BABC)算法[10],然而其邻域搜索方式存在一些不足:a.邻域搜索方式是随机的,导致算法的开采能力较弱,收敛速度较慢;……
登录APP查看全文
