新颖的离散差分演化算法求解D{0-1}KP问题

Novel Discrete Differential Evolution Algorithm for Solving D{0-1}KP Problem

折扣{0-1}背包问题(D{0-1}KP)是0-1背包问题(0-1KP)的一种更复杂的扩展形式。为了利用离散差分演化高效求解D{0-1}KP,首先提出了一个新V型转换函数(NV),通过NV将个体的实向量映射为一个二进制向量,与已有的S型和V型转换函数相比,NV计算复杂度更低,求解效率更高。然后,基于新V型转换函数给出了一种新的离散差分演化算法(NDDE),并利用NDDE提出了求解D{0-1}KP的一个新的高效方法。最后,为了验证NDDE求解D{0-1}KP的性能,利用它求解四类大规模D{0-1}KP实例,并与基于群论的优化算法(GTOA)、基于环理论的演化算法(RTEA)、混合教学优化算法(HTLBO)和鲸鱼优化算法(WOA)等已有算法的最好计算结果进行比较,比较结果表明,NDDE不仅求解精度更高,而且算法的稳定性佳,非常适于求解大规模D{0-1}KP实例。

The discounted{0-1}knapsack problem(D{0-1}KP)is a more complex variant of the classic 0-1 knapsack problem(0-1KP).In order to efficiently solve the D{0-1}KP by using discrete differential evolution algorithm,firstly,a novel V-shape transfer function(NV)is proposed.The real vector of an individual is mapped into a binary vector by NV.Compared with the existing S-shaped and V-shaped transfer function,NV has lower computational complexity and higher efficiency.Then,a new discrete differential evolution algorithm(NDDE)is given based on the novel V-shape transfer function.A novel and efficient method for solving D{0-1}KP is proposed by NDDE.Finally,in order to verify the efficiency of NDDE in solving D{0-1}KP,it is used to solve four kinds of large-scale D{0-1}KP instances,and the results are compared with the existing algorithms such as group theory-based optimization algorithm(GTOA),ring theory-based evolutionary algorithm(RTEA),hybrid teaching-learning-based optimization algorithm(HTLBO)and whale optimization algorithm(WOA).The results show that NDDE not only has higher accuracy,but also has good stability,which is very suitable for solving large-scale D{0-1}KP instances.