Surrogate-Assisted Evolutionary Q-Learning for Black-Box Dynamic Time-Linkage Optimization Problems

Dynamic time-linkage optimization problems (DTPs) are special dynamic optimization problems (DOPs) with the time-linkage property. The environment of DTPs changes not only over time but also depends on the previous applied solutions. DTPs are hardly solved by existing dynamic evolutionary algorithms because they ignore the time-linkage property. In fact, they can be viewed as multiple decision-making problems and solved by reinforcement learning (RL). However, only some discrete DTPs are solved by RL-based evolutionary optimization algorithms with the assumption of observable objective functions. In this work, we propose a dynamic evolutionary optimization algorithm using surrogate-assisted Q-learning for continuous black-box DTPs. To observe the states of black-box DTPs, the state extraction and prediction methods are applied after the search process at each time step. Based on the learned information, a surrogate-assisted Q-learning is introduced to evaluate and select candidate solutions in the continuous decision space in a long-term consideration. We evaluate the components of our proposed algorithm on various benchmark problems to study their behaviors. Results of comparative experiments indicate that the proposed algorithm outperforms other compared algorithms and performs robustly on DTPs with up to 30 decision variables and different dynamic changes.