计算机工程

• 人工智能及识别技术 • 上一篇    下一篇

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

钱淑渠 1,2,武慧虹 2,林妤 2   

  1. (1.安顺学院 数理学院,贵州 安顺 561000; 2.南京航空航天大学 自动化学院,南京 210016)
  • 收稿日期:2016-08-03 出版日期:2017-09-15 发布日期:2017-09-15
  • 作者简介:钱淑渠(1978—),男,副教授、博士,主研方向为智能计算、系统建模及控制;武慧虹,副教授、硕士;林妤,讲师、硕士。
  • 基金项目:
    国家自然科学基金(61304146);贵州省科技计划项目(黔科合J字[2015]2002号);贵州省教育厅优秀科技创新人才奖励计划项目(黔教合KY字[2014]255);贵州省科技厅安顺市政府安顺学院联合基金(LKA201221)。

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

QIAN Shuqu 1,2,WU Huihong 2,LIN Yu 2   

  1. (1.School of Sciences,Anshu University,Anshun,Guizhou 561000,China; 2.College of Automation Engineering,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China)
  • Received:2016-08-03 Online:2017-09-15 Published:2017-09-15

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

关键词: 克隆修复, 免疫算法, 高维, 动态背包问题, 环境跟踪

Abstract: 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.

Key words: clonal repair, immune algorithm, high-dimensional, Dynamic Knapsack Problem(DKP), environmental tracking

中图分类号: