求解0-1背包问题的改进二进制捕鱼算法

陈建荣

(右江民族医学院 公共卫生与管理学院,广西 百色 533000)

0 引 言

背包问题(Knapsack Problem,KP)[1-3]是经典的NP难问题,其目标是寻找在给定背包容量的限制条件下价值量最大的物品选择方案。当涉及资源或任务分配等工作时,可使用背包问题的相关理论去处理和解决,如投资决策等。背包问题有多个变体,最基本的是0-1背包问题,其它类型问题能转换成该问题而顺利求解[3]。

求解0-1背包问题的方法包括精确算法和启发式算法这两类[2-3]。其中,精确算法包括贪心算法、动态规划法、分支定界法、穷举法、回溯法等。这些算法普遍存在计算效率低、计算量随问题维数的增加而呈指数级增长等缺点,因而难以有效处理高维背包问题。另一类算法是启发式算法,其本质上属于近似搜索算法,能在合理时间内找到问题的最优解或者满意解。常见的有遗传算法[2]、模拟退火算法[4]、粒子群算法[5]、蚁群算法[6]、布谷鸟算法[7]、蝙蝠算法[8]等。但这些算法在求解0-1背包问题时,仍存在全局搜索能力不强、收敛速度慢等不足。

陈建荣等人[9]通过观察渔夫在江面上捕鱼的行为习惯而提出了捕鱼算法(Fishing Algorithm)。目前,该算法及其改进或结合算法已被应用于解决各类优化问题,并获得良好的效果[10-13]。

捕鱼算法是针对连续问题提出的,无法直接应用于求解0-1背包问题,所以该文首先对渔夫编码及搜索方法进行重新定义和描述,称之为二进制捕鱼算法(Binary Fishing Algorithm,BFA)。然后,在对其分析的基础上,提出改进二进制捕鱼算法(Improved Binary Fishing Algorithm,IBFA)。最后,使用不同维度的背包问题对算法进行性能测试。

1 捕鱼算法

捕鱼算法对渔夫捕鱼行为的模拟主要包括7个假设和3类搜索方法[12]。7个假设分别是:(1)水中鱼的分布保持不变;(2)渔夫不知道鱼在水里的分布情况;(3)渔夫总是向鱼多的方向前进;(4)渔夫倾向于停留在鱼密度大的位置捕鱼;(5)渔夫希望通过使用网眼更小的渔网将鱼打尽;(6)渔夫会离开没有鱼的位置前往其它地方捕鱼;(7)渔夫之间避免碰撞。3类搜索方法包括移动搜索、收缩搜索和随机搜索。

算法运行过程中,渔夫在给定的寻优区域(问题的定义域)内撒网捕鱼,并通过渔夫之间的通力合作最终找到水中鱼密度最高的位置(问题的最优解)。

2 问题描述及二进制捕鱼算法

2.1 问题描述

0-1背包问题可描述为:给定一个最大容量为C的背包和n个物品,第k个物品的价值和体积分别为pk和wk。在不超过背包最大容量的条件下,将物品尽可能地装进背包,使得背包中物品的总价值达到最大。

若假定xi的取值0和1分别表示第k个物品没有装入背包和装入背包两种状态,则该问题用数学模型可表示为:

其中,xk∈{0,1}。

引入罚函数法,可将上述问题转化为:

(1)

2.2 渔夫编码及相关定义

对于n维的0-1背包问题,第i个渔夫的位置向量表示为Xi=(xi1,…,xik,…,xin)。其中,xik是Xi的第k个分量,取值为0或1。该渔夫对应位置的目标函数值可通过(1)式求得。

定义1:设两个位置向量分别为Xi1和Xi2,则它们之间的距离定义为D=sum(|Xi1-Xi2|)。其中,|·|表示对向量中的每一个分量取绝对值,sum(·)表示将向量的所有分量相加。

例1:给定位置X1=(1,0,1,0)和X2=(0,1,1,0),那么两位置间的距离D=|1-0|+|0-1|+|1-1|+|0-0|=2。

