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

摘要： 具有单连续变量的背包问题（knapsack problem with a single continuous variable，KPC）是标准0-1背包问题的自然推广，在KPC中背包容量不是固定的，因此其求解难度变大。针对现有差分进化（differential evolution，DE）算法在高维KPC实例上求解精度不够高的不足，提出基于拉马克进化的DE（Lamarckian evolution-based DE，LEDE）算法，将贪心修复优化算子产生的改进遗传给后代，以加快DE算法的收敛速度，提高DE算法在高维KPC实例上的求解精度。同时，在贪心修复优化算子中引入基于价值的贪心优化策略，用于优化使用基于价值密度的贪心修复策略生成的可行解，以帮助算法跳出局部最优。在40个KPC实例上对LEDE算法进行了实验分析，结果表明拉马克进化和基于价值的贪心优化策略能够提高LEDE算法的求精能力，LEDE算法在获得最优解和平均解方面均优于其他智能优化算法。

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