折扣{0-1}背包问题的简化新模型及遗传算法求解

杨洋 潘大志 刘益 谭代伦

摘 要：当前折扣{0-1}背包问题（D{0-1}KP）模型将折扣关系作为一个新的个体，导致求解过程必需采取修复法对个体编码进行修复，求解方式较少。针对求解方法单一的问题，通过改变模型中二进制的编码表达方式，提出折扣关系不在个体编码中的表达方法。该方法首先，设定对任意折扣关系，当且仅当所涉及个体编码值同时为1（即其乘积为1）时，折扣关系成立，据此建立简化折扣{0-1}背包问题（SD{0-1}KP）模型;然后，针对SD{0-1}KP模型，基于杰出者保留策略（EGA），结合贪心策略（GRE），提出改进遗传算法——第一遗传算法（FG）;最后，再结合罚函数法，提出求解SD{0-1}KP高精度罚函数法——第二遗传算法（SG）。结果表明，SD{0-1}KP能够完全覆盖D{0-1}KP问题领域，与FirEGA相比，所提出的两类算法在求解速度方面优势明显，且SG算法首次引入罚函数法，有效地丰富了该问题的求解算法。

关键词：折扣{0-1}背包问题;简化折扣{0-1}背包问题;贪婪策略;近似计算;数学模型;遗传算法

中图分类号： TP18

文献标志码：A

文章编号：1001-9081（2019）03-0656-07

Abstract： Current Discounted {0-1} Knapsack Problem （D{0-1}KP） model takes the discounted relationship as a new individual， so the repair method must be adopted in the solving process to repair the individual coding， making the model have less solving methods. In order to solve the problem of single solving method， by changing the binary code expression in the model， an expression method with discounted relationship out of individual code was proposed. Firstly， if and only if each involved individual encoding value was one （which means the product was one）， the discounted relationship was established. According to this setting， a Simplified Discounted {0-1} Knapsack Problem （SD{0-1}KP） model was established. Then， an improved genetic algorithm — FG （First Gentic algorithm） was proposed based on Elitist Reservation Strategy （EGA） and GREedy strategy （GRE） for SD{0-1}KP model. Finally， combining penalty function method， a high precision penalty function method — SG （Second Genetic algorithm） for SD{0-1}KP was proposed. The results show that the SD{0-1}KP model can fully cover the problem domain of D{0-1}KP. Compared with FirEGA （First Elitist reservation strategy Genetic Algorithm）， the two algorithms proposed have obvious advantages in solving speed. And SG algorithm introduces the penalty function method for the first time， which enriches the solving methods of the problem.

Key words： Simplified Discounted {0-1} Knapsack Problem （SD{0-1}KP）; greedy strategy; approximate calculation; mathematical model; Genetic Algorithm （GA）

0 引言

0-1背包問题（{0-1} Knapsack Problem， {0-1}KP）[1]作为一种在实际社会生产生活中应用广泛的数学模型，虽然{0-1}KP属于NP-complete问题，但通过近似算法等元启发式算法对于{0-1}KP模型刻画的下料问题、资源调度、拆料切割方面有着优异的求解效果[2-5]。在此类{0-1}KP中，物品的价值及质量恒定为一个常量，不随时间及个体选取产生任何变化。但在实际问题中，{0-1}KP中个体的价值及质量不一定始终为一个定值，因而将{0-1}KP中个体价值质量随着时间变化而随机变化的问题刻画为随机时变背包问题（Randomized Time-Varying Knapsack Problem， RTVKP）[6]，对于个体价值质量随着其他物品的选择而变化的问题刻画为折扣{0-1}背包问题（Discounted {0-1} Knapsack Problem， D{0-1}KP） [7-8]。

D{0-1}KP可以认为是经典{0-1}KP的一个拓展形式[7-11]，它刻画了商业活动中物品销售的捆绑销售及折扣营销等现象。因而在商业活动中，面对大量采购物品存在此类关系时，D{0-1}KP是一个更好地使商业价值最大化且具备广阔应用前景的数学模型。

D{0-1}KP模型由于约束条件过多，且编码个体易于出现非正常编码个体等原因，导致研究成果相对较少。Guder[7]和Guldan[8]两人对基于单目标和多目标的D{0-1}KP模型进行了刻画及基础性求解，但并未给出大规模实例的求解方式，同样也未能对模型进行进一步的完善和简化。此后，较多文献利用算法在求解精度上对问题进行了改进[9-19]。对于启发式算法则主要集中在如：核（core）算法[9] 及动态规划[11]两种算法;元启发算法[10，12-18]则主要有遗传算法[10]、帝王蝶算法[12-13]、乌鸦算法[15-16]等成果。而在优化策略方面，则主要对贪婪算子进行改进[10，19]。

