混合人工化学反应优化算法求解0-1背包问题

王建辉，郑光勇，徐雨明

(1.长沙南方职业学院 民航学院，湖南 长沙 410208；2.湖南大学 信息科学与工程学院，湖南 长沙 410208；3.衡阳师范学院 计算机科学与技术学院，湖南 衡阳 421002；4.长沙师范学院 信息科学与工程学院，湖南 长沙 410001)

0 引 言

0-1背包问题(knapsack problem)是一个典型的组合优化问题，即给定n个物品，每个物品重量为gi,价值为ui，从中选出若干个物品，使得选出物品的总价值V最大但总重量W不超过背包的重量总量C。背包问题在实际中有很多应用，如切割问题、调度问题[1]、密码问题[2-3]等。这些都是NP难问题，因此不可能有多项式时间算法，除非P=NP[4]。背包问题的模型表示如下：

总价值为：

(1)

总重量为：

(2)

其中，xi取值为1或0，表示第i个物品的选择或不选择。

求解KP01问题的方法可以分为精确算法和近似算法两类。精确算法研究包括Bellman[1]提出的动态规划、Kolesar提出的分支定界法等。在早期的启发式算法中[5]，Sahni最先提出了用多项式近似方法求解背包问题[6]，Ibarra和Kim改进为完全多项式近似方法[7]。

近年来，针对背包问题提出了大量的元启发式算法。例如，吕晓峰等提出了一种求解0-1背包问题的改进遗传算法[8]；吴迪等提出了基于改进的蜂群遗传算法求解多选择背包问题[9]；喻学才等提出了多维背包问题的蚁群优化算法(ACO)[10]；高尚等提出了背包问题的混合粒子群优化算法[11]；Han等提出了量子进化算法(QEA)[12]；Liu等提出了一种模式指导的进化算法(SGEA)[13]；Zou等提出了全局调和的搜索算法[14]。

文中提出在ACROA算法中融入贪心算法思想来解决KP01问题。ACROA算法具有很强的搜索能力，在高效性和多样化两个特征上表现出色[15-16]。因为化学反应算子中使用了与遗传算法操作算子中相似的交叉和变异算子，使得ACROA算法也具有了GA的优点。在修正算子的阶段采用贪心思想，在其他阶段则采用文献[12]中用到的随机方法。文中提及的修复函数有两个优势：一是贪心思想使得算法具有更快的收敛性；二是通过随机搜索保证多方向覆盖，有效避免局部最优解。

1 人工化学反应优化算法(ACORA)

ACORA是Alatas受化学反应过程的启发[15]提出的一种启发式算法。在化学反应过程中，系统倾向于最高的熵和最低的焓。化学反应中所拥有的有效对象、状态、过程和事件，可以被设计为一种计算方法。焓或潜在的能量(对于最小化问题)、熵(对于最大化问题)可以作为相关问题的目标函数。算法1给出了ACROA算法的轮廓。更多的细节可以参考文献[15-16]。

算法1：ACROA algorithm

Output：The best solution

1 formreacNum calculate enthalpye(mi);

2 initial{f→δ,E→φ,T→max};

3 Setting the initial reactantsR0={q1,q2,…,qn}、R1={l1,l2,…,ln} and evaluation;

4 whileTnot met do;

5 {for bimolecular reactions do

{binary encoding synthesis reaction;

binary encoding displacement reaction;

binary encoding redox2 reaction;

calculatefandE;}

for monomolecular reactions do

{binary encoding decomposition reaction;

binary encoding redox1 reaction;

calculatefandE;}

}

6 if(f<δ) andE>Φthen

{

Apply reversible reaction update Φ of enthalpy,

updateδof functionf，Rset of reactants，maximum number of iterationT，dimensions of the problemD;

goto 4;}

else

{output the best solution; }

7 end if

8 end while

1.1 化学反应

在ACROA中，有两种化学反应类型，即单分子反应和双分子反应。单分子反应只需要一个反应物参与，包含redox1反应和分解反应两种。双分子反应包含合成反应、redox2反应和置换反应三种，需要两种反应物参与。对于ACORA，采用二进制编码。上述5种化学反应的运算分别描述如下：

1.1.1 二进制编码合成反应

具体规则是：两个反应物通过比特位运算(相同为1，不同为0)，产生一个新的反应物。这种运算的过程如图1所示。

图1 二进制编码的合成反应

1.1.2 二进制编码置换反应

该运算由两种初始反应物产生两种新的反应物。两种反应物二进制串的每个比特位都通过基于随机生成的掩码进行变换，以实现两种反应物之间的信息交换。对于掩码为0的位，两种反应物对应位的值相交换，否则不变，如图2所示。

图2 二进制编码置换反应

1.1.3 二进制编码氧化还原反应2

首先随机选择两个交叉点，对应位的数据交换即可，如图3所示。

图3 二进制编码氧化还原反应2

