基于粒计算理论的背包问题研究

肖镞

摘要：本文阐述了遗传算法是解决背包问题的有效方法，指出将粒计算理论引入背包问题求解的可行性，研究了基于粒矩阵知识约简遗传算法求解背包问题，为背包问题的求解提供了新的思路，本文通过一个四背包问题进行举例说明。

关键词：遗传算法；粒计算理论；背包问题

中图分类号：TP301.6 文献标识码：A 文章编号：1007-9416（2018）06-0062-02

遗传算法是一种问题求解方法，它模仿了生物进化过程，可以使用多种编码方法来表征复杂的结构，可以用一组编码表示进行遗传操作，经过优胜劣汰的自然选择，决定搜索路径，在解决背包问题的众多算法中，遗传算法可以是一个比较好的方法遗传算法将0-1背包问题看成一个知识系统，包括了条件和决策属性。背包问题中的各个物件可以认为是条件属性，在滿足约束条件的情况下，决策属性为背包中物件的总价值是否大于等于群体某一值，大于等于则为优秀个体，记为1，小于则为劣质个体记为0。即可将背包问题用遗传算法表示，进行编码和运算等工作，用遗传算法的规则求出0-1背包问题的最优解[1]。

1 粒矩阵知识约简方法的实现过程

1.1 决策信息系统的知识粒化

对决策表T=（U，A，C，D）进行知识粒化，针对不同要求可采取不同的粒化方法（均匀粒化、模糊粒化、分层粒化等），这里采用等价类的二进制粒化法，根据条件类与决策类，求取对应的二进制粒矩阵BGrM。

1.2 判断初始决策信息系统是否相容

定义2 相容与不相容：在决策表中，对于U/C中同一等价类的记录都是相同的决策值，就称这个等价类的任一记录为确定性记录，若有不同的决策值，则为不确定性记录。如果在决策表中的所有记录都是确定性的，就称这个决策表为相容表，否则称为不相容表，根据公式：。

计算k，如果k=1，决策信息系统相容，转下一步，否则根据Cm×n，通过矩阵的变换将其拆分成相容决策表，篇幅有限，这里只讨论相容决策表。

1.3 合并相同规则，进行属性约简

2 将粒计算理论引入遗传算法求解0-1背包问题

在求解0-1背包问题的过程中，遗传算法产生新基因型个体的方法有两种，一是基因交换，另一种是突变。而这两种方式都是随机产生的，并没有让个体向适应度更好的方向发展，而只是经过模拟自然选择的过程，对劣质个体进行了淘汰。这样在一定程度上让运算更加复杂。通过粒矩阵知识约简方法，在进行遗传算子操作之前，先对初始群体进行属性约简。然后在最简属性的基础上进行选择复制、交换和突变的操作。在能够终止之前，每一代个体都存在着差别，可以进行属性约简，获得每一代个体染色体上的主要基因，然后再进行遗传算子操作。基于粒矩阵的知识约简方法实际上是将决策信息表的属性及属性值约简等效为矩阵的数学计算。决策信息表中相同规则的合并，不相容决策信息表的分解都可以认为是一种矩阵运算，从而0-1背包问题的信息可以用矩阵来表示，描述更加直观[2]。

3 算法对比和结果分析

GA和GCGA都可以得到20个背包问题的最优解，此时最优解的个体相同，背包重量也一样，但GA在128代达到最优解，GCGA在42代获得最优解，本文提出的GCGA算法在迭代次数上明显优于遗传算法，GCGA算法比遗传算法具有更快的收敛速度。

参考文献

[1]朱阅岸.解0-1背包问题的算法比较和改进[D].暨南大学，2011.

[2]贺毅朝，王熙照，李文斌，等.基于遗传算法求解折扣0-1背包问题的研究[J].计算机学报，2015，（12）：2614-2630.

Abstract：This paper expounds that genetic algorithm is an effective method to solve the knapsack problem， points out the feasibility of introducing the grain computing theory into the knapsack problem solving， and studies the solution of knapsack problem based on the kernel matrix knowledge reduction genetic algorithm， and provides a new idea for the solution of the knapsack problem. This paper is carried out through a four knapsack problem. Examples are given.

Key words：genetic algorithm； grain computing theory； knapsack problem