基于猴群算法求解0-1背包问题①

徐小平,师喜婷,钱富才

1(西安理工大学 理学院,西安 710054)

2(西安理工大学 自动化与信息工程学院,西安 710048)

背包问题是由Merkel和Hellman在1978年提出的[1],它是一个典型的组合优化问题,属于NP-hard难题,随着问题规模越来越大,复杂度增强.在实际应用中,许多工业和金融等问题都可以用背包问题来描述,如预算控制、资源分配、项目选择、资本投资、金融组合、材料切割和物件装箱等[2].近年来,背包问题已成为众多学者研究的一个热点问题,寻找新的方法来求解背包问题具有重要的理论和实际意义[3].目前,求解背包问题的方法主要有两种: 最优算法和启发式算法.最优算法包括穷举法、动态规划法、递归算法、回溯法和分支界限法等[4–7].启发式算法包括差分进化算法[8],粒子群算法[9]和遗传算法[10]等.前者的思想比较简单,不需要其它专业知识,一般适用于求解规模较小的问题; 后者一般适用于求解规模较大的问题,可是对其求解的精度还需继续探讨.

猴群算法是一种新兴的群智能优化算法[11],该算法的突出特点在于求解高维的优化问题时,无需考虑函数是否可导或可微,只需要计算当前位置的伪梯度,就可以确定算法的搜索方向,并且该算法的结构简单,参数少和易实现.因此,猴群算法在提出不久便得到了众多学者的广泛关注,在各个领域内得到了快速地发展,例如在大跨径连续刚构桥传感器优化布置问题[12]、入侵检测系统存在高漏报率的问题[13]、加气站项目进度的问题[14]、混合动力优化[15,16]、模糊规则的分类器[17]等领域.而文献[12–17]中均是基本猴群算法的应用,可以看出在某种程度上解决了一些问题.但是,在上述问题的应用中,随着测点数目或者规则等的增加,基本猴群算法暴露出易陷入局部最优,导致存在求解精度不高的弊端.因此,对该算法进一步研究是很必要的,并将其的应用进行扩展,来解决实际生活中的诸多应用问题具有重要的实际意义.

为了提高猴群算法的寻优性能,本文将诱导因子引入基本猴群算法的爬过程中,给出了一种诱导因子猴群算法,并将其应用到求解 0-1 背包问题.最后,通过仿真实验验证了该方法的可行性.

1 0-1 背包问题

0-1背包问题是一种常见的组合优化问题.一般可简单叙述为: 设物品的数量为D,第i个物品的体积(重量)和价格分别为wi和pi,一个背包的能承受的最大容量为V,选择一些物品,放入背包中.如何选择物品,在满足背包约束条件下,使背包中物品的总价值最大,这个问题被称为0-1背包问题,其数学模型建立如下:

其中表示物品的价值向量,表示物品对应的体积(重量)向量,表示解向量.式(1)表示目标函数;式(2)中xi为决策变量,xi=0表示第i个物品未装入包中,xi=1表示第i个物品装入包中.

2 猴群算法

2.1 基本猴群算法

基本猴群算法是由Zhao和Tang两位学者首次在期刊 Journal of Uncertain Systems 上提出的[11].该算法主要包括解的表示和初始化、爬过程、望过程和跳过程,其具体的操作过程如下:

Step1.解的表示和初始化: 设是目标函数的一个可行解,表示第i只猴子当前的位置,由式(3)生成.

其中,M表示种群规模,D为维数,xij表示第i只猴子在第j维的位置,变量的区间为是由[0,1]之间的均匀分布的随机数组成的D维向量.

Step2.执行爬过程: 爬过程是每只猴子在当前的范围内通过逐步爬行迭代,寻找优化问题的目标函数值的过程,具体过程如下:

2) 计算其中,是目标函数所在位置的伪梯度.

3) 令其中,sign为符号函数.

4) 如果向量在范围内,并且更新Xi为Yi: 否则,Xi不变.

5) 重复 1)–4),直到达到预定的执行次数Nc.

Step3.执行望过程: 在爬过程之后,每只猴子都到达了各自所在的山峰的顶端,并向四周眺望,观察视野范围内是否存在比当前位置更高的山峰.若存在,就从当前位置跳到更高的位置.具体过程如下:

1) 在视野范围内随机产生实数yij,令那 么其中,b为视野长度,它决定了猴子从当前位置眺望的最远距离.

2) 如果向量的范围内,并且更新Xi为Yi; 否则,重复1),直至找到可行的Yi.

3) 以Y作为初始位置,执行爬过程.

Step4.执行跳过程: 它的主要目的是由当前区域转移到新的区域进行搜索.选择所有猴子的重心位置作为支点,每只猴子从当前位置朝着支点的方向跳到新的区域进行搜索,具体过程如下:

1) 在跳区间[c,d]内随机生成一个实数θ.

2) 令:

其中,其中被称为支点.

3) 如果向量范围内,并且更新Xi为Yi; 否则,重复1)和2),直至找到可行的Yi.

