考虑主观需求的0-1背包问题的求解方法及电子设备

技术领域

本发明涉及动态规划技术领域，具体涉及一种考虑主观需求的0-1背包问题的求解方法及电子设备。

背景技术

背包问题[1](knapsack problem，简称KP)，最早由Dantzing与20世纪50年代提出并研究，作为一类经典的组合优化问题，属于NP-hard问题，该问题具有众多的变种，包括0-1背包问题[2]、有界背包问题、多背包问题、多维背包问题[3]、二次背包问题和折扣0-1背包[4]问题等。在资源分配、投资决策、车辆装载、信息公共安全等领域具有重要的理论研究价值与实际应用价值。

由于背包问题的提出时间较早，各种背包问题的模型都趋于完善，具有较强的适应能力。然而，在常见的背包问题中约束条件一般都是背包的额定容量，即便是较为复杂的折扣0-1背包问题，除了需要考虑编码结构的可行性，其约束条件也同样是背包的额定容量。但在实际生活中，不同的决策者对于同样的问题不仅需要考虑问题本身的约束等客观因素，决策者的自身需求等主观因素同样值得考虑。

目前，针对背包问题的研究算法主要分成两类：贪心算法[5]、动态规划算法、穷举法等精确算法与遗传算法[6]、蚁群算法[7]、和声搜索算法[8]、蝙蝠算法[9]、狮群算法[10]等近似算法。两类算法各有优劣，在针对不同规模的背包问题时两类算法都能够展现出各自的优势。其中，贪心算法作为一类针对最值问题的经典算法，常被用以解决各类背包问题，但是由于其局部收敛性太强众多学者在使用它时，通常是将其与其他近似算法结合使用，以求达到提高算法收敛性能和防止陷入局部最优的目的。模拟退火算法[11]、禁忌搜索算法[12]和果蝇算法[13]等局部搜索由于其较弱的全局搜索能力，对初始解的要求十分严格，初始解质量越高，最终解质量就越高。因此，贪心算法通常会以算子的形式与其他近似算法结合，用来修补优化初始解以期提升算法的全局收敛性能，提升解的质量。文献[13]就将贪心算法作为果蝇算法的修复补偿策略，用来修复非法解和优化可行解，有效提升了果蝇算法的求解质量。遗传算法作为经典的优化算法之一，研究时间之长，应用领域之广，尤其针对各类优化问题更是展现出了无与伦比的优势。文献[14]在遗传算法中针对背包问题的特点引入贪心算子实现了对种群中解的质量的提升，提升了遗传算法的收敛性能；在一些较新的背包问题上，遗传算法同样展现出了极强的适用性，文献[16]借鉴了启发式搜索思想设计了3种交叉算子与1种变异算子，能够有效解决折扣0-1背包问题无效编码结构的问题，保证了算法进化中的解的可行性；当然遗传算法演化过程中的经典操作同样作用非凡，文献[15]就将遗传算法的经典交叉操作引入到了蝙蝠算法之中，建立了全新的位置转移方式，有效提升了算法的求解效率。

基于此，本文结合实际生活，将决策者的主观需求与背包问题结合，在0-1背包问题模型中引入“主观需求”的概念，提出考虑决策者需求上限的0-1背包问题，并设计了一种混合贪心遗传算法(Hybird Greedy Genetic Algorithm，HGGA)对问题进行求解。首先，考虑到遗传算法产生解的不稳定性和新模型的特征。

本实施例对被广泛应用的贪心修补算子进行针对性的改进；其次，考虑到遗传算法易于陷入局部最优的缺点，设计并嵌入了新的局部搜索算子，对局部最优个体进行扰动以期跳出局部最优并得到更优质的解。最后，经过仿真实验的验证，本实施例的模型以及求解算法在较短的时间内保证解的质量，并通过与简单遗传算法和贪心遗传算法的对比，显示出较好的性能。

发明内容

针对现有技术的不足，本发明公开了一种考虑主观需求的0-1背包问题的求解方法及电子设备，用于解决上述论述的问题。

本发明通过以下技术方案予以实现：

第一方面，本发明公开了一种考虑主观需求的0-1背包问题的求解方法，所述方法包括以下步骤：

S1利用主观需求概念，建立考虑决策者主观需求的0-1背包问题模型；

