作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2011, Vol. 37 ›› Issue (20): 216-218. doi: 10.3969/j.issn.1000-3428.2011.20.075

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

动态免疫优化算法及其在背包问题中的应用

钱淑渠 1,武慧虹 1,涂 歆 2   

  1. (1. 安顺学院数学与计算机科学系,贵州 安顺 561000;2. 东南大学自动化学院,南京 211189)
  • 收稿日期:2011-03-19 出版日期:2011-10-20 发布日期:2011-10-20
  • 作者简介:钱淑渠(1978-),男,讲师、硕士,主研方向:智能优化算法;武慧虹,讲师、硕士;涂 歆,讲师、博士研究生
  • 基金资助:
    贵州省自然科学基金资助项目(20090074)

Dynamic Immune Optimization Algorithm and Its Application in Knapsack Problem

QIAN Shu-qu 1, WU Hui-hong 1, TU Xin 2   

  1. (1. Department of Mathematic and Computer Science, Anshun College, Anshun 561000, China;2. School of Automation, Southeast University, Nanjing 211189, China)
  • Received:2011-03-19 Online:2011-10-20 Published:2011-10-20

摘要: 利用人工免疫系统的学习、记忆、识别等功能,提出一种动态免疫优化算法(DIOA),用于解决一类高维动态约束优化问题。其中对可行抗体进行克隆突变操作,非可行抗体按价值密度使用贪婪算法进行修正,环境识别模块借助记忆细胞产生新的环境初始群,从而加快算法收敛速度。利用DIOA求解不同环境下的高维背包问题,结果表明,与同类算法相比,该算法能更快地跟踪最优值,收敛效果更好。

关键词: 动态环境, 高维动态约束优化, 背包问题, 免疫优化, 贪婪算法

Abstract: This paper proposes a Dynamic Immune Optimization Algorithm(DIOA) based on biological immune system learning, memory and recognition functions to solve a class of high-dimensional dynamic optimization problem with constraints. The feasible antibodies are cloned and mutated, the infeasible antibodies are repaired, by means of the profit-density of antibody, and the new environmental population is generated by using memory cells of similar environment, which accelerates the convergence of algorithm. The algorithm is applied in the high-dimensional knapsack problems are solved in different environments. Experimental results prove that, compared with traditional algorithms, DIOA can track the optimum rapidly and has stronger convergent capability.

Key words: dynamic environment, high-dimensional dynamic constraint optimization, knapsack problem, immune optimization, greedy algorithm

中图分类号: