Dynamic Stochastic Ranking Selection Immune Optimization Algorithm for Dynamical 0/1 Knapsack Problem

摘要

In this paper, a dynamic stochastic ranking selection immune optimization algorithm with constraints (DSRIOA), Based on adaptive memory and dynamic recognition functions of artificial immune 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 population, Environmental memory pools are constructed to store memory cells, meanwhile, environmental recognition operator is designed to examine the 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 DSRIOA's convergence. In numerical experiments, four well-known dynamic evolutionary algorithms are selected to compare with the DSRIOA by three groups of dynamic high dimensional knapsack problems. The results indicate that the DSRIOA shows a promising convergence capability. Meanwhile, in order to improve DSRIOA's response over time, a kind of secondary response present in the algorithm, which can track more rapidly the optimum in similar environments and require less time than the other algorithms proposed in literature.