约束动态免疫算法及对背包问题性能测试研究

ON CONSTRAINED DYNAMIC IMMUNE ALGORITHM AND PERFORMANCE TESTING OF KNAPSACK PROBLEMS

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

A constrained dynamic immune algorithm（CDIOA） is proposed in reference of adaptive memory and dynamic recognition functions of artificial immune systems,and is used to solve a class of high-dimensional dynamic Knapsack problems with constraints.The stochastic constraint selection strategy is used to select feasible antibodies and infeasible antibodies and the latter participate into the population evolution.The antibody modification strategy is employed to guarantee that there are a certain proportion of feasible antibodies in the evolving population so as to improve search function of the algorithm.The environment recognition module is designed to judge whether or not the environments are changed over the time,the environments memory pool is constructed as well to reserve memory cells with excellent performance,and the memory cells participate into the generation of initial population in similar or same environments,which accelerates the search speed of the algorithm in similar environment.Three types of dynamic knapsack problems in different environments are set up as the standard test instances,and four existing dynamic optimisation algorithms are selected to compare with the CDIOA for testing.The results indicate that the CDIOA demonstrates a promising convergent capability on various testing tasks in different environments,and can rapidly track the optimum in similar environments.