1.1.4 二进制编码分解反应

在原反应物二进制串中随机选取两个随机点，把这两个点之间的每个位反转，即0变成1，1变成0。如图4所示，随机选取的是第2、6位随机点，将它们之间的每位反转。

图4 二进制编码分解反应

1.1.5 二进制编码氧化还原反应1

具体规则是：随机选取一位取反，如图5所示。

图5 二进制编码氧化还原反应1

1.2 反应物更新

这一步骤来源于可逆化学反应，进行化学平衡测试。如果新生成的反应物具有更好的功能价值，则新反应物被保留，否则被排斥，这样有助于反应物趋向最优解。当终止条件满足时，ACROA报告最好的解，否则，重复前面的化学反应过程。

2 KP01问题的ACROA算法设计

该算法用二进制编码表示解的结构，求解KP01问题的ACROA算法描述如下：

2.1 解的表示

所求KP01问题的解用一个二进制串来表示，第i位为1表示第i项物品被选择，为0则表示未被选择。二进制解串的长度等于问题中的物品个数n。

2.2 目标函数

在反应中，熵(entropy)是非负的且在反应过程中递增，定义如下：

(3)

2.3 约束处理

使用二进制串有时会使得产生的解违反约束条件，通常用惩罚和修复两种技术解决这个问题。第一种方法是惩罚系数[14]。虽然这种方法可以帮助算法找到足够的解，但它并不有助于改进解的质量。下面引入的修复函数正是用来克服这个缺点。

修复算子是基于重复随机选择直到满足背包约束，这可能会在某些情况下消耗大量的CPU时间。相反地，传统的贪婪策略也带有背包问题中的其他一些缺点，详细分析见文献[8]。文中使用一个新的修复算子，它依赖于贪婪策略和随机选择[17]。此修复程序的优点是在CPU时间成本和摆脱局部最优之间取得了平衡。将问题中的物品按价值重量比率ui/gi(i=1,2,…,n)从大到小排序，即：

(4)

这种修复操作包括两个阶段。第一阶段(称为增加阶段)按照价值重量比ui/gi递减的顺序检查每个变量xi，只要不违背约束，就将变量的值0变为1。第二阶段(称为减少阶段)随机检查一个变量，如果违背约束，将这个变量的值1变为0.减少阶段的目标是把非可行解变为可行解；而增加阶段是改进可行解的价值最大化。修复算子描述见算法2。

算法2：Repair(ω)

Input：原解ω

Output：经修复算子处理后的解ω'

2i=1;

3 while(m>0 andi≤n) do

4 if(m≥gi) then

5ωi=1;

6m=m-gi;

7i=i+1;

8 end if

9 end while

11 while(k>0) do

12 随机从背包选择一项，假设为第i项;

13ωi=0;

14k=k-gi;

15 end while

16ω'←ω//ω经处理后变为ω'

3 仿真实验

采用8个KP01问题来证明ACROA算法的有效性。所有的算法用C#2010实现。采用PC机，Pentium E5500 CPU/2.8 GHz、2G RAM，运行Windows7操作系统。

3.1 三种算法求解小维度规模0-1背包问题的性能

在这一部分，采用文献[14]中使用的5个测试函数。在表1中，5个测试函数的维度分别是4、10、7、5和20。

这5个测试函数的实验独立运行30次。ACROA算法中仅有参数reacNum需要调整，并且设置为5。终止条件设置为100 000。对于所有的函数，算法找出最优解的成功率为100%。

为了进一步研究ACORA算法的性能，还应用了3个大维度的强相关实例。

表1 5个测试集的维度大小和设置参数

3.2 三种算法求解大维度规模0-1背包问题的性能

为了测试ACROA算法求解大维度KP01问题的性能，与GA算法和QEQEA算法进行比较实验。在这些测试案例中，采用强相关的数据集。物品的重量gi、价值ui和背包容量C由下式计算得出：

gi=rand[1,10]

(5)

ui=gi+5,i=1,2,…,n

(6)

(7)

其中，rand[1,10]随机产生1到10的整数，服从均匀分布。

实验采用3个测试实例，分别是200、600和1 000个物品。图6～图8显示了在3个实例中运行30次得到的平均最大总价值中，ACROA算法都是最好的，证明了ACROA算法的全局搜索能力和收敛能力都明显优于GA和QEA。

图6 最大利益情况(迭代200次)

图7 最大利益情况(迭代600次)

图8 最大利益情况(迭代1 000次)

4 结束语

基于人工化学反应和贪心策略提出了有效求解0-1背包问题的一种新算法。其中仔细设计了5个特定问题的基本化学反应，基于贪婪策略给出了一个新的修复函数及其有效算法。通过5个基准实例和3个强相关数据集实例的仿真实验，将ACROA算法与GA、QEA算法进行了比较，验证了ACROA算法的性能优于其他算法。