基于遗传算法的0/1背包问题的改进算法*

蔡照鹏，杨盛苑

(河南城建学院计算机科学与工程学院，河南平顶山467036)

作为强有力且应用广泛的随机搜索和优化方法，遗传算法可能是当今影响最广泛的进化计算方法之一［1］。在过去的几年中，研究人员将更多的注意力放在工业工程领域的优化问题上，因而得到了深入的研究［2］。理论方面的研究大多是围绕该问题简单的结构，这种特点既可以深入探索许多组合特性，又可以通过解决一系列背包子问题来最终求解更为复杂的优化问题。从实践的角度来看，这些问题可以表述许多工业问题的应用，最典型的应用包括资本预算、货物装载和储存分配等［3］。

在目前对背包问题的研究中，比较成熟的是使用贪心算法、回溯算法、遗传算法、动态规划算法等求解。与其他组合优化问题类似，许多研究人员常采用遗传算法来求解背包问题［4］。本文提出了采用十进制实数表示法求解背包问题的方法。

1 背包问题描述

背包问题:假设需要从许多物品中选择一些来填充一个背包。存在n个不同的物品可以使用，每个物品j具有重量wj和费用cj，物品被装入的部分占该物品的百分比Xj(0≦Xj≦1)，背包可以承重的上限是W。问题是如何寻找物品的最优子集从而在满足背包承重约束上线W的条件下最大化总费用，即在的条件下，求，其中m表示背包中装入的物品的个数。其中费用、重量和承重是正整数。

0/1背包问题:在背包问题的基础上，每个物品不能被分割，一个物品只有被装载和不被装载两种状态，不存在部分装载的情况，即上述背包问题中的Xj只能取0或者1。其数学模型实际上是一个0－1规划问题。

背包问题是一个NP难的问题。相对于传统的算法(如动态规划算法、回溯算法等)，使用遗传算法求解背包问题能最快找出较优的解。然而在一般情况下，使用基本遗传算法解决背包问题时，得到问题的近似解不能满足逼近最优解的要求，并且算法会搜索一些无效解，成为当前亟待解决的问题。本文探讨了改进遗传算法解决0/1背包问题，使遗传算法的搜索效率更高，并得到最优的解。

一般认为，遗传算法有5个基本的组成部分［5］:问题解的遗传表示、创建解初始种群的方法、根据个体适应值对其进行优劣判定的评价函数、用来改变复制过程中产生的子个体遗传组成的遗传算子即杂交(这是遗传算法中最主要的遗传操作)［6］、遗传算法的参数值。

遗传算法由一群个体组成的种群P(t)(t代表遗传代数)。每一个个体均代表问题的潜在的解。遗传算法的步骤描述如下:

(1)随机生成初始种群;(2)是否满足停止条件，如果满足则转到步骤(7)，否则，计算当前群体每个个体的适应度函数;(3)根据当前群体的每个个体的适应度函数进行选择生成中间群体;(4)以概率Pc选择两个个体进行染色体交换，产生新个体替换老个体，插入到群体中去(交叉);(5)以概率Pm选择某一个染色体的某一位进行改变，产生新的个体替换老的个体(变异);(6)转到步骤(2);(7)终止。

2 算法二次优化

2.1 算法准备

染色体的编码:采用十进制实数表示法，首先选取正整数Mj，然后转变为与背包个数相同的n位二进制，并且按照项目中各个物品的重量由大到小映射，即这个n位二进制的第一位对应的物品重量最大，第二位对应的物品重量次之，以此类推，最后一位对应的物品的重量最小，显然0≤Mj≤2n(0≤j≤n，n为背包的个数)。

适应值计算方法:与传统算法相类似，当染色体是“存活的”，即该染色体Mj所表示的选中物品的总重量没有超过背包的重量上限W时，其适应值为其所表示的选中物品的总价值，否则为0。

选择办法:对个体进行评价，计算一代种群中的每一条染色体的适应值。根据一代种群中的染色体Nj选择概率的大小，采用轮盘赌选择方式选取，即选取MAX(Mj/(M1+… +Mn))。

杂交算子:随机选择两条染色体Mi和Mj，将Mi和Mj转变为n位二进制以后，随机选取一个不大于背包个数n的数acrossBit，acrossBit称为杂交位，使两条染色体从开始到杂交位的所有位进行按序交换，即单点杂交方式。

变异算子:选取一条染色体Mj，将Mj转变为对应的n位二进制后，随机选取一个杂交位，将该位进行反置，即“0”变“1”，或者“1”变“0”。

最优个体保护:由于杂交和变异具有随机性，有可能破坏最优解结构，因此要对最优解进行保护，方法是选取上一代中满足条件且适应值最大的个体Mj，并且选取下一代中适应值最小的个体Mi，将Mj复制到下一代Mi对应的位置(即将Mi覆盖)。

处理死亡个体:首先将一代种群中的所有染色体按照适应值由小到大排序，并检查每一条染色体是否满足

2.2 算法流程

(1)随机生成初始种群P(t)，种群P(t)中每一条染色体都是随机生成的正整数Mj(0≤Mj≤2n);(2)是否已经进行了t代，如果是则转到步骤(8)，否则根据适应值计算方法计算P(t)中每一条染色体的适应值，并按照适应值由小到大进行排序;(3)检查P(t)中的各染色体的值是否小于limitw，若大于则处理死亡个体，并且更新limitw的值为最小值;(4)根据选择办法对种群P(t)中的每一条染色体进行评价;(5)通过杂交、变异等方法，生成下一代群体P(t+1);(6)根据上述方法，保护最优个体;(7)转到步骤(2);(8)终止。

3 算法模拟

模拟环境:时间单位为s;硬件环境，CPU为Intel Core2 duo E8400，内存容量为2.00GB;软件环境，操作系统为Microsoft Windows xp，开发环境为Microsoft VC++6.0。，若不满足，首先保存该染色体的值limitw(limitw的初值为背包的承重约束上线W)，并且更新limitw的值为最小的值，limitw的含义是适应值等于或大于limitw的染色体，没有必要进行下一步的杂交和变异，因为这n位二进制是根据物品的重量由大到小进行映射的，当适应值等于limitw的染色体无法满足条件时，大于limitw的染色体更无法满足条件，然后将该染色体及其之后的染色体重新生成新一代染色体，直到生成的群体中的每一条染色体均满足以上算法的实验数据如表1所示。实验效果对比如图1所示。

表1 8组实验结果数据

4 结论

遗传参数假定:杂交概率 Pc=0.8，变异概率 Pm=0.1。从实验结果可以看出:改进后的遗传算法明显比以前的遗传算法搜索的效率高，运行时间短，并且误差小。这说明，改进后的遗传算法可以有效避免无效搜索和算法在局部搜索，即能够及时发现无效解，避免没有必要的计算，并且防止算法在一个并非最优解的局部不停搜索，甚至无法找到最优解。这些证明对原遗传算法在背包问题中应用的改进是有效可行的。

图1 实验结果对比图

［1］ 玄光男，程润伟.遗传算法与工程优化［M］.北京:清华大学出版社，2009.

［2］ Alander J.An Indexed Bibliography of Genetic Algorithms［C］//Finland:Art of CAD Ltd，1994:102 －103.

［3］ Gordon V and Whitley D.Serial and parallel genetic algorithms as functions optimizers［C］//New York:Forrest，2008:177－183.

［4］ Michalewicz Z.Genetic Algorithm+Data Structure=Evolution Programs［M］.3rd.New York:Springer-Verlag，1996.

［5］ 王小平，曹立明.遗传算法理论，应用与软件实现［M］.西安:西安交通大学出版社，2002.