Generalizable Meta-Heuristic based on Temporal Estimation of Rewards for Large Scale Blackbox Optimization
This addresses the problem of deteriorating generalization in optimization for researchers and practitioners in fields requiring high-dimensional blackbox optimization, though it appears incremental as it builds on existing meta-heuristic and bandit methods.
The paper tackles the challenge of maintaining generalization in heuristic optimizers for Large Scale Blackbox Optimization (LSBO) by proposing a meta-heuristic based on Temporal Estimation of Rewards (TER) that ensembles heuristics and uses multi-armed bandits with non-stationary rewards, achieving competitive performance on benchmarks with dimensions up to 10000.
The generalization abilities of heuristic optimizers may deteriorate with the increment of the search space dimensionality. To achieve generalized performance across Large Scale Blackbox Optimization (LSBO) tasks, it ispossible to ensemble several heuristics and devise a meta-heuristic to control their initiation. This paper first proposes a methodology of transforming LSBO problems into online decision processes to maximize efficiency of resource utilization. Then, using the perspective of multi-armed bandits with non-stationary reward distributions, we propose a meta-heuristic based on Temporal Estimation of Rewards (TER) to address such decision process. TER uses a window for temporal credit assignment and Boltzmann exploration to balance the exploration-exploitation tradeoff. The prior-free TER generalizes across LSBO tasks with flexibility for different types of limited computational resources (e.g. time, money, etc.) and is easy to be adapted to new tasks for its simplicity and easy interface for heuristic articulation. Tests on the benchmarks validate the problem formulation and suggest significant effectiveness: when TER is articulated with three heuristics, competitive performance is reported across different sets of benchmark problems with search dimensions up to 10000.