当前D{0-1}KP模型由于将折扣关系作为独立个体在编码个体中进行体现，非正常编码过多，导致除修复法方法之外，如罚函数法等可以用于求解{0-1}KP的加速算法无法适用于D{0-1}KP[10]。为改变这一现状，本文为D{0-1}KP模型设计新的二进制编码方式，简化数学模型，扩大求解方法，从而得到更优良的解值。本文在第2章中，给出传统D{0-1}KP模型的定义，针对模型存在的缺陷进行分析。第3章中，通过给出相关基本定义，设计新的二进制编码方法，建立简化折扣{0-1}背包问题（Simplified Discounted {0-1} Knapsack Problem， SD{0-1}KP）模型。在第4章中介绍基于杰出者保留策略（Elitist Reservation Strategy， EGA）遗传算法求解机制。结合加速贪心算法（Greedy， GRE），给出第一遗传算法（First Genetic Algorithm， FG）算法伪代码。再结合罚函数法，首次提出可适用于SD{0-1}KP问题的混合罚函数法，给出SG算法伪代码。在第5章中，给出四类大规模D{0-1}KP实例各10个，并转化为SD{0-1}KP实例，进行求解。结果表明：SD{0-1}KP能够完全覆盖D{0-1}KP在实际商业折扣活动的模型功能，同时通过减少对于额外修复的GROA（Greedy Repair Optimization Algorithm） [10]的使用，算法速度提升明显。且第一遗传（First Gentic algorithm， FG）算法和第二遗传（Second Genetic algorithm， SG）算法对于求解SD{0-1}KP均能够有效应用，且在综合性能上FG算法更优于SG算法。

1.2 D{0-1}KP模型缺陷

在传统D{0-1}KP模型中，虽然刻画商品之间的“折扣”关系，但整体系统略显复杂，其约束条件过多，甚至因为个体的编码问题，导致传统{0-1}KP中的加速算法无法有效利用，对于问题求解造成较大影响。针对D{0-1}KP模型中个体编码方式，以下主要从两方面进行缺陷分析。

一方面，D{0-1}KP个体非正常编码过多。在传统二进制个体编码情况下，物品A、物品B及假设出来的物品C至多只能取一个。这种方式直接导致元启发式算法中，在n个物体及m（m≤2n-n-1）个折扣关系问题中，正常编码个体的概率仅为（（m+1）/2m）n[10]，求解过程中必须对产生的个体进行大量的编码修复工作，保证算法收敛。所以对于求解D{0-1}KP，任意元启发式算法中的迭代寻优都必须要采取编码修复，有些算法甚至需要采取多次个体编码修复。如遗传算法中，在变异算子和交叉算子对个体进行处理后，都必须要采取编码修复，大大增加了算法收敛所需要的迭代时间。

另一方面，求解D{0-1}KP加速方法受限。对于{0-1}KP模型中常见的加速求解方式，如罰函数法等，基本无法在D{0-1}KP对问题进行有效求解，其结果误差无法接受[10，20]。这使得求解D{0-1}KP模型可选方法大为减少，对于模型的求解存在不利。

综上，对于现有D{0-1}KP模型，由约束条件（2）可知，同一项集内的物品至多只能选择一个，这一特性导致在求解过程中，非正常个体编码过多，进而必须通过采取修复操作对个体编码进行修复，最终大幅度增加计算时长。对于这一难点，本文通过提出SD{0-1}KP模型对问题进行求解。

当然，虽然D{0-1}KP模型存在明显不足，但却是当前唯一可以对{0-1}KP模型中对于“折扣”关系刻画的有效模型。故考虑针对D{0-1}KP模型设计新的编码方法，对原模型进行简化，构建模型的求解方法。

2 D{0-1}KP问题的简化数学模型

传统D{0-1}KP模型中由于将物品A和B的折扣关系假设为物品C，从而导致模型缺陷，故考虑在新数学模型中，通过设计新的编码方式，避免出现物品C的情况，克服原模型出现的缺陷。

2.1 两个物品折扣关系的新编码方式

