Intelligent Optimization Strategies in Uncertain and Dynamic Environments

In this paper we propose a new benchmark problem for dynamic combinatorial optimisation. Unlike most previous benchmarks, we focus primarily on the underlying dynamics of the problem and consider the distances between successive global optima only as an emergent property of those dynamics. The benchmark problem is based upon a class of difficult instances of the 0/1-knapsack problem that are generated using a small set of real-valued parameters. These parameters are subsequently varied over time by some set of difference equations: It is possible to model approximately different types of transitions by controlling the shape and degree of interactions between the trajectories of the parameters. We conduct a set of experiments to highlight some of the intrinsic properties of this benchmark problem and find it not only to be challenging but also more representative of real-world scenarios than previous benchmarks in the field. The attributes of this benchmark also highlight some important properties of dynamic optimisation problems in general that may be used to advance our understanding of the relationship between the underlying dynamics of a problem and their manifestation in the search space over time.