2023年7月29日发(作者：)

一种有效求解多维背包问题的遗传算法

摘要：就多维背包问题的求解，提出一个基于遗传算法的启发式算法（MKPGA）。该算法中加入了一个利用问题特性知识的启发式修复算子以帮助求解。测试实例使用270个不同特性的多维背包问题，实验结果表明，该算法对多维背包问题的求解十分有效，能获得不同特性问题的高质量解。

关键词：遗传算法;多维背包问题;贪婪算法

遗传算法，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，对它的研究起源于20世纪70年代初，由美国Michigan大学的d教授于1975年正式提出。GA的主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题，可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域，是21世纪有关智能计算中的关键技术之一。2求解MKP的遗传算法设计

MKPGA使用了一个基于简单贪婪算法的修复算子来修复交叉、变异操作后可能产生违反背包约束的不可行解。虽然在标准遗传算法中并未提到修复算子的使用，但根据不同问题特性设计的修复算子被广泛应用在解决不同问题的遗传算法中。MKPGA所采用的策略描述如下：①联赛选择方法；②一致交叉；③物品数小于500时变异概率取2／个体基因串长位，当物品数等于500时，变异概率取3/个体串长度；④不允许种群中有相同的个体；⑤每次迭代只产生一个不 同于当前种群的新个体，如果新个体比当前种群中最差的个体好，则替换掉该最差个体。

3计算实验

3.1实例

本文使用的测试实例是由Beasley和Chu所提供的270个多维背包问题。其中约束个数m包括5、10和30，物品数量n包括100、250和500，每一组m-n各有30个问题。下面介绍这270个实例的生成方法。

物品j消耗资源i的量wij为一个均匀分布在区间（0，1 000）上的整数。对于每一个m-n的组合，每个资源约束bi=α∑nj=1wij，α是问题的紧密比，前十个问题的α取0.25，接下来十个问题的α取0.50，最后十个问题的α取0.75。物品的价值p与wij有联系，pj=∑nj=1wij/m+500qi,j=1,…n。qi是随机产生的一个范围为（0，1）的实数。

3.2MKPGA的计算结果

由于很多问题的最优解还不知道，所以采用100（松弛LP最优解-所求最优解）／（松弛LP最优解）的值对所求解的评估，记为%gap。显然，%gap越小，该解就越接近最优解。使用MKPGA在普通PC（CPU为AMD速龙64位3 000+ 1.8GHz，内存512M）上对每一个实例求解10次，每次产生106个个体后终止，即算法3中的tmax=106，取10次中最好1次的解作为MKPGA的所求解，且把该次求解所花时间作为计算时间。表1根据不同的m、n和α对MKPGA 的计算时间进行统计，表中的有关数据为m、n和α相同的10个实例的平均值（下同）。

3.2.1与Beasley和Chu的结果比较

表1将MKPGA与Beasley和Chu的GA（BCGA）的计算结果进行比较，前三列是问题的规模（m-n）和紧密率α，接下来两列是BCGA计算结果，最后两列是MKPGA计算结果。观察表1可知，随着m、n的增大，问题的难度也随着增大，且%gap与紧密率α有关，当α越大时，%gap越小。MKPGA计算结果的平均%gap仅为0.543，表2的对比说明了MKPGA同BCGA一样，对求解大规模的MKP实例十分有效。

在这270个实例中，MKPGA的计算结果有64个比BCGA的好，67个比BCGA的差，相等的有139个。其中MKPGA比BCGA差的解主要集中在物品数为500的90表1MKPGA与BCGA的计算结果对比表问题MNαBCGA平均%gap最优解个数MKPGA平均%gap最优解个数51000.25

