基于拉马克进化的差分进化算法求解KPC问题  

Lamarckian Evolution-Based Differential Evolution Algorithm for Solving KPC Problem

作　　者：杨新花 周昱帆 沈爱玲 林娟[1,2] 钟一文[1,2] YANG Xinhua;ZHOU Yufan;SHEN Ailing;LIN Juan;ZHONG Yiwen(College of Computer and Information Science,Fujian Agriculture and Forestry University,Fuzhou 350002,China;Key Laboratory of Smart Agriculture and Forestry(Fujian Agriculture and Forestry University),Fuzhou 350002,China)

机构地区：[1]福建农林大学计算机与信息学院,福州350002 [2]智慧农林福建省高等学校重点实验室(福建农林大学),福州350002

出　　处：《计算机工程与应用》2022年第10期162-171,共10页Computer Engineering and Applications

基　　金：福建省自然科学基金(2019J01401,2019J01661,2020J01570)。

摘　　要：具有单连续变量的背包问题(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算法在获得最优解和平均解方面均优于其他智能优化算法。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 highdimensional 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.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]