S2利用贪心算子，先考虑主观需求再考虑客观约束，对初始种群进行优化与修正；

S3利用局部搜索算子，改进扰动位点的选择方式，实现对局部最优解的扰动；

S4将上述算子嵌入到遗传算法得到混合贪心遗传算法；

S5利用混合贪心遗传算法对主观需求的0-1背包问题模型进行求解。

通常，人们在选择商品的时候，不同的人都有不同的需求，在满足自身需求的前提下，才会考虑其他的约束。为了更好地描述“需求”的概念，以蔬菜批发为例。假设，商贩驾驶额定载重为0.5吨的车辆前往蔬菜批发市场进行采购，对青椒、萝卜和白菜的需求均为0.2吨，每一类蔬菜拥有不同的收益。显然三类蔬菜的总需求已超过车辆的额定载重，那么在尽量满足各类蔬菜需求和不超过车辆额定载重的前提下，合理的蔬菜选购方案就意味着更高的收益。

更进一步的，所述问题模型描述为：给定n个物品，共分为A、B、C三类，每一个物品i都有它的重量w

已知三类物品的数量分别为a、b、c(a+b+c＝n)，决策者对这每一类物品的需求上限分别为C

更进一步的，所述问题型表示如下：

s.t.C

模型中，目标函数(1)表示最大化装入包中三类物品的总价值；约束式(2)，(3),(4)分别表示a，b，c三类物品的需求上限为C

更进一步的，所述贪心算子优化修正的步骤为：

T1分别计算当前解X对应的包内三类物品的重量W

T2分别对三类物品(A、B、C)进行修复操作，得到中间解X’；

T3计算中间解X”对应的所有物品总重量W”，确定所有已选物品；

T4将所有已选物品按照价值密度递减的顺序进行排列，依次选取放入包内直到满足背包的容量C；

T5将中间解X”的对应二进制位点进行调整，得到最终解。

更进一步的，若此类物品的总重量w大于此类物品的需求D，则将已选的物品按照价值密度递减的顺序进行排列，依次选取放入包内直到满足此类物品的需求D，并将当前解X的对应二进制位点进行调整；

若此类物品的总重量w小于此类物品的需求D，则将未选的物品按照价值密度递减的顺序进行排列，依次选取放入包内直到满足此类物品的需求D，并将当前解X的对应二进制位点进行调整。

更进一步的，所述局部搜索算子包括以下步骤：

B1根据局部最优解个体x

B 2在序列index_1中随机选择一个数，将个体x

B3在序列index_0中随机选择一个或两个数，以概率的形式实现位点数目的选择方式；

B4返回步骤2，重复100次，得到种群pop_temp，求出新种群中物品总价值大于xbest对应的物品总价值且满足各个约束的新个体x

B5返回第1步，重复100次，得到最终个体x

更进一步的，所述B2中，当随机概率P＞0.5时，选择一个位点，将个体x

更进一步的，所述方法针对解的修复优化方法，通过对不满足约束条件的解增加一个惩罚系数或是一个负值罚分，来降低此类解进入到下一次迭代进化的可能性，其适应度函数的设计如下：

若当前解满足各类约束：

若当前解不满足各类约束：

α为惩罚系数，取0.1。

更进一步的，所述方法对初始种群进行贪心修补与优化，以保证算法的收敛性能；并按照概率对每一代的局部最优个体进行精细化搜索，在尽量减少算法耗时的前提下，提升解的质量，具体算法描述如下：

M1以概率向量初始化的方式生成初始种群pop，种群规模为popsize；

M2调用贪心算子，将初始种群pop中的所有个体进行修正与优化得到新的种群pop1；

M3将新种群pop1代入遗传算法框架中，调用轮盘赌选择算子。计算所有个体的适应度值，并找到适应度值最大的个体，记为best_ind。最后得到规模相同的新种群pop2；

M4交叉操作，随机选择新种群pop2中的任意两个个体作为父代和母代个体，并将其按照概率P

M5变异操作，对新种群pop3中的所有个体按照概率P

M6计算并找到种群pop4中适应度最大的个体记为better_ind与最小的个体记为worst_ind；按照概率P

M7调用精英保留算子，比较pop5中适应度最大的个体better_ind与种群pop1中适应度最大的个体best_ind的适应度大小，若better_ind的适应度值小于best_ind，则将pop5中适应度最小的个体worst_ind替换为best_ind个体；反之，则不进行任何操作。最后得到最终种群pop6；

