混合遗传模拟退火算法求解背包问题

林 耿

(闽江学院 数学系，福建 福州 350108)

背包问题是运筹学中一个著名的问题，它是指从n个不同价值和重量的物品集合中选择若干个物品装入指定容量C的背包，使得被选物品的总重量不超过背包容量且价值总和最大.假设第i个物品的价值和重量分别为pi和wi,引入向量x∈{0,1}n，当物品i被选择放入背包时,xi=1；否则xi=0.背包问题可以建模为如下的整数规划模型：

背包问题属于带约束的NP困难问题[1]，在现实生活中有着广泛的应用背景，比如货物装载、工厂下料、电子商务和软硬件划分等[2].并且背包问题往往作为子问题出现在许多复杂的组合优化问题中，所以研究背包问题的有效求解算法具有重要的理论和实际意义.

常见的求解背包问题的算法有精确算法和智能优化算法[3-6].精确算法具有指数时间的算法复杂度，难以应用于求解大规模问题.智能优化算法能够较快地求得精度较高的近似解，特别是遗传算法和模拟退火算法操作简单实用，受到了学者们的广泛关注.然而，每种算法都有其自身的优势和缺陷.遗传算法[7]是一种基于自然选择和自然遗传学机制上的随机搜索算法，具有较强的全局搜索性能，但是遗传算法在搜索过程中容易出现早熟现象.模拟退火算法模拟固体退火的过程，不仅能够向目标函数优化的方向迭代，而且通过引入接受准则，能够以一定概率接受较差的解，从而避免陷入局部最优解，但当问题规模较大时，收敛速度较慢.

本研究将模拟退火算法有效地融入遗传算法，结合遗传算法和模拟退火算法的优点，提出了一种求解背包问题的混合遗传模拟退火算法，有效地避免陷入局部最优解.与单纯的遗传算法比较，实验结果表明了该混合算法求解背包问题的有效性和适用性.

1 混合遗传模拟退火算法

遗传算法具有很强的全局搜索能力，但是局部搜索能力较差，容易陷入局部最优解.模拟退火算法具有较强的局部搜索能力，但搜索速度较慢.本研究将这两个算法结合起来，提出混合的遗传模拟退火算法，随机构造种群，采用模拟退火对种群中的解进行局部搜索，引入新的种群更新策略，保持种群的多样性，避免早熟现象发生.

1.1 适应度函数

1.2 改进的模拟退火局部搜索算法

传统模拟退火算法能够有效避免陷入局部最优解，但当问题的规模较大时，模拟退火算法的收敛速度较慢.本研究基于模拟退火的思想，提出了一个改进模拟退火局部搜索算法SALS，加快了局部搜索的速度.设x为初始解，N(x)为x的某个邻域结构，T>0为SALS算法的参数，则SALS算法可描述为：

(1)初始化，down=0,xmax=x.

(2)计算N(x)中所有解的适应度函数值，假设y是N(x)中适应度函数值最大的解，令Δf=f(y)-f(x).

(3)如果Δf>0，则令x=y，转(2)；否则，如果f(y)>f(xmax)，令xmax=y，转(4).

(4)如果down

1.3 交叉算子

假设x和y是从种群中选择到的两个解，本研究采用fixed交叉算子[8]来产生新的解向量z.fixed交叉算子的基本思想是：如果第i个物品在x和y中都是处于装入状态，则在新的解中将该物品装入背包，即zi=1；如果第i个物品在x和y中都是处于未装入状态，则在新的解中不将该物品装入背包，即zi=0；如果第i个物品在x和y中的状态不一样，那么在新的解中以50%的概率装入背包.

1.4 种群更新策略

良好的种群更新策略应当既能维持高质量的解，又能保持种群的多样性. 采用如下的种群更新策略：一个解如果能够插入种群中，那么它要么提高了种群中解的质量，要么使种群中的解更多样化.假设x1和x2分别为种群中适应度函数值最大和最小的解，y为新产生的解.如果y的适应度函数值比x1大，即f(y)>f(x1)，则将y插入种群，并将x2从种群中删除.假设函数H(y,x1)表示解y和x1间的海明距离，函数H(x2,x1)表示解x2和x1间的海明距离,如果H(y,x1)+f(y)>H(x2,x1)+f(x1)，则将y插入种群，并将x2从种群中删除.否则，不改变种群的结构.

2 算法求解步骤

基于以上分析，提出了混合遗传模拟退火算法，算法的具体步骤如下：

(1)随机产生s个解向量构造出初始种群{x1,…,xs}.

(2)对种群中的每个解xi应用改进的模拟退火局部搜索算法SALA进行局部搜索，所得结果仍记为xi.

(3)随机选出种群中的两个解，应用fixed交叉算子构造新解z，并利用SALA算法对z进行优化，优化结果仍记为z.

(4)应用更新策略更新种群.如果算法已经持续NO次未找到更好的解，则停机，输出种群中适应度函数值最大的解；否则转(3).

其中，NO为算法的停止参数.

3 仿真实验

为了验证本算法的有效性，选取文献[6]中的实例来测试本算法，并将结果与文献[6]中的结果进行对比.采用Visual C++进行编程实验，实验环境为AMD 2.11 GHz处理器，1 GB内存，Windows XP 操作系统,实验例子的数据如下：

P={p1,…,p25}={350，310，300，295，290，287，283，280，272，270，265，251，230，220，215，212，207，203，202，200，198，196，190，182，181}，

W={w1,…,w25}={135，133，130，11，128，123，20，75，9，66，105，43，18，5，37，90，22，85，9，80，70，17，60，35，57}，C=1 400.文献[6]采用递归算法求得该问题的最优解，最优解的目标函数值和总质量分别为5 686和1 398.

表1 实验结果

由表1可得，混合遗传模拟退火算法能够找到比单纯的遗传算法更好的解，能够避免早熟现象并有效地提高背包的利用率.

4 结论

提出了一种求解背包问题的混合遗传模拟退火算法，该算法发挥了遗传算法和模拟退火算法的优势，采用同时考虑解的质量和种群多样性的种群更新策略，有效地避免了早熟现象，并且加快了局部搜索速度.与单纯的遗传算法比较，实验结果证明了算法的有效性.

参考文献：

[1]Garey M,Johnson D.Computers and intractability:a guide to the theory of NP-completeness[M].Freeman:San Francisco,1979:71-72.

[2]Ray A,Wu J G,Thambipillai S. Knapsack model and algorithm for HW/SW partitioning problem[J].Lecture Notes in Computer Science,2004(3036):200-205.

[3]赵新超，韩宇，艾文宝.求解背包问题的一种改进遗传算法[J].计算机工程与应用，2011，47(24):34-36.

[4]苗世清，高岳林.求解0/1背包问题的离散差分进化算法[J].小型微型计算机系统,2009，30(9):1828-1830.

[5]钱淑渠，武慧虹，涂歆.动态免疫优化算法及其在背包问题中的应用[J].计算机工程，2011，37(20):216-218.

[6]程春英，张玉春.利用遗传算法求解0/1背包问题[J].内蒙古民族大学学报，2010,25(6):637-639.

[7]陈国良，王煦法，庄镇泉，等.遗传算法及其应用[M].北京:人民邮电出版社，2001.

[8]Chardaire P,Barake M, McKeown G P.A probe-based heuristic for graph partitioning[J].IEEE Transactions on Computers,2007,56(12):1707-1720.