对于物品A和B的折扣关系，在原有的D{0-1}KP模型中，通过虚构物品C来表示，得到3个选择项，通过一个三元组二进制向量X=[x1，x2，x3]∈{0，1}3来表示物品的选择情况。其中，分量xj（1≤j≤3）表示对应的项是否被装入背包中。在向量X的所有8种组合中，只有[0，0，0]、[1，0，0]、[0，1，0]和[0，0，1]是正常编码，分别表示全部不选、选择物品A、选择物品B和选择物品C，而其余4种组合均是非正常编码，在M个这个关系对应的编码中，其正常编码率极低，这导致用遗传算法求解时必须大量采用编码修复操作。

为提正常编码率，减少编码修复操作，就需要对物品折扣关系重新设计编码方式。在新的编码方式中并不将物品A和B同时选择的折扣关系虚构成一个物品，其定义如下。

根据定义2，在新的编码方式中，两个物品的折扣关系只需要一个二元组的二进制向量来表示，对应的四种编码组合全是正常编码，因而在求解模型时，不需要采用修复操作。

针对定义1中D{0-1}KP模型给出了折扣关系R中物品A和B对应的折扣重量系数，为了便于新编码方法的实施，需要给出折扣关系对应的折扣量d。

2.2 D{0-1}KP问题的简化模型

根据D{0-1}KP问题的描述，每个折扣关系中只包含两个物品，为采用定义2的新编码方式，我们需要利用定义3给出的折扣量计算方式，对定义1中的D{0-1}KP模型进行重新刻画，可得到折扣0-1背包问题的简化数学模型（记为：SD{0-1}KP）。

由定义2可知，通过采用SD{0-1}KP模型刻画问题，在求解过程中，个体编码始终保持为正常编码;因此，新模型中的编码个体不再需要使用修复操作，大大减少了问题的求解时长。同时，SD{0-1}KP模型的求解可采用此前不能使用的罚函数法、分离法、纯正法[21-22]等算法，使得SD{0-1}KP相对于D{0-1}KP在算法求解的选择上进行了大规模的延伸拓展。

3 用遗传算法求解SD{0-1}KP

遗传算法（Genetic Algorithm， GA）[20-29]是一种借鉴“适者生存”这一理念的迭代进化算法，由Holland教授于1975年提出。因该算法在函数约束条件上要求少、限值弱，且具备全局搜索能力[28-29]，因而在生产调度、图像处理、数值计算与优化等领域[24-29]应用广泛延伸拓展性强且算法相对成熟完善。Rudolph[23]通过对马尔可夫链讨论支出传统CGA（Canonical Genetic Algorithm）无法保证全局收敛的性质，而在引入杰出者保留策略后，能够实现EGA（Genetic Algorithm based on Elitist Reservation Strategy）在全局收敛性。为尽可能达到算法求解的精度，本文沿用杰出者保留策略遗传算法（EGA）对SD{0-1}KP求解。

遗传算法通过选择算子（SElection Operator， SEO）、交叉算子（CRossover Operator， CRO）和变异算子（MUtation Operator， MUO）三类基本算子实现种群择优、更替等功能。有关遗传算法的具体内容可参考文献[26-29]，此处限于篇幅不再赘述。

基于SD{0-1}KP模型，本文提出两种分别混合贪婪算法和罚函数法的遗传算法，记为第一遗传（FG）算法和第二遗传（SG）算法。因为两类算法在求解过程中始终保持个体编码正常，因而大大减少求解时长。

3.1 求解SD{0-1}KP第一遗传算法

对于遗传算法在交叉操作和变异操作时，往往导致个体编码所对应的重量不能有效利用完背包容量或超出背包容量，不能达到最优解，这使得遗传算法种群中较多个体不能有效投入使用，影响算法迭代收斂。在运用遗传算法对问题进行求解时，往往通过混合其他算子可以对问题进行加速算法收敛或者提升计算精度，通常有罚函数法、修复法、纯正法和分离法等[6-7]。对于不同情况，不同算法各有优势和劣势，但彼此互斥。本文采取贪婪算法和罚函数法对算法作出改进。

3.1.1 贪婪策略

贪婪算法（GREedy algorithm， GRE）[30-31]作为一种求解{0-1}KP的一种重要加速算子，因为其算法简单直接，对于KP适应度高[24]而受到广泛的使用。针对遗传算法，基于贪心策略提出一种优化编码个体的贪心修复与优化算法GRE。本文所针对的问题为单一目标，不考虑多目标情况，故而相对简单。

