0 引言

0-1背包问题(0-1 knapsack problem，0-1 KP)是运筹学中一类重要的组合优化问题，同时也是一类NP难问题，旨在寻求满足背包约束条件下具有最大价值的物品装载方案^[1-2]。现实世界中很多复杂问题通过编码都可以转换为背包问题，如工业、经济、金融等方面的资源配置、资金预算、公钥密码系统构建以及装载问题等^[3]。0-1背包问题的求解过程本质上为：在不超出背包可装载极限的条件下，选取那些装包比不装包更能使背包获得最大价值的物体。目前求解0-1背包问题的算法很多，除精确算法如回溯法、分支限界法等以外，还有可快速近似求解背包问题的演化算法(evolutionary algorithm，EA)、启发式遗传算法(genetic algorithm，GA)、蚁群优化算法(ant colony optimization, ACO)以及粒子群优化算法(particle swarm optimization，PSO)等^[4-7]。但当问题规模较大时，精确算法的求解复杂度是指数函数，而启发式算法求解精确度低。置信传播(belief propagation，BP)算法是一种有效求解组合优化问题的近似算法，可计算边际概率，被广泛应用于人工智能和工程技术的各个方面^[8-9]。分析BP算法的原理可以发现，其特征是基于因子图模型的一种消息循环更新算法，该消息可以理解为图上相连两节点之间的一种以概率表示的约束关系。通过某种迭代策略对因子图边上的信息进行传播计算，所有传入节点的信息共同决定该节点传出的信息。信息迭代过程可能收敛到某一组固定点，或可能无限次进行迭代(不收敛)。如果BP算法收敛，则产生一组稳定的边际分布，可以确定部分变量的取值。当求解的问题可用树状因子图表示时，BP算法将退化为一种与动态规划算法相似的优化方法，在图模型上沿着边传递更新变量节点之间的消息，从而得到优化和推理的正确解。

基于上述研究发现，0-1背包问题的可行解由一组高概率装包的物体组成，而BP算法可根据变量的边际概率确定变量取值。因此，本文提出一种求解0-1背包问题的BP算法。首先确定0-1背包问题的线性规划，将线性规划的约束条件转化为因子图的子句节点，设计出0-1背包问题的因子图模型；然后采用指数函数的形式，根据每个物体项的价值设置因子图的初始概率；最后利用BP算法的信息迭代方程在因子图上计算求解。

1 基本知识 1.1 图模型

因子图是将一个具有多变量的全局函数因子分解为几个局部函数的乘积而得到的一种双向图模型^[10-12]。这种图模型可以为信息传播算法的使用提供建模基础，简化概率分布的边缘化计算，以概率判断并确定变量取值。因子图包含两种节点：变量节点和子句节点^[13]。变量节点代表联合概率分布函数的所有自变量，子句节点代表因式分解得到的多个局部函数。每个子句节点相连的变量节点都是对应的局部函数辖域内的自变量，每个变量节点相连的子句节点都是包含该变量的局部函数节点。对于f(i₁, i₂, i₃, i₄)=α_A(i₁, i₃)α_B(i₁, i₂, i₄)α_C(i₂, i₄)，函数f和变量i之间的关系如图 1所示。

1.2 BP算法

BP算法以因子图模型为传播载体，在因子图的每条边(i, α)上定义两种信息，分别为变量发送给约束的信息μ_i→α(d_i)和约束发送给变量的信息η_α→i(d_i)^[14-15]。其中μ_i→α(d_i)表示在假设没有约束α的条件下，变量i取值为d_i的概率；η_α→i(d_i)表示约束α要求变量i取值为d_i的概率^[16-17]。则可得BP算法的迭代方程为

$ \mu _{i \to \alpha }^{t + 1}({d_i}) = {Z_{i \to \alpha }}\prod\limits_{b \in V\left( i \right)\backslash \alpha } {\eta _{b \to i}^t} ({d_i})，$

(1)

$ \eta _{\alpha \to i}^{t + 1}({d_i}) = {Z_{\alpha \to i}}\sum\limits_{j \in V\left( \alpha \right)\backslash i} S (X_0^{^\alpha })\prod\limits_{j \in V\left( \alpha \right)\backslash i} {\mu _{j \to \alpha }^t} ({d_j})，$

(2)

