修补二进制差分进化算法:高效解决高维动态0-1背包问题

需积分: 22 4 下载量 43 浏览量 更新于2024-09-07 1 收藏 1.24MB PDF 举报
本文主要探讨了在解决高维动态0-1背包问题(DKNP)时,现有的动态优化算法存在难以获得高质量可行解以及跟踪环境速度较慢的问题。针对这些问题,研究者提出了修补二进制差分进化算法(BDE/R)。该算法在设计上具有创新性,包括以下几个关键部分: 1. 随机压缩变异策略:算法采用了直接基于个体间差异的离散域突变策略,这种方法可以更好地挖掘问题空间中的潜在解决方案,增强算法的搜索能力。 2. 贪婪修补策略:通过引入一种贪婪策略,算法能够优先选择最有可能改进当前可行解的变异操作,从而提高了所得解的质量,并加快了算法的收敛速度。 3. 对偶变换算子:设计了一种对偶变换算子,旨在提升种群的多样性,使得算法在应对动态环境变化时能更迅速地调整自身,增强了其跟踪环境的能力。 为了评估BDE/R的性能,研究者选取了平均环境跟踪精确度(Av-Acc)和平均环境跟踪适应度(Av-Ada)作为评价指标,通过四个不同类型的DKNP测试来验证算法在跟踪动态最优值方面的表现。对比实验结果显示,BDE/R在这些指标上的表现优于其他五种知名的优化算法,这证明了其在解决高维动态问题上的优势。 此外,通过对平均适应度跟踪曲线的分析,BDE/R显示出更快的环境跟踪速度,这进一步强调了其在实时优化场景中的竞争力。本文提出的修补二进制差分进化算法BDE/R为高维动态0-1背包问题的求解提供了一个有效的解决方案,其在收敛速度、解的质量和环境跟踪性能上都展现出显著的优势。这项研究对于优化理论和实际应用具有重要的推动作用,特别是在处理动态环境和复杂优化问题时。