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

• 作者: 杨新花 周昱帆 沈爱玲 林娟 钟一文
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 具有单连续变量背包问题 差分进化算法 拉马克进化 贪心修复优化
• 年，卷（期）: 2022,（10）
• 所属期刊栏目: 模式识别与人工智能|Pattern Recognition and Artificial Intelligence
• 页码范围: 162-171
• 页数: 10页
• 分类号: TP18
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2011-0302

摘要

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