带惯性权重的Jaya算法求解0-1背包问题

张小萍

(广西大学 计算机与电子信息学院，广西 南宁 530004)

0 引言

0-1背包问题是一个非常经典的组合优化问题，这个问题是NP-hard的.在实际应用中，任务调度、资源分配和材料切割等难解问题都可以转化为0-1背包问题来求解，因此0-1背包问题的求解不论在理论研究和实际应用都具有重要的价值.求解0-1背包问题的算法可以分为两类，一类是以贪心算法、分支定界法和动态规划法为代表的确定性算法，一类是以智能优化为代表的非确定性算法.确定性算法的基本思路是枚举，即将所有可能的解都进行尝试比较得到最优解，这种算法的时间复杂度呈指数爆炸，当问题规模比较大时，难以在有效的时间内求得问题的解，因此这类算法只能求解小规模的0-1背包问题.智能优化算法求解0-1背包问题的时间复杂度比较低，可以在多项式时间内求解，但一般只能求解得到最优解域，不一定获得精确的最优解，这类算法可以用于求解大规模的0-1背包问题.许多学者在基本的智能优化算法基础上进行改进，提出了能快速求解0-1背包的智能优化算法.文献[1]提出了混沌二进制乌鸦算法(CBCSA),先使用混沌序列初始化种群，使初始种群的分布均匀，然后对个体进行二进制编码，使用贪心策略来修复和优化编码大大加快了算法的收敛速度.文献[2]提出了混合蝙蝠算法(HPA)，在基本蝙蝠算法的基础上进行改进，借鉴遗传算法中的交叉和反置算子进行位置转移和局部搜索，也结合了贪心策略来加速算法收敛速度.文献[3]提出了离散正余弦算法(DSCA)，使用非线性指数递减函数来更新个体步长，避免搜索的盲目性.

Jaya算法[4]是2016年提出的一种新颖的智能优化算法，它所需要的参数相对较少，算法易于理解和实现，能够获得较好的寻优效果和较快的收敛速度.Jaya算法已经被广泛应用在小型无人直升机航向控制[5]、绿色并行机调度[6]和无刷直流电机优化设计[7]等领域.由于Jaya算法相对于经典的智能优化算法例如遗传算法和粒子群算法等出现的时间没有那么长，因此它的应用领域还相对较少，也还没有应用到0-1背包问题的求解上.为了更有效地求解0-1背包问题，在基本Jaya算法的基础上提出具有惯性权重的Jaya算法，结合二进制编码和贪心策略设计了一个适用于求解0-1背包问题的改进算法，并通过仿真实验的数据对比说明提出算法的有效性.

1 0-1背包问题

0-1背包问题是一个有约束条件的优化问题，可以描述为：有一个容量为C的背包，有m件物品，每件物品的价值为pi,容积为wi,从m件物品中选择一些物品装入背包，使得在不超过背包容量的前提下装入背包的物品价值最大.若向量Y=(y1,y2,…,ym),yi=0或1，i=1,2,…,m,yi=0表示该物品没有放入背包，yi=1表示物品放入背包，用数学模型描述可以表示为：

(1)

2 基本Jaya算法

Jaya在梵语中是“胜利”的意思，算法力求获得最佳解决方案而取得胜利.算法同时考虑最佳个体和最差个体，在迭代过程中不断远离最差个体并逐渐向最佳个体靠近，进而逐步改善解的质量.算法的主要迭代公式如公式(2)所示：

(2)

3 带惯性权重的Jaya算法(WJaya)

3.1 二进制离散化

(3)

3.2 贪心策略

0-1背包问题是带有约束条件的，在进行二进制离散化得到的二进制向量有可能因为不满足约束条件而成为不可行解.目前对不可行解的处理有两种办法，一种是使用惩罚函数，将不可行解的适应度降低，一种是修补不可行解，将它变为可行解.贪心策略是修补不可行解最常用的方法，一般使用贪心策略要比使用惩罚函数的方法要好，因为贪心策略在修补不可行解之外还加入了局部优化规则，可以大大加快算法的收敛速度.令ei=pi/wi,那么ei表示每件物品的价值密度比，将物品按照ei从大到小的顺序排列，对于一个二进制向量Y=(y1,y2,…，ym)，贪心策略的修复和优化分为两个步骤：