M8判断是否达到算法最大迭代次数，若是，则输出最优解并结束算法；若否，则返回步骤3，并将新种群pop1替换为种群pop6，重复以上操作。

第二方面，本发明公开了一种电子设备，包括处理器以及存储有执行指令的存储器，当所述处理器执行所述存储器存储的所述执行指令时，所述处理器执行如权利要求1至9中任一所述的求解方法。

本发明的有益效果为：

本发明被广泛应用的贪心修补算子进行针对性的改进；其次，考虑到遗传算法易于陷入局部最优的缺点，设计并嵌入了新的局部搜索算子，对局部最优个体进行扰动以期跳出局部最优并得到更优质的解。最后，经过仿真实验的验证，本发明的模型以及求解算法在较短的时间内保证解的质量，并通过与简单遗传算法和贪心遗传算法的对比，显示出较好的性能。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1是一种考虑主观需求的0-1背包问题的求解方法原理步骤图；

图2是本发明实施例HGGA算法流程图；

图3是本发明实施例算法收敛对比图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

实施例1

本实施例公开如图1所示的一种考虑主观需求的0-1背包问题的求解方法，包括以下步骤：

S1利用主观需求概念，建立考虑决策者主观需求的0-1背包问题模型；

S2利用贪心算子，先考虑主观需求再考虑客观约束，对初始种群进行优化与修正；

S3利用局部搜索算子，改进扰动位点的选择方式，实现对局部最优解的扰动；

S4将上述算子嵌入到遗传算法得到混合贪心遗传算法；

S5利用混合贪心遗传算法对主观需求的0-1背包问题模型进行求解。

本实施例中，针对问题模型的特殊性，分别对遗传算法框架中的经典算子进行了针对性的设计，具体如下：

选择操作：本实施例采用经典的轮盘赌选择算子与精英保留机制结合。一方面能够保证每一代种群中优秀个体都有较大的机会参与到下一代的迭代演化过程，保证优秀基因结构会继承下去；另一方面能够降低遗传算法的其他两类操作破坏优秀基因结构的可能性，保证算法一直是朝着理论最优解的方向进化。

交叉操作：随机选取种群中的两个解作为父代个体与母代个体，按照交叉概率P

首先在数组{1,2,3}中随机选取一个数。当随机数为1时，表示在代表A类物品的染色体结构上随机选择一个点作为交叉位点，进行单点交叉操作；当随机数为2时，表示在代表B类物品的染色体结构处进行交叉操作；当随机数为3时，表示在代表C类物品的染色体结构处进行交叉操作。

变异操作：对子代个体按照变异概率P

本实施例结合实际生活，将决策者的主观需求与背包问题结合，在0-1背包问题模型中引入“主观需求”的概念，提出考虑决策者需求上限的0-1背包问题，并设计了一种混合贪心遗传算法(Hybird Greedy Genetic Algorithm，HGGA)对问题进行求解。

首先，考虑到遗传算法产生解的不稳定性和新模型的特征，本实施例对被广泛应用的贪心修补算子进行针对性的改进；其次，考虑到遗传算法易于陷入局部最优的缺点，设计并嵌入了新的局部搜索算子，对局部最优个体进行扰动以期跳出局部最优并得到更优质的解。

最后，经过仿真实验的验证。本实施例的模型以及求解算法在较短的时间内保证解的质量，并通过与简单遗传算法和贪心遗传算法的对比，显示出较好的性能。

实施例2

本实施例论述问题分析与建模，首先对于问题描述通常，人们在选择商品的时候，不同的人都有不同的需求，在满足自身需求的前提下，才会考虑其他的约束。结合0-1背包问题的特点，将“需求”的概念与之结合，提出考虑决策者需求上限的0-1背包问题，供选择则的每一个物品都有自己固定的属性(价值和重量)，这些物品又分为若干类，决策者对于每一类物品都有自己的需求，在尽量满足自身需求和不超过背包额定限重的前提下，使得背包内的物品的总价值最大。

