Dynamic immune optimization algorithm for Knapsack problem in dynamic environments

摘要

In this paper, a dynamic immune optimization algorithm with constraints (DCIOA), based on adaptive memory and dynamic recognition functions of artificial systems, was proposed to deal with Knapsack problem with constraints in dynamic environments. A novel dynamic stochastic ranking strategies is used to select excellence antibodies, meanwhile, infeasible antibodies participate in evolution of population; Improving the searching functions utilizes repairing method to remedy infeasible antibodies, and make sure the rate of feasible antibody in current environmental population; Environmental memory pools are constructed to store memory cells, at the same time, environmental recognition operator is designed to examine the environments changing over time, the initial population of similar or same environments are generated via introducing some memory cells into the current population, which accelerates the DCIOA's convergence. In numerical experiments, four well-known dynamic evolutionary algorithms are selected to compare with the DCIOA by three groups of dynamic high dimensional knapsack problems. The results indicate that the DCIOA shows a promising convergence capability, meanwhile, we will also show that our algorithm improves its response over time, a kind of secondary response present in the immune system, and can track more rapidly the optimum in similar environments and requires less time than the other algorithms proposed in literature.