An enhanced genetic algorithm for constrained knapsack problems in dynamic environments

In this paper, an enhanced genetic algorithm (ERGA), based on memory updating and environment reaction schemes, has been proposed to solve constrained knapsack problems in dynamic environments (DKPs). Its key operators, e.g., the memory updating and the environment reaction schemes, have been further investigated to improve the ability of adapting to different dynamic environments. To maintain the diversity of solutions in the memory, when the memory is due to update, the elite that differs from any of the solutions in the memory in terms of the hamming distance will replace the worst solution in the memory set. In this way, the memory set can store diversiform information as much as possible. On the other hand, the environment reaction operation is used to determine when to retrieve and how to use the solutions saved in the memory set. Experimental results on a series of DKPs with different randomly generated data sets indicate that ERGA can faster track the changing environments and manifest superior statistical performance, when compared with peer dynamic genetic algorithms. The sensitivity analysis concerning some important parameters of ERGA has also been made and presented in the section on experimental results.