Evolutionary Multi-Objective Optimization for the Dynamic Knapsack Problem
share
Evolutionary algorithms are bio-inspired algorithms that can easily adapt to changing environments. In this paper, we study single- and multi-objective baseline evolutionary algorithms for the classical knapsack problem where the capacity of the knapsack varies over time. We establish different benchmark scenarios where the capacity changes every τ iterations according to a uniform or normal distribution. Our experimental investigations analyze the behavior of our algorithms in terms of the magnitude of changes determined by parameters of the chosen distribution, the frequency determined by τ, and the class of knapsack instance under consideration. Our results show that the multi-objective approaches using a population that caters for dynamic changes have a clear advantage in many benchmarks scenarios when the frequency of changes is not too high. Furthermore, we demonstrate that the distribution handling techniques in advance algorithms such as NSGA-II and SPEA2 do not necessarily result in better performance and even prevent these algorithms from finding good quality solutions in comparison with simple multi-objective approaches.
READ FULL TEXT