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

Yichao He

doi:10.1016/j.swevo.2019.03.002

Return

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

2019-11-01

PRE

DOI：10.1016/j.swevo.2019.03.002

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

Differential evolution

Encoding transformation

Gauss-Seidel method

Infeasible solution

Repair and optimization

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.