求解多维0/1背包问题的Memetic算法

刘梦佳+向凤红+郭宁

摘要：根据多维0/1背包问题的特点，结合遗传算法和模拟退火算法的优点，设计了一种Memetic算法。该算法以基于模式替换的改进遗传算法作为全局搜素算法，采用模拟退火算法进行局部搜索。全局搜索算法引入了模式替换，使每代种群中的最好基因个体保存下来形成模式，引导种群搜索方向，提高搜索性能，然后进行选择、均匀交叉和变异操作，最后采用最大化修复策略，对不可行解进行修复，并对可行解进行修正。模拟退火算法以一定概率接受较差的解，从而避免陷入局部最优解。通过实验仿真和算法比较验证了Memetic算法的优越性和有效性。

关键词：多维0/1背包；Memetic算法；遗传算法；模拟退火算法

DOIDOI：10.11907/rjdk.172027

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2017）012-0070-04

Abstract：According to the characteristics of multidimensional 0/1 knapsack problem and the advantages of genetic algorithm and simulated annealing algorithm，a Memetic algorithm is designed. The Memetic algorithm uses the improved genetic algorithm introduced model of replacementas the global search algorithm， and uses the simulated annealing algorithm to perform local search. The global search algorithm introduced the pattern substitution， so excellent genes from each generation population are preserved to form mode and guide the search direction of the population，which improve the search performance. After that，through selection， uniform crossover and mutation operation， the solutions are obtained. Finally the infeasible solution and the feasible solution are repaired by introduced maximum repair strategy.The simulated annealing algorithm accepted poor solutions with a certain probability， thus avoiding trapping in local optimal solutions.The superiority and effectiveness of the Memetic algorithm are verified by experimental simulation and algorithm comparison.

Key Words：the multidimensional 0/1 knapsack； Memetic algorithm； genetic algorithm； simulated annealing algorithm

0 引言

多維背包问题（Multidimensional Knapsack Problem，MKP）是著名的整数规划问题，有着许多重要的实际应用背景，如货物装载、材料切割、资源分配、投资决策等问题[1]。现有3种求解方法：精确方法（中间匹配法、动态规划等[2]）、启发式方法（粒子群算法[3]、遗传算法[4]、布谷鸟算法[5]、混合算法[6]等）以及上述方法的混合算法。其中，精确方法只适用于较小规模的问题且计算过程非常复杂，故启发式方法及其混合算法得到了广泛应用。进化算法多采用精英策略，在具有高进化效率的同时，存在易陷入局部最优解等局限性[7]。

Memetic算法是一种基于种群的全局搜索与基于个体的局部启发式搜索的结合体，由Moscato和Norman等[8]在1992年正式提出。Memetic算法提出的是一种框架及一个概念，在该框架下，可以采用不同的搜索策略构成不同的Memetic算法，如全局搜索策略可以采用遗传算法、进化策略、进化规划等，局部搜索策略可以采用爬山搜索、模拟退火、贪婪算法、禁忌搜索、导引式局部搜索等。正是这种全局搜索和局部搜索的结合机制使模因算法的搜索效率在某些问题领域比传统进化算法快几个数量级，因而可被广泛地应用于问题求解领域[9]。

遗传算法具有较强的全局搜索性能，但是遗传算法在搜索过程中容易出现早熟现象。模拟退火算法模拟固体退火过程，不仅能够向目标函数优化的方向迭代，而且通过引入接受准则，能够以一定概率接受较差的解，从而避免陷入局部最优解。但当问题规模较大时，其收敛速度较慢。本文根据多维背包问题的特点，结合遗传算法和模拟退火算法，设计了基于模式替换的改进遗传算法作为全局搜索算法，局部搜索部分采用模拟退火算法的Memetic算法。其中，基于模式替换的改进遗传算法是在贪婪遗传算法的基础上引入模式替换，使每代种群中的最好基因个体保存下来形成模式，引导种群的搜索方向，提高搜索性能，接着进行选择、均匀交叉、变异操作；最后引入最大化修复策略，对不可行解进行修复，同时对可行解进行修正。实验结果表明，该Memetic算法比传统的贪婪遗传算法和基于模式替换的改进遗传算法具有更强的寻优能力。

1 多维背包问题

背包问题（Knapsack Problem，KP）有多种形式，普通背包问题仅考虑物品的某一约束，但实际中的背包问题常常受到多类资源限制，如投资决策问题中资金、人力、原材料等多维约束的限制，这一类在多种资源约束条件下的背包问题即多维背包问题（MKP）[10]。MKP可描述为：给定n个价值为Pj （j=1，2，…，n）的物品， m种有限数量的资源约束ci （i=1，2，…，m），物品j对资源i的消耗为wij （i=1，2，…，m；j=1，2，…，n），从n个物品中选择出一组满足所有资源约束的物品组合，使所选物品价值总和最大。数学模型为：

