遗传大洪水演算法求解多维背包问题

朱 君 蔡延光 汤雅连 杨 军

（广东工业大学 自动化学院，广州 510006）

遗传大洪水演算法求解多维背包问题

朱 君 蔡延光 汤雅连 杨 军

（广东工业大学 自动化学院，广州 510006）

由于遗传算法具有较强的全局搜索能力，但在实际应用中容易产生早熟收敛现象，且进化后期搜索效率较低，而大洪水演算法是求解组合优化问题的独特算法，结合两者的优点，形成基于遗传算法的大洪水演算法（Genetic Great Deluge Algorithm，GGDA），然后应用该混合算法求解不同规模的多维背包问题（Multidimensional Knapsack Rroblem，MKR），求解结果表明提出的算法是简单有效的，优于标准遗传算法和大洪水演算法。

多维背包问题；大洪水演算法；遗传算法

多维背包问题［1］已经被证明是NR-hard问题，而且有广泛的应用背景，包括资本预算、存储分配、分布式计算系统中分配处理器和数据库及货物装载等。所以本文研究的多维背包问题具有实际应用意义。目前，多维背包问题也得到了广泛的研究。喻学才等人［2］提出了一种计算复杂性较低而求解性能较好的改进蚁群算法求解多维背包问题，实验结果表明新算法耗用时间少且解的价值更高；冀俊忠等人［3］提出了一种高性能的蚁群求解算法，将信息素更新和随机搜索机制的改进相融合，避免蚁群算法求解多维背包问题存在的迭代次数多和精度低的不足，实验表明，新算法优于蚁群算法；贺一等人［4］构造了基于双禁忌表的禁忌搜索算法求解多维0-1背包问题，证明了算法是有效可行的；刘勇等人［5］将元胞及其邻居解引入到算法中来保持种群的多样性，且利用元胞的演化规则进行局部优化，结果表明提出的元胞微粒群算法有良好的全局优化能力；王凌等人［6］提出一种基于分布估计算法的混合求解算法求解多维背包问题，基于标准测试集的仿真结果和算法比较验证了提出的混合算法的有效性和鲁棒性；杜巍等人［7］针对遗传算法求解复杂组合优化问题时易出现早熟收敛和丧失种群多样性，提出了二进制编码小世界算法，应用该算法求解多维背包问题，结果表明具有解决复杂组合优化问题的潜力；杨广益等人［8］提出了一种改进的分布估计算法-松弛互补分布估计算法，求解多维背包问题的结果表明，算法在较短时间内能找到最好解，证明了该算法是一种较好的演化算法；Chaitr S等人［9］应用禁忌搜索算法求解多选择多维背包问题，将简单的贪婪法则引入初始解，结果证明提出的算法优于传统的启发式算法；Murat Ersen Berberler等人［10］应用提出的遗传算法求解MKR，与传统遗传算法不同的是，其初始解并不是随机产生的，实验证明该算法能搜索到最优解。

1 多维背包问题

多维背包问题可以这样描述：假设我们需要从许多物品中选择一些来填充一个背包。存在n个不同的物品可以使用，每个物品j具有重量wj、体积vj和费用cj。背包可以承重的上限是W，容积为V。问题是如何寻找最优的方案在满足背包承重和容积的约束条件下最大化总费用。

式（1）为目标函数，求所装载的货物总价值最大；式（2）为约束条件，有载重约束、容积约束及xj的取整非负约束。

2 遗传大洪水演算法

2.1 大洪水演算法

大洪水演算法在1993年由Dueck［11-14］提出。若邻居解的目标函数值小于当前的边界值LEVEL，那么该邻居解将被接受。初始的边界值可以设定为初始解的目标函数值。在搜索过程中，边界值的单调下降，每次下降的幅度UR是算法的重要参数，它象征水平面升高的速度。大洪水演算法最终获取解的质量和运算时间的长短只依赖于UR参数的选取。UR值太小，算法会耗费太长时间求出高质量解；UR值太大，算法虽耗时短但求解质量不高。一般将UR值设定小于当前解的目标函数值与边界值LEVEL的平均差距的1%。