在本实施例所提出的问题中，三类物品的需求上限之和若是小于或等于背包的额定载重，那么在达到各类物品的需求上限的同时，装入背包内的物品一定不会超过背包的额定载重，那么此时问题就变成了简单的多背包问题，失去了研究的价值。但是，若三类物品的需求上限之和大于背包的额定载重，那么至少有一类物品必然无法满足其需求上限，或多或少都要有所损失。那么在此前提下，如何根据决策者对各类物品的主观需求合理地规划并分配背包空间，降低包内物品总价值的损失，最大化包内物品的总价值，便成为了解决此类问题的核心要点。

对于问题建模，考虑到问题的普适性和复杂性，问题模型构建如下：给定n个物品，共分为A、B、C三类，每一个物品i都有它的重量w

该问题数学模型表示如下：

s.t.C

模型中，目标函数(1)表示最大化装入包中三类物品的总价值；约束式(2)，(3)，(4)分别表示a，b，c三类物品的需求上限为C

实施例3

本实施例公开一种贪心算子，遗传算法在产生初始种群时，为了保证算法全局搜索能力通常采用随机的方式产生解，但这些解往往无法满足问题本身所带有的各种约束。以背包问题为例，初始种群的解通常分为两类：非法解与可行解。非法解对应的包内物品总重量往往会超过背包容量；近似解对应的包内物品总重量虽然不超过背包容量，但此时的背包往往还存在未得到充分利用的空间。

针对这些特殊解，学者们便根据背包问题的特点结合贪心算法提出了贪心算子，为物品的选择提供了明确的方向，大大降低了物品选择的盲目性，因此被广泛地应用于求解各类具有复杂约束的背包问题，有效解决了初始种群中解质量不高的问题。

贪心算子的物品选择策略主要分为两种：价值和价值密度。价值显而易见，价值密度一般定义为：。通过实验，对比两种策略产生的解的质量，以价值密度作为物品选择策略的解的质量通常高于以价值为准的选择策略。然而，仅以价值密度作为物品选择策略的方法将导致价值较大但价值密度过小的物品被选入包中的概率降低，导致整体算法陷入局部最优。

针对这一问题文献[14]则提出了同时考虑价值与价值密度的改进贪心算子，并以概率实现这两种策略的动态调用，进一步优化了贪心算子效率。当然，由于本实施例并不仅只采用贪心算子作为优化解的方法，所以文中使用的贪心算子并没有采取这种方法而是采用传统的考虑价值密度的策略，以保证解的质量。

结合本实施例提出的问题模型的特点，考虑到背包的客观约束和决策者对各类物品的主观需求两种约束。针对所有解的修复方案可以分为两类：1.先考虑客观约束，再考虑主观需求。在满足背包容量需求的前提下，根据决策者对各类物品的需求再对当前解进行调整，得到最终解；2.先考虑主观需求，再考虑客观约束。首先考虑各类物品的需求得到初步的解，再判断此解是否满足背包容量的约束，最后对此解进行调整与优化。经过试验证明，策略1得到的解的质量还需要进行二次调整才能够得到与策略2相同质量的解。策略2在修复解的时候无需二次调整，相较于策略1更加简便、高效。因此，本实施例最终确定采用策略2对当前解进行修复优化。具体操作描述如下：

分别计算当前解X对应的包内三类物品的重量w

分别对三类物品(A、B、C)进行修复操作，得到中间解X′：

若此类物品的总重量w大于此类物品的需求D，则将已选的物品按照价值密度递减的顺序进行排列，依次选取放入包内直到满足此类物品的需求D，并将当前解X的对应二进制位点进行调整。

若此类物品的总重量w小于此类物品的需求D，则将未选的物品按照价值密度递减的顺序进行排列，依次选取放入包内直到满足此类物品的需求D，并将当前解X的对应二进制位点进行调整。

输出的到中间解X′。

计算中间解X″对应的所有物品总重量W′，确定所有已选物品。将所有已选物品按照价值密度递减的顺序进行排列，依次选取放入包内直到满足背包的容量C。将中间解X″的对应二进制位点进行调整，得到最终解X′。

实施例4