式中：V(i)表示所有与i相连的约束集合，V(i)\α表示从V(i)中除去α；V(α)表示子句α包含的所有变量集合，V(α)\i表示从V(α)中除去i；Z_i→α和Z_α→i为归一化因子；S(X₀^α)为标识函数。算法收敛后，得到一组不变的概率值，即不动点η_α→i^f(d_i)，利用η_α→i^f(d_i)计算每个变量节点的边际概率η_i(d_i)，即${\eta _i}\left( {{d_i}} \right) = \mathop \prod \limits_{\alpha \in V\left( i \right)} {\rm{ }}\eta _{\alpha \to i}^f({d_i})$。BP算法的输出为

$ d_i^{BP} = \left\{ {\begin{array}{*{20}{l}} {\;\;\;1\;\;\;\;\;\;\;{\rm{if}}\;\;{\eta _i}\left[ 1 \right] > {\eta _i}\left[ 0 \right],}\\ {\left\{ {0,1} \right\}\;\;\;\;\;{\rm{if}}\;\;{\eta _i}\left[ 1 \right] = {\eta _i}\left[ 0 \right],}\\ {\;\;\;0\;\;\;\;\;\;\;{\rm{if}}\;\;{\eta _i}\left[ 1 \right]{\rm{ ＜ }}{\eta _i}\left[ 0 \right]} \end{array}} \right.。$

(3)

BP算法的伪代码描述如下。

输入：因子图模型，最大迭代次数t_max。

输出：固定点η_α→i^f。

begin

  初始时刻t=0, 对因子图中的每一条边(α, i)随机赋值η_α→i(0)∈{0，1}；

  for t=1 to t_max

    按顺序对边(α, i)调用BP算法的迭代方程对η_α→i进行更新：η_α→i(t)←η_α→i(t－1)；

  如果因子图中所有的边都满足η_α→i(t)=η_α→i(t－1)，算法结束并使η_α→i^f=η_α→i(t)；

   end for

如果t≥t_max，算法不收敛；如果t＜t_max，算法收敛并返回固定点η_α→i^f；

end

2 求解0-1背包问题的BP算法 2.1 0-1背包问题的线性规划

根据0-1背包问题的特点，定义以下向量：对于有n个物体的0-1背包问题，物体的价值属性为w=(w₁, w₂, …, w_n)，物体的重量属性为D=(D₁, D₂, …, D_n)。根据问题的求解需求，特别地定义物体的标签属性为x=(x₁, x₂, …, x_n)^T。标签x_i=1，表示该物体装入背包；标签x_i=0，表示该物体不装入背包。背包载重定义为C，0-1背包问题的线性规划(linear programming, LP)如下：

$ \begin{array}{l} {\rm{maximize}}\;\;\;\;\;\mathit{\boldsymbol{w}}{\rm{ }}\mathit{\boldsymbol{x}}\\ {\rm{subject to}}\;\;\;\;\;\mathit{\boldsymbol{Dx}}{\rm{ }} \le C\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{x_i} \in 0, 1 \end{array} $

2.2 0-1背包问题的因子图设计

将线性规划中的约束条件转化为因子图中的子句节点，决策变量转化为因子图中的变量节点。根据约束条件中约束函数与所属变量的统计关系，将对应的变量节点与子句节点以边相连，得到0-1背包问题的因子图模型，如图 2所示。图中载重约束为因子图中的因子节点α，其余与各自变量相连的因子节点为各自变量的状态约束节点。

2.3 标识函数的设计

在0-1背包问题的因子图模型基础上，设计求解0-1背包问题的BP算法，算法的迭代方程同(1)、(2)。其中，针对该问题设置算法中对应的标识函数为

$ \begin{array}{*{20}{l}} {S\left( {X_0^\alpha } \right) = 1,\;\;{\rm{if}}\;\;\;{\bf{Dx}} \le C,}\\ {S\left( {X_0^\alpha } \right) = 0,\;\;{\rm{if}}\;\;\;{\bf{Dx}} > C} \end{array}。$

2.4 0-1背包问题的求解过程

在正向传播过程中，主要考虑边上信息的初始化。为与线性规划的目标函数契合，设置每条边上的初始信息e^wx。调用BP算法的迭代方程，以此初始概率沿着因子图的边进行传播更新，设定与图 2中箭头方向相反的方向为反向传播。在反向传播过程中，子句节点传给变量节点的信息需要根据其他变量节点传给它的概率信息来确定。用3个物体的简单实例因子图来说明反向传播过程，如图 3所示。图中的子句节点表示背包的容量约束函数。3个圆形为变量节点，表示有3个物体。假设这3个物体的重量依次为D₁=2，D₂=2，D₃=4，背包载重为5，子句节点的函数为D₁+D₂+D₃≤5。以节点1的信息获得为例，根据物体2和物体3的标签状态排列组合，可得如表 1所示的物体状态分布情况。

表 2描述的是在表 1的4种分布情况下x₁=0的状态分布情况，即第1个物体不放进背包。显然，在这个实例中，前3种情况为可行解。根据迭代方程，第1个物体不装包的概率为：P(x₁=0)=1×P(1)+1×P(2)+1×P(3)+0×P(4)，其中P(1)=P(x₁=0)×P(x₂=0)×P(x₃=0), P(2)=P(x₁=0)×P(x₂=0)×P(x₃=1), P(3)=P(x₁=0)×P(x₂=1)×P(x₃=0)，这个计算过程体现了BP算法"和"与"积"的过程。

表 3描述的是在表 1的4种分布情况下x₁=1的状态分布情况，即第1个物体放进背包。原理如上，只有第1、3种情况为可行解，则第1个物体装包的概率为：P(x₁=1)=1×P(1)+0×P(2)+1×P(3)+0×P(4)。

从子句节点到变量节点一次迭代的信息更新过程如上文所述，在该信息的基础上继续调用BP算法进行新一轮的传播求解，直至算法收敛。算法收敛后得到一组固定点η_α→i^f，根据这组概率值分别计算每个变量的边际概率。由变量的边际概率判断该物体是否装包，具体方法为：如果该物体取x_i=1的概率大于取x_i=0的概率，则物体装包；否则，物体不装包。对每个物体进行计算判断，最终得到0-1背包问题的解。

BP算法求解0-1背包问题的伪代码描述如下。

输入：0-1背包问题的因子图模型以及物体的重量D，物体的价值w，背包的载重C；最大迭代次数t_max。

输出：一组固定点η_α→i^f。

begin

  对因子图上各子句节点到变量节点的边赋值e^wx；

  for t=1 to t_max

    调用改进后的BP算法，利用迭代方程在因子图上进行信息更新；

    如果因子图中所有的边都存在η_α→i(t)=η_α→i(t－1)，算法结束并使η_α→i^f=η_α→i(t)；

  如果t＜t_max，算法收敛并返回固定点η_α→i^f；否则，算法不收敛；

end

3 数值实验及分析

在数值实验中采用随机生成数据集的方法，设置不同的问题规模，在相同问题规模的情况下随机生成多组不同实例进行算法性能验证。BP算法收敛即可计算得到问题的解，也说明了该算法求解的有效性。不同问题规模下BP算法的收敛情况如图 4所示。不同问题规模分别随机生成100组实例并求解，统计收敛情况，最终生成收敛概率。可以看出，用BP算法结合线性规划解决0-1背包问题，问题规模在100以内均以概率1收敛，性能良好。但由于0-1背包问题是一类复杂度较高的NP完全问题，随着问题规模的增大，算法后期收敛性能下降。

利用BP算法求解不同问题规模所需的平均运行时间如图 5所示。每个数据点由100组随机实例构成，统计得出不同问题规模下求解0-1背包问题的平均运行时间。可以发现，在线性规划基础上，结合BP算法求解0-1背包问题的时间复杂度与问题规模成正比。造成这一现象的原因是随着问题规模的增大，0-1背包问题的解空间也不断增大，算法求解的速度相应降低。

通过与线性规划(LP)对比来说明BP算法的近似性。对于不同的问题规模，分别在随机生成的50个实例上测试LP和BP算法的求解性能，最优解对比结果如图 6所示。可以看出，在不同的问题规模下，BP算法能更有效地找到实例的解，求解质量比LP更优，近似性良好。

以上实验数据集均为随机产生。为证明算法的鲁棒性，引用文献[18]中0-1背包问题的经典数据集实例1进行实验，该实例的最优解为295，对应总重量为269。使用贪婪算法(greedy)、GA、PSO与本文提出的BP算法进行对比实验，每种算法的迭代次数均为50，4种算法的迭代过程如图 7所示。由求解结果可以看出，BP算法能有效地找到实例的解，提高了求解精确度。

4 小结

针对一些启发式算法易陷于局部最优和寻优精度低的缺点，设计了一种求解0-1背包问题的BP算法，实验结果证实了该算法具有较强的全局寻优能力。进一步降低算法求解复杂度以及解决更大规模的难问题是接下来的研究重点，在其他背包问题上的扩展性也是后续可以研究的方向。