变尺度背包问题研究

摘 要：在使用传统的算法来对背包问题进行解决时，有收敛问题和精度不高问题的情况出现，所以本文提出了一种使用粗尺度与细尺度相结合的变尺度方式来对背包问题进行解决的方案，从而提高算法的搜索性能。

关键词：背包问题 变尺度 算法 收敛

一、0-1 背包问题

它可以作如下阐述：假定有一个背包，还有 种物品，这些物品都是有相应的价值和重量的，那么，此时在不超过背包重量极限的情况下，达到价值的最大值。它所对应的数学模型是：

（1）

（2）

二、变尺度背包问题算法

本文提出的便尺度背包问题涉及到两种变异算子，一种是粗尺度变异算子，当然，它的很多的性能都是由震荡周期来决定的，周期不同，它的搜索的性能是不同的，当然，这里指的是大范围的搜索能力，通过粗尺度变异算子可以在进行全局的搜索过程中有较好的性能，使搜索的广度增大。另一种是细尺度变异算子，它是针对于小范围的搜索，并且随着搜索的进行，它的值也是在变动的，越往下执行它的精确度越高，提高其收敛的性能，这样可以搜索的精度得到提高，具体说明如下：

在进行算法的进化开始时，系统里面的最优粒子和全局最优解的距离是无从得知的，有这样的情况出现，即两者之间的距离是无规律的，距离大小是随机变动，所以，就得使用粗尺度变异算子来完成大面积的搜索功能，在具体使用的过程中，使用周期性的震荡函数来计算出变异算子，通过这样的方式来完成粒子的多变性，当然所选择的函数可以根据实际情况而定：

假定，粗尺度变异算子个数为 ，其初始化的结果为：

（3）

当然，具体计算时，它的选取是随机的，在实际的迭代过程中，其会使用一下的方式来进行变动：

（4）

参数说明：

――空g宽度，本文所选择空间宽度B=8；

――当前迭代次数；

――可以决定震荡频率。

所以，通过使用上述的算法进行计算完毕后，已经把全局最优解控制在一定的范围了，所以在这种情况下，就要使用细尺度变异算子来实现最优解的精确搜索和确定，在本文具体实现的过程中使用递减的指数函数来实现细尺度变异算子的筛选，从而使其搜索的能力更强。当然，在具体实现时，其速度也是可以根据实际情况来把控的：

假定，粗尺度变异算子个数为 ，其初始化的结果为：

（5）

（6）

参数说明：

――可以实现控制变异算子速度调节，可以实现精度的变化；

――当前迭代次数；

――在y的范围内进行选择。

在具体计算的过程中，假设经过了 次迭代过程，在经过计算后，此时刻的最优解的速度定义为 ，当然 是在 之中进行选择的，那么，就可以对速度进行变尺度了，如果要是保证速度的多变性，从而使搜索更有效，如果 ，如果速度增加，则将其减小，如果 减小，则将其增大，其变化多少由高斯标准差来决定。

本文的便尺度算法可以实现速度取值空间的覆盖，其实现原理类似游标卡尺的工作原理，在这里，粗尺度变异算子相当于主尺，可以实现大概的长度的测量，而细尺度变异算子相当于游尺，可以进一步实现长度的精确测量。使用变尺度算法中的粗尺度，就可以迅速的逃逸出局部极小值，从而使定位最优解区域的能力更优；使用变尺度算法中的细尺度，可以对一个区间范围内的数据进行精确的搜索，从而找到最优解。

三、变尺度背包问题解决方案

在解决背包问题时，一个很关键的步骤是选择初始群体，它的选择能够使最终的结果更加明显，那么选择怎样的初始群体才算是一个好的初始群体，首先，保证分布性良好，能够正确的反映出空间覆盖情况，这样做的目的是避免所使用的算法计算的局限性太强；其次，群体里面的个体的质量良好，从而在具体计算过程中，能够使算法计算过程有效，从而减小盲目搜索的概率。所以，在本文初始化粒子位置的过程中，把各个物品先求解价值重量比值，然后按照此值进行相关排序操作，此时就是初始位置，其他粒子则不进行相应计算，而是随机产生。其部分实现过程描述如下：1、选择参数，确定粒子位置；2、选择全局最优粒子；3、计算粗尺度变异算子和细尺度变异算子；4、根据算法对粒子状态进行相应更新操作；5、根据上述操作确定最优解。

四、结论

本文提出了一种使用粗尺度与细尺度相结合的变尺度方式来对背包问题进行解决的方案，从而提高算法的搜索性能，一是因为变尺度使得在计算量减小的情况下使得粒子的多样性增加，另外，使用贪心测量提高了收敛速度。为了更好阐明本文的变尺度算法，说明其用于解决背包问题的优势，本文对其进行了实验验证，并与一些经典算法进行了比较，如更贪心粒子群算法、病毒协同进化粒子群算法、模拟退火思想改进的粒子群算法等进行了相关的比较和分析。综合数据分析，本文设计的算法更加优异。

参考文献：

[1]张晓琴，黄玉清.基于禁忌搜索的启发式求解背包问题算法[J].成都：电子科技大学学报，2005， 3（34）： 359-362

[2]严太山.用基于贪婪算法的混合遗传算法求解0/1背包问题[J].岳阳：现代计算机，2007， 26（5）： 247-249

[3]贺毅朝，刘冲起，张翠军，等.求解背包问题的贪心遗传算法及其应用[J].计算机工程与设计，2007，28（11）：2655-2657

[4]宋海生等.求解多限制 0-1背包问题的混合遗传算法[D].计算机工程 2009， 35（13） 4-7

[5]秦玲等.解0-1 背包问题的蚁群算法[J]. 计算机工程，2006， 3（26）： 212-214

[6]杜海峰等. 解0-1 背包问题的人工免疫抗体修正克隆算法[J]. 控制理论与应用，2005， 3（22）： 436-439

[7]陶新民等.变尺度变异离散粒子群算法求解背包问题[J]系统仿真学报，2013， 25（1）：12-17

作者简介：

乔世成（1984.09-）男，汉族，内蒙古通辽市库伦旗人，讲师，工学硕士，研究方向：计算机网络；姜静清（1968.05-）女，汉族，内蒙古通辽市人，教授，工学博士，硕士研究生导师，研究生方向：数据挖掘、机器学习。

基金项目：

内蒙古民族大学科学研究基金资助项目（项目编号：NMDYB15081）