大洪水演算法的伪程序

INRUT：边界值LEVEL

s=s0；

Choose the rain speed UR；

Choose the initialwater level LEVEL；

REREAT

Generate a random neighbor s'；

IF f（s'）＜LEVEL THEN s=s'；LEVEL=LEVEL-UR；

UNTIL stopping condition met

OUTRUT：已找到的最优解

2.2 遗传大洪水演算法流程图

求解步骤如下：

1）设定控制参数，初始化种群。

2）计算各个体的适应度值。

3）进行遗传操作：选择、交叉和变异。此例中，采用轮盘赌选择、均匀交叉和单点变异。

4）计算新种群的个体适应度值，并将其与大洪水演算法的边界值相比较。

5）如果迭代次数达到最大，执行6）；否则，执行3）。

6）目标函数值小于边界值，则接受当前解，结束，输出结果；否则不断下降边界值，迭代次数加1，执行3）。

遗传大洪水演算法流程图如图1所示。可见，在进化初期，应用遗传算法对解空间进行搜索，在进化后期，应用大洪水演算法的边界值与前期产生的新种群的目标函数值比较，将多维背包优化问题的全局最优解看作山峰最高的顶端，那么求解算法就是登山者在一片连绵的山峰中寻找最高顶端的策略。

2.3 遗传大洪水演算法流程图

求解步骤：

1）设定控制参数，初始化种群。

2）计算各个体的适应度值。

3）进行遗传操作：选择、交叉和变异。此例中，采用轮盘赌选择、均匀交叉和单点变异。

4）计算新种群的个体适应度值，并将其与大洪水演算法的边界值相比较。

5）如果迭代次数达到最大，执行6）；否则，执行3）。

6）目标函数值小于边界值，则接受当前解，结束，输出结果；否则不断下降边界值，迭代次数加1，执行3）。

遗传大洪水演算法流程图如图1所示。可见，在进化初期，应用遗传算法对解空间进行搜索，在进化后期，应用大洪水演算法的边界值与前期产生的新种群的目标函数值比较，将多维背包优化问题的全局最优解看作山峰最高的顶端，那么求解算法就是登山者在一片连绵的山峰中寻找最高顶端的策略。

3 仿真分析

3.1 实验数据

已知：货车载重为65 t，容积为55 m3，可装载20种货物，每种货物最多6件，货物的单位重量、单位价值和单位体积如表1所示。

建立数学模型：

（1）决策变量。

货车装载编号为i的货物xi（i=1，2，...，20）。

（2）目标函数。

max z=3x1+7x2+x3+4x4+2x5+5x6+2x7+4x8+2x9+x10+3x11+7x12+11x13+14x14+ 3x15+5x16+2x17+3x18+4x19+x20

（3）约束条件。

3.2 应用三种算法求解MKP

GA的参数设置：初始种群pop-size=30，交叉概率pc=0.85，变异概率pm=0.01，最大迭代次数max gen=500，运行30次。

GDA的参数设置：UP=0.01，最大迭代次数max gen=500，运行30次。

GGDA的参数设置：初始种群pop-size=30，交叉概率pc=0.85，变异概率pm=0.01，最大迭代次数max gen=500，运行30次。

在Intel（R）CoreTMi3 CRU 2.53 GHz、内存为2.0G、安装系统为win7的RC机上采用Matlab R2010b编程实现。

求解结果：

1）装载货物的最大价值/千元：499.00；

2）装载货物的总重量/t：64.50；

3）装载货物的总体积/m3：54.90。

求解结果：三种算法求解MKR的结果如表3所示，三种算法求解的一次优化过程如图2所示，随机产生不同规模的多维背包问题模型，求解结果如表4所示。可知，通过三种算法都可以求得最优解，但是GGDA优于GDA和GA，GGDA收敛速度高，稳定性更强，且求解最优解的耗时最少；表4更体现出了GGDA的优势。

