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

具有单连续变量的背包问题(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实例。

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.