Responsive Multi-population Models for the Dynamic Travelling Thief Problem

Multi-population evolutionary models are effective methods for solving many difficult optimisation problems due to their ability to preserve population diversity via isolated evolution mechanisms. However, applications to multi-objective combinatorial problems containing time-varying characteristics is limited. In this paper, we propose a multi-population model to improve optimisation performance on the recent dynamic formulations of the Travelling Thief Problem. A key feature of our model relates to how the currency of exploitable problem information, with regard to problem dynamics, can be used for population seeding in response to dynamic events. We contrast performance of a multi-population model with differing optimisation goals in each isolated sub-population with a similar model featuring migration between populations and a standard single population method. The sharing of information between differently directed subpopulations provides significant improvements in terms of hypervolume measurements throughout the optimisation procedure. A performance analysis method is applied here to capture the significant improvements of the different models throughout the varying dynamic intervals of the problem instances. Significant performance improvements are achieved with a relatively simple multi-population topology and migration patterns that ensure currency of exploited problem information. The application of multi-population techniques to further examples of complex dynamic multi-objective optimisation problems remains an ongoing research pursuit. © 2020 IEEE.