Step5.终止条件: 重复 Step2–Step4,直到达到预先设定的迭代次数N,算法终止,输出结果.

2.2 诱导因子猴群算法

在基本猴群算法中,爬过程是非常重要的,它是控制算法的搜索精度.可是,在基本猴群算法中,猴群位置在爬过程中的更新,是没有规律的,往往具有很大的随机性,使得算法很难找到局部范围内的最优个体,从而不容易找到全局最优个体,这样就降低了算法的求解精度.

为了克服算法的这个缺陷,本文在爬过程中引入诱导过程,提出了一种诱导因子猴群算法.具体为: 在猴子爬行过程中,给定猴子向上爬行的指示,诱导它们向最优位置的方向爬行,这样可以避免绕路,尽快找到局部范围内的最优个体,从而迅速找到全局最优个体,来提高算法的寻优能力,达到提高算法的精度,其具体操作如下.

在爬过程中,随机生成爬向量其中,分量由下述过程生成.

随机生成一个M×D阶矩阵其 中 ,分 量βi j是在区间[0,1]上随机生成的一个实数.当时,否则,这样,分量就可由下式(6)来表示.

这样,在猴子爬行的过程中,就可以通过爬向量中0的个数来诱导猴子的爬行,来提高算法的寻优能力,进而达到提高算法的求解精度.其中,M为种群规模,D为维数,Nc为爬过程中爬的次数,kc为每次爬行的迭代次数,参数为猴子的爬步长.

在爬过程中引入诱导过程时,为了达到提高算法寻优能力的目的,那么就需要选择一个合适的诱导次数.如果诱导次数过低,提高算法寻优能力就不太明显.如果诱导次数过高,算法往往会出现陷入局部最优,达不到提高算法寻优能力的目的.因此,本文经过多次仿真后,找到当诱导次数时,既可以提高局部寻优能力,又可以避免因过高的局部寻优能力而降低了全局寻优能力,从而提高了算法的寻优性能.

3 利用诱导因子猴群算法求解0-1背包问题

利用诱导因子猴群算法求解0-1背包问题时,就是以式(1)作为目标函数,寻找式(1)的最大值.在求解中,它们的对应关系为: 每只猴子的位置,相当于式(1)的一组可行解; 猴群规模对应可行解的个数; 维数对应物品的数量.实施步骤如下.

Step1.参数值设定,如种群规模M=20,最大迭代次数等.

Step2.随机生成一个二进制向量作为初始位置(其中,第i位为1表示第i件物件被选中,若为0,则表示第i件物件未被选中).并计算所有猴子的目标函数值找出较优位置.

Step3.执行爬过程,计算,产生新的二进制向量若则更新第i只猴子当前的位置,即直到预定的执行次数Nc.然后,为了能够优先选取物品中单位体积价值较高的装入背包,在这里设计一个诱导因子,具体过程如下.

① 求出每件物品的单位体积的价值量,第i件物品为:

② 求出每件物品所占背包的比例,第i件物品为:

③ 据此设计诱导因子为:

其中,α为常量,用来调整的关系.

④ 随机选取两个值c1和c2,其中,如果并且则更新猴子的位置的变量为否则更新为计算若则更新第i只猴子的位置.直到一定的诱导次数guide.

Step4.执行望过程,在视野范围内生成新的二进制向量并计算则更新第i只猴子当前的位置,即

Step5.执行跳过程,计算,产生新的二进制向量计算计算若则更新第i只猴子当前的位置,即

Step6.重复 Step3–Step5,直到达到预定的最大迭代次数nMax,算法结束,输出最优个体和最优值.

4 实例仿真及其分析

为了验证所给算法的可行性,下边给出两个算例,它们的规模由小变大,具体数据见以下相关算例数据.比较差分进化算法 (Differential Evolution Algorithm,DEA)[8]、粒子群算法 (Particle Swarm Optimization,PSO)[9]、遗传算法 (Genetic Algorithm,GA)[10]、基本猴群算法 (Basic Monkey Algorithm,BMA)[11]以及本文所给诱导因子猴群算法 (Inducing Factor Monkey Algorithm,IFMA)求解问题的效果.

算例 1.物品数量n=50,背包容量V=1000,物品价值R=[220,208,198,192,180,180,65,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1],物品重量W=[80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1].

算例 2.物品数量n=100,背包容量V=2010,物品价值R=[68,101,125,159,65,146,28,92,143,37,5,154,183,117,96,127,139,113,100,95,12,134,65,112,69,45,158,60,142,179,36,43,107,143,49,6,130,151,102,149,24,155,41,177,109,40,124,139,83,142,116,59,131,107,187,146,73,30,174,13,91,37,168,175,53,151,125,31,192,138,88,184,110,159,189,147,31,169,192,56,160,138,84,42,151,37,21,22,200,85,135,200,139,189,68,94,84,22,18,115],物品重量W=[42,35,70,79,63,6,82,62,96,28,92,3,93,22,19,48,72,70,68,36,4,23,74,42,54,48,63,38,24,30,17,91,89,41,65,47,91,71,7,94,30,85,57,67,32,45,27,38,19,30,34,40,5,78,74,22,25,71,78,98,87,62,56,56,32,51,42,67,8,8,58,54,46,10,22,23,7,14,1,63,11,25,49,96,3,92,75,97,49,69,82,54,19,1,28,29,49,8,11,14].

