Encoding transformation-based differential evolution algorithm for solving knapsack problem with single continuous variable

摘要

The knapsack problem with a single continuous variable (KPC) is an extension of the standard 0-1 knapsack problem. It is an especial combinatorial optimization problem with continuous variable S so that its solution is more difficult. In this paper, a novel differential evolution algorithm is proposed based on the encoding transformation technique, which is named Encoding Transformation-based Differential Evolution algorithm (ETDE). In ETDE, the individual is represented as an (n + 1)-dimensional vector in which the first n components are transformed into an n-dimensional 0-1 vector by using a special surjection, and the last component is as the value of continuous variable S. From this, a potential solution of KPC is obtained. Moreover, the Gauss-Seidel method is used to accelerate the convergence rate of ETDE, and an effective repair and optimization method is used to handle the infeasible solutions. In order to verify the performance of ETDE, we use it and the exact algorithm, approximation algorithm, particle swarm optimization, and artificial bee colony to solve four classes of large-scale KPC instances, respectively. The computational results show that ETDE not only has the fast speed, but also the calculation result is better than other algorithms. Consequently, ETDE is more suitable for quickly and efficiently solving the KPC problem than other algorithms in practical applications.