本实施例公开一种局部搜索算子，遗传算法作为经典的优化算法，对于各类问题都具有良好的适应性，但其算法的缺陷也尤为明显，容易陷入局部最优，导致解过早的收敛。如何使遗传算法在求解问题时避免早熟收敛就成了提升其算法性能的有效途径。文献[17]在二进制差分演化算法中引入精英局部搜索，针对局部最优个体随机选取3个位点进行取反，实现了针对多维背包问题的高效求解。文献[18]结合二进制编码，对果蝇算法进行改进，通过控制二进制编码取反位点的数量实现了对果蝇算法搜索步长的模仿，同样取得了不错的效果。各类局部搜索算法的文献资料都表明，初始解的质量对于局部搜索算法的效率影响至关重要。

考虑到遗传算法的全局寻优能力与局部搜索算法的高效局部搜索能力。本实施例在遗传算法的基本框架中加入了改进的局部搜索算子，实现了对局部最优个体的进一步优化。文献[15]中所提出的随机选取3个位点的方式过于野蛮，往往会产生较多的无用结构。例如，x＝[0100111100]，当随机选取到第2、5、6号位点，进行取反后得到新的个体x′＝[0000001100]。显然，这些位点的取反是没有意义的，会增加的算法运行时间。在此基础上，本实施例结合果蝇算法的局部搜索特点并改进了取反位点的选择方式，设计了一种新的局部搜索算子。具体操作描述如下：

步骤1根据局部最优解个体x

步骤2在序列index_1中随机选择一个数，将个体x

步骤3在序列index_0中随机选择一个或两个数，以概率的形式实现位点数目的选择方式。当随机概率P＞0.5时，选择一个位点，将个体x

步骤4返回步骤2，重复100次。得到种群pop_temp，求出新种群中物品总价值大于x

步骤5返回第1步，重复100次。得到最终个体x

实施例5

本实施例公开遗传算法框架，编码方式与种群初始化，针对0-1背包问题的特点，本实施例采取常用的二进制编码方式，编码串中的1表示选择对应序号的物品放入背包内，0表示对应序号的物品不放入背包内。例如，x＝[0100111100]表示10个物品中的第2，5，6，7，8号物品放入背包内。

