利用改进的二进制狼群算法求解多维背包问题
2015-02-18吴虎胜张凤鸣战仁军梁晓龙
吴虎胜, 张凤鸣, 战仁军, 李 浩, 梁晓龙
(1. 武警工程大学装备工程学院, 陕西 西安 710086;
2. 空军工程大学装备管理与安全工程学院, 陕西 西安 710051;
3. 空军工程大学空管领航学院, 陕西 西安 710051)
利用改进的二进制狼群算法求解多维背包问题
吴虎胜1,2, 张凤鸣2, 战仁军1, 李浩2, 梁晓龙3
(1. 武警工程大学装备工程学院, 陕西 西安 710086;
2. 空军工程大学装备管理与安全工程学院, 陕西 西安 710051;
3. 空军工程大学空管领航学院, 陕西 西安 710051)
摘要：狼群算法启发于狼群群体生存智慧,已被用于复杂函数寻优和0-1普通背包问题求解。针对多维背包问题特点,设计了试探装载式的修复机制有效修复和改进人工狼群中的不可行解,改进了传统基于大惩罚参数的目标函数,减小了由于惩罚参数过大而导致算法陷入局部最优的风险;并受狼群的繁衍方式的启发,在二进制狼群算法的基础上提出了求解多维背包问题的改进二进制狼群算法(improve binary wolf pack algorithm, IBWPA)。通过求解19组不同规模的典型多维背包算例和与其他算法的对比分析,例证了算法的有效性和计算稳定性。
关键词：进化计算; 群体智能; 二进制狼群算法; 组合优化; 多维背包问题
0引言
背包问题是经典的NP-hard问题,旨在寻求背包容积限制下具有最大价值的物品装载方案。如金融产品组合投资、无人机任务分配、物料资源分配、货运装载等很多实际问题都可抽象为背包问题,应用非常广泛[1]。背包问题有多种形式:如普通背包问题[2]、多维背包问题[3]、多选择背包问题[4]、多选择多维背包问题[5]、多目标背包问题[6]和二次背包问题[7]等。普通背包问题仅考虑装入背包中的物品总重量不超过背包重量限制这一个约束。但实际中如经费预算和项目选择、分布式计算机系统中处理器和数据库的分配、资产证券化、生产计划拟制等都需要考虑多个约束。学者们将这类具有多个约束的背包问题称为多维背包问题(multidimensional knapsack problem,MKP),它是普通背包问题的一种推广,同属NP-hard问题但相对更为复杂[8],具有非常重要的理论和实际研究价值。
给定一待选物品集合Q={q1,q2,…,qn},MKP问题可描述为:从集合Q中选出一组满足所有问题约束的物品组合并使得所选物品价值总和最大,MKP的数学表述如下:
(1)
目前,求解MKP的方法主要有精确法和启发式算法2大类。前者诸如动态规划法、分支界定法、统计分析法、广义模糊算法等。这类算法对于小规模的MKP问题可求得精确解,但面对大规模MKP问题的庞大解空间却尽显乏力,表现为计算量大、迭代收敛慢、求解效果较差。于是,学者们研究了求解MKP问题的启发式算法,诸如蚁群优化算法[9]、混合遗传算法[10]、竞争决策算法[11]、二进制粒子群算法[12]、二进制果蝇优化算法[13]、二进制鱼群算法[14]等。这些启发式算法大都是在模拟自然界生物演化或集群行为的基础上提出的,具有框架灵活,求解效率较高等特点,但同时也不同程度地存在易陷入局部最优解的缺点[15]。
狼群算法(wolfpackalgorithm,WPA)是一种借鉴狼群生存智慧,模拟狼群分工协作式捕猎行为、猎物分配规则的群体智能优化算法[16]。狼群算法具有较好的计算鲁棒性和全局搜索能力,其衍生算法已成功应用于求解高维复杂函数优化问题[17]、0-1普通背包问题[18]和PID控制器参数整定[19]。本文结合狼群的繁衍方式对二进制狼群算法进行改进,并针对MKP问题的特点设计了修复机制,提出一种解决MKP问题的改进二进制狼群算法(improvedbinarywolfpackalgorithm,IBWPA),最后基于大量的算例仿真和算法比较验证了所提方法的有效性。
1改进的二进制狼群算法
1.1一些定义
设在N×m的欧式空间,人工狼i的位置Xi=(xi1,xi2,…,xij,…,xim),其中xij={0,1}(i=1,2,…,N;j=1,2,…,m)。人工狼感知到的猎物气味浓度Y=f(X),Y即是目标函数值;人工狼之间距离为两者位置编码的Manhattan距离。
定义 1反置。对xij反置即是对人工狼i的位置Xi中的第j个编码位作相异赋值,原为1的设为0,原为0的设为1。
定义 2运动算子[18]。设人工狼i的位置为Xi={xi1,xi2,…,xim},M表示进行反置的编码位集合且不为空集,可理解为人工狼的可活动范围;r表示进行反置的编码位的数目,可理解为人工狼的行走步长;运动算子Θ(Xi,M,r)表示在M中随机选择r个编码位并将其值反置。例如Xi=(0,1,0,1,0,0),M={2,5},r=1,则Θ(Xi,M,r)=(0,0,0,1,0,0)或(0,1, 0,1,1,0)。
1.2二进制狼群算法简介
二进制狼群算法(binarywolfpackalgorithm,BWPA)是在基本狼群算法的基础上通过定义运动算子,对人工狼位置、步长和智能行为重新进行二进制编码设计后提出的。BWPA由头狼产生规则,游走行为、召唤行为、围攻行为3种智能行为和狼群更新机制组成。BWPA保留了基本狼群算法基于职责分工的协作式搜索特性。同时,算法中的随机操作和参数的限定范围内随机选取方法使得算法可接受一些退化解,同时使算法能更好地遍历解空间,维持着较大的搜索区域。文献[18]已通过大量仿真实验验证了BWPA相对于学习型和声搜索算法、二进制粒子群算法、贪婪遗传算法、量子遗传算法等算法拥有较好的求解稳定性、收敛性和全局搜索能力。
为论述的完整性,下面首先给出BWPA具体算法的计算步骤。
步骤 1设置相应算法参数,初始化人工狼位置。
式中,j=1,2,…,m,k的初值为1；null表示空值。此时的集合Mb实际是猛狼位置Xi与头狼位置Xd不相同编码位的集合。若Mb为空集时执行运动算子Θ(Xi,Ma,1)。设Yi和Ylead分别为猛狼i和头狼位置对应的目标函数值,若Yi>Ylead,则Ylead=Yi,猛狼i替代头狼;若Yi 步骤 4围攻行为。将头狼所在位置Xd视为猎物的位置,参与围攻的人工狼i的位置Xi依下式进行位置变换得到新位置:比较人工狼实施围攻行为前后在新旧位置所感知到的猎物气味浓度并进行贪婪决策。 上述智能行为所涉及的游走步长stepa、奔袭步长stepb、围攻步长stepc皆为整数,表示人工狼搜索的精细程度。 步骤 5狼群更新。按“胜者为王”的头狼产生规则对头狼位置进行更新;再按照“强者生存”的狼群更新机制进行群体更新,即淘汰R匹人工狼,再随机产生R匹新人工狼,R取[N/(2β),N/β]之间的随机整数,β为更新比例因子。 步骤 6判断是否结束。判断是否达到优化精度要求或最大迭代次数kmax,若达到则输出头狼的位置,即所求问题的最优解,否则转步骤2。 1.3狼群繁衍方式启发的新人工狼产生方式 自然界狼群除了其协作式搜索、捕猎行为外,其繁衍方式也较为独特。本文受自然界狼群繁衍方式的启发改进了原有人工狼位置随机生成的产生方式。下面将从自然界狼群的繁衍方式和算法中新人工狼产生2方面进行详述。 (1) 自然界狼群的繁衍方式。成功的生产和幼崽抚育是动态维持狼群种群规模的关键。通常,每年11月末,狼开始发情追逐,经过一番较量和决斗,最终胜出的头狼才有资格和母狼形成配偶而后交配和繁衍后代。狼群中其他狼都严格遵守着这一交配戒律,否则会受到严厉惩罚[20]。头狼是狼群里体质最好、最具智慧的,是最好基因的拥有者。进而使得狼群后代拥有遗传优势,保证了后代的优秀,同时也控制了狼群的数量,有利于狼群的生存和繁衍。 幼狼出生后,在狼群的呵护下成长,逐渐学会行走、追逐和捕食猎物。需指出的是:从概率意义上讲,头狼和狼群越强,新生育的狼就能越快适应环境和参与捕猎。在此进化过程中,幼狼的适应能力和独立生存能力越来越强,与头狼的能力差距也逐渐缩小。其中少数狼成年后甚至可以打败原有头狼而成为狼群领袖。 (2) 算法中新人工狼的产生。通常,自然界狼群唯有头狼拥有交配权,即新产生的幼狼都为头狼的子女,拥有头狼的优良基因。因此,算法中新的人工狼Xnew由式(2)计算得到 (2) 式中，Xd为头狼所在位置；Ma={1,2,…,m}。L由式(3)计算得到 (3) 图1 L与k的关系曲线 由1.1节中的定义可知,L表示对头狼位置编码Xd进行反置的编码位数目,人工狼之间距离为两者位置编码的Manhattan距离,因此L也可表示头狼与新人工狼之间的距离,即可理解为两者的差异。由图1可知,L由一定限值随着k的减小而减小,表明根据式(2)所产生的新人工狼的位置与头狼位置差异逐渐减小。 此种设计在原理上与自然界狼群的繁衍特点是一致的。同时,对于算法,在迭代进化初期,一方面新人工狼位置是以头狼位置为基础,使得头狼的部分优良基因得以继承;另一方面又对头狼位置编码赋予较多的反置,探索更广域的解空间,有利于优秀新解的产生,并减小了陷入局部极值的概率;随着人工狼群迭代进化,各人工狼逐渐处于优良解域,此时赋予较小的反置编码位数有利于算法在优良解域内进行精细搜索。 L的这样设计体现狼群通过进化使得后代生育质量逐渐提高,后代的适应能力逐渐增强。同时也有利于算法以较快的速度收敛。 新狼产生后即可采用“强者生存”的狼群更新机制对狼群进行更新。即在算法中去除目标函数值最差的R匹人工狼,同时依照上述方法新产生R匹人工狼。同样,R的设定方法同BWPA算法计算步骤5所述。 1.4目标函数 MKP问题是典型的多约束组合优化问题。为方便寻优计算,通常利用一较大的惩罚参数对不满足约束的变量进行惩罚并建立单目标无约束目标函数,进而将MKP问题转化为无约束问题[21]。但文献[22]的研究显示惩罚参数过大会导致算法很容易陷入局部最优。这里采用一种动态惩罚函数的形式对式(1)中目标函数进行改进有 (4) 这样的目标函数设计减小了由于惩罚参数过大而导致算法陷入局部最优的风险,将人工狼导向MKP问题的可行解域或可行解边界附近的不可行解域,防止算法深陷不可行解域。 1.5试探装载式的修复机制 求解背包问题时,算法产生的新个体有可能为不可行解,因此应该采用修复机制来处理。对于MKP问题,常采用的基于伪效用比率的修复方法的核心步骤需求解MKP对偶问题,进而引入较多的计算量,降低算法效率[23]。 这里采用一种相对更为简便易于理解的、无需计算多维背包问题对偶问题的最优解的试探装载式修复机制,其具体计算步骤如下。 步骤 1据{ρj}的值按降序产生序列T=(T1,T2,…,Tn),其中ρj由式(5)求得 (5) 步骤 2按照序列T的顺序对不可行解的编码位设为1,即试探性地逐个装入物品,并判断是否满足所有的约束。若满足则编码位j为1得以保留,物品j被装入背包；否则置为0。 步骤 3试探性地依T的逆序将上步所得可行解中编码位为0的置为1,即载入该物品,直到不满足某背包约束。 如此,即可得到修复后的可行解。 1.6算法流程 IBWPA算法同BWPA,也由头狼产生规则,游走行为、召唤行为、围攻行为3种智能行为和狼群更新机制组成。IBWPA是在BWPA的基础上改进了新人工狼产生方式,并针对多维背包问题的特点,设计了试探装载式的修复机制。具体地,给出求解MKP的IBWPA的算法流程如图2所示。 图2 求解MKP的IBWPA的算法流程图 2实验与分析 为充分验证算法有效性,设计了3组实验,算例分别来自于以下2组可选算例。 第1组可选算例来自ELIB数据库(http:∥elib.zib.de/pub/mp-testdata/ip/sac94-suite/index.html)。该数据库提供了hp、pb、pet、sent、weing、weish6类共55个MKP问题算例。 第2组可选算例来自OR_LIB数据库(http:∥people.brunel.ac.uk/～mastjjb/jeb/info.html)。该数据库提供了按照n～m～g方式组合产生了270个大规模难解的MKP问题算例,其中 n={100, 250, 500}为物品数,m={5,10,30}为背包约束维数,g={0.25,0.50,0.75}为紧度。 实验环境为:WindowsXP系统,2GB内存,CPU2.00GHz,算法基于Matlab2008a实现。 2.1实验1——修复机制的有效性测试 (6) 随机产生10 000个随机解作为初始解,采用3种方法分别对初始解中的不可行解进行修复,并统计经修复后10 000个解的物品总价值的均值和计算平均耗时,实验结果如表1所示。 表1 判定距离dnear对IBWPA的影响 由表1可见,对于4个典型的MKP算例,方法1均能获得相对较好的修复效果,修复后物品总价值的平均值要大于其他2种方法所得。且从计算时间上看,方法1所需时间也相对较短。分析认为:相对于方法1而言,方法2和方法3中都有大量的求和运算,且2种方法都是先取出其所定义的比值小的物品再放入比值大的物品,其间会产生较多的盲目操作,因而所需计算时间相对较少。综上,可见试探装载式的修复机制在计算耗时和修复效果方面的相对优势。 2.2实验2——10个来自ELIB数据库的算例 在ELIB数据库6类算例中每类选取1～2个典型的算例组成共10个算例进行实验。实验用算例物品个数为28 ～ 90,背包约束维数为2 ～ 30,属于中小规模的MKP问题。 将IBWPA与BWPA、最新文献[25]所提的具有时变加速度二进制粒子群算法(binary particle swarm optimization with time-varying acceleration coefficients, BPSOTVAC)和具有时变加速度的混沌二进制粒子群算法(chaotic binary swarm optimization with time-varying acceleration coefficients, CBPSOTVAC)进行对比。 BPSOTVAC和CBPSOTVAC的参数设置如下:粒子数目N=5n,n为MKP算例的物品数目;最大迭代次数kmax=20 000,学习因子c1i=c2f= 2.5,c2i=c1f= 0.5,惯性权重wmax=1.5,wmin=0.5,最大速度Vmax=4。另CBPSOTVAC采用logistic方程且初值y1(0)=y2(0)为[0,1]间的随机数。对于BWPA和IBWPA,狼群规模也设置为N=5n,但为突出算法收敛效率,设Kmax=200。更新比例因子β仅决定淘汰人工狼的数量R的随机选取范围,最大游走次数Tmax仅决定可能的游走次数上限,因此,一般将两者分别设置为β=3和Tmax=10即可。2个算法中的智能行为、更新规则也有大量的随机操作。因此，2个算法对于参数设置并不敏感。判定距离dnear决定着人工狼何时由召唤行为进入围攻行为,即在解域中算法由向当前种群最优位置逼近状态转入对全局最优解的精细搜索状态;游走步长stepa决定探狼邻域搜索精细程度;奔袭步长stepb决定猛狼向当前种群最优位置逼近的速度;经验地,三者存在关系:dnear=stepb=2×stepa。一般而言对于较小规模的MKP问题,三者的取值都较小,本实验中stepa=2。 利用BPSOTVAC、CBPSOTVAC、BWPA和IBWPA这4种算法对ELIB数据库10个MKP问题分别进行100次独立计算。结果从成功率(success rate, SR),平均绝对偏差(mean absolute deviation, MAD),平均绝对误差率(mean absolute percentage error, MAPE),标准差(standard deviation, SD)共4个方面进行对比,如表2所示。SR即计算中得到已知最优解次数除以总计算次数,MAD即为100次计算中与所给最优值之差的平均值,MAPE即为100次计算结果相对于已知最优值的误差率的平均值。 表2 各算法计算ELIB数据库10个MKP算例的结果 续表2 从表2可看出,对于ELIB数据库这10个MKP问题,IBWPA都能找到其参考最优解且成功率在90%以上。而其他3种方法在物品数量大于30时成功率就下降至70%以内,对于规模较大的weish22和weish26两组算例成功率更降至50%以内。对于维数较小的weing3和pb4算例,在100次计算中,BWPA和IBWPA对于每个算例都能获得已知最优解,而BPSOTVAC和CBPSOTVAC则不然,可见2种狼群算法对于小规模MKP问题的求解稳定性。 随着问题规模的增大,在有限次迭代计算中,各算法的求解精度和稳定性均受到影响,表现为平均绝对误差率MAD和SD增大、SR降低等。但从SR、MAD等4个指标来看,IBWPA算法无论从求解精度还是求解稳定性方面都要优于原BWPA、BPSOTVAC和CBPSOTVAC这3种算法。 2.3实验3——9个来自OR_LIB数据库的算例 为了进一步测试IBWPA算法性能,选取较实验2规模更大的OR_LIB数据库中的9组算例作为试验用算例。利用IBWPA算法对每个算例独立计算50次,如表3所示，结果从算例的已知最优解G,相对于G的最小偏差率(least error rate, LER)，偏差方差(error standard deviation，ESD)等4个方面进行对比。其中LER=(Y-Y*)/Y*,Y为算法所得最优解，Y*为已知最优解。 表3 IBWPA计算OR-LIB数据库9个MKP算例的结果 同时算例名称包含了背包约束维数m、物品数量n、紧度g和编号共4个信息,例如OR5x100-25_1就表示此MKP算例为m=5,n=100,g=0.25的第1个算例。对于BWPA和IBWPA算法,除Kmax=1 000,stepa=3外,Tmax,β,N的参数设置也同实验2。 由表3可见,在50次计算中,IBWPA找到的最优解与已知最优解的相对偏差很小。其中OR5x100-25-1和OR5x100-50-2这2组算例所得的最优解分别为24 381(放入背包的物品集合为:2,4,7,9,11,19,24,26,27,29,30,32,44,50,57,62,63,66,69,71,74,77,79,85,86,92,93,96,99),42 545(放入背包的物品集合为:7,8,11,12,13,14,21,23,24,25,28,29,31,33,34,35,36,38,40,41,43,44,47,48,49,50,51,52,55,56,58,59,62,69,70,71,74,77,79,82,84,86,87,88,90,94,97,98,99,100)。这2组所得的结果要优于文献[11]所得出的24 373(放入背包的物品集合为:2,7,8,9,11,16,18, 19,24,27,29,30,32,35,44,50,57,62,63,66,68,69,76,77,79,85,86,93,99),和42 471(放入背包的物品集合为:2,5,7,12,13,14,23,24,25,27,29,31,33,34,35,36, 38,40,41,43,44,46,47,48,49,50,51,52,55,56,58,59,62,69,70,71,72,74,77,79,82,84,86,87,88,90,94,97,98,99,100)。9个典型算例计算所得的最差的LER仅为0.004 7,最差MAPE仅为0.85%,由此可见IBWPA对于大规模MKP问题的求解精度。 由表3可知,算例OR5x100-75-3的紧度为0.75且其MAPE值为0.15%,OR5x100-50-2和OR5x100-25-1的紧度分别降至0.50和0.25,其MAPE值分别增加至0.26%和0.55%;而算例OR5x250-75-3的紧度也为0.75且其MAPE值为0.19%,OR5x250-25-1的紧度降至0.25，而且其MAPE值则增加至0.85%。观察可以发现MAPE具有随紧度减小而增大的趋势,且问题规模大趋势更明显。分析认为:当问题规模相同时,紧度值越小则可行解空间也相对越小。而MKP问题的规模越大则其对应的解空间也就越大。自然地,当面对更大规模、较小紧度值的MKP问题时,算法就需要在相对更大的解空间中寻找相对更小的可行解,从而导致了算法求解质量的下降。另外,由9个算例的ESD可知,IBWPA计算得到的最佳ESD和最差ESD分别为5.40e-4和0.003 1,由此也可见IBWPA具有较好的求解稳定性。 3结论 在二进制狼群算法的基础上,深入分析了狼群繁衍方式,改进了新人工狼产生方法,使得头狼的部分优良基因得以继承的同时新人工狼还可探索更广的解域,减小了陷入局部极值的概率;针对MKP问题的特点,提出了无需求解MKP对偶问题的试探装载式的修复机制,并通过对比实验例证了修复方法的有效性;最终提出了求解MKP问题的改进二进制狼群算法,并通过与二进制狼群算法、新近文献所提出的两种粒子群算法的改进算法就19个不同规模、不同特点的经典算例进行了仿真对比计算,结果表明IBWPA算法具有相对较好的求解稳定性、收敛性和全局搜索能力。将来可进一步分析IBWPA算法的参数效应,设计新的参数设置方法以精简参数,并将算法应用于装备优化配置、无人机任务分配等组合优化问题中。 参考文献： [1] Zou D X, Gao L Q, Li S, et al. Solving 0-1 knapsack problem by a novel global harmony search algorithm[J].AppliedSoftComputing, 2011, 11(2):1556-1564. [2] Kaushik K B, Sarmah S P. Shuffled frog leaping algorithm and its application to 0/1 knapsack problem[J].AppliedSoftComputing, 2014, 19(6):252-263. [3] Yoon Y, Kim Y H, Moon B R. A theoretical and empirical investigation on the lagrangian capacities of the 0-1 multidimensional knapsack problem[J].EuropeanJournalofOperationalResearch, 2012, 218(2):366-376. [4] Sharkey T C, Geunes J. A class of nonlinear non-separable continuous knapsack and multiple-choice knapsack problems[J].MathematicalProgramming, 2011, 126(1):69-96. [5] Zhang X X, Tang L X. A new ACO&PR algorithm for multiple-choice multi-dimensional knapsack problem[J].ControlandDecision, 2009, 24(5):729-733.(张晓霞, 唐立新. 一种新的求解MMKP问题的ACO&PR算法[J]. 控制与决策, 2009, 24(5):729-733.) [6] Gao J Q, He G X, Liang R H, et al. A quantum-inspired artificial immune system for the multi-objective 0-1 knapsack problem[J].AppliedMathematicsandComputation, 2014, 230(1):120-137. [7] Azad M K, Rocha A M, Fernandes E M. A simplified binary artificial fish swarm algorithm for 0-1 quadratic knapsack problems[J].JournalofComputationalandAppliedMathematics, 2014, 259(3):897-904. [8] Freville A. The multidimensional 0-1 knapsack problems:an overview[J].EuropeanJournalofOperationResearch, 2004, 155(1):1-21. [9] Yu X C, Zhang T W. An improved ant algorithm for multidimensional knapsack problem[J].ChineseJournalofComputers, 2008, 31(5):810-819.(喻学才, 张田文. 多维背包问题的一个蚁群优化算法[J]. 计算机学报, 2008, 31(5):810-819.) [10] Djannaty F, Doostdar S. A hybrid genetic algorithm for the multidimensional knapsack problem[J].InternationalJournalofContemporaryMathematicalSciences, 2008, 9(3):443-456. [11] Xiong X H, Ning A B, Ma L. Competitive decision algorithm for multidimensional 0/1 knapsack problem based on multi-exchange neighborhood search[J].SystemsEngineeringTheory&Practice,2010,30(8):1448-1456.(熊小华,宁爱兵,马良.基于多变换领域搜索的多维0/1背包问题竞争决策算法[J].系统工程理论与实践,2010,30(8):1448-1456.) [12] Bansal J C, Deep K. A modified binary particle swarm optimization for knapsack problems[J].AppliedMathematicsandComputation, 2012, 218(22):1042-1061. [13] Wang L, Zheng X L, Wang S Y. A novel binary fruit fly optimization algorithm for solving the multidimensional knapsack problem[J].Knowledge-BasedSystems,2013,48(8):17-23. [14] Azad M A, Rocha A M, Fernandes E M. Improved binary artificial fish swarm algorithm for the 0-1 multidimensional knapsack problems[J].SwarmandEvolutionaryComputation,2014,14(2):66-75. [15] Chu S C, Huang H C, Roddick J F, et al. Overview of algorithms for swarm intelligence[C]∥Proc.ofthe3rdInternationalConferenceonComputationalCollectiveIntelligence,2011:28-41. [16] Wu H S, Zhang F M, Wu L S. New swarm intelligence algorithm-wolf pack algorithm[J].SystemsEngineeringandElectronics, 2013, 35(11):3430-3438.(吴虎胜,张凤鸣,吴庐山.一种新的群体智能算法——狼群算法[J].系统工程与电子技术,2013,35(11):3430-3438.) [17] Wu H S, Zhang F M. Wolf pack algorithm for unconstrained global optimization[EB/OL]. [2014-03-09].http∥dx.doi.org/10.1155/20141465082. [18] Wu H S, Zhang F M, Zhan R J, et al. A binary wolf pack algorithm for solving 0-1 knapsack problem[J].SystemsEngineeringandElectronics, 2014, 36(8):1660-1667.(吴虎胜,张凤鸣,战仁军,等.求解0-1背包问题的二进制狼群算法[J].系统工程与电子技术,2014,36(8):1660-1667.) [19] Wu H S, Zhang F M. A uncultivated wolf pack algorithm for high-dimensional functions and its application in parameters optimization of PID controller[C]∥Proc.oftheIEEECongressonEvolutionaryComputation, 2014:1477-1482. [20] Michael L.Wolf:habitats,lifecycles,foodchains,threats[M]. London:Hodder Wayland, 2002. [21] Ling G, Zhu W X. A filled function based variable neighborhood search method for the multidimensional knapsack problem[J].JournalofFuzhouUniversity(NaturalScienceEdition), 2012, 40(1):14-21.(林耿, 朱文兴. 多维背包问题的变邻域填充函数算法[J]. 福州大学学报(自然科学版), 2012, 40(1):14-21.) [22] Unler A, Murat A. A discrete particle swarm optimization method for feature selection in binary classification problems[J].EuropeanJournalofOperationalResearch,2010,206(3):528-539. [23] Wang L, Wang S Y, Fang C. A hybrid distribution estimation algorithm for solving multidimensional knapsack problem[J].ControlandDecision,2011,26(8):1121-1125.(王凌,王圣尧,方晨.一种求解多维背包问题的混合分布估计算法[J].控制与决策,2011,26(8):1121-1125.) [24] Hao C M, Wu B. Improved particle swarm algorithm for the multi-dimensional knapsack problem[J].Microelectronics&Computer, 2012, 29(9):129-132.(郝春梅, 吴波. 改进型粒子群算法解决多维背包问题[J]. 微电子学与计算机, 2012, 29(9):129-132.) [25] Chih M C, Lin C J, Chern M S, et al. Particle swarm optimization with time-varying acceleration coefficients for the multidimensional knapsack problem[J].AppliedMathematicalMo-deling, 2014, 38(4):1338-1350. 吴虎胜(1986-),男,博士研究生,主要研究方向为信息系统工程与智能决策、智能优化算法、智能数据挖掘。 E-mail:wuhusheng0421@163.com 张凤鸣(1963-),男,教授,博士,主要研究方向为系统工程、数据挖掘、故障诊断。 E-mail:zfmwenzhang007@163.com 战仁军(1963-),男,教授,博士,主要研究方向为军事装备学、警用器材、非致命武器。 E-mail:zrwenzhang007@163.com 李浩(1981-),男,讲师,博士,主要研究方向为军事通信、数据挖掘。 E-mail:lwdwenzhang007@163.com 梁晓龙(1981-),男,副教授,博士,主要研究方向为武器控制系统、数据融合。 E-mail:xiaolong.liang@hotmail.com 网络优先出版地址：http:∥www.cnki.net/kcms/detail/11.2422.TN.20141119.2214.006.html Improved binary wolf pack algorithm for solving multidimensional knapsack problem WU Hu-sheng1,2, ZHANG Feng-ming2, ZHAN Ren-jun1, LI Hao2, LIANG Xiao-long3 (1.MaterielEngineeringCollege,ArmedPoliceForceEngineeringUniversity,Xi’an710086,China; 2.MaterielManagementandSafetyEngineeringCollege,AirForceEngineeringUniversity, Xi’an710051,China;3.AirTrafficControlandNavigationCollege,AirForce EngineeringUniversity,Xi’an710051,China) Abstract:The wolf pack algorithm has been proposed based on inspiration by group survival swarm intelligence of the wolf pack, and successfully applied to complex function optimization problems and the normal 0-1 knapsack problem. To solve the multidimensional knapsack problem (MKP), a trying-loading repair operator based on the MKP specific knowledge is designed to effectively repair and improve infeasible solutions. Then, traditional objective function based on large penalty parameters has been improved so as to reduce the risk of easily trapping in the local optima. Meanwhile, inspired by the reproductive rule of the wolf pack, an improved binary wolf pack algorithm (IBWPA) is proposed for solving the MKP. Simulation results based on 19 benchmark MKP instances with different scales and comparative analysis between the IBWPA and other algorithms demonstrate the effectiveness and computational robustness of the proposed algorithm. Keywords:evolutionary computation; swarm intelligence; binary wolf pack algorithm; combinatorial optimization; multidimensional knapsack problem 作者简介： 中图分类号：TP 18 文献标志码：ADOI:10.3969/j.issn.1001-506X.2015.05.17 基金项目：国家自然科学基金(71401178,61472443)；陕西省自然科学基金(2013JQ8042)资助课题 收稿日期：2014-04-25；修回日期：2014-10-20；网络优先出版日期：2014-11-19。