在仿真中,用本文所给IFMA求解上述问题时,算法的参数设定为: 种群规模M=20,最大迭代次数nMax=500,爬步长a=1,爬的迭代次数Nc=20,诱导次数guide=5,视野长度b=0.5,望的迭代次数Nw=3,跳区间常量α=1.2.

利用上述五种算法分别对算例1和算例2进行一次求解,得到算例1的最优值和最优个体罗列在表1,寻优过程如图1所示,算例2的最优值和最优个体罗列在表2,优化过程曲线如图2所示.

表1 算例 1 的最优值和最优个体

表2 算例 2 的最优值和最优个体

接着,进一步利用这5种算法分别对算例1和算例2进行50次求解,得出它们的最优值、最差值、平均值和方差分别罗列在如表3和表4.

表3 算例 1 的结果

表4 算例 2 的结果

通过以上仿真结果中的图1,图2和表1至表4可以看出,文中在BMA算法中的爬过程中引入诱导过程后,很好地诱导了猴子向着指定的方向爬行,从而避免了算法走弯路,提高了算法的局部寻优能力和全局寻优能力.而且随着物品数量的增大,复杂度的增强,相对于 DEA,PSO,GA 和 BMA 算法,所给 IFMA 算法的求解精度仍然较高,且方差较小.从而说明所给IFMA算法具有较高的可行性和稳定性,达到了预期的效果,为求解0-1背包问题提供了新的途径.

5 结束语

在利用猴群算法求解0-1背包问题时,在爬过程中,引入诱导因子后,可以诱导猴子向着指定的方向爬行,从而避免绕路,使得所给IFMA能够找到全局最优解.通过仿真实验表明,利用所给的IFMA求解0-1背包问题达到了预期的结果,提高了求解精度.

图1 算例 1 优化过程曲线

图2 算例 2 优化过程曲线

参考文献

1Merkle R,Hellman M.Hiding information and signatures in trapdoor knapsacks.IEEE Transactions on Information Theory,1978,24(5): 525–530.[doi: 10.1109/TIT.1978.1055 927]

2赵学武,刘向娇,王兴,等.求解 0-1 背包问题的遗传算法.南阳师范学院学报,2014,13(6): 21–25.

3Srinivasan V,Varghese G.Fast address lookups using controlled prefix expansion.ACM Transactions on Computer Systems,1999,17(1): 1–40.[doi: 10.1145/296502.296503]

4李鸣山,郑海虹.0-1背包问题的多重分枝－限界算法.武汉测绘科技大学学报,1995,20(1): 83–87.

5宁爱兵,马良.0/1背包问题快速降价法及其应用.系统工程理论方法应用,2005,14(4): 372–375.

6王粉兰,孙小玲.不可分离凸背包问题的拉格朗日分解和区域分割方法.运筹学学报,2004,8(4): 45–53.

7王乐,王世卿,张静乐.基于 Matlab 的 0-1 背包问题的动态规划方法求解.计算机技术与发展,2006,16(4): 88–89,92.

8荆源.背包问题的差分进化算法.才智,2011,(7): 92–93.

9赵传信,季一木.粒子群优化算法在0/1背包问题的应用.微机发展,2005,15(10): 23–25.[doi: 10.3969/j.issn.1673-629X.2005.10.009]

10乐天.遗传算法求解0/1背包问题的综述.浙江海洋学院学报 (自然科学版),2013,32(1): 71–74.

11Zhao RQ,Tang WS.Monkey algorithm for global numerical optimization.Journal of Uncertain Systems,2008,2(3):164–176.

12李晓,倪富陶,孙维刚,等.基于猴群算法的连续刚构桥传感器优化布置研究.公路,2016,61(3): 65–69.

13张佳佳,张亚平,孙济洲.基于猴群算法的入侵检测技术.计算机工程,2011,37(14): 131–133.[doi: 10.3778/j.issn.1002-8331.2011.14.037]

14赵涛,夏雨,宗玛利.基于猴群算法的加气站项目进度研究.价值工程,2010,29(8): 90–92.

15申彩英,高韬.基于猴群算法的混合动力汽车能量管理策略 .计 算 机 工 程 与 应 用 ,2014,50(14): 9 –13,120.[doi:10.3778/j.issn.1002-8331.1308-0015]

16Ituarte-Villarreal CM,Lopez N,Espiritu JF.Using the monkey algorithm for hybrid power systems optimization.Procedia Computer Science,2012,(12): 344 –349.[doi: 10.1016/j.procs.2012.09.082]

17Hodashinsky IA,Samsonov SS.Design of fuzzy rule based classifier using the monkey algorithm.Mathematical Methods and Algorithms of Business Informatics,2017,1(39): 61–67.