2 Memetic算法求解多维0/1背包问题

2.1 基于模式替换的全局搜索算法

（1）编码及初始种群生成。本文采用二进制矩形编码，随机生成PopSize个个体，每个个体是长度为n的字符串，相当于一条染色体，字符串中的每一位相当于一个基因位，PopSize行n列的矩阵即为初始群体。

（2）适应度函数计算。根据遗传算法定义适应度函数f=∑nj=1Pj *xj，计算群体中每个个体的适应度值，判断其是否符合优化准则，若符合，输出最佳个体及其代表的最优解，并结束计算，否则转向选择操作。

（3）模式替换操作。为增强搜索导向和搜索能力，本文在选择操作之前引入模式替换操作。模式替换[11]即是利用种群中“*”这一不确定字符产生新个体，用产生的新个体替换原种群中质量不好的个体，使替换后的个体在经过交叉和变异之后仍能较大概率地存活下来，保证好的基因不丢失。

传统的遗传算法只在最优个体中寻找最优解，起初能找到比较满意的最优解，但随着迭代次数增加，最优解变得越来越少，导致交叉和变异操作往往只能在最优解内部发生，极大地降低了遗传速度，使收敛过程放慢。为了提高遗传算法的搜索速度、寻优能力，防止早熟现象出现，本文根据文献[11]的模式替换思想进行了改进。具体操作如下：①每隔20代进行一次模式生成、模式替换；②将种群适应值按降序排列的个体集中前ML个个体记录下来，并进行统计；③将质量优良的ML个个体生成模式采样空间。设定一个模式固定率，Ra=0.5。计算被记录个体每一基因位上0（或1）的个数占当前种群此基因位总字符数的比例，若比例超过Ra，则该基因位值为0（或1），否则为*，由此得到采样空间模式。被确定为0或1的基因称为个体的优良基因；④将具有优良基因的新个体加入原种群中，计算所有个体的适应度，并按适应度降序排列。然后取前PopSize个个体作为当前种群，由此替代原种群中质量较差的个体。

（4） 选择操作。保留父代和子代的最优个体，染色体在种群中被选择的可能性与个体的适应度大小成正比。

（6）变异操作。定义参数Pm=0.1作为变异操作的概率，由交叉操作得到的每条染色体的每个基因位都以概率Pm进行变异。

（7）最大化利率修复策略。为修复遗传过程中不满足约束条件的不可行解，Zitzler等提出了最大化利率修复策略，即将物品的价值密度ρij=Pj/wij按升序排列，搜索出不满足约束条件的情况，然后从包中逐一拿出价值密度小的物品，直到每一维资源都满足约束条件。该修复策略简单易行，是目前求解背包问题中最常用的修复策略。但该策略存在一个缺陷，即它只考虑了物品的价值重量比，没有兼顾各维资源的利用率，不利于算法的快速收敛。针对以上缺陷，本文作了以下改进：在对不可行解进行修复的同时，对可行解进行修正。具体操作如下：①搜索出不满足资源约束条件的物品选择策略，对于在该选择策略下被放入的物品，按价值密度升序排列的先后次序依次减掉物体（即令相应物体对应的xj=0）；②对xj=0的物体按价值密度降序排列的先后次序依次选择具有最大剩余的资源，直到消耗的資源达到约束上限为止。

2.2 基于模拟退火的局部搜索算法

模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却。加温时，固体内部粒子随温度升高变为无序状，内能增大，而徐徐冷却时粒子渐趋有序。在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小[12]。基本流程如下：

Step1：初始化：设置初始温度T（充分大）、退火终止温度Tf（足够小）以及退火系数k，选定一个初始解X，令当前解为X，每个T值的迭代次数设为L。

Step2：从当前解的邻域中随机选择一个邻居X′，计算Δf=f（X′ ）-f（X）。

Step3：若Δf>0，则令X=X′，否则若exp（-Δf/T）>random（0，1），则令X=X′。令L=L-1，若L>0，执行Step2、Step3，否则执行Step4。

Step4：T=k*T，若T>Tf，转Step2，否则输出当前解作为最优解，程序结束。

2.3 Memetic算法具体流程

Step1：随机生成初始种群P={X1，X2 Xpopsize}，迭代次数g=0。

Step2：进行模拟退火算法对种群进行局部优化。

Step3：计算适应度函数并进行排序。

Step4：若Mod（g，20）=1，则按2.1节中的步骤（3）进行模式替换，否则转Step4。