贪婪算法应用于背包问题，以非增序列的价值效率ei=pi/wi作为物品选取的优先级指标。对于SD{0-1}KP模型而言，虽然相对于D{0-1}KP模型，不将折扣关系作为独立个体在编码中进行体现，但在贪心加速的时候，仍然需要将任意折扣关系作为一个独立的个体进行价值效率的排序。

由定义4知，n个折扣关系对应的项（或物品）组合对应价值密度编号范围为2n+1～3n，与2n个单一项（或物品）的价值密度一起共有3n项。通过对ek（1≤k≤3n）排序，确定组合的优先选择顺序，并按照价值密度进行从高到低选择。

在GRE算法中，首先通过1）～3）步生成折扣关系的价值和重量向量，其时间复杂度为O（T），并利用4）步进行储存，然后利用5）～6）步按照价值密度对折扣选择进行排序，其时间复杂度为O（3n）。通过6）步生成选择矩阵。通过7）～17）步对个体未能有效利用的背包容量进行物品选择，其时间复杂度为O（3nK）。所以GRE的算法时间复杂度为O（n2）。

3.1.2 第一遗传算法

在FG中，首先利用第1）～3）步设定初始参数，利用4）步对初代个体进行贪心修复。在5）～14）步的循环过程中，通过6）步进行交叉操作、7）步进行变异操作。并通过8）～12）步在上一代的最优个体和新产生的群体进行最优值筛选，随后通过13）步进行选择操作产生下一代新的群体。最后15）步输出最优个体编码及其价值。不难得到FG的算法时间复杂度为O（n3）。

3.2 求解SD{0-1}KP第二遗传算法

求解D{0-1}KP，现有求解方法较多运用贪婪加速情况[5-6]。为突出SD{0-1}KP模型的广泛性，本文首次提出混合罚函数优化的遗传算法，记为第二遗传算法（SG）。

3.2.1 罚函数法

3.2.2 第二遗传算法

罚函数加速算法能够广泛应用于个体编码算法中，但需要保障个体编码尽可能为正常编码个体[32]。在传统D{0-1}KP模型中，n个项集规模的个体编码正常概率仅为（1/2）n，导致罚函数法求解D{0-1}KP误差不可接受。基于SD{0-1}KP，首次提出混合罚函数的遗传算法SG。

在PSEO中，首先利用1）步实现EGA过程。2）～3）步对个体编码进行折扣计算。4）步混合罚函数。5）～15）步进行轮盘赌操作，实现选择操作过程。最后利用16）步输出子代。类比于算法FG，不难得到PSEO的算法时间复杂度为O（n2）。因SG算法与FG仅在SEO和PSEO的选择操作过程略有不同，其余完全一样，此处限于篇幅对SG算法伪代码不再赘述。

4 实例计算与比较

在本章中，沿用文献[10]中所提出的四类D{0-1}KP实例数据，且每种数据各有规模依次等量递增的数据10种。关于数据的具体阐述可参考文献[10]。通过前述简易算法，将经过折扣后的整个折扣关系组合价值Wi（1≤i≤n）转化为折扣量di（1≤i≤n），因方法简单，限于文章篇幅不再赘述。将转化得到实例记为不相关SD{0-1}KP实例（Uncorrelated instances of SD{0-1}KP， SUDKP），弱相关SD{0-1}KP实例（Weakly correlated instances of SD{0-1}KP， SWDKP），强相关SD{0-1}KP实例（Strongly correlated instances of SD{0-1}KP， SSDKP）和逆向强相关SD{0-1}KP实例（Inverse Strongly correlated instances of SD{0-1}KP， SIDKP）。

由于本文所提出新算法FG和SG与文献[10]中FirEGA（First Elitist reservation strategy Genetic Algorithm）选择算法框架基本一致，通过GRE算法求解SD{0-1}KP的形式未发生改变，故而在遗传算法中的交叉算子pc和变异算子pm具体数值的设定对于问题的求解而言，沿用文献[10]中所求得参量，即pc=0.8，pm=0.01，同时设定种群规模为50。对于SG算法中惩罚因子的设定pe=2。

本文使用计算机基本配置为：Intel Core i7-8700 CPU @3.2GHz，8GB DDR4L，Microsoft Windows 10家庭版。利用Matlab 7.0进行问题进行求解，并将结果绘制成图。

