摘要：动态背包问题是一类常见的工程设计问题,同时也是动态进化算法研究领域的难点之一。将贪婪近似法与双概率原对偶映射思想相结合,提出一种求解动态背包问题的改进双概率原对偶遗传算法。一方面,针对传统遗传算法求解动态问题时存在多样性缺失的缺陷,从保持等位基因多样性角度出发,引入基于基因位值的双概率对偶映射,该映射通过弱势基因位值的概念,在迭代过程中根据该数目对两个对偶概率进行适应性调整,使种群具有较理想的多样性;另一方面,通过当前环境反馈的启发式信息使种群较快地搜索到"可行优秀"区域,使得算法更快地追踪最优点的变化轨迹。仿真结果表明,采用该贪婪法后的原对偶遗传算法在动态背包问题的求解中具有较好的性能。

摘要：高维动态背包问题(DKP)为一类较难求解的约束优化跟踪问题。为挖掘生物免疫系统的学习、记忆及识别功能,提出一种处理DKP的克隆修复免疫算法(IACR)。将抗体浓度融入亲和力的设计,运用环境识别规则判断当前环境是否相似或相同。通过环境记忆池保存一定量的记忆细胞,这些记忆细胞参与环境初始种群的产生,可用于提高算法的环境跟踪速度。采用贪婪修补策略提高可行抗体比例。测试IACR对不同变化幅率和频率的高维DKP的跟踪能力,并与4种同类算法进行比较。实验结果表明,IACR能更快速地适应环境变化,并具有较小的环境跟踪误差。

摘要：借鉴人工免疫系统的记忆、动态识别等功能,提出一种约束动态免疫算法(CDIOA),并用于高维约束动态背包问题的求解。通过随机约束选择策略选择可行及非可行抗体,非可行抗体参与群体的进化;利用抗体修正策略确保进化群中有一定比例可行抗体,提高算法搜索功能;设计环境识别模块判断环境变化与否,建立环境记忆池保存较优秀记忆细胞,记忆细胞参与相似(相同)环境初始群的产生,加速算法在相似环境搜索速度。建立三种不同环境的动态背包问题作为标准测试实例,将CDIOA与已有的四种动态优化算法进行测试比较,结果表明:CDIOA对各测试问题在不同环境表现出较好的收敛性能,在相似环境能快速跟踪最优值。

摘要：借鉴人工免疫系统的记忆、动态识别等功能及模拟退火选择理论,提出一种适用于求解动态环境优化问题的动态免疫算法(DIASA),并将其用于高维动态约束背包问题。算法设计包括:(1)抗体的亲和力随群体进化而变化;(2)可行抗体被克隆和动态突变,突变概率与抗体浓度相关,而非可行抗体按价值密度贪婪修正;(3)新环境初始群经环境识别算子按不同方式生成,相似环境初始群由记忆细胞及随机抗体产生。数值实验中,选取著名的动态进化算法(ETGA)和动态免疫遗传算法(ISGA),通过不同难度的高维动态约束背包问题进行仿真比较,结果表明:DIASA较算法ISGA和ETGA对不同问题在各环境内表现较强的优化性能,群体中抗体多样性保持较好,能快速跟踪不同环境的最优值,收敛性强。