本实施例参照文献[17]和[18]的初始化方法，采取概率向量的方式生成初始种群。直接随机生个一个概率向量P(X)＝[p(x

结合本实施例的模型，编码结构如下：

对于适应度函数，无论何种背包问题，都属于带有约束条件的最大值问题。对于此类问题，除了上文提到的针对解的修复优化方法，还有一类——罚函数法，通过对不满足约束条件的解增加一个惩罚系数或是一个负值罚分，来降低此类解进入到下一次迭代进化的可能性。本实施例考虑到整体的算法性能，采用惩罚系数的方法。适应度函数的设计如下：

若当前解满足各类约束：

若当前解不满足各类约束：

α为惩罚系数，取0.1。

实施例6

本实施例公开算法流程设计，具体流程如图2所示。考虑到遗传算法的特点以及贪心算子和局部搜索算子的作用以及耗时，本实施例仅对初始种群进行贪心修补与优化，以保证算法的收敛性能；并按照概率对每一代的局部最优个体进行精细化搜索，在尽量减少算法耗时的前提下，提升解的质量。具体算法描述如下：

步骤1以概率向量初始化的方式生成初始种群pop，种群规模为popsize；

步骤2调用贪心算子，将初始种群pop中的所有个体进行修正与优化得到新的种群pop1；

步骤3将新种群pop1代入遗传算法框架中，调用轮盘赌选择算子。计算所有个体的适应度值，并找到适应度值最大的个体，记为best_ind。最后得到规模相同的新种群pop2；

步骤4交叉操作。随机选择新种群pop2中的任意两个个体作为父代和母代个体，并将其按照概率P

步骤5变异操作。对新种群pop3中的所有个体按照概率P

步骤6计算并找到种群pop4中适应度最大的个体记为better_ind与最小的个体记为worst_ind；按照概率P

步骤7调用精英保留算子。比较pop5中适应度最大的个体better_ind与种群pop1中适应度最大的个体best_ind的适应度大小，若better_ind的适应度值小于best_ind，则将pop5中适应度最小的个体worst_ind替换为best_ind个体；反之，则不进行任何操作。最后得到最终种群pop6；

步骤8判断是否达到算法最大迭代次数，若是，则输出最优解并结束算法；若否，则返回步骤3，并将新种群pop1替换为种群pop6，重复以上操作。

实施例7

本实施例对仿真实验与结果分析，为了验证算法性能，本实施例参考文献[14]、[21]中的数据构造方法，分别构造了物品维数为150、300和600的背包数据集，每种规模的物品数据分为无相关、强相关与弱相关3类，共9个算例。每个算例所包含的A、B、C三类物品，具体物品种类划分规则为：每1/3维数的物品为一类。例如，维数为150的算例，1号至50号物品划为A类物品，51号至100号物品划为B类物品，101号至150号物品划为C类物品。算例数据分类特征如表1所示。

表1算例数据分类特征

背包的额定容量C＝0.75*所有物品的总重量，取整。各类物品的需求D＝0.8*对应种类的物品总重量，取整。确保三类物品的需求之和大于背包的额定容量C。相同维数的算例使用相同的重量集合W和不同的价值集合V，故同一维数的算例的客观约束与主观需求是相同的。算例的各类物品的主观需求D和客观约束背包容量C等具体信息如表2。

表2约束信息

对于算法参数及实验环境，在本实施例的算法中，遗传算法框架中的经典参数设置：最大迭代次数为300，种群规模为100，交叉概率为0.85，变异概率为0.05。每个算法独立运行30次。而在遗传算法框架中，局部搜索的种群规模和搜索次数不仅会影响到算法的寻优能力，也会影响到算法整体耗时。为了平衡种群规模和搜索次数对于算法整体性能的影响，本实施例经过多次尝试，最终确定局部搜索种群规模和局部搜索次数均为100次，局部搜索概率为0.05。表3给出了详细的算法参数信息。

实验的硬件环境为惠普ProDesk 400G4 MT Bussiness PC，CPU型号为Inter(R)Core(TM)i5-7500 CPU@3.40GHz-3.41GHz，内存8G，软件环境为64位Windows10操作系统，算法使用matlab语言在matlab 2016中编写。

表3参数设置

本实施例对实验结果与分析，为了检验HGGA算法性能，本实施例使用3.1中构造的9个不同规模、不同相关性的算例进行实验，并分别与同类型的遗传算法进行对比，其中包括简单遗传算法(SGA)和引入贪心修正算子的贪心遗传算法(GGA)。经过30次的算法实验，统计得到最优解、最差解、平均解、标准差和30次实验的平均耗时，表4给出具体实验结果。加粗的算法表示该算法在三类算法中综合性能最好。

结合表4给出的最优解、最差解和平均解三类解，本实施例提出的HGGA除了在KP3和KP5两个算例上，解的质量略低于GGA，在其他7个算例上均取得了不错的优势。而表中的标准方差是评价算法鲁棒性的重要指标，方差越小，算法的鲁棒性越强；反之，鲁棒性则越差。同样，HGGA的标准方差在除了KP3和KP5两个算例以外的其他7个算例上也展现出不错的优势。

考虑到算法的平均耗时。随着算例规模的扩大，算法耗时也在明显增加。在相同规模的算例上，虽然SGA虽然耗时最短，但由于其易陷入早熟收敛的缺点，SGA求解精度和鲁棒性都是三种算法中最差的；而本实施例提出的HGGA算法耗时在同等规模的算例中虽然耗时最大，并随着数据规模的增加，同其他两类算法的差距也会逐渐增加，但在较多算例的求解精度和算法鲁棒性上则表现出一定的优势。

表4实验结果

考虑到算例的相关性差异。图2给出了规模同为150的三类相关性算例的算法收敛折线图，由表4可知SGA的整体求解精度较差，故仅在图2中绘出GGA与HGGA两类算法。从图中，明显可以看出当算例规模相同，本实施例提出的HGGA算法在无相关算例上表现出的收敛效果和求解精度明显优于GGA算法，但在强相关和弱相关两类算例上收敛效果和求解精度明则与GGA算法不相上下。结合表4中的算例3和算例5的结果，可以得出HGGA算法在求解无相关的数据时，其综合性能在三类算法中表现最好；在处理具有一定相关性的数据时，HGGA算法的性能难以与GGA拉开差距，甚至劣于GGA算法。

综上，考虑到实际生活中存在的“主观需求”与“客观约束”两类约束，本文将之与0-1题结合，提出了考虑决策者需求的0-1背包问题，根据问题构建了具体的数学模型，并针对遗传算法全局搜索能力强、易早熟收敛和局部搜索能力弱的缺点，提出了贪心混合遗传算法。

本发明在不改变遗传算法框架的前提下，针对问题特点对贪心修正优化算子进行了一定的改进，增强了遗传算法的收敛性能；同时设计了一种局部搜索算子，改进其扰动位点的选择规则，提升了遗传算法的局部搜索能力。此算法在9个随机生成的规模不同、相关性不同的算例进行仿真实验，并与同类型的遗传算法比较显示出本文算法求解精度高、算法鲁棒性强的特点。

参考文献

[1]Dantzig G B.Discrete-Variable Extremum Problems[J].OperationsResearch,1957,5(2):266-277.

[2]王莉,绍定宏,陆金桂.基于遗传算法的0/1背包问题求解[J].计算机仿真,2006,23(003):154-156.

[3]Chu P C,Beasley J E.A Genetic Algorithm for the MultidimensionalKnapsack Problem[J].Journal of Heurs,1998,4(1):63-86.

[4]He Y C,Wang X Z,He Y L,et al.Exact and approximate algorithms fordiscounted{0-1}knapsack problem[J].Information ences,2016,369:634-647.

[5]Zhang L L,Zhang H,Wang M G.An Algorithm of 0-1Knapsack ProblemBased on Greedy Degree Determination and Dynamic Expectation Efficiency[J].Applied Mechanics&Materials,2014,644-650:1957-1960.

[6]葛继科,邱玉辉,吴春明,等.遗传算法研究综述[J].计算机应用研究,2008,25(10):2911-2916.DOI:10.3969/j.issn.1001-3695.2008.10.008.

[7]Nakbi W,Alaya I,Zouari W.A Hybrid Lagrangian Search Ant ColonyOptimization Algorithm for the Multidimensional Knapsack Problem[J].ProcediaComputer ence,2015,60:1109-1119.

[8]Kong X,Gao L,Ouyang H,et al.A simplified binary harmony searchalgorithm for large scale 0–1knapsack problems[J].Expert Systems withApplications,2015,42(12):5337-5355.

[9]李枝勇,马良,张惠珍.遗传变异蝙蝠算法在0-1背包问题上的应用[J].计算机工程与应用,2014,50(011):49-52.

[10]刘生建,杨艳,周永权.求解0-1背包问题的二进制狮群算法[J].计算机工程与科学,2019,41(11):2079-2087.

[11]耿亚,吴访升.基于粒子群-模拟退火算法的背包问题研究[J].控制工程,2019,026(005):991-996.

[12]廖飞雄,马良,王攀.一种改进的禁忌搜索算法求解背包问题[J].计算机应用与软件,2009(03):131-133.

[13]张清勇,钱浩,雷德明.求解多维背包问题的二级协作果蝇优化算法[J].控制与决策,2019,34(03):503-510.

[14]陈桢,钟一文,林娟.求解0-1背包问题的混合贪婪遗传算法.计算机应用.

https://kns.cnki.net/kcms/detail/51.1307.TP.20200822.1326.002.html

[15]万晓琼,张惠珍.求解0-1背包问题的混合蝙蝠算法[J].计算机应用研究,2019,036(009):2579-2583

[16]吴聪聪,贺毅朝,赵建立.求解折扣{0-1}背包问题的新遗传算法[J].计算机工程与应用,2020,056(007):57-66.

[17]吴聪聪,赵建立,刘雪静,等.改进的差分演化算法求解多维背包问题[J].计算机工程与应用,2018,054(011):153-160.

[18]Meng T,Pan Q K.An improved fruit fly optimization algorithm forsolving the multidimensional knapsack problem[J].Applied Soft Computing,2017:S1568494616305920.

[19]Wang L,Zheng X L,Wang S Y.A novel binary fruit fly optimizationalgorithm for solving the multidimensional knapsack problem[J].KnowledgeBased Systems,2013,48(8):17–23.

[20]贺毅朝,王熙照,寇应展.一种具有混合编码的二进制差分演化算法A BinaryDifferential Evolution Algorithm with Hybrid Encoding[J].计算机研究与发展,2007,044(009):1476-1484.

[21]史亮,董槐林,王备战,龙飞.求解大规模0-1背包问题的主动进化遗传算法[J].计算机工程,2007,033(013):31-33

王熙照,贺毅朝.求解背包问题的演化算法[J].软件学报,2017,028(001):1-16。

以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。