从表1可以看出，对物品数n小于500的6组实例的求解，MKPGA要略优于BCGA。由于5-100这组实例由于规模相对较小，MKPGA和BCGA都能找到全部最优解。对于5-250和10-100这两组实例，MKPGA找到的最优解都比BCGA多，性能要好于BCGA。对于其它三组实例，虽然不能确定MKPGA找到的就是最优解，但从%gap的对比可以看出，MKPGA的%gap小于BCGA的%gap，说明MKPGA的解更接近于最优解。对物品数n等于500这三组实例的求解，MKPGA则不如BCGA， 特别是30-500这组实例，MKPGA与BCGA的差距相对于其它各组大，对于5-500这组实例，MKPGA的平均%gap略高于BCGA，而对于10-500这组实例，MKPGA和BCGA的平均%gap一样。

综上所述，MKPGA对大规模背包问题的求解要略优于BCGA，而对于超大规模的背包问题，MKPGA的性能则不如BCGA。虽然MKPGA的平均%gap比BCGA的大0.002，但在部分实例的求解中，MKPGA能找到比BCGA好的解，只是在求解物品数为500的实例上略差于BCGA，可以说MKPGA与BCGA的整体性能基本一样。

3.2.2与数学软件Lingo8的结果比较

Lingo是用来求解线性和非线性优化问题的简易工具。利用Lingo高效的求解器可快速求解并分析结果。使用Lingo8对270个多维背包问题进行求解，如果运算时间等于900秒时还没找到最优解，则停止运算，用当前的解作为Lingo8的求解。表2是MKPGA与Lingo8计算结果的比较。从表2可以看出，对于相同的实例，MKPGA的计算结果都比Lingo8的计算结果好，整体性能优于Lingo8。

4.3与其它启发式算法的结果比较

文献[1]中还提到运用其它启发式算法对这270个实例进行求解的计算结果。本文引用了文献[1]中的有关数据与MKPGA的计算结果进行比较，并列于表3中。这些算法包括：M&Q（Magazine and Oguz，1984）、V&Z（Volgenant and Zoon，1990）、MKHEUR（Pirkul，1987）。

由表4可知，MKPGA的解都比这些启发式算法的解要好得多。说明MKPGA对多维背包问题的求解其它启发式算法有效。5结束语

本文针对多维背包问题的特性，设计了一个带有修复算子的遗传算法MKPGA。并使用该算法对270个大规模的多维背包问题进行求解，计算结果表明，该算法对于不同m-n组合的多维背包问题都是有效的，且都能获得高质量的解。计算结果的平均%gap为0.543，仅比同样使用遗传算法的BCGA大0.002，而优于其它算法或软件的计算结果，这也说明了GA对多维背包问题求解十分有效。

虽然MKPGA计算结果的平均%gap仅为0.543，但还有大部分背包问题的实例不能求出最优解，这说明多维背包问题仍难以解决。遗传参数对遗传算法影响很大，如果参数选择适当，会使MKPGA的性能更加优越，所以对遗传参数的研究将会是探讨MKPGA求解多维背包问题的下一步工作。

参考文献：

[1]P C CHU,J E BEASLEY．A Genetic Algorithm for the

Multidimensional Knapsack Problem [J]．Journal of Heuristics，1998(4)：63-86.

[2]姚瑞枫．多维0_1背包问题的遗传算法研究[J]．武汉科技学院学报，2003（2）．

[3]陈国良，王煦法，庄镇泉，等．遗传算法及其应用[M]．北京：人民邮电出版社，1996．

[4]刘勇，康立山，陈毓屏．非数值并行算法(第2册)[M]．北京：科学出版社，1997．

[5]J PUCHINGER，G R RAIDL，ULRICH PFERSCHY．The Core Concept

for the Multidimensional Knapsack Problem [M]．Lecture Notes in

Computer Science，USA，Springer Berlin / Heidelberg，2006：195-208.

[6]ZBIGNIEW MICHALEWICX,DAVID B FOGEL．如何求解问题——现代启发式方法[M]．曹宏庆，李艳，董红斌，等,译.北京：中国水利水电出版社，2002．

[7][日]玄光男，程润伟．遗传算法与工程设计[M]．北京：科学出版社，2000．

[8]阎平凡，张长水．人工神经网络与模拟进化计算(第2版)[M]．北京：清华大学出版社，2005．