计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (36): 57-60.

• 研究、探讨 • 上一篇    下一篇

基于模拟退火选择的动态免疫算法及其应用

钱淑渠,武慧虹   

  1. 安顺学院 数学与计算机科学系,贵州 安顺 561000
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-12-21 发布日期:2011-12-21

Dynamic immune algorithm based on simulated annealing selection and its application

QIAN Shuqu,WU Huihong   

  1. Department of Mathematics and Computer Sciences,Anshun College,Anshun,Guizhou 561000,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-12-21 Published:2011-12-21

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

关键词: 动态环境, 动态背包问题, 免疫算法, 模拟退火选择, 群体多样性

Abstract: A novel dynamic immune optimization algorithm(DIASA),based on simulated annealing selection theory,adaptive memory and the functions of dynamic recognition of immune system,is proposed to solve the high-dimensional dynamic knapsack problem with constraints.The keys of algorithm are included:(1)The affinity of antibody is designed based on the performance of current population.(2)The infeasible antibodies are repaired by the increasing sorting of price consistency of antibodies gene,while the feasible antibodies are cloned and mutated dynamically,the mutation probability is designed by the density of antibody.(3)The new environmental population is generated using memory cells according to environmental recognition operator,which accelerates the convergence of algorithm.In numerical experiments,two existing intelligent algorithms ETGA and ISGA for dynamic optimization problem are selected to compare with the algorithm designed for dynamic high-
dimension knapsack problem,the results indicate that the DIASA shows a promising convergent capability,and can track rapidly the optimum,powerful diversity of population.

Key words: dynamic environments, dynamic knapsack problem, immune algorithms, simulated annealing selection, population diversity