4.1 FG和SG求解结果

通过运用FG和SG对上述所有数据进行计算，所得结果见表1。其中Opt为通过动态规划法（Dynamic Programming of Discounted Knapsack Problem， DPDKP）求解得到所给数据的实际最优解值，也即问题的理想最优解。此外，为了有效体现模型改进后的结果比对，引用文献[10]实验数据FirEGA。Best、Worst和Mean分别为FG和SG在30次独立计算中所得最优解、最差解及期望。本文考虑比较上述三种算法在求解SD{0-1}KP中的具体求解精度，为了更为明显地展示两种算法在算法精度方面的比较，通过计算近似比差率来作为分析数据结果主要参数。其中，1-Best/Opt、1-Mean/Opt、1-Worst/Opt為最优解近似差率、期望值近似差率和最差解近似差率。Time1、Time2、Time3分别表示FirEGA、FG和SG三类算法在求解实例时，30次重复独立计算的运行总时间（单位：秒）。

4.2 FG和SG求解精度及求解速度分析

表1数据表明：FirEGA求解SUDKP实例最优值近似比差异率在7.040%～12.610%，平均值和最差值的近似比差异率在8.090%～14.410%，为可接受范围内;FG求解SUDKP实例的最优值近似比差异率在0.604%～1.287%，平均值和最差值的近似比差异率在0.874%～2.193%。SG算法求解SUDKP实例最优值近似比差异率在0.604%～1.287%，平均值和最差值的近似比差异率在0.699%～2.243%。

FirEGA求解SWDKP实例的最优值近似比差异率在0.237%～0.928%，平均值的近似比差异率在0.671%～2.745%;FG算法求解SWDKP实例的最优值近似比差异率在0.044%～0.180%，平均值和最差值的近似比差异率在0.091%～0.363%;SG算法求解SWDKP实例的最优值、平均值和最差值的近似比差异率在0.044%～0.180%和0.093%～0.418%。

用FirEGA求解SSDKP1-SSDKP10实例的最优值近似比差异率在1.050%～2.559%，平均值和最差值的近似比差异率在1.162%～4.056%;FG算法求解SSDKP实例的最优值近似比差异率在0.244%～0.437%，平均值和最差值的近似比差异率在0.572%～1.420%;SG算法求解SSDKP实例的最优值近似比差异率在0.244%～0.437%，平均值和最差值的近似比差异率在0.440%～1.519%。

对于SIDKP1～SIDKP10共10类SD{0-1}KP实例求解，FirEGA算法的最优值近似比差异率在0.000%～0.508%，平均值的近似比差异率在0.040%～5.071%;FG算法求解SIDKP实例的最优值近似比差异率在0.000%～0.020%，平均值和最差值的近似比差异率在0.001%～0.083%;SG算法求解SIDKP实例的最优值近似比差异率在0.000%～0.020%，平均值和最差值的近似比差异率为0.001%～0.120%。

为了更加直观展示计算结果精度，将三种算法求解SUDKP等四类SD{0-1}KP实例的最优值和平均值近似比差异率以曲线图形式刻画出来，如图1～8。综合图1～8可知，FG算法与SG算法在最优值方面基本一致，个体实例所得略有不同，但相对于FirEGA算法而言，有显著性提升。

通过表1所得数据，不难发现，对于算例规模较小实例，三类算法计算时长较为接近，但随着算例规模的增长，FirEGA算法与FG、SG算法相比，计算时长太长。

由實验结果对比可得，SD{0-1}KP模型通过采用定义2中的编码方式，使同一项集中的个体在编码中不相互影响，减少求解过程中的修复操作，大大减少求解时长，同时对于求解精度有小幅度提升。

5 结语

本文通过改进D{0-1}KP中个体编码的表达方式，进而提出SD{0-1}KP模型。基于EGA算法、混合贪婪算法与罚函数法，提出FG和SG两类算法对SD{0-1}KP实例进行求解。数据结果综合表明：FG和SG对于SD{0-1}KP在求解精度、计算效率两方面有显著性提升。总体看来，通过SD{0-1}KP简化D{0-1}KP，减少约束条件，从而加速求解、提升求解精度是确实可行的一种方法。此外，通过SD{0-1}KP拓展了D{0-1}KP的加速求解方法，但是较多数据未能跳出贪心算法最优解，下一步不妨考虑通过其他方法对此类问题进行有效求解，如改进其他元启发式算法对SD{0-1}KP进行求解。同时，无论SD{0-1}KP还是D{0-1}KP，其模型与实际情况相比，条件假设过强，也可考虑削减模型假设方面条件，尤其是考虑尽可能削弱“项集”这一假设，使得模型更加贴合实际问题。

