当前位置: 中国硕士论文网 >>> 管理学硕士论文 >>> 探究0-1背包问题的贪婪遗传算法
探究0-1背包问题的贪婪遗传算法
来源:中国硕士论文网-www.masterlw.com
1.引言
最近的研究表明，背包问题（Knapsack Problems，简称KP）仍然难于解决。虽然，背包问题普通人理解起来也毫不费力，而且过去几十年，有关KP 的完全算法（Exactalgorithms）、近似算法（Approximate algorithms）与启发式方法（Heuristics）都发表了大量研究成果。但是，由于以前的计算测试限于少数有高度结构的实例（highly structuredinstances），不能显示KP 的全部特征。D. Pisinger 从两方面着手构造0-1 背包问题（0-1 orBinary Knapsack Problem, 简称0-1KP）的新实例。其中之一，是用更大的系数测试原先的标准实例，并利用基于分支限界（branch and bound）与动态规划（dynamic programming）的完全算法进行许多计算实验。这些算法经过几十年的改进，达到最新技术水平，几乎可以解决文献上所有传统的标准实例。但对于精心构造的新实例，执行情况很差。
或许 KP 是“比较容易”的NP-难（NP-hard）问题之一，应用遗传算法（Genetic Algorithm,简称GA）解决KP 远远少于用GA 解决旅行商问题（Traveling Salesman Problem，简称TSP），虽然它们都是典型的组合问题，而且在理论和实际上都有很重要的价值。就参考文献来说，用GA 解决KP 主要讨论了约束条件下的编码方法，有二进制编码法、顺序表达法、变长表达法和二重结构编码法等，以及相应的遗传算子的设计；对于迭代过程产生的不可行解，通常采用惩罚法或者解码法来解决；后者利用贪婪法则在解码的过程中把不可行解转化为可行解，从而进一步构成某种混合遗传算法（Hybrid Genetic Algorithm, 简称HGA）。P. C.Chu 和J. E. Beasley[5]综述KP 研究文献之后，提出一种解决多维背包问题（MultidimensionalKnapsack Problem, 简称MKP）的遗传算法，计算结果显示，对于各类大规模的更难求解的MKP，只需适度的计算努力，GA 就能够获得高质量的解，而且优于其它一些启发式方法。
其中，结合问题的具体知识构造的修补算子（repair operator）确保每一个子代个体都是可行解，以应付MKP 的约束条件与可行性。近年来，A. Sim?es 等人利用生物学的Transposition机制，提出一种代替传统交叉的遗传算子——转置，在求解0-1KP 和函数优化领域，转置总是优于交叉；Steven O. Kimbrough 等人则探索双种群遗传算法在约束优化中的应用，对KP 的求解获得较好的结果。
1994 年，V. Gordon 等人利用分支限界法和深度优先法（depth-first methods）这样简单通用的搜索算法和GA 求解同样的0-1KP。结果发现，对于小的问题，前两者比GA 更快产生解；对于大的问题，前两者在寻找最优解和寻找近似解都比GA 出色，尽管他们的GA利用了有用的局部信息。根据获得的数据，他们认为需要更多了解哪些问题适合于GA 而哪中国科技论文在线些不，像0-1KP 也许不太适合于盲目遗传搜索，可能需要改用混合方法。无疑地，我们需要更好地了解哪些问题实际上不能由完全算法解决，而是适用于遗传方法或混合方法，或者相反。另外，文献还提到Martello 和Toth 使用更专门的分支限界法，在1 分钟之内解决更大的KP。这正是文献涉及的前人工作之一。
本文提出一种新的混合遗传算法——贪婪遗传算法（Greedy Genetic Algorithm, 简称GGA），用于解决一类0-1KP。1995 年，曾有人应用GA 专门解决这一类0-1KP，文中给出专门设计的评估函数，值得借鉴。其初始群体随机产生，群体规模40，最大代数250，标准交叉运算、但pc 不明，变异包括三个过程：随机位变异、邻居交换、随机两点间二进制位反转，三者的概率分别是0.0001、0.001 和0.001。结果发现，GA 能够容易而且迅速地找到接近于最优值的解，然而，从接近于最优值的解到达最优解很慢，因此加入一个局部搜索程序改善求解速度。
下一节介绍 0-1KP；第3 节给出并论述GGA；第4 节说明计算实验的情况并分析计算结果；最后得出结论。相关阅读：经济学硕士论文
2 0-1 背包问题
2.1 定义
0-1KP 的传统定义是，一个有n 个项目的集合和一个有限容量c 的背包，每个项目有重量wj 连带价值pj，c、wj 和pj 为正整数（j = 1, …， n）。问题要求挑选具有总价值最大的项目子集，其重量之和不超过背包容量。
2.2 Subset-Sum Problem
当pj = wj（j = 1, …， n）时，0-1KP 称为Subset-Sum Problem（SSP），这个问题是寻找一子集，其重量之和小于等于c。可以证明，SSP 是NP-难问题。实际应用中经常出现这一类特殊情况，即应该达到一定的数量指标，其负偏差必须最小，且不许正偏差。
由于 pj = wj，于是获得一个装满的背包就是唯一的目标。但SSP 实例仍象其它0-1KP实例一样难以解决，因为大多数深思熟虑的上界返回同一平凡值c，从而在找到最优解之前，不能使用约束规则切断分支。而在项目数不太少的问题中，求解0-1KP 的分支限界法对于SSP 甚至会退化成完全枚举。
解决 0-1KP 的方法显然可以用来解决SSP。然而，SSP 值得特殊处理是因为专用算法通常给出更好的结果。反之，也有人把求解SSP 的多项式时间近似方案推广到0-1KP。
3.贪婪遗传算法这里，我们给出贪婪遗传算法
3.1 贪婪算法
除了完全算法，求解SSP 的最直接途径是贪婪算法（Greedy Algorithm）。贪婪算法简单得出奇，在每一步“贪婪地”选择最好的部分解，毫不顾及眼前局部的选择对今后全局的影响，因此，一般不能得到最优解，只能获得近似解。对于SSP，可按任何顺序逐项检查，将合适的新项目装入背包，直至不能再装为止。如果事先对所有项目按其重量降序排列，效果更好。
许多文献都利用贪婪算法求解KP，包括前述的HGA。由于遗传算法与贪婪算法的互补性，混合算法通常比单一算法优越。但是，我们应用贪婪算法有所不同，一是在产生初始群体时，二是在遗传迭代过程中对可行解与不可行解的进一步处理。
3.2 初始群体
贪婪算法采用的二进制决策变量自然就是遗传算法采用的二进制编码，与HGA 一般遵守的第一个原则相符，即保留包含在原编码中的有关知识。贪婪算法因此可产生GGA 的第一个染色体s0，s0 是一个近似解。这样，按照HGA 一般遵守的第二个原则，GGA 得到的解至少不会比贪婪算法的解差。初始群体其余个体由2-opt 邻域映射获得。当然，我们只随机选择s0 的邻域中的部分可行解。
3.3 贪婪算子
进一步，不妨把应用贪婪法则的过程称为贪婪算子，相当于修补算子的ADD 阶段。我们的贪婪算子由贪婪概率pg 控制操作，就像交叉算子和变异算子分别由交叉概率pc 和变异概率pm 控制操作一样。当GA 作全局最优搜索时，贪婪算子对未装满的背包再次操作，直至不能再装为止，即对代表近似解的染色体进一步改进。
这样，在GA 典型的重组选择迭代中嵌入贪婪算子，即直接由贪婪算子替代常用的局部爬山法，对部分新产生的后代在其进入种群之前应用贪婪算子操作，使之移动到最近的局部最优点，甚至全局最优点。因此，GGA 具有典型的HGA 形式。
这也是混合策略一般遵守的第二个原则的另一途径，吸收原有算法的优点，把原有算法中的一系列变换结合到HGA 中可能很有用。例如，退火演化算法就是把模拟退火算法（Simulated Annealing）中的退火过程与群体的演化结合而成的。
3.4 约束优化
0-1KP 作为一个单约束的整数规划，应用GA 求解时也必须满足约束。对染色体作遗传操作产生的不可行后代，多数采用惩罚法或者解码法来解决，参考文献则有修补算子的DROP 阶段。GGA 采用拒绝策略，严格限制进入种群的新生染色体，凡不可行的，一律抛弃。对于可行解，GGA 利用贪婪算子按贪婪概率部分改进。而更多更复杂的约束优化处理，可参考有关文献，其中各种满足约束的策略有待进一步的研究。
3.5 遗传算子
GGA 在父代种群P（t）中随机选择两个染色体，进行一点交叉和位点变异操作，生成新的染色体，经译码，把可行解作为子代种群C（t）中的染色体。这里，交叉概率pc 为0.1，变异概率pm 为0.9。
变异概率 pm 如此之大，随机性加强，如何保证算法收敛？我们知道，GA 的运行依赖各种各样的参数。但是，迄今为止，这些参数的设置还没有成熟的原则和方法，基本上依赖经验和对所求解问题的了解，因此需要认真选取。而如何有效配合使用交叉和变异这两种操作，仍然值得研究。
前人早已指出，GA 存在未成熟收敛即早熟缺陷，这主要是pm 太低，以至于不能使搜索转向解空间的其他区域进行搜索。pm 取较大值可维持种群多样性，防止早熟。另外，交叉操作使种群中的染色体具有局部相似性，从而使搜索停滞不前即爬山能力差。
徐宗本等人在1990 年代后期完成的工作揭示了一个重要事实：交叉操作的作用是有限的，变异操作的作用更为重要而基本。这与传统对GA 的认识有很大的区别，交叉的作用是在“子空间”上搜索，而变异的作用是不断改变子空间，从而扩大搜索范围，原则上可以扩大到整个空间。或者说，变异算子有能力从任何个体出发搜索到整个空间中的任何其他一个个体，即整个空间是变异算子的搜索可达域。因此，如果说交叉算子是局部搜索算子，则变异算子可认为是全局搜索算子。他们的研究表明：较大的Pm 使GA 在整个搜索空间中大步跳跃，而小的Pm 使GA 聚焦于特别区域作局部搜索。一般在不使用交叉算子的情形，Pm 取较大值（0.4 ~ 1）；在与交叉算子联合使用的情况下，Pm 通常取较小值（0.0001 ~ 0.5）。当变异算子用作核心搜索算子时，比较理想的是自适应设置Pm，以实现GA 从“整体搜索”慢慢过渡到“局部搜索”。
4.计算实验
提出解决某个问题的算法之后，除了理论分析，人们往往也通过计算测试，验证算法的有效性。当然，具体如何评价GA 的性能是复杂又困难的，而且用于评价GA 的测试问题会影响GA 的执行结果。由于现实存在的KP 数据很少在文献上报道，而且实际数据往往是偏颇的，会在某个有限范围内变化，以此不能正确评价算法的性能，算法的适应性也缺乏保证。
因此，我们采用大规模计算来分析评价算法。具体应用综合测试问题产生器1 生成大批随机数据，这些测试数据蕴含的一些结构也许不存在于现实生活的实例中。
由于没有实现文献描述的算法提纲的源代码，目前也未见应用GA 求解这类SSP 的其他报道，因此，我们的计算测试将用于比较GGA 与文献中各算法对于解决SSP 的性能。
许多文献都通过与其他完善的技术相比，评估新算法的价值，并说明新方法的可能性。但或许有人认为，比较遗传算法与完全算法的实验数据，以说明GA 性能是不合理的，特别是运行时间。因为性能上，前者优于后者。其实未必，而且应该注意的是，两者都各有新的进展。
本节先给出一个实例的计算结果，进行初步对比；接着叙述综合基准测试（Syntheticbenchmark test）设计，然后给出计算结果并加以分析。
4.1 一个实例
实例项目数n 为100 ~ 17,000，但具体数据不详。文献[3]的KP 实例2 倒是一个SSP。其GA 是，惩罚系数1.10，一点交叉、pc=0.88，位点变异、pm=0.0088，初始群体随机产生，群体规模100，采用正比于适应度的比例选择机制。在386PC 上执行时间为123s，第14 代得到最优解。
而应用 GGA 求解同一实例，1 代就得到最优解，时间不到0.1ms。
4.2 综合基准测试
考虑算法 GGA 对于不同的问题大小与数据范围的工作情况。在全部397,272 实例中，问题大小即项目数n 分别为50、100、200、500、1000、2000、5000 和10000，重量都均匀分布在一个给定的区间[1, R]，其数据范围R 分别为1000、10000、100000、1000000 和10000000。
GGA 群体规模100，采用最佳个体保存方法从P（t）选择最佳染色体替换C（t）中最差染色体，从而形成P（t+1）。GGA 对每个实例执行100 轮、每轮100 代的遗传计算。
4.3 计算结果
有1.7%的测试实例在100 轮、每轮100 代的遗传搜索后没有找到最优解。
大多分布在n=50、100，其中R=107 是最难解的。由于GGA 在遗传搜索过程中以装满背包为终止条件，所以这6,734 个实例中部分是重量和小于背包容量c 的。
4.4 平均计算时间比较
采用综合基准测试，对于中等大小的系数（R=1000, 10000），有5 个算法进行计算；对于大系数（R=105, 106, 107），有3 个算法计算。全部测试运行在Intel Pentium III, 933MHz的机器上，指定1 小时的时间限制给每类实例的全部H 个实例。任何在时间限制之内没有解决的实例，表中用破折号表示。其中，MT2 和Expknap 都是分支限界算法，MThard 是MT2 的一个特殊形式；Minknap 是一个动态规划算法，Combo 是以动态规划结合其它技术的混合算法。
5.结论
