Scalable Transfer Evolutionary Optimization: Coping With Big Task Instances

Mojtaba Shakeri, Erfan Miahi, Abhishek Gupta, Yew-Soon OngIEEE Trans. Cybernetics 2020 · DOI · OpenReview

TL;DR

This paper introduces sTrEO, a novel framework for Transfer Evolutionary Optimization (TrEO) that efficiently handles a massive number of source tasks (over 1000) while remaining agile in learning from sparse, relevant sources. It achieves this through a unique co-evolutionary approach, enabling practical deployment in large-scale applications like cloud services.

What Problem Does This Paper Address?

In today's data-rich world, many applications rely on optimizing complex problems using evolutionary algorithms. Transfer Evolutionary Optimization (TrEO) aims to speed up these processes by leveraging knowledge gained from previously solved "source" tasks to help solve new "target" tasks. However, existing TrEO methods struggle with two critical challenges:

  1. Scalability: They can't efficiently handle a vast number of source tasks, often limited to tens. This is a major bottleneck for real-world scenarios like cloud platforms that accumulate millions of user interactions (each a potential source task).
  2. Online Learning Agility with Sparse Relevance: When only a tiny fraction of available source tasks are actually relevant to the target task, existing methods are slow to identify and utilize this useful knowledge, leading to inefficient learning or even "negative transfer" (where learned knowledge harms performance).

This paper tackles these limitations to enable TrEO in scenarios with "big task-instances."

Methods

The core innovation is the Scalable Transfer Evolutionary Optimization (sTrEO) framework. It employs a novel co-evolutionary approach with two "species" that evolve jointly:

  • Source Knowledge Space: This species learns how to best utilize knowledge from the source tasks.
  • Target Solution Space: This species optimizes the solution for the current target task.

The key mechanism for learning transfer coefficients (how much to rely on each source) is a specialized (1+1)-Evolution Strategy (ES). This ES is designed for:

  • Scalability: By evolving only one individual per generation, it avoids the computational overhead of larger populations.
  • Novel Mutation: It uses a mutation function that estimates the expected fitness of each source model relative to the target objective. This allows it to dynamically adjust transfer coefficients, giving higher weights to relevant sources and effectively neutralizing irrelevant ones.
  • Neutralization Strategy: A threshold-based mechanism filters out irrelevant sources, preventing negative transfer and improving efficiency.

Datasets

The paper evaluates sTrEO on several practically motivated benchmarks:

  • 0/1 Knapsack Problem: A classic combinatorial optimization problem, used with 1000 source instances (varying in relatedness to the target).
  • Robotic Arm with Variable Morphology: A continuous optimization problem involving controlling a robotic arm. Experiments were conducted with 10 and 20 joints, and with up to 10,000 source instances.
  • Double Pole Balancing Controller System: A challenging control problem used to assess performance on increasingly difficult task variants.

No new benchmarks were introduced; existing problem formulations were adapted for the large-scale transfer learning context.

Key Insights and Ideas

  • Co-evolution is Key for Scalability: The simultaneous evolution of source knowledge and target solutions allows for dynamic adaptation and efficient knowledge orchestration, crucial for handling thousands of sources.
  • (1+1)-ES is Surprisingly Effective for Transfer: The simplicity and low computational cost of the (1+1)-ES, when augmented with a smart mutation strategy, make it a powerful tool for learning transfer coefficients in large-scale settings.
  • Targeted Neutralization Prevents Negative Transfer: Actively filtering out irrelevant sources is as important as identifying relevant ones, especially when the proportion of relevant sources is very low.
  • Scalability Doesn't Necessarily Mean Sacrificing Agility: sTrEO demonstrates that it's possible to achieve both massive scalability and quick adaptation to sparse relevant knowledge, a significant improvement over prior methods.

Key Results

  • Massive Scale-Up: sTrEO successfully handles over 1000 source task-instances, a two-order-of-magnitude improvement over previous state-of-the-art methods.
  • Competitive Performance: In experiments on the 0/1 knapsack and robotic arm problems, sTrEO achieved comparable or superior performance to existing TrEO methods (AMTEA, MAB-AMTEA) in terms of convergence speed and final solution quality.
  • Efficiency: sTrEO demonstrated significantly lower computational cost, especially when dealing with a large number of sources, making it more practical for real-world applications.
  • Agility with Sparsity: The framework effectively learns from sparse relevant sources, outperforming methods that struggle to identify useful knowledge in such scenarios. For instance, in the double pole balancing problem, sTrEO achieved a higher success rate with fewer function evaluations.

Limitations and Future Work

  • Sensitivity to Hyperparameters: While the paper includes a sensitivity analysis, the performance of sTrEO is still influenced by hyperparameters like temperature (λ) and learning rate (η).
  • Future Work: The authors suggest extending sTrEO to a wider variety of real-world optimization problems, including those with graph-based representations. They also propose investigating its application in evolutionary multitasking, where multiple tasks are solved simultaneously, and exploring its use with millions of prior optimization experiences.

Summary updated

Abstract

In today’s digital world, we are faced with an explosion of data and models produced and manipulated by numerous large-scale cloud-based applications. Under such settings, existing transfer evolutionary optimization (TrEO) frameworks grapple with simultaneously satisfying two important quality attributes, namely: 1) scalability against a growing number of source tasks and 2) online learning agility against sparsity of relevant sources to the target task of interest. Satisfying these attributes shall facilitate practical deployment of transfer optimization to scenarios with big task instances, while curbing the threat of negative transfer. While applications of existing algorithms are limited to tens of source tasks, in this article, we take a quantum leap forward in enabling more than two orders of magnitude scale-up in the number of tasks; that is, we efficiently handle scenarios beyond 1000 source task instances. We devise a novel TrEO framework comprising two co-evolving species for joint evolutions in the space of source knowledge and in the search space of solutions to the target problem. In particular, co-evolution enables the learned knowledge to be orchestrated on the fly, expediting convergence in the target optimization task. We have conducted an extensive series of experiments across a set of practically motivated discrete and continuous optimization examples comprising a large number of source task instances, of which only a small fraction indicate source–target relatedness. The experimental results show that not only does our proposed framework scale efficiently with a growing number of source tasks but is also effective in capturing relevant knowledge against sparsity of related sources, fulfilling the two salient features of scalability and online learning agility.
BibTeX
@article{shakeri2020scalable,
  author = {Mojtaba Shakeri and Erfan Miahi and Abhishek Gupta and Yew-Soon Ong},
  title = {{Scalable Transfer Evolutionary Optimization: Coping With Big Task Instances}},
  journal = {IEEE Trans. Cybernetics},
  year = {2020},
  doi = {10.1109/tcyb.2022.3164399},
}
Figure