关键词: 具有单连续变量背包问题, 差分进化算法, 拉马克进化, 贪心修复优化

Abstract: Knapsack problem with a single continuous variable（KPC） is a natural generalization of the standard 0-1 knapsack problem. In KPC, the capacity of the knapsack is not fixed, so it becomes more difficult to solve. In order to overcome the shortcoming that the performance of existing differential evolution （DE） algorithm is not good enough on high-dimensional KPC instances, this paper proposes Lamarckian evolution-based DE（LEDE） algorithm to solve KPC. The improvement generated by the greedy repair and optimization operator is inherited to the offspring, which can speed up the convergence speed of DE algorithm and improve the precision of DE algorithm on high-dimensional KPC instances. At the same time, a profit-based greedy optimization strategy is introduced in the greedy repair and optimization operator to optimize the feasible solution generated by greedy repair strategy based on profit weight ratio, so as to help the algorithm jump out of local optimum. The LEDE algorithm is experimentally analyzed on 40 KPC instances. The experimental results show that the Lamarckian evolution and the profit-based greedy optimization strategy can improve the exploitation ability of LEDE algorithm, and LEDE algorithm is better than other intelligent optimization algorithms in terms of obtaining the best solution and the mean solution.

Key words: knapsack problem with a single continuous variable, differential evolution, Lamarckian evolution, greedy repair and optimization