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

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

为了高效求解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.