由定义可知,当渔夫撒网时,其所在位置和撒网点之间的距离刚好等于撒网半径。

2.3 搜索方法

(2)

下面给出三类搜索方法的具体描述。

(1)移动搜索。

(2)收缩搜索。

(3)随机搜索。

若渔夫i不满足前两类搜索的执行条件,且连续执行收缩搜索的次数达到算法给定的阈值,则对该渔夫进行随机初始化,并按式(2)构造撒网点集。

2.4 算法流程

算法设置有公告板,输入参数为:渔夫个体数量N、撒网半径L、撒网次数ξ、收缩系数β、收缩搜索阈值η和迭代次数T。

算法流程:

步骤1:对渔夫进行随机初始化;

步骤2:算法迭代次数达到T(或找到已知最优解)则停机,并输出最优值和最优解;

步骤3:各渔夫根据当前情况,选择执行相应的搜索方法(移动搜索、收缩搜索和随机搜索);

步骤4:找到更优值则更新公告板;转Step 2。

3 改进二进制捕鱼算法

3.1 分析与说明

首先,在BFA算法中,使用随机函数生成并给渔夫个体位置赋初值,由于受到随机性的影响可能会使得算法收敛速度偏慢。其次,渔夫的撒网半径对算法收敛速度影响较大,而所求解问题的维数不尽相同,若撒网半径设置为固定值,则会出现对于不同问题需要频繁设置不同半径值的尴尬局面。最后,为提高渔夫之间的信息共享,避免陷入局部最优,增加了一种名为靠近搜索的搜索方法。

3.2 贪心轮盘赌

3.3 自适应半径

通过下式给出初始半径值:

R=εn

(3)

其中,ε∈(0,1]为给定的自适应半径系数;n是所求问题的维数,即0-1背包问题中物品的总数。

3.4 随机比例

为避免因出现早熟而陷入局部最优,算法设置有随机比例参数Υ用于控制采用随机函数进行初始化渔夫位置的比例,其取值范围是[0,1]。当Υ=0时,全部采用随机函数进行初始化;当Υ=1时,则全部使用贪心轮盘赌的方法对渔夫位置进行初始化。

3.5 靠近搜索

定义3:设渔夫位置和目标位置分别为Xi和XG,且Xi与XG之间的距离D>R。从|Xi-XG|中随机选出R个非零分量,并将Xi中位于该非零分量位置的R个分量值用其二进制反码替换,则称渔夫Xi以步长R向位置XG随机靠近一次。

靠近搜索可描述为:若渔夫i连续执行收缩搜索的次数达到算法给定的阈值η,且其当前所处的位置并非群体最优,则该渔夫以步长⎣R×rand」向群体最优位置靠近(⎣·」表示向上取整);渔夫每向群体最优位置随机靠近一次,都重新按式(2)构造撒网点集。

3.6 算法流程

与BFA算法相比,IBFA算法取消了撒网半径L,新增自适应半径系数ε和随机比例参数Υ,其它参数保持不变。IBFA算法使用自适应半径和随机比例对渔夫进行初始化,并在搜索方法中增加了靠近搜索,其余操作和流程均与原算法相同。

4 实验与对比

4.1 软硬件环境与说明

实验电脑是华为MateBook X Pro超极本,配置为:Intel Core i7-1165G7 CPU @2.8 GHz,16 GB LPDDR4X内存;64位Windows 11家庭版操作系统,MATLAB版本是2020a。

实验分为常用算例测试和高维算例测试两部分。除另有说明外,各算法均使用固定的参数,并且连续运行一定次数,以降低随机性对结果的影响,同时也能在一定程度上反映不同算法在稳定性方面的差异。

4.2 常用算例测试与结果对比

常用算例测试中的九个经典算例均来自参考文献[3],各算法运行参数见表1。测试时,所有算法都连续运行30次,并记录包括最优值、最差值、平均值、标准差等指标在内的数据以便后续对比。七种不同算法的测试结果见表2。其中,对比算法的运行结果均来自文献[3]。

BFA与IBFA算法测试结果对比:从表2中的数据可以看出,IBFA算法能找到全部九个背包问题的最优解,且标准差均为零,说明算法适应性强、稳定性好;而BFA算法只能找到前三个问题的最优解,这说明对于维数相对较高的问题(KP4-KP9)来说,IBFA算法的性能有较明显的改善。

IBFA算法与其它算法测试结果对比:从最差值指标可知,对比算法中的ACPSO、BBA和HBA算法,在最差的情况下,未能找到全部九个背包问题(KP1-KP9)的最优解。对于IBFA、DPSPO和BLSO这三个能找到九个问题最优解的算法来说,它们的测试结果数据各有优势。值得注意的是,从100维的五个问题(KP5-KP9)的测试结果来看,除KP6外,IBFA在最小迭代次数指标上是最优的,均优于其它对比算法;特别是对于KP5和KP7这两个问题,在连续的30次运行中,IBFA算法在每一次初始化时都能找到问题的最优解,其对比指标均优于其它算法,这说明本文的改进方法在获得优秀初始值方面有较好的效果。注意到,IBFA算法的种群数量只有20,而其它对比算法均为50,这表明该算法的全局搜索能力较强,即使在种群数量较少的情况下,也不容易陷入局部极值点。此外,IBFA在求解背包问题时的运行耗时非常短,只需要不足0.04秒的时间就能找到问题的最优解。

表1 各算法运行参数设置

表2 七种不同算法的测试结果对比

续表2

4.3 高维算例测试与结果对比

为进一步验证算法性能,本节进行了高维算例的测试,这些算例使用下面的公式随机产生[7]:

其中,wi、pi和C分别表示算例中的物品体积、价值和背包容量;randint[1,10]表示随机地从集合{1,2,…,10}中抽取一个整数。根据上述公式,随机产生维数为100、200、400、600、800和1 000的六个高维0-1背包问题,每个算例产生后就保持不变。测试时,算法均连续运行50次,最大迭代次数均设置为500代。BBA算法参数取表1中的对应值;BFA和IBFA算法除η=20和θ=70外,其余参数均与表1保持一致。测试结果见表3。

表3 高维算例测试结果

从表3中的数据可以看到,对于这六个高维背包问题而言,IBFA算法能找到的解是最优的,且其标准差均为零,说明该算法性能稳定,鲁棒性强,不易陷入局部极值。

从各项对比指标上看,BBA和BFA算法性能基本相当,且这两种算法均因陷入局部极值而未能找到全局最优解。此外,随着问题维数的提高,各对比算法的运行耗时都相应地增加了:BBA算法耗时增加最快,其次是IBFA,最后是BFA。从最小迭代次数、最大迭代次数和平均迭代次数上看,问题维数的变化(提高)对IBFA算法收敛速度的影响不大,对于这六个高维问题,该算法最多只需要23次迭代就能找到最优解。

图1至图6展示的是BBA、BFA和IBFA算法连续运行50次的平均进化曲线。从图中可以看出,IBFA算法的收敛速度很快,仅需要20次左右的迭代就能收敛到最优值,而BBA和BFA算法经历500次迭代后仍未能收敛到稳定值。

图1 KP01(100维)问题平均进化曲线

图2 KP02(200维)问题平均进化曲线

图3 KP03(400维)问题平均进化曲线

图4 KP04(600维)问题平均进化曲线

图5 KP05(800维)问题平均进化曲线

图6 KP06(1 000维)问题平均进化曲线

5 结束语

为求解0-1背包问题,首先对捕鱼算法进行修改,即引入二进制编码而提出二进制捕鱼算法。并在此基础上,对其进行优化和改进,提出了改进二进制捕鱼算法。数值实验结果表明,与其它群智能算法相比,改进二进制捕鱼算法具有收敛速度快、全局搜索能力强、求解结果稳定、鲁棒性好等优点。特别是对于高维背包问题,与经典二进制蝙蝠算法相比,改进二进制捕鱼算法的综合性能明显占优。在未来的研究中,拟将该算法应用于车间调度等问题,以进一步测试其性能。