步骤1.将背包初始置为空，对向量Y中相应比特位为1的物品按ei从大到小的顺序尝试加入背包，若新加入物品后总体积没有超过背包容量则加入，否则不加入背包，将相应的比特位重新置为0.

步骤2.对向量Y中相应比特位为0的物品按ei从大到小的顺序尝试加入背包，若新加入物品后总体积没有7超过背包容量则加入，将相应的比特位重新置为1；否则不加入背包.

步骤1的作用是将不可行解修复为可行解，将超过背包容量的一部分物品拿出来.步骤2是对解进一步优化，在没有超过背包容量的前提下，优先将价值密度比比较高的物品放入背包，提高解的质量并加快算法的收敛速度.

3.3 惯性权重

在粒子群算法[8]中惯性权重控制着飞行速度的变化，当惯性权重比较大时，粒子的飞行速度会发生较大的变化，全局搜索的能力比较强，局部搜索能力比较弱；当惯性权重比较小时，局部搜索的能力增强，全局搜索的能力会减弱.惯性权重在整个寻优过程中起着平衡全局寻优和局部寻优能力的作用.在一个好的寻优算法中，一般要求在算法迭代初期主要进行全局搜索，以便尽快确定全局最优解的大致位置，在迭代后期，主要进行局部搜索，以便提高寻优的精度.受粒子群算法的启发，为了增强Jaya算法的寻优能力，引入了线性递减的惯性权重，设置惯性权重的最大值为βmax，最小值为βmin,T是算法的最大迭代次数，则惯性权重β是与当前迭代次数t呈线性递减的关系，在迭代初期β比较大，在迭代后期β比较小，其具体公式为：

β=βmax-(βmax-βmin)t/T

(4)

Jaya公式中个体位置更新公式(2)改进为公式(5)：

(5)

3.4 WJaya算法步骤

步骤1.对系统参数进行初始化.

步骤2.对种群个体初始化并进行二进制离散化得到个体的二进制向量，然后使用贪心策略修复和优化二进制向量，计算每个个体的适应度值，求解出当前的最佳个体和最差个体.

步骤3.利用公式(4)(5)对个体进行更新，二进制编码后使用贪心策略修复和优化二进制向量，计算每个个体的适应度值.

步骤4.利用每个个体的适应度值更新最佳个体和最差个体.

步骤5.判断结束条件是否满足，若满足则输出最优解后结束，否则回到步骤3.

4 仿真实验和数据分析

为了测试WJaya算法的寻优效果，利用文献[1]提供的维度分别为50至200的0-1背包的7个测试案例进行仿真实验，分别与CBCSA,HPA和DSCA进行对比分析，其中在WJaya中定义βmax=1.5，βmin=0.6，其他算法的参数设置按照其原参考文献的定义.仿真计算实验的硬件环境为：操作系统64位的Windows 7,内存8G,编程环境MatlabR2019b.为避免实验的偶然性，每个算法在每个测试案例中都单独测试20次，算法的迭代次数都是200次，种群个体数为50，分别计算迭代后的最小值、平均值、最大值、方差和命中理论最优解的比率，获得的实验数据如表1所示.

表1 仿真实验数据对比

从表1可以看出，WJaya在KP1，KP2，KP3，KP4和KP6中每次都能找到理论最优解，方差全为0,不逊于其他三种算法，而在KP5中，WJaya的平均值是所有算法中最大的，而且找到理论最优值的比率也是最高的，达到了40%，方差是所有算法中最小的，在KP7中，只有WJaya以20%的概率找到了理论最优解，其他算法都没有找到，而且WJaya的平均值是所有算法中最大的.

综上所述，WJaya的整体寻优效果要好于其他三种算法，不仅可以有效求解低维度的背包问题，对于高维度的背包问题也能获得更好的寻优效果.

5 总结

Jaya是一种新兴的智能优化算法，本文提出了具有惯性权重的Jaya算法求解0-1背包问题，将种群个体二进制离散化，利用贪心策略修复不可行解并对可行解局部优化，结合使用惯性权重平衡全局搜索和局部搜索能力.仿真实验表明，提出算法在低维和高维0-1背包问题中都具有良好的全局寻优能力，避免早熟，易于跳出局部最优解，找到全局最优解.