4 结语

大洪水演算法是求解组合优化问题的独特算法，而遗传算法具有较强的全局搜索能力，但在实际应用中容易产生早熟收敛现象，且进化后期搜索效率较低，结合两者的优点，取长补短，构成混合算法——基于遗传算法的大洪水演算法，应用该混合算法求解不同规模的多维背包问题的结果表明所提出的算法是有效可行的，优于标准遗传算法和大洪水演算法。如何改进遗传算法的操作算子、保持种群的多样性、消除解空间的不可行解等问题，将是下一步研究的重点。

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

［2］ 喻学才，张田文.多维背包问题的一个蚁群优化算法［J］.计算机学报，2008，31（5）：810-819.

［3］ 冀俊忠，黄振，刘椿年.基于变异和信息素扩散的多维背包问题的蚁群算法［J］.计算机研究与发展，2009，46（4）：644-654.

［4］ 贺一，邱玉辉，刘光远，等.多维背包问题的禁忌搜索求解［J］.计算机科学，2006，33（9）：169-172.

［5］ 刘勇，马良.元胞微粒群算法及其在多维背包问题中的应用［J］.管理科学学报，2011，14（1）：86-96.

［6］ 王凌，王圣尧，方晨.一种求解多维背包问题的混合分布估计算法［J］.控制与决策，2011，26（8）：1121-1125.

［7］ 杜巍，李树茁，陈煜聪.一种求解多维背包问题的小世界算法［J］.西安交通大学学报，2009，43（2）：10-14.

［8］ 杨广益，欧阳智敏，全惠云.松弛互补的分布估计算法求解多维背包问题［J］.计算机工程与应用，2007，43（12）：77-80.

［9］ Hiremath C S，Hill R R.First-level tabu search approach for solving themultiple-choicemultidimensional knapsack problem［J］.International Journal of Metaheuristics，2013，2（2）：174-199.

［10］ Berberler M E，Guler A，Nurîyev U G.A gentic algorithm to solve themultidimensional knapsack problem［J］.Mathematical and Computational Applications，2013，18（3）：486-494.

［11］ 魏欣，马良.多目标旅行商问题的大洪水算法求解［J］.系统工程，2009，27（7）：116-118.

［12］ 盛虹平.求解最小比率旅行商问题的大洪水算法［J］.杭州师范大学学报：自然科学版，2010，9（6）：401-405.

［13］ 盛虹平，马良.混沌大洪水算法求解函数优化问题［J］.计算机应用研究，2011，28（5）：1626-1630.

［14］ 赵秋红，肖依永，Mladenovic N.基于单点搜索的元启发式算法［M］.北京：科学出版社，2013.

Genetic Great Deluge Algorithm for Solving the Multidimensional Knapsack Problem

ZHU Jun CAIYan-guang TANG Ya-lian YANG Jun
（School of Automation，Guangdong University of Technology，Guangzhou 510006，China）

The Genetic Algorithm（GA）has better global search ability，but is easily prone to have premature convergence phenomenon in the practical application，with the low search efficiency in late evolution，while the Great Deluge Algorithm（GDA）is a unique algorithm for solving combinatorial optimization problems.Combined the advantages of the both algorithms，we form the genetic great deluge algorithm（GGDA），and then apply the hybrid algorithm to solve differentscales ofMultidimensional Knapsack Rroblem（MKR）.The results show that the hybrid algorithm is simple and effective，superior to the standard GA and the GDA.

Multidimensional Knapsack Rroblem；Great Deluge Algorithm；Genetic Algorithm

TR3

：A

：1009-0312（2014）05-0023-05

2014-07-03

国家自然科学基金（61074147，61074185）；广东省自然科学基金（S2011010005059，8351009001000002）；广东省教育部产学研结合项目（2012B091000171，2011B090400460）；广东省科技计划项目（2012B050600028，2010B090301042）。

朱君（1991—），男，江西新余人，硕士生，主要从事组合优化、物流信息技术与应用研究。