摘要: 利用人工免疫系统的学习、记忆、识别等功能,提出一种动态免疫优化算法(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
中图分类号:
钱淑渠, 武慧虹, 涂歆. 动态免疫优化算法及其在背包问题中的应用[J]. 计算机工程, 2011, 37(20): 216-218.
JIAN Chu-Ju, WU Hui-Gong, CHU Xin. Dynamic Immune Optimization Algorithm and Its Application in Knapsack Problem[J]. Computer Engineering, 2011, 37(20): 216-218.