基于改进蛙跳算法求解背包问题

刘陆洲，张晓霞

（辽宁科技大学计算机与软件工程学院，鞍山 114051）

1 问题的提出

近年来，我国物流行业发展迅速、市场规模日益扩大，物流行业逐渐走向有序化，整个行业开始进入到快速发展时期。与此同时，物流行业在如何提高工作效率方面的压力与日俱增，高人力成本成为了物流公司的一大负担，这也促使传统的物流行业必须加快向着智能化、高效化的方向转型升级。我国无人卡车、人工智能正处于研发测试阶段，未来发展前景巨大[1]，因此，研究多维背包问题，对如何选取所要运输的包裹和怎样装载包裹才能更好地利用有限的资源都有着较大的积极作用，同时对加快我国的“智慧城市”建设也有着重要的理论价值和意义。

2 多维背包问题

在一定范围内给出n 个物品，每个物品都具有三个属性值，即价值（f），体积（v）和重量（w），其中，fi为第i 个物品所具有的价值，vi为第i 个物品的体积（i=1，2，…，n），wi为第 i 个物品的重量（i=1，2，…，n），背包所能承受的最大重量为W，最大容量为V，则多维背包问题的数学模型为：

其中，所求目标为所有选中物品的总价值之和的最大值F，同时所选物品占用的资源必须遵循约束（2）背包容量V 的限制和约束（3）中背包最大承重W 的限制；约束（4）中xi表示可选择的物品i 的状态值被限制为0 或者1，若将物品i 选中放入背包，则xi的值设置为1，否则设置为0。每件物品只能选择一次，并且不能将物品切割部分放置在背包中。通过对公式（1）-（3）的分析不难看出，该问题的计算复杂度随物品个数的增加呈现指数形式的增长，因此，背包问题[2]属于一个NP 完全组合优化问题[3]，在合理时间内，蛙跳算法在非连续的解空间条件下无法精准计算出结果，故需要对蛙跳算法的求解方法进一步改进。

3 改进的蛙跳算法

选用遗传算法的更新策略来替代普通的蛙跳算法[4-5]的个体更新方式，该方法不但具有蛙跳算法的优点，拥有了较高的搜索性能，而且也提升了在不同解空间下得到更好的解决方案的能力。

改进的蛙跳算法的概述如下：

初始化蛙跳算法的阈值，设置相关的约束参数，包括背包的极限载重W 和极限容积V。在可行解空间下，初始化解决方案，利用随机数生成器生成适宜数量的个体，个体集为F={x1,x2,…,xF}，并计算它们的适应度fi。将个体按照适应度降序的方式排列并划分子群，标记子群中最优个体Pb和种群内最优个体Pg。用所要更新的子群中最优个体Pb与当前子群内个体进行交叉遗传变异操作，产生新的子个体。如果子个体的适应度优于所要更新的亲代个体，那么子个体替代亲代个体；否则，用整个种群内最优个体Pg与所要更新的个体进行遗传操作产生新的子个体，如果子个体的适应度优于亲代的，则用其替代亲代；否则，随机生成一个新的子个体替代亲代个体，完成上述更新操作，则视为个体更新结束。对种群内所有个体都重复执行更新操作直至达到预先设定的迭代次数，则视为种群的局部搜索过程完成。重复不断地划分种群、保留下较好的基因序列，直至达到设定的更新阈值即为结束，图1 给出了改进的蛙跳算法解决多维背包问题的具体流程。

图1 改进的蛙跳算法的具体流程

4 实验结果与分析

为验证改进后算法的性能，所提出的改进型蛙跳算法采用C++编程。测试实例采用OR-Library（http://people.brunel.ac.uk/～mastjjb/jeb/orlib/files/mdmkp_ct1.

txt）中的典型数据。改进的蛙跳算法中存在一些约束参数，这些参数的设置会影响到算法解的质量，我们设定改进的蛙跳算法的种群规模为200，子群数量为20，迭代的最大次数为1000，为测试跳跃阈值对解的影响，选取跳跃值不同时，得出的解的质量，经过大量实验得出，跳跃阈值为6 时所获得的解的质量更好。

表1 给出了改进的蛙跳算法与普通的蛙跳算法运行结果的比较，为了能更加清晰的得出改进的蛙跳算法相比普通的蛙跳算法性能上的提升量，设定解的价值、实际载重和占用空间在性能上的权值分别为0.6、0.2 和0.2，通过实验得出改进的蛙跳算法解的性能更高，平均提升的的权值约5.20‰，从表中的数据可以看出，改进的蛙跳算法在得到高质量解的同时能够更有效地利用背包资源，该算法在解决MKP 问题时相比普通的蛙跳算法具有一定的优越性。

表1 改进的蛙跳算法与普通的蛙跳算法运行结果比较

5 结语

本文详细阐述了改进后的蛙跳算法的基本原理，将遗传算法的交叉遗传变异机制嵌入到普通的蛙跳算法的更新方法中，获得了一种计算性能更好的改进算法，避免了算法在解决问题当中出现局部最优和过早收敛的问题。通过大量的实验，对测试所得的数据进行分析得出：改进后的蛙跳算法在解决多条件背包问题时所产生的解仍然具有较高的可行性，相较于普通的蛙跳算法拥有更广的适用范围。