Learning from Offline and Online Experiences: A Hybrid Adaptive Operator Selection Framework

Jiyuan Pei, Jialin Liu, Yi Mei

Introduction

Meta-heuristic algorithms, such as Genetic Algorithms and Differential Evolution, are essential tools for solving complex optimization problems across diverse fields, from logistics to engineering design. A central challenge in these algorithms is Adaptive Operator Selection (AOS): the task of determining which search operator (the mathematical rule used to modify a solution) is most effective at any given step of the optimization process.

Historically, researchers have approached AOS through two distinct lenses:

  1. Offline Learning: Models are trained on extensive libraries of historical problems to learn generalizable strategies. While powerful, these models are often brittle; if a new problem deviates significantly from the training data, the model's performance can degrade.
  2. Online Learning: Algorithms learn which operators work best on-the-fly during the current problem-solving session. This approach is robust but computationally expensive, as the algorithm must spend time exploring different operators before identifying the most effective ones.

This paper introduces a Hybrid AOS Framework (HF) designed to bridge this gap, combining the immediate insights of offline knowledge with the flexibility of online adaptation.

The Hybrid Framework Architecture

The proposed framework integrates three core components to balance "expert" knowledge with "quick" learning:

1. The State-based Module (The "Expert")

This module utilizes Deep Reinforcement Learning (specifically DDQN or DQN-GSF). It is pre-trained offline on representative problem sets to learn a mapping between the current state of the optimization landscape and the optimal operator. To maintain relevance, the module continues to update its weights online as it encounters the specific characteristics of the new problem.

2. The Stateless Module (The "Quick Learner")

In contrast to the state-based module, this component uses a lightweight Multi-Armed Bandit (MAB) approach. It ignores the complex "state" of the problem and instead tracks which operators have yielded recent improvements. Its simplicity ensures that it adds virtually no computational overhead while providing a rapid response to the current problem's dynamics.

3. The Decision Policy (The "Manager")

The Decision Policy is the governing logic that chooses between the Expert and the Quick Learner. It maintains a probability $p$ for selecting a module. When the algorithm successfully finds an improvement, it increases the weight of the stateless module to encourage further exploration of currently successful operators. If the algorithm becomes stuck—indicating a potential local optimum—it shifts the weight back toward the state-based Expert to leverage sophisticated pattern recognition and navigate out of the "sticky" landscape.

Experimental Evaluation

The framework was evaluated across two distinct optimization domains to test its versatility:

  • Real-Value Optimization: The model was trained on 32 problems from the CEC2005 benchmark and tested on 138 instances from CEC2017 and BBOB2023, covering dimensions from 10D to 50D.
  • Combinatorial Optimization: The team applied the framework to the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW). Using the classic Solomon instances, the model was trained on a single instance (R101) and tested on 33 others with varying customer distributions.

Key Insights and Results

The Hybrid Framework (HF) demonstrated superior performance compared to state-of-the-art (SOTA) methods that rely exclusively on one type of experience:

  • Superior Generalization: In real-value problems, the hybrid approach significantly outperformed the SOTA DE-DDQN method on 36 instances, while underperforming on only 7 out of 138. In routing problems, it won on 21 instances against the DQN-GSF method, losing on only 5.
  • The "Safety Net" Effect: The stateless module serves as a critical buffer. When the offline-trained model encounters an unfamiliar problem, the stateless module quickly identifies effective operators, preventing the algorithm from following the "misled" advice of the expert.
  • Strategic Use of Expertise: The framework effectively uses the deep-learned model as a specialized tool for escaping local optima, while relying on the simpler online learner for more straightforward progress.

Conclusion and Future Work

The Hybrid AOS Framework proves that combining offline and online experiences creates a more resilient and efficient optimizer. By treating offline knowledge as a flexible starting point rather than a rigid rulebook, the framework achieves high performance across diverse and unseen problem sets.

Future research will focus on refining the decision policy logic, exploring more sophisticated feature engineering for the state-based module, and extending the hybrid logic to other meta-heuristics such as Particle Swarm Optimization.

Summary updated

BibTeX
@inproceedings{pei2024learning,
  author = {Jiyuan Pei and Jialin Liu and Yi Mei},
  title = {{Learning from Offline and Online Experiences: A Hybrid Adaptive Operator Selection Framework}},
  booktitle = {GECCO},
  year = {2024},
  doi = {10.1145/3638529.3654062},
}
Figure