Step5： 按个体适应度选择两个解，通过均匀交叉产生新的解，应用模拟退火算法进行局部搜索并保留最优个体。

Step6：每条染色体的每个基因位都以概率Pm进行变异操作。

Step7： 对种群采取最大化利率修复策略，通过模拟退火算法进行个体的深度搜索，记录迄今为止最好的解。

Step8：g=g+1，若g达到最大迭代步数，则输出最优结果，否则转Step3。

3 算例及结果分析

为检验算法的有效性，本文采用Matlab软件编程，并将其与文献[13]中改进的遗传算法MGA、文献[14]中的混合遗传算法GGA进行对比。问题算例来源于文献[14]。

资源数和物品数分别为m=2，n=28；资源约束为C1=C2=600；项目j对应的效益为Pj，对第i维资源的消耗为wij；实例的最佳效益为141 278（此时，第3，5，6，7，8，10，12，13，14，19，21，23，24，26号项目被执行）。实例数据如表1所示。

由表2可知，3种算法都可以在有限的迭代次数中达到最优，但Memetic算法求得的平均最优值比MGA和GGA算法更接近最优值，说明Memetic算法在解决多维背包问题时求解精度更高；从平均迭代次数看，Memetic算法达到最优值时代数最小，说明该算法的收敛速度比MGA和GGA算法快；3种算法中，Memetic算法求得的平均最差值最大，表明该算法的求解能力高于其它两种算法。从图1三种算法的迭代图看，Memetic算法迭代到15代左右已经接近最优解，而MGA和GGA算法分别在接近35代和70代时才趋于收敛，本文算法的全局搜索导向和寻优能力明显较强。

4 结语

本文设计了一种基于模式替换的改进遗传算法作为全局搜索算法，局部搜索部分采用模拟退火算法的Memetic算法。其中基于模式替换的改进遗传算法引入了模式替换操作，并使用了最大化修复策略，引导种群的搜索方向，提高了搜索性能，避免了早熟现象出现。同时，以模拟退火算法作为局部搜索，提高了求解精度。仿真结果表明，Memetic算法在求解多维0/1背包问题时具有良好的收敛性和较强的寻优能力。目前，本文只研究了待选物品数量多的情况，今后将对大规模资源约束的多维背包问题进行深入研究。

参考文献：

[1] 李枝勇，马良，张惠珍.求解多维背包问题的改进布谷鸟搜索算法[J].控制工程，2016，23（7）：1069-1075.

[2] Y CUI.A new dynamic programming procedure for three-staged cutting patterns[J]. Journal of Global Optimization， 2013，5（2）：349-357.

[3] CHIL M C.Self-adaptive check and repair operator-based particle swarm optimization for the multidimensional knapsack problem[J].Applied Soft Computing， 2015，26（1）：378-389.

[4] 曾智，杨小帆，陈静，等.求解多维0-1背包问题的一种改进的遗传算法[J].计算机科学，2006，33（7）：220-223.

[5] 张晶，吴虎胜.改进二进制布谷鸟搜索算法求解多维背包问题[J].计算机应用，2015，35（1）：183-188.

[6] 任志刚，赵松云，黄姗姗，等.求解多维背包问题的蚁群—拉格朗日松弛混合优化算法[J].控制与决策，2016，31（7）：1178-1184.

[7] SC CHU， HC HUANG， JF RODDICK.Overview of algorithms for swarm intelligence[C].Proc.of the International Conference on Computational Collective Intelligence，2011：8-41.

[8] MOSCATO P，NORMAN M G.A memetic approach for the travelling salesman problem implementation of a computational ecology for combinatorial optimization on message-passing systems[C].Proceedings of the International Conference on Parallel Computing and Transport Applications，Amsterdam：IOS press，1992：177-186.

[9] 李藝贞.基于模因算法的动态多目标优化问题的研究[D].厦门：厦门大学，2012.

[10] 薛俊杰，王瑛，孟祥飞，等.二进制反向学习烟花算法求解多维背包问题[J].系统工程与电子技术，2017，39（2）：451-458.

[11] 李康顺，贾玉珍，张文生.一种基于模式替代的遗传算法解0/1背包问题[J].计算机应用研究，2009，26（2）：470-471.

[12] 晏杰.模拟退火算法解决0-1背包问题的研究与实现[J].赤峰学院学报：自然科学版， 2013 （8）：9-10.

[13] X LIU，F XIANG，J MAO.An improved method for solving the large-scale multidimensional 0-1 knapsack problem[C].International Conference on Electronics & Communication Systems. Coimbatore， INDIA，2014.

[14] 姚瑞枫，宋玉阶.多维0-1背包问题的混合遗传算法[J].武汉科技大学学报，2003，26（2）：214-216.

（责任编辑：黄 健）