求解高维动态背包问题的克隆修复免疫算法

Clonal Repair Immune Algorithm for Solving High-dimensional Dynamic Knapsack Problem

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

High-dimensional Dynamic Knapsack Problem（ DKP） is a challenging constrained optimization tracking problem. In order to mine the learning,memory and recognition functions of biological immune system,this paper proposes an Immune Algorithm based on Clonal Repair（ IACR） for solving DKP. The antibody concentration is integrated into the design of affinity. The environment recognition rule is developed to determine whether the current environment is similar or identical. The memory pool is utilized to store a certain amount of memory cells. These memory antibodies are participated in the emergence of environment initial population to improve the environment tracking speed of the algorithm. A greed repair strategy is proposed to increase the ratio of feasible antibodies. IACR is carried out on tracking the ability of high-dimensional DKP under different change severities and frequencies,and compared with 4 similar algorithms. Experimental results show that IACR can adapt to environmental changes more quickly and obtain less environmental tracking errors.