参考文献 （References）

[1] DANTZIG G B. Discrete-variable extremum problems [J]. Operations Research， 1957， 5（2）： 266-277.

[2] KELLERER H， PFERSCHY U， PISINGER D. Knapsack Problems [M]. Berlin： Springer， 2004： 1-445.

[3] KARP R M， MILLER R E， THATCHER J W. Reducibility among combinatorial problems [J]. Journal of Symbolic Logic， 2010， 40（4）： 618-619.

[4] MARTELLO S， TOTH P. Knapsack Problems： Algorithms and Computer Implementations [M]. New York： John Wiley & Sons， 1990： 13-102.

[5] 王熙照，贺毅朝.求解背包问题的演化算法[J].软件学报，2017，28（1）：1-16.（WANG X Z， HE Y C. Evolutionary algorithms for knapsack problems [J]. Journal of Software， 2017， 28（1）： 1-16.）

[6] 贺毅朝，王熙照，李文斌，等.求解随机时变背包问题的精确算法与进化算法[J].软件学报，2017，28（2）：185-202.（HE Y C， WANG X Z， LI W B， et al. Exact algorithms and evolutionary algorithms for randomized time-varying knapsack problem [J]. Journal of Software， 2017， 28（2）：185-202.）

[7] GUDER J. Discounted knapsack problems for pairs of items [D]. Diplomarbeit， University of Erlangen-Nrnberg

Erlangen： Friedrich-Alexander-Universitt Erlangen-Nürnberg， 2005.

[8] GULDAN B. Heuristic and exact algorithms for discounted knapsack problems [D]. Nuremberg： University of Erlangen-Nuremberg

Erlangen： Friedrich-Alexander-Universitt Erlangen-Nürnberg， 2007.

[9] RONG A. FIGUEIRA J R. KLAMROTH K. Dynamic programming based algorithms for the discounted {0-1} knapsack problem [J]. Applied Mathematics and Computation， 2012， 218（12）： 6921-6933.

[10] 贺毅朝，王熙照，李文斌，等.基于遗传算法求解折扣{0-1}背包问题的研究[J].计算机学报，2016，39（12）：2614-2630.（HE Y C， WANG X Z， LI W B， et al. Research on genetic algorithms for the discounted {0-1} knapsack problem [J]. Chinese Journal of Computers， 2016，39（12）：2614-2630.）

[11] HE Y-C， WANG X-Z， HE Y-L， et al. Exact and approximate algorithms for discounted {0-1} knapsack problem [J]. Information Sciences， 2016， 369： 634-647.

[12] FENG Y， WANG G-G， LI W， et al. Multi-strategy monarch butterfly optimization algorithm for discounted {0-1} knapsack problem [J]. Neural Computing and Applications， 2018， 30（10）：3019-3036.

[13] 馮艳红，杨娟，贺毅朝，等.差分进化帝王蝶优化算法求解折扣{0-1}背包问题[J].电子学报，2018，46（6）：1343-1350.（FENG Y H， YANG J， HE Y C， et al. Monarch butterfly optimization algorithm with differential evolution for the discounted {0-1} knapsack problem [J]. Acta Electronica Sinica， 2018， 46（6）： 1343-1350.）

[14] FENG Y， WANG G-G. Binary moth search algorithm for discounted {0-1} knapsack problem [J]. IEEE Access， 2018， 6（99）：10708-10719.

[15] 刘雪静，贺毅朝，路凤佳，等.基于Lévy飞行的差分乌鸦算法求解折扣{0-1}背包问题[J].计算机应用，2018，38（2）：433-442.（LIU X J， HE Y C， LU F J， et al. Differential crow search algorithm based on Lévy flight for solving discount {0-1} knapsack problem [J]. Journal of Computer Applications， 2018， 38（2）： 433-442.）

[16] 刘雪静，贺毅朝，路凤佳，等.基于差分演化策略的混沌乌鸦算法求解折扣{0-1}背包问题[J].计算机应用，2018，38（1）：137-145.（LIU X J， HE Y C， LU F J， et al. Chaotic crow search algorithm based on differential evolution strategy for solving discount {0-1} knapsack problem [J]. Journal of Computer Applications， 2018，38（1）：137-145.）

[17] 吴聪聪，贺毅朝，陈嶷瑛，等.变异蝙蝠算法求解折扣{0-1}背包问题[J].计算机应用，2017，37（5）：1292-1299.（WU C C， HE Y C， CHEN Y Y， et al. Mutated bat algorithm for solving discounted {0-1} knapsack problem[J]. Journal of Computer Applications， 2017， 37（5）： 1292-1299.）

[18] 刘雪静，贺毅朝，吴聪聪，等.基于细菌觅食算法求解折扣{0-1}背包问题的研究[J].计算机工程与应用，2018，54（2）：155-162.（LIU X J， HE Y C， WU C C， et al. Research on bacterial foraging optimization algorithm for discounted {0-1} knapsack problem [J]. Computer Engineering and Applications， 2018， 54（2）： 155-162.）

[19] 杨洋，潘大志，贺毅朝.改进修复策略遗传算法求解折扣{0-1}背包问题 [J/OL].计算机工程与应用，2018 [2018-07-30].http：//kns.cnki.net/ kcms/detail/11.2127.TP.20180319.1806.006.html.

（YANG Y， PAN D Z， HE Y C. Improved repair strategy genetic algorithm solve discount {0-1} knapsack problem [J]. Computer Engineering and Applications， 2018 [2018-07-30]. http：//kns.cnki.net/kcms/detail/11.2127.TP.20180319.1806.006.html.）

[20] MICHALEWICZ Z， SCHOENAUER M. Evolutionary algorithms for constrained parameter optimization problems [J]. Evolutionary Computation， 1996， 4（1）：1-32.

[21] RUNARSSON T P， YAO X. Stochastic ranking for constrained evolutionary optimization [J]. IEEE Transactions on Evolutionary Computation， 2000， 4（3）： 284-294.

[22] COELLO C A. Theoretical and numerical constraint-handling techniques used with evolutionary algorithm： a survey of the state of art [J]. Computer Methods in Applied Mechanics and Engineering， 2002， 191（11/12）： 1245-1287.

[23] RUDOLPH G. Convergence analysis of canonical genetic algorithms [J]. IEEE Transactions on Neural Networks， 1994， 5（1）： 96-101.

[24] GOLDBERG D E. Genetic algorithms in search [J]. Optimization and Machine Learning， 1989， 13（7）： 2104-2116.

[25] Sampson J R. Adaptation in Natural and Artificial Systems （John H. Holland）[J]. SIAM Review， 1976， 18（3）：53.

HOLLAND J H. Adaptation in Natural and Artificial Systems [M]. Cambridge， MA： MIT Press， 1992： 1-13.

[26] SCHMITT L M. Theory of genetic algorithms [J]. Amsterdam， Netherlands. Elsevier Science Publishers Ltd. 2001： 1-13.

SCHMITT L M. Theory of genetic algorithms [J]. Theoretical Computer Science， 2001， 259（1/2）： 1-61.

[27] SIVANANDAM S N， DEEPA S N. Introduction to Genetic Algorithms [M]. Berlin： Springer， 2008： 1-19.

[28] 陳国良，王熙法，庄镇泉，等.遗传算法及其应用[M].北京：人民邮电出版社，1999：1-25.（CHEN G L， WANG X F， ZHUANG Z Q， et al. Genetic Algorithm and Its Application [M]. Beijing： Posts & Telecom Press， 1999： 1-25.）

[29] 刘勇.非数值并行算法.第二册，遗传算法[M]. 北京：科学出版社，1995：36-45.（LIU Y. Non-numerical Parallel Algorithm. Book 2， Genetic Algorithm [M]. Beijing： Science Press， 1995： 36-45.）

[30] PIRKUL H. A heuristic solution procedure for the multiconstraint zero-one knapsack problem [J]. Naval Research Logistics， 1987， 34（2）： 161-172.

[31] LV J， WANG X， HUANG M， et al. Solving 0-1 knapsack problem by greedy degree and expectation efficiency [J]. Applied Soft Computing， 2016， 41（C）：94-103.

[32] TESSEMA B， YEN G G. An adaptive penalty formulation for constrained evolutionary optimization [J]. IEEE Transactions on Systems， Man and Cybernetics—Part A： Systems and Humans， 2009， 39（3）： 565-578.