基于带有编码复用的离散混合差分进化算法求解KPC问题  

Discrete Hybrid Differential Evolution Algorithm with Code Reuse for Knapsack Problem with a Single Continuous Variable

作　　者：郝翔 李香军 HAO Xiang;LI Xiang-jun(Department of Information Engineering,Hebei GEO University,Shijiazhuang 050031,China)

机构地区：[1]河北地质大学信息工程学院,河北石家庄050031

出　　处：《新一代信息技术》2020年第10期1-7,13,共8页New Generation of Information Technology

基　　金：河北省自然科学基金(项目编号:F2016403055,F2020403013);河北省高等学校科学研究计划项目(项目编号:QN2019075)。

摘　　要：为了高效求解KPC问题,通过结合具有不同编码结构的S-HBDE和ETDE两种进化算子,提出了一个具有编码复用的离散混合差分进化算法DHDE。首先,在单种群中利用具有(n+1)维空间的ETDE编码方式表示个体,然后通过记录DHDE在前一次进化模式中种群个体改善数目,自适应的选择下一次的进化算子来进化个体,进而获得实例的最优解。最后,通过将DHDE求解四类大规模KPC实例的计算结果与ETDE、S-HBDE和B-HBDE的计算结果对比,证明了算法DHDE不仅寻优性能好,而且稳定性强,是一个适合高效求解KPC实例的新方法。In order to solve the KPC problem efficiently,a discrete hybrid differential evolution algorithm with code reuse(DHDE)is proposed by combining S-HBDE and ETDE,both of which are characterized by different coding structures.First of all,the individual is represented by ETDE coding with(n+1)dimensional solution space in a single population.Second,by recording the number of individuals improved in the previous evolution mode of DHDE,the next evolution operator is adaptively selected to evolve individuals to obtain the optimal solution of the case step by step.Finally,by comparing the results of DHDE with those of ETDE,S-HBDE and B-HBDE in terms of solving four kinds of large-scale KPC instances,it is proved that DHDE not only has better optimization performance and stronger stability,but also is a novel algorithm suitable for solving KPC examples efficiently.

关 键 词：离散混合差分进化算法 编码复用 双进化算子 KPC问题 

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