基于离散差分演化的KPC问题降维建模与求解  

Modeling and Solving by Dimensionality Reduction of KPC Problem Based on Discrete Differential Evolution

作　　者：贺毅朝 王熙照[2] 张新禄[3] 李焕哲 HE Yi-Chao;WANG Xi-Zhao;ZHANG Xin-Lu;LI Huan-Zhe(College of Information and Engineering,Hebei GEO University,Shijiazhuang 050031;College of Computer Science and Software Engineering,Shenzhen University,Shenzhen,Guangdong 518060;College of Mathematics and Information Science,Hebei Normal University,Shijiazhuang 050024)

机构地区：[1]河北地质大学信息工程学院,石家庄050031 [2]深圳大学计算机与软件学院,广东深圳518060 [3]河北师范大学数学与信息科学学院,石家庄050024

出　　处：《计算机学报》2019年第10期2267-2280,共14页Chinese Journal of Computers

基　　金：国家自然科学基金（71371063,11471097）;河北省高等学校科学研究计划项目（ZD2016005）;河北省自然科学基金项目（F2016403055）资助~~

摘　　要：具有单连续变量的背包问题(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不仅在求解精度和稳定性方面均优于其它3个算法,而且求解速度很快,非常适于在实际应用中快速高效地求解大规模KPC实例.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

关 键 词：具有单连续变量背包问题 离散差分演化 遗传算法 粒子群优化 降维法 修复与优化法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]