计  算  机  学  报  2018 年 Abstract  Knapsack  problem  with  a  single  continuous  variable  (KPC)  is  a  new  extension  of  the  standard  0-1 knapsack problem. It is not only an NP-complete problem in computer sciences, but also a novel combinatorial optimization problem with continuous variable S in practical applications.   Because of the range of continuous variable  S  is  a  closed  interval  of  real  numbers,  KPC  is  more  difficult  to  solve  than  the  standard  0-1  knapsack problem.  In  order  to  solve  KPC  problem  quickly  and  efficiently,  this  paper  presents  a  new  idea  of  using evolutionary  algorithm  to  solve  KPC  problem,  and  proposes  two  effective  methods  for  solving  KPC  problem based on discrete differential evolutionary algorithm.  In  the paper, the general principle of standard differential evolution  algorithm  is  firstly  introduced.  The  discretization  method  in  the  binary  differential  evolution  with hybrid  encoding  (HBDE)  is  introduced  based  on  an  encoding  transforming  function,  and  the  pseudo-code  of HBDE is described in more detail. Moreover, the computational complexity of the original mathematical model KPCM1  of  KPC  problem  is  analyzed  by  using  a  scaling  technique.  Secondly,  On  the  basis  of  eliminating  the continuous  variable  S  in  the  mathematical  model  KPCM1  by  dimension  reduction  method,  a  new  discrete mathematical  model  KPCM2  of  KPC  problem  is  established,  which  is  suitable  to  solve  by  using  binary evolutionary  algorithms.  Moreover,  an  effective  algorithm  M2-GROA  for  handling  the  infeasible  solutions  of KPC  problem  is  given,  which  used  a  special  greedy  repair  and  optimization  strategy.  The  first  discrete evolutionary algorithm for solving  KPC problem, named S-HBDE,  is proposed based on the single-population HBDE  and  M2-GROA.  The  pseudo-code  of  S-HBDE  is  described  in  more  detail,  and  the  algorithm  time complexity of S-HBDE is analyzed. Thirdly, by dividing the range of the continuous variable S into two closed intervals of real numbers, the KPC is decomposed into two sub-problems established in two different intervals respectively. And the second discrete mathematical model KPCM3 of KPC is established by using the dimension reduction  method,  which  is  consist  of  two  sub-models  KPCM3.1  and  KPCM3.2  and  is  suitable  for  parallel solving by binary evolutionary algorithms. At the same time, by using the greedy repair and optimization strategy, two  effective  algorithms  M3.1-GROA  and  M3.2-GROA  for  dealing  with  the  infeasible  solutions  of  KPCM3.1 and  KPCM3.2  is  proposed,  respectively.  Combining  with  KPCM3.1  and  KPCM3.2,  the  second  discrete evolutionary algorithm B-HBDE for solving KPC problem is proposed based on the bi-population HBDE. The pseudo-code of B-HBDE is described in more detail, and the algorithm time complexity of B-HBDE is analyzed. Finally, the four kinds of large-scale KPC instances are first generated by using the existing generation method. For  validating  the  performance  of  S-HBDE  and  B-HBDE,  they  are  used  to  solve  the  four  kinds  of  large-scale KPC instances respectively, and their average calculation results, average time-consuming and stability compare with  that  of  approximate  algorithm  AP-KPC,  genetic  algorithm  and  discrete  particle  swarm  optimization algorithm. The comparison results show that S-HBDE and B-HBDE are superior to the other three algorithms in solving accuracy and stability, and have very fast computing speed. So it is very suitable for solving large-scale KPC instances quickly and efficiently in practical applications. Key words  knapsack  problem  with  a  single  continuous  variable;  discrete  differential  evolution;  genetic algorithm;  particle  swarm  optimization;  dimension   reduction  method;  repair  and  optimization method  1 引言 具有单连续变量的背包问题(knapsack  problem with  a  single  continuous  variable,  KPC)[1]是标准 0-1背包问题(0-1  knapsack  problem,0-1KP)的一个自然扩展形式,  它是由 Marchand 和 Wolsey 于 1999 年提出的一个带有连续变量的新颖组合优化问题.  KPC的一般描述为：给定 n 个物品的集合 N={1,2,…,n}和一个基本载重为 C 的背包，其中物品 j∈N 具有价值 pj和重量 wj，背包的可变载重 S 是在区间[l,u]上连续变化的一个变量，pj，wj和 C 为正有理数，S,  l 和 u 为有理数,  且 l<0<u.  给定一个正常数 c 作为惩罚系数，确定在 S 取何值以及此时如何选择物品装入背包,  使得装入物品的重量之和在不超过背包载重 C+S 的前提下价值之和减去 c S 最大. KPC 的基本数学模型[1,2](记为 KPCM1)为： 计算机学报 贺毅朝  等：基于离散差分演化的 KPC 问题降维建模与求解  3 SXfpc Sxnjjjå-==1),(max            (1) s.t.   SCwxnjjjå+£=1              (2) xj∈{0,1},   j=1,2,…,n,   S∈[l, u]          (3) 其中，X=[x1,x2,…,xn]∈{0,1}n，xj=1(j=1,2,„,n)当且仅当物品 j 被装入了背包.  在 KPC 中,  背包载重不再固定不变，而是由变量 S 进行连续调整,  当 S>0时背包载重增加，当 S<0 时背包载重减少;  同时，目标函数也不只是装入背包物品的价值之和，而是要加上了一个关于 S 的增量(-c S)。由于 0-1KP 是KPC 在 S=0 时的特例，因此 KPC 也是一个 NP 完全问题，不存在多项式时间精确算法. Lin[2]等人利用变量代换将 KPC 转化为一个伪背 包 问 题 (pseudo-knapsack  problem,PKP) 和 标 准0-1KP 的 组 合 形 式 ,  并分 别 调 用 COMBO[3]和EXPKNAP[4]进行求解，提出了求解 KPC 的一个精确算法.  由于要对 PKP  进行可行性检查且涉及到动态规划法，故而该算法的时间复杂度较高. Buther 和 Briskorn[5]将 KPC 的物品集划分为三个子集,  并根据启发式策略以及对变量的上下界变形,  提出了将 KPC 转化为标准 0-1 KP 形式求解的方法；该方法只能求出 KPC 的一个近似结果,  而且时间复杂度较高.  Zhao 和 Li[6]将单连续变量 S 的取值区间划分为两部分,  从而将 KPC 分解为两个具有标准0-1KP 形式的子问题，进而提出了一个时间复杂度为 O(n2) 的 2- 近似算法 ( 记为 AP-KPC).  然而 , AP-KPC 的近似比较大,计算结果不能令人满意.  贺毅朝[7]等人利用放缩法首先对 KPC 进行等价变换, 然后基于动态规划法提出了求解 KPC 的一个精确算法 DP-KPC.  与其它精确算法一样, DP-KPC 也存在时间复杂度较高的缺点。由于 KPC 是一个 NP 完全问题，其精确算法至少具有伪多项式时间复杂度，难以实现对大规模 KPC 实例的快速求解；已有的非精确算法(如 AP-KPC)虽然求解速度快，但是求得解的精度欠佳，不足以满足实际应用的要求. 由此,  设计 KPC 的求解速度快且求解精度高的非精确算法是一个值得探讨的问题. 演化算法(evolutionary algorithms,EAs)[8-16]是一类群体智能算法,  其本质是一种随机近似算法，具有不需要计算目标函数的导数与梯度、不要求目标函数具有连续性的优点,  并且具有内在隐含并行性和 极 强 的 全 局 寻 优 能 力 ,  已 被 成 功 用 于 求 解0-1KP、随机时变背包问题(RTVKP),  多维背包问题(MDKP)、二次背包问题(QKP)、集合联盟背包问题(SUKP)、折扣{0-1}背包问题(D{0-1}KP)、经济调度问题(EDP)、集合覆盖问题(SCP)、设施定位问题(FLP)、旅行商问题(TSP)、流水车间调度问题(FSSP) 和 可 满 足 性 问 题 (SAT)[17-30]等 组 合 优 化 问 题(combinatorial  optimization  problems,  COPs).  正是由于 EAs 在 COPs 中的成功应用，激发了人们对它的研究兴趣.  一方面,  为了高效求解各种 COPs,  人们不断尝试应用各种理论构造新的优秀演化算法；另一方面，为了拓展已有 EAs 的应用范畴，人们不断探索利用已有 EAs 求解 COPs 的新方法.  本文利用差分演化(differential evolution, DE)[12,31]探索求解KPC 的新方法,  在利用降维法建立了 KPC 的两个适于离散 EAs 求解的数学模型基础上,基于混合编码二进制差分演化算法(HBDE)[32]给出了快速求解KPC 的两个高效离散演化算法. 本文其余内容组织如下：在第 2 节介绍了 DE与 HBDE 的原理,  并给出了 HBDE 的伪代码描述. 在第 3 节中,  分析了 KPCM1 的解空间规模及其对求解算法的影响.  在第 4 节基于降维法建立了 KPC的离散数学模型 KPCM2,  给出了处理不可行解的有效算法 M2-GROA,  将其与单种群 HBDE 相结合提出了求解 KPC 的第一个离散演化算法 S-HBDE. 在第 5 节中,  基于分解与降维法建立了 KPC 的离散数学模型 KPCM3,  给出了处理不可行解的有效算法 M3.1-GROA 和 M3.2-GROA,  并与双种群 HBDE相结合提出了求解 KPC 的第二个离散演化算法B-HBDE.  在第 6 节，首先给出了四类大规模 KPC实例与算法的参数设置，然后利用 S-HBDE 和B-HBDE 分别求解四类大规模 KPC 实例,  通过与近似算法 AP-KPC[6]、遗传算法(GA)[33]和离散粒子群优化算法(BPSO)[34]的计算结果比较指出:  S-HBDE和 B-HBDE 不仅求解速度快，而且比其它三个算法的计算精度更佳，非常适于快速高效求解实际应用中的大规模 KPC 实例.  最后,  总结全文并展望今后进一步的研究思路. 2 差分演化与离散差分演化 2.1   差分演化 差分演化(differential evolution, DE)[12,31]是一个具有极强全局搜索能力的演化算法，因其在第一届IEEE 演化大赛中的超群表现引起了国内外学者的极大关注,已被广泛应用于求解众多领域中的数值计算机学报 计  算  机  学  报  2018 年 优化问题[31,35-38].  为了介绍 HBDE 的需要,下面首先基于 DE/rand /1/bin 模式简述 DE 的算法原理. 不失一般性，设 max  f(Y),  Y=[y1,y2,…,yn]∈Ω, 是一个数值优化问题,  Õ==WnjjjUL1],[是其解空间, 其中 Lj<Uj且为实数. 在 DE 中，一次迭代进化是由变异操作、交叉操作和选择操作共同完成的，它们的实现方法如下:    1)  变异操作:  设 Yi=[yi1,yi2,…,yin]是当前种群 P中的第i个个体, Y1=[y11,y12,…,y1n], Y2=[y21,y22,…,y2n]和 Y3=  [y31,y32,…,y3n]  是 P 中不同于 Yi的任意三个不同个体,  则 DE 基于 DE/rand /1/bin 模式进行变异操作的公式为： zij= y1j+F*(y2j-y3j)            (4) 其中，Zi=[zi1,zi2,…,zin]是变异操作产生的临时个体, zij∈[Lj,Uj], j=1,2,„,n；F 为缩放因子且 F∈(0,1).   2)  交叉操作:  对于给定的概率值 CR，DE 利用(5)式对 Zi与 Yi进行交叉操作，产生对应于 Yi的中间个体仍记为 Zi=[zi1,zi2,…,zin]. , ( );, .ijijijz r CR j R izyì< =ï= íïî如果 或否则       (5) 其中，CR∈(0,1)称为交叉因子(或交叉概率)，r~(0,1)是一个随机数, R(i)是[1, n]上的一个随机正整数. 3)  选择操作:  当 P 中每一个体 Yi均产生中间个体 Zi之后,  DE 利用(6)式从 Yi和 Zi中选择适应度最大的作为新一代种群中的第 i 个个体(仍记为 Yi). , ( ) ( );, .i i iiiZ f Z f YYYì>= íî如果否则         (6)     DE 通过反复执行 1) ~3)实现进化,直到满足终止条件为止.  最后,输出当前种群中适应度最大个体对应的可行解,  即为 DE 求得 max f(Y)的最好结果. 2.2   离散差分演化 在 DE 中,  由于变异操作是实数运算,  不适合直接用于求解 COPs.  为了能够利用 DE 求解COPs(例如 0-1KP,  RTVKP 和 D{0-1}KP 等)，文献[32]基于编码转换机制提出了一个离散差分演化算法:具有混合编码的二进制差分演化算法 HBDE. HBDE 在保持 DE 原有进化模式和寻优特性的基础上，利用满射将实数编码转换为 0-1 编码,  非常适于求解以 0-1 向量为可行解的 COPs[27,32,39,40].  下面对于COPs问题П: max f(X), X=[x1,x2,…,xn]∈{0,1}n,  基于 DE/rand/1/bin 进化模式给出 HBDE的算法原理[32,39]和伪代码描述. 记 Yi=[yi1,yi2,…,yin]为 HBDE 的当前种群 P 中第i 个个体,  并限定 yij∈[-A,A], j=1,2,„,n, n 是问题 П的维数, A 是一个给定的正实数, i=1,2,…, N，N 为种群规模.  记 Xi=[xi1,xi2,…,xin]∈{0,1}n为个体 Yi按照(7)式求得问题  П 的可行解(或潜在解). 1, 0;0, .ijijyxìï³= íïî如果否则          (7) 在 HBDE 的一次迭代进化中,  对于 P 中每一个体 Yi (1≤i≤N)，首先利用(4)式进行变异操作，利用 (5) 式 进 行 交 叉 操 作 , 得 到 中 间 个 体Zi=[zi1,zi2,…,zin],  zij∈[-A,A],  j=1,2,„,n.  然后,  利用(8)式求得 Zi对应问题  П 的可行解 Ui=[ui1,ui2,…,uin]∈{0,1}n，并利用(9)式选择 Yi和 Zi中适应度最佳的替换个体 Yi.  重复这一过程，直到 P 中所有个体均完成以上操作为止. 1, 0;0, .ijijzuìï³= íïî如果否则          (8) , ( ) ( );, .i i iiiZ f U f XYYì>= íî如果否则       (9) 令Xb=[xb1,xb2,…,xbn]∈{0,1}n为种群P中个体对应的最好解，MIT 为 HBDE 的迭代次数,  则 HBDE的伪代码描述如下: 算法 1.   HBDE[32,39]   输入:  问题 П 的实例,  参数 A, N,CR, F 和 MIT. 输出: П 的实例的近似解(或最优解)Xb与 f(Xb). 1  随机产生初始种群   P={Yi=[yi1,…,yin]|yij∈[-A, A], 1≤i≤N, 1≤j≤n}; 2  利用(7)式计算 Yi(1≤i≤N)对应的可行解 Xi,并根据 f(Xi)确定 P 中最好解 Xb; 3   FOR   t ←1 TO MIT    DO 4     FOR   i←1 TO N   DO 5       FOR    j←1 TO n   DO 6          IF (r<CR∨j=R(i))   THEN zij←yp1,j+F*(yp2,j - yp3,j); 7          ELSE   zij←yij; 8          IF zij≥0 THEN uij←1 ELSE uij←0； 9       END FOR 10      IF f(Ui)>f(Xi) THEN Yi←Zi; Xi←Ui; 11   END FOR 12   根据 f(Xi) (1≤i≤N)确定 P 中最好解 Xb; 13 END FOR 计算机学报———————— 本课题得到国家自然科学基金(No.71371063，No.11471097)、河北省高等学校科学研究计划项目(No.ZD2016005)和河北省自然科学基金项目(No.F2016403055)资助. 贺毅朝，男，1969 年生，硕士，教授，计算机学会(CCF)会员(15468S),主要研究领域为演化算法及其应用、计算复杂性和群测试理论，E-mail:heyichao119@163.com，Tel:13623115445. 王熙照，男，1963 年生，博士，教授，IEEE Fellow,主要研究领域为机器学习、进化计算和大数据分析，E-mail:xizhaowang@ieeee.org. 张新禄，男，1968 年生，硕士，副教授，主要研究领域为智能计算和群测试理论，E-mail:xinluzhang@163.com.李焕哲，男，1975 年生，博士，副教授，主要研究领域为演化算法与机器学习，E-mail:lihuanzhe@hgu.edu.cn.  基于离散差分演化的 KPC 问题降维建模与求解*  贺毅朝 1)   王熙照 2)    张新禄 3)   李焕哲 1)  1)(  河北地质大学  信息工程学院,  石家庄  050031) 2)(  深圳大学  计算机与软件学院,  广东  深圳  518060) 3)(  河北师范大学  数学与信息科学学院,  石家庄  050024)  摘  要  具有单连续变量的背包问题(Knapsack Problem with a single Continuous variable, KPC)是标准 0-1 背包问题的一个新颖扩展形式,  它既是一个 NP 完全问题,  又是一个带有连续变量 S 的新颖组合优化问题,  求解难度非常大.  为了快速高效地求解 KPC 问题,  本文提出了利用演化算法求解 KPC 的新思路，并给出了基于离散差分演化算法求解 KPC 的两个有效方法.  首先,  介绍了基本差分演化算法和具有混合编码的二进制差分演化算法(HBDE)的原理，给出了 HBDE 的算法伪代码描述，并分析了 KPC 的基本数学模型 KPCM1 的计算复杂度.  然后，在基于降维法消除 KPCM1 中连续变量 S 的基础上，建立了 KPC的一个新离散数学模型 KPCM2；随后在基于贪心策略提出处理不可行解的有效算法基础上,  基于单种群 HBDE 给出了求解KPC 的第一个离散演化算法 S-HBDE.  第三,  通过把连续变量 S 的取值范围划分为两个子区间将 KPC 分解为两个子问题，并基于降维法建立了 KPC 的适于并行求解的第二个数学模型 KPCM3；在利用贪心策略给出处理子问题不可行解的两个有效算法基础上,  基于双种群 HBDE 提出了求解 KPC 的第二个离散演化算法 B-HBDE.  最后,  在给出四类大规模 KPC 实例的基础上，利用 S-HBDE 和 B-HBDE 分别求解这些实例,  并与近似算法 AP-KPC、遗传算法和离散粒子群优化算法的计算结果、耗费时间和稳定性等指标进行比较，比较结果表明  S-HBDE 和 B-HBDE 不仅在求解精度和稳定性方面均优于其它三个算法，而且求解速度很快，非常适于在实际应用中快速高效地求解大规模 KPC 实例. 关键词:  具有单连续变量背包问题;  离散差分演化;  遗传算法;  粒子群优化;  降维法;  修复与优化法 中图法分类号  TP301      Modeling and Solving by Dimensionality Reduction of KPC Problem Based on Discrete Differential Evolution* HE Yi-Chao1)   WANG Xi-Zhao2)   ZHANG Xin-Lu3)   LI Huan-Zhe1) 1)( College of Information and Engineering, Shijiazhuang Hebei GEO University, Shijiazhuang 050031)    2)( College of Computer Science and Software Engineering, Shenzhen University, Shenzhen Guangdong518060) 3)( College of Mathematics and Information Science, Hebei Normal University, Shijiazhuang 050024)  计算机学报 贺毅朝  等：基于离散差分演化的 KPC 问题降维建模与求解  5 14 RETURN(Xb, f(Xb)). 在 HBDE 中, Yp1,Yp2和 Yp3是不同于 Yi且互不相同的三个个体.  令 O(f)表示计算 f(Xi)的时间复杂度. 则 HBDE 的 时 间 复 杂 度 为 O(N*n)+N*O(f) +MIT*N*(O(n)+O(f)).  注意到 N 和 MIT 是 n 的常数倍，O(f)是关于 n 的多项式,  所以  HBDE 是一个具有多项式时间复杂度的随机近似算法. 3   KPCM1 解空间的规模 在模型 KPCM1 中，KPC 的可行解可视为有序对<X,S>，其中 X=[x1,x2,…,xn]∈{0,1}n是一个 n 维0-1 向量，S∈[l,u]是一个有理数。因此,  KPC 的解空间SAPCE={0,1}n×[l,u]是一个n+1维卡氏积[7,41].  虽然 KPCM1 中  [l,u]是有理数构成的一个无限可数集,  但是根据 KPC 的特性不难计算出 SAPCE的基数,  从而确定 KPCM1 的解空间规模. 令 K=min{k|k∈Z+∧kwj∈Z∧k C∈Z+},  其中Z+是正整数集,  则有 xCKSKCKwx Swnjjjnjjjåå+£Û+£==)(11.            由于 xj, Kwj (1≤j≤n)和 KC 均为正整数,  从而必然有ååë û==+£Û+£njjjnjjjCKwxSKSKCKwx KK11)()(       其中 ëaû 为底函数,  表示不超过 a 的正整数.  于是, KPCM1 中的(2)式等价于下面的(10)式: ëKSKCKwxtsûnjjjå+£=)(..1.     (10) 注意到 ë lû ë Sû ££ëKu KKû,  则 ëKSû 的取值依次为ëKlû, ëKlû+1,  ëKlû+2 ,…, ëKuû,令 ë uû ëKl Kmû +-=1, 于是 SAPCE 实质上是一个基数为 m2n的 n+1 维卡氏积{0,1}n×{êëklúû,êëKlúû+1,..,êëKuúû}，即 KPCM1的解空间规模为 m2n,  ë uû ëKl Kmû +-=1. 如果利用 EAs 基于 KPCM1 模型求解 KPC，采用混合编码形式表示个体是一种容易想到的方法, 但是针对此编码方法如何高效实施 EAs 的进化操作却是一个有待探讨的问题.  此外,  在利用 EAs 求解 COPs 时，解空间越大 EAs 需要搜索的范围就越大,  越不利于问题的求解.  为此本文另辟蹊径，首先基于降维法建立 KPC 的适于 EAs 求解的离散数学模型，然后利用 HBDE 给出求解 KPC 的两个高效算法.  4 利用单种群 HBDE 求解 KPC 在本节中，首先基于降维法建立 KPC 的离散数学模型 KPCM2，然后利用贪心策略提出一个处理 KPC 不可行解的有效算法 M2-GROA,  最后将单种群 HBDE 与 M2-GROA 相结合给出求解 KPC 的第一个离散演化算法 S-HBDE. 不妨记 å==njjjWwx X1)( ,其中 X=[x1,x2,…,  xn]∈{0,1}n是一个 n 维 0-1 向量. (a)  当 W(X)<C+l 时 .  对任意 S∈ [l,u]  均有W(X)<C+S，故 X 是 KPC 的一个可行解，并且满足 åå==-+£-+=njjjnjjjXx Sfclcpx Sp11)()(),( . 所以有 å=-+=njjjXlcpx Sf1)(),(max . (b)  当 C+l≤W(X)≤C+u 时.  不妨设 S0=W(X)-C，则-u≤-S0≤-l.  对任意 S∈[S0, u]  均有 W(X)≤C+S，故X 是 KPC 的一个可行解，并且满足 )(),(1XScpx Sfnjjjå-+== å=+£njjjScpx10)-( å=-+=njjjXWCcpx1))(( ， 所以有( )å å= =-+=njnjjjjjXx Sfcwx Cp1 1),(max . 注意到 ( ))()(01cx Cclc Swnjjjå-£-=-=，于是根据(a)和(b)的分析易知:  通过消去连续变量 S 使解空间的维数由 n+1 降低为 n,  可以如下建立 KPC 的一个类似于 0-1KP 的离散数学模型 KPCM2： å( ){ å}= =--+=njnjjjjjfcpx Xcwx Cl1 11),(min)(max  (11) s.t      wu Cxnjjjå+£=1         (12) xj∈{0,1},   j=1,2,…,n           (13) 其中,  X=[x1,x2,…,xn]∈{0,1}n,  xj=1(j=1,2,..,n)当且仅当物品 j 被装入了背包中. 显然,  模型 KPCM2 的解空间 SAPCE={0,1}n，计算机学报 计  算  机  学  报  2018 年 其基数 2n<m2n.  在利用 EAs 基于模型 KPCM2 求解KPC 时，由于不涉及变量 S，大大降低了求解难度. 此外,  当求得可行解 X=[x1,…,xn]∈{0,1}n以后,  变量 S 可根据等式11[ ( )] /nj jjS x p f X c== å- 确定. 在基于模型 KPCM2 求解 KPC 时,存在  n 维 0-1向量 X=[x1,x2…,xn]∈{0,1}n是 KPC 的不可行解的情况.  不可行解的存在既影响算法求解效率,  还不能直接利用目标函数值对个体进行评价.  为此,  借鉴求解 KP 问题时处理不可行解的成功经验[18,24,39,40]，基于“价值密度比大而且能够使目标函数值增大的物品优先装入”的贪心策略，给出一个将不可行解修复为可行解、同时还能够对可行解做进一步优化的算法 M2-GROA. 在M2-GROA中，当输入X=[x1,x2,…,xn]∈{0,1}n是一个不可行解时,反复将背包中价值密度最小的物品从中取出，直到 X 成为一个可行解为止；当 X是可行解时，则反复对还没有装入背包、且具有最大价值密度、并能够使目标函数值增大的物品进行尝试装入，如果能被装入背包则装入之，否则放弃它继续尝试其它还未装入的物品,直到所有未被装入的物品均被尝试为止. 将 n 个物品的下标按照价值密度 pj/wj由大到小的 次 序 依 次 存 入 数 组 H[1…n] 中 ,  即 H 满 足[ 1 ]][][]2[]2[]1[HH. .HHnn HH³³³wpwpwp . 令 Y=[y1,y2,…,yn]∈{0,1}n是一个临时向量，X=[x1,x2,…,xn]∈{0,1}n是 KPC 的一个潜在解，则 M2-GROA 的算法伪代码描述如下： 算法 2.    M2-GROA 输入:潜在解 X=[x1, x2,…,xn]和 H[1…n];  输出:可行解 X=[x1, x2,…,xn]和  f1(X). 1   j←n;   2   WHILE W(X)>C+u   DO 3      IF xH[j]=1 THEN xH[j]←0; 4      j←j-1; 5   END WHILE 6   FOR   j←1 TO n   DO 7      IF (xH[j]=0∧W(X) +wH[j]≤C+u ) THEN 8         Y←X;   yH[j]←1;  9         IF   f1(Y)> f1(X)   THEN   xH[j]←1;   10     END IF 11   END FOR 12   RETURN(X, f1(X)) 在算法 2 中，Step2-5 将一个不可行解修复为可行解, Step6-11 对可行解进行优化处理, Step12 输出优化后的可行解 X 与其函数值 f1(X).  易知,  算法 2的时间复杂度是 O(n2). 在求解 KPC 时，利用 M2-GROA 对 HBDE 中每一个体对应的潜在解进行修复与优化处理，利用所得可行解的目标函数值作为该个体的适应度对其进行评价,  这样既可消除不可行解，又能对个体进行优劣评价.  由于基于模型 KPCM2 求解 KPC 时HBDE 仅有一个种群,  为了区别后面的算法，我们将在模型 KPCM2 下求解 KPC 的单种群 HBDE 记为 S-HBDE,  其算法伪代码描述如下： 算法 3.   S-HBDE   输入: KPC 实例 П,  参数 A, N, CR, F 和 MIT. 输出: П 的近似解(或最优解)Xb与 f1(Xb). 1 按照 pj/wj(1≤j≤n)由大到小的顺序依次将 n 个物品的下标存入数组 H[1…n]中; 2  随机产生初始种群   P={Yi=[yi1,yi2,…,yin]|yij ∈[-A,A] ,1≤i≤N, 1≤j≤n }; 3   FOR   i←1 TO N   DO 4       利用(7)式计算 Yi对应的潜在解 Xi ; 5       (Xi, f1(Xi)) ←M2-GROA(Xi, H[1…n]); 6   END FOR 7   根据 f1(Xi) (1≤i≤N)确定  P 中最好解 Xb; 8   FOR t ←1 TO MIT   DO 9     FOR i←1 TO N   DO 10       FOR    j←1 TO n   DO 11           IF (r<CR∨j=R(i)) THEN  12                 zij←yp1,j+F*(yp2,j - yp3,j) 13           ELSE   zij←yij; 14           IFzij≥0 THEN uij←1ELSE uij←0； 15        END FOR 16        (Ui,f1(Ui)) ←M2-GROA(Ui,H[1…n]); 17        IF f1(Ui)>f1(Xi) THEN Yi←Zi, Xi←Ui ; 18     END FOR 19     根据 f1(Xi) (1≤i≤N)确定 P 中最好解 Xb; 20   END FOR 21   RETURN(Xb, f1(Xb)). 在 S-HBDE 中，Step1 由快速排序算法[42]实现，其时间复杂度为 O(nlogn);  Step2 的时间复杂度为O(n*N),  Step3~Step6 的时间复杂度 为 O(n2*N), Step7 的时间复杂度为 O(N), Step8~Step20 的时间复杂度为 O(MIT* n2*N),  因此 S-HBDE 的时间复杂度为 O(nlogn)+O(n*N)+O(n2*N)+O(N)+O(MIT*n2*N) 计算机学报 贺毅朝  等：基于离散差分演化的 KPC 问题降维建模与求解  7 = O(MIT* n2*N). 5 利用双种群 HBDE 求解 KPC  如果将单连续变量 S 的取值区间[l, u]划分为两个子区间[l,0]和[0,u]，则 KPC 可分解为下面两个子问题.  记 OPT1 为子问题 1 的最优值,  OPT2 为子问题 2 的 最 优 值 ， 则 KPC 的 最 优 值 为 OPT= max{OPT1, OPT2}. KPC 子问题 1: SXfpc Sxnjjjå-==1),(max    s.t.   SCwxnjjjå+£=1 xj∈{0,1}, j=1,2,…,n, S∈[l, 0]. KPC 子问题 2: SXfpc Sxnjjjå-==1),(max   s.t.   SCwxnjjjå+£=1  xj∈{0,1}, j =1,2,…,n, S∈[0, u]. 类似于第 4 节中的分析，基于降维法如下建立KPC 子问题 1 的一个类似于 0-1KP 的离散数学模型KPCM3.1,  建立 KPC 子问题 2 的一个类似于 0-1KP的离散数学模型 KPCM3.2: KPCM3.1： ( ){ }åå==--+=njjjnjjjgcpx Xcxw Cl111),(min)(max  (14) s.t.   Cwxnjjjå£=1          (15) xj∈{0,1}，j=1,2,…,n .            (16) KPCM3.2： ( åå){ }==-+=njjjnjjjgx Xcxw Cp112,0min)(max (17) s.t   wu Cxnjjjå+£=1          (18) xj∈{0,1},   j=1,2,…,n .          (19) 显然，KPC 的最优值为 max{max  g1(X),  max g2(X)}，因此 KPCM3.1 与 KPCM3.2 构成了 KPC 的一个新的离散数学模型,记为 KPCM3.易知 KPCM3的解空间 SAPCE={0,1}n,  其基数 2n<m2n,  而且也不涉及连续变量 S,  因此非常适用于 EAs 求解. 下面根据 KPCM3 由 KPCM3.1 与 KPCM3.2 两个子问题构成的事实,  基于双种群 HBDE 提出一个求解 KPC 的离散演化算法(简记 B-HBDE).在B-HBDE 中,存在两个同等规模的种群 P1和 P2,  其中 P1用于对 KPCM3.1 的求解, P2用于对 KPCM3.2的求解.  于是, B-HBDE 通过并行计算 KPCM3.1 和KPCM3.2 实现对 KPC 的求解. 在利用 B-HBDE 求解 KPCM3.1 和 KPCM3.2时,  也会出现个体对应的潜在解是不可行解的情况.  为此,  基于前述贪心策略分别给出处理不可行解的两个有效算法 M3.1-GROA 和 M3.2-GROA,  其中 M3.1-GROA 用于处理 KPCM3.1 的不可行解, M3.2- GROA 用于处理 KPCM3.2 的不可行解.  设数组 H[1…n]已按照物品的价值密度 pj/wj由大到小的顺序依次存放了n个物品的下标,  即H  满足][][]2[]2[]1[HH[1]. .HHnn HH³³³wpwpwp .令 Y=[y1,y2,…,yn]∈{0,1}n为一个辅助向量, X=[x1,x2,…,xn]∈{0,1}n是KPCM3.1 的一个潜在解，则算法 M3.1-GROA 的伪代码描述如下： 算法 4.   M3.1-GROA 输入:潜在解 X=[x1,…,xn]和 H[1…n];  输出:优化后的可行解 X=[x1, x2,…,xn]和 g1(X). 1    j←n;   2   WHILE W(X)>C DO 3       IF xH[j]=1 THEN xH[j]←0; 4        j←j-1; 5    END WHILE 6    FOR j←1 TO n    DO 7       IF (xH[j]=0∧W(X) +wH[j]≤C) THEN 8            Y←X;   yH[j]←1;  9            IF g1(Y)> g1(X) THEN xH[j]←1;   10      END IF 11   END FOR 12   RETURN(X, g1(X)) 在 M3.1-GROA 中，函数 g1(X)按照(14)式进行计 算 ,  Step2-Step5 将 不 可 行 解 修 复 为 可 行 解 , Step6-Step11 对可行解进行优化处理, Step12 输出优化后的可行解 X 与其函数值 g1(X).  不难看出 , M3.1-GROA 的时间复杂度是 O(n2). 由于除了目标函数的计算方法不相同之外，M3.2-GROA 的 算 法 流 程 和 时 间 复 杂 度 均 与M2-GROA 相同，即只需将 M2-GROA 中所有的f1(Y)与 f1(X)分别替换为 g2(Y)与 g2(X),  并且按照(17)式计算g2(Y)与 g2(X)即可.  由此,  限于篇幅不再赘述M3.2-GROA 的算法伪代码. 计算机学报 计  算  机  学  报  2018 年 在利用 M3.1-GROA 和 M3.2-GROA 处理不可行解的基础上,  算法 B-HBDE 的伪代码描述如下： 算法 5.   B-HBDE  输入: KPC 实例 П,  参数 A, N,CR, F 和 MIT. 输出: П 的近似解(或最优解)与其目标函数值. 1 按照 pj/wj (1≤j≤n)由大到小的次序依次将 n 个物品的下标存入数组 H[1…n]中;  2  随机产生初始种群 P1={Y1i=[y1i1,y1i2,…,y1in]| y1ij∈[-A,A],  1≤i≤N,  1≤j≤n 和 P2={Y2i=[y2i1, y2i2,…,y2in] | y2ij∈[-A, A], 1≤i≤N, 1≤j≤n }; 3   FOR i←1 TO N   DO 4      利用(7)式分别计算 Y1i对应于 KPCM3.1的潜在解 X1i和 Y2i对应于 KPCM3.2 的潜在解 X2i; 5      (X1i,g1(X1i))←M3.1-GROA(X1i,H[1…n]); 6      (X2i,g2(X2i))←M3.2-GROA(X2i,H[1…n]); 7   END FOR 8   根据 g1(X1i)和 g2(X2i)(1≤i≤N)分别确定 P1和P2中最好解 X1b和 X2b; 9   FOR t ←1 TO MIT    DO 10     FOR i←1 TO N   DO 11       FOR j←1 TO n   DO 12         IF (r1<CR∨j=R1(i)) THEN  13               z1ij←y1,p1,j+F*(y1,p2,j - y1,p3,j); 14         ELSE z1ij←y1ij; 15         IFz1ij≥0 THEN u1ij←1ELSE u1ij←0； 16         IF (r2<CR  ∨j=R2(i)) THEN 17               z2ij←y2,p1,j+F*(y2,p2,j - y2,p3,j); 18         ELSE z2ij←y2ij; 19         IFz2ij≥0 THEN u2ij←1ELSE u2ij←0； 20       END FOR 21       (U1i,g1(U1i))  ←M3.1-GROA(U1i,H[1…n]); 22       IF g1(U1i)>g1(X1i) THEN                      Y1i←Z1i; X1i←U1i ; 23       (U2i, g2(U2i))  ←M3.2-GROA(U2i, H[1…n]); 24       IF g2(U2i)>g2(X2i) THEN                    Y2i←Z2i; X2i←U2i ; 25     END FOR 26     根据 g1(X1i)和 g2(X2i)(1≤i≤N)确定 P1和P2中最好解 X1b和 X2b; 27 END FOR 28 IF g1(X1b)≥g2(X2b) THEN  RETURN(X1b,g1(X1b)); 29 EISE RETURN(X2b, g2(X2b)). 在 B-HBDE 中, r1和 r2为(0,1)中的随机数，R1(i)和 R2(i)表示[1,n]上的随机整数.易知:  B-HBDE 的时间复杂度也为 O(MIT* n2*N).  注意:  当 B-HBDE 的两个种群的规模为|P1|=|P2|=N，S-HBDE 的种群规模为|P|=N 时,  B-HBDE 一次进化过程耗费的时间是S-HBDE 的 2 倍. 6 实例计算与比较 由于 GA 和 BPSO 在求解组合优化问题中的成功应用，已成为衡量其它 EAs 在求解组合优化问题时算法性能优劣的标准。为了验证 S-HBDE 和B-HBDE 求解 KPC 的性能，下面分别利用 S-HBDE、B-HBDE、AP-KPC、GA 和 BPSO 对四类大规模KPC 实例进行仿真计算，通过比较它们的计算效果说明 S-HBDE 和 B-HBDE 的优异性.  所有仿真计算均使用 Acer  Aspire  E1-570G 笔记 本 , 硬 件 配 置 为 Intel(R)  Core(TM)i5-3337u CPU-1.8  GHz，4GB DDR3 内存(3.82GB 可用)，操作系统为 Microsoft  Windows  8.  所有算法均利用C++编程实现，编译环境为 Visual C++6.0. 6.1   KPC实例生成方法 根据文献[2,4]中的方法，生成的四类大规模KPC实例分别是：不相关KPC实例  (记为ukpc),  其编号为ukpc100-ukpc1000; 弱相关KPC实例(记为wkpc),  其编号为 wkpc100-wkpc1000;  强相关 KPC实例(记为skpc),   其编号为skpc100-skpc1000;  逆强 相 关 KPC 实 例 ( 记 为 ikpc),  其 编 号 为 ikpc100- ikpc1000.  在 ukpc 实例中，wj  和 pj  在区间[1.0, R]上随机均匀取值.  在 wkpc 实例中，wj在区间[1.0,  R]上随机均匀取值,  pj在区间[wj−R/10,  wj+R/10]上随机均匀取值，并且 pj ≥ 1.0.  在 skpc 实例中, wj在区间[1.0, R]上随机均匀取值,并且  pj = wj + R/10.  在 ikpc 实例中, pj在区间[1.0, R]上随机均匀取值,  并且 wj = pj + R/10. 在所有 KPC 实例中,  取 R=100.1, C=0.55W,  其中 å==njjw W1.  l 在区间[-W/12, -W/30]上随机均匀取值,  u  在区间[W/30,W/12]上随机均匀取值；c在区间[3E/10,  23E/10]  上随机均匀取值，其中计算机学报