SupReferences

# Scalable Transfer Evolutionary Optimization: Coping with Big Task-Instances

Mojtaba Shakeri, Erfan Miahi, Abhishek Gupta, _Senior Member_ , _IEEE_ , and
Yew-Soon Ong, _Fellow_ , _IEEE_ This work was supported by the A*STAR Cyber-
Physical Production System (CPPS) – Towards Contextual and Intelligent
Response Research Program, under the RIE2020 IAF-PP Grant A19C1a0018, and
Model Factory@SIMTech. Abhishek Gupta was also supported in part by the AI3
seed grant C211118016 on Upside-Down Multi-Objective Bayesian Optimization for
Few-Shot Design. _(Corresponding author: Abhishek Gupta)_ M. Shakeri is with
Singapore Institute of Manufacturing Technology, Singapore 138634, and also
with Computer Engineering Department, Faculty of Engineering, University of
Guilan, Rasht 13769-41996, Iran (e-mail:
<EMAIL_ADDRESS>shakeri@guilan.ac.ir).E. Miahi is with
Department of Computing Science, Faculty of Science, University of Alberta,
Canada T6G 2E8 (e-mail: miahi@ualberta.ca).A. Gupta is with Singapore
Institute of Manufacturing Technology, Singapore 138634
(abhishek_gupta@simtech.a-star.edu.sg).Y.-S. Ong is with the School of
Computer Science and Engineering, Nanyang Technological University, Singapore,
and also with the Agency for Science, Technology and Research (A*STAR),
Singapore (e-mail<EMAIL_ADDRESS>ongyewsoon@hq.a-star.edu.sg).

###### 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 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 paper, we take a
quantum leap forward in enabling more than two orders of magnitude scale-up in
the number of tasks; i.e., we efficiently handle scenarios beyond 1000 source
task-instances. We devise a novel transfer evolutionary optimization 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.

###### Index Terms:

Transfer evolutionary optimization, big task-instances, scalability, online
learning agility.

©2022 IEEE. Personal use of this material is permitted. Permission from IEEE
must be obtained for all other uses, in any current or future media, including
reprinting/republishing this material for advertising or promotional purposes,
creating new collective works, for resale or redistribution to servers or
lists, or reuse of any copyrighted component of this work in other works. DOI:
10.1109/TCYB.2022.3164399

##  I Introduction

There have been sustained attempts at designing algorithms that are able to
automatically transfer and reuse learned knowledge across datasets, problems,
and domains. The main objective is to promote the _generalization capacity_ of
intelligent systems in a way that performance efficiency and effectiveness is
not only restricted to an individual (narrow) task, but can also be reproduced
in other _related_ tasks by reusing _computationally encoded knowledge priors_
[1]. This idea has particularly strong implications in the field of
evolutionary computation. As evolutionary optimization algorithms are
population-based, their sample complexity, i.e., the number of evaluations
needed to find good solutions, can become prohibitive when searching from
scratch. In this regard, _transfer evolutionary optimization_ (TrEO) is a
promising approach that enhances computational tractability, reusing evolved
skills drawn from previously tackled _source_ tasks to speed up the solving of
related _target_ tasks at hand [2, 3, 4].

Reusing knowledge priors for sample efficient problem-solving constitutes what
has broadly been referred to as _transfer optimization_ in the literature [2].
There have been a growing number of successful examples of the transfer
optimization paradigm in areas such as neuro-evolution [5], multi-objective
continuous optimization [6, 7, 8], combinatorial optimization [9, 10, 11, 12],
dynamic optimization [13, 14, 15], training hyperheuristics [16, 17], and
learning classifier systems [18, 19, 20] with real-world applications from the
composites manufacturing industry [7], engineering design [6, 8, 21], last-
mile logistics [22], image feature learning [23], automated machine learning
[24, 25], reinforcement learning [26], to name a few.

In the class of _sequential transfer optimization_ (where a set of tasks are
solved sequentially by utilizing information from those already solved), two
ways of reusing priors are normally employed. One is the _exact storage_ and
reuse of past solutions (either directly [27, 28, 29] or after passing through
a mapping function [7, 30]) for subsequent injection into the search space of
the target problem. The other is _model-based_ transfer where reuse of priors
has recently been realized by sampling from probabilistic models of elite
candidate solutions drawn from previously solved optimization tasks [31, 32].
Irrespective of which approach is being applied, the challenge is to
_efficiently_ curb the threat of _negative transfer_ when there are _big_
source task-instances and _many_ are not relevant to the target problem. (Note
that an _instance_ represents a single optimization problem.) Measuring inter-
task similarity, however, requires utilization of problem-specific data that
may not be a priori known before the onset of the search, particularly in
black-box evolutionary optimization settings which is the focus of this paper.
This promoted _online source-target similarity learning_ as an effective
strategy to mitigate the risks of negative transfer on the fly during the
course of evolutionary optimization [8, 32, 33]. In [8], Zhang _et al._
introduced a multi-source selective transfer framework where inter-task
similarity is captured by measuring the Wasserstein distance of the respective
source and target probabilistic search models. The final source population is
then formed by applying heuristic rules based on the max and variance of
similarities across different sources, and, through a mapping function,
injects the candidate solutions into an evolutionary algorithm. The work
utilized Feng _et al._ ’s single layer denoising autoencoder [7, 34] as the
mapping function to connect source and target populations in continuous search
spaces. Their approach, however, requires similarity computations and
comparisons in every generation of the evolution to effectively mandate the
process of transfer. This incurs significant computational cost when the
number of sources starts to grow; see complexity analysis in Section II-B.

The threat of negative transfer was also tackled by Da _et al._ [32]. They
developed an adaptive model-based transfer evolutionary algorithm (AMTEA) in
which the measure of source-target similarity is defined as the extent of
overlap between the optimized source and target search distributions captured
via stacked density estimation of the target population. The AMTEA, however,
requires a learning algorithm to be nested within the target evolutionary
search to reveal latent source-target similarities during the course of the
search. This impedes the approach from _scaling_ efficiently when large number
of source probabilistic models are to be stacked with the target model.
Shakeri _et al._ [33] addressed the scaling burden of the AMTEA by
incorporating a source selection mechanism, based on the theory of multi-armed
bandits (MAB), to stack only a single source model to the target each time the
similarity learning procedure is launched. However, a shortcoming of the
resultant MAB-AMTEA is that identification of useful sources can become slow
under sparsity of relevant source models. The uniformly random sampling of
sources at initial stages of the MAB-AMTEA often prevents the algorithm from
_quickly converging_ to the most relevant source.

Given this background, the present paper aims at _simultaneously_ tackling two
critical issues that have only been addressed in isolation by today’s transfer
evolutionary optimization frameworks, namely (1) lack of _scalability_ when
faced with a growing number of source instances and (2) lack of _online
learning agility_ against sparsity of relevant sources to the target task of
interest. While applications of most existing algorithms are limited to the
order of tens of source tasks, this paper takes a quantum leap forward to
handle scenarios beyond 1000 source task-instances. The impact of such
scalability is becoming increasingly apparent given large-scale cloud-based
platforms of today, where online services catering to thousands of clients
worldwide have emerged. For example, consider a cloud service that recommends
_packages_ to _clients_. For any new query raised by a client, the process of
finding customized packages to recommend can be cast as the NP-hard 0/1
knapsack problem [35] (a classical example in combinatorial optimization that
we also study in Section IV-B). Although NP-hard problems are known to be
difficult to solve, especially when starting the search from scratch, the idea
of TrEO makes uniquely possible the reuse of past problem solving experiences
pertaining to the same or other similar clients. (In this setting, every
experience is seen as a solved source task.) The ability to efficiently and
effectively cope with thousands of experiences could then facilitate real-time
generation of the best recommendation package, augmenting service level and
throughput of cloud services as a whole.

To this end, we devise a novel _scalable transfer evolutionary optimization_
(sTrEO) framework comprising two co-evolving species for joint evolutions in
the space of source priors and in the space of solutions to the target
problem. The proposed co-evolutionary transfer mechanism enables the learned
knowledge to be rapidly orchestrated by applying a _two-membered evolution
strategy_ , i.e., (1+1)-(ES), with a mutation function that can adjust the
level of transfer based on the relatedness of sources to the target. The key
contribution of this work can thus be summarized as follows.

  1. 1.

We establish a scalable transfer evolutionary optimization framework with two
salient features of scalability and online learning agility through co-
evolution in the knowledge and target search spaces.

  2. 2.

We incorporate a novel mutation mechanism in the (1+1)-ES based source-target
similarity learning algorithm that enables efficient and effective utilization
of relevant source task-instances beyond two orders of magnitude larger in
number than those encountered in existing works.

  3. 3.

We empirically verify the efficiency and effectiveness of the algorithm
through an extensive and rigorous experimental study across a set of
practically motivated discrete and continuous optimization examples.

The rest of the paper is organized as follows. Section II contains
preliminaries on probabilistic model-based transfer evolutionary optimization
and conducts a complexity comparison for some of the state-of-the-art
algorithms. In Section III, we first present formal definitions for
scalability and online learning agility before describing the sTrEO and its
(1+1)-ES based source-target similarity learning module. Extensive experiments
supplemented with rigorous analyses are conducted in Section IV for assessing
the performance of sTrEO across three case studies ranging from discrete to
continuous search spaces. Finally, Section V concludes the paper and
highlights potential future research directions.

##  II Preliminaries

###  II-A Basics of Probabilistic Model-Based Transfer

The probabilistic model-based expression of a typical optimization problem
$\mathcal{T}$ with a maximization function $f(\boldsymbol{x})$ (we adopt
$\scalebox{0.5}[1.0]{$-$}f(\boldsymbol{x})$ if the underlying optimization
problem is one of minimization) over a search space $\mathcal{X}$ can be
mathematically formulated as [36],

$\max_{p(\boldsymbol{x})}\int_{\mathcal{X}}f(\boldsymbol{x}).p(\boldsymbol{x}).d\boldsymbol{x},$
(1)

where, $p(\boldsymbol{x})$ is the probabilistic search distribution model of
candidate solutions in $\mathcal{X}$. Given a global optimum fitness value
$f^{*}$, an optimized model $p^{*}(\boldsymbol{x})$ is one of low entropy that
generates high-quality (near optimal) solutions satisfying,

$\int_{\mathcal{X}}f(\boldsymbol{x}).p^{*}(\boldsymbol{x}).dx\geq
f^{*}-\varepsilon,$ (2)

where, $\varepsilon$ represents a small positive convergence threshold. Note
that if we let $\varepsilon$ be $0$, $p^{*}(\boldsymbol{x})$ could then become
a degenerate distribution that collapses to just a single point; this is not
what we want.

In the sequential transfer optimization setting, when the objective is to
optimize _target_ task $\mathcal{T}_{T}$, we assume that we have solved $T-1$
_source_ tasks $\mathcal{T}_{1},\dots,\mathcal{T}_{T-1}$ giving low entropy
knowledge priors $p^{*}_{1}(\boldsymbol{x}),\dots,p^{*}_{T-1}(\boldsymbol{x})$
over a _unified_ search space $\mathcal{X}_{u}$ that encodes solutions to all
$T$ tasks. A complete description of unified search spaces can be found in
[5]; details are left out herein for the sake of brevity. Under this setting,
the transfer evolutionary optimization of the target problem from the
viewpoint of probabilistic model-based search is described as [5],

$\begin{split}\max_{w_{1},\dots,w_{T-1},w_{T},p_{T}(\boldsymbol{x})}\int_{\mathcal{X}_{u}}f_{T}(\boldsymbol{x}).\Big{[}\sum_{s=1}^{T-1}w_{s}.p_{s}^{*}(\boldsymbol{x})+w_{T}.p_{T}(\boldsymbol{x})\Big{]}.d\boldsymbol{x}\\\
\textrm{such that}\sum_{i=1}^{T}w_{i}=1\textrm{ and }w_{i}\geq 0,\forall
i\in\\{1,\dots,T-1,T\\}.\end{split}$ (3)

In this formulation, $w_{1},\dots,w_{T-1},w_{T}$ are referred to as _transfer
coefficients_ in the probabilistic mixture model
$\big{[}\sum_{s=1}^{T-1}w_{s}.p_{s}^{*}(\boldsymbol{x})+w_{T}.p_{T}(\boldsymbol{x})\big{]}$,
and determine the extent of knowledge transfer from each source to the target.
The mixture model is trained to capture the true underlying distribution of
the target population, from which candidate solutions are sampled to
adaptively bias the target search. A proper adjustment of the coefficients is
challenging nonetheless as there is no prior knowledge on the optimal search
distribution $p_{T}^{*}(\boldsymbol{x})$ of the target problem to help
identify related and unrelated sources offline. The consequences of improper
assignments are twofold. On one hand, designating an unreasonably high
transfer coefficient to an unrelated source model will result in injecting
poor solutions into the search space of the target that may significantly
impede the target search performance. On the other hand, the inability to
assign an adequately high value to a relevant source model suppresses the
transfer of useful solutions to improve optimization efficiency in the target
task. The challenge is more severe in black box optimization. Due to the
absence of an algebraic model of the system to be optimized in such settings,
we can only rely on online data generated during the course of target
optimization to discover inter-task similarities. It is thus crucial for a
transfer optimization algorithm to be able to accurately orchestrate the
mixture transfer coefficients of (3) based on the data generated during the
target optimization search.

###  II-B State-of-the-Art Transfer EAs

It can be inferred from (3) that the optimization of the target probabilistic
model as well as adjustment of the mixture transfer coefficients are two
intertwined components of the online model-based transfer optimization. The
adaptive model-based transfer EA framework (AMTEA), as proposed in [32],
captures the latter via stacked density estimation of the target population
[37]. At any generation of the target EA where the source-target similarity
learning procedure is launched, a mixture model comprising a linear
composition of $T$ available probabilistic models is learned from $n$
solutions (of dimensionality $d$) of the current generation by finding the
optimal configuration of the transfer coefficients to each model. The learning
process is carried out by applying the classical _expectation-maximization_
(EM) algorithm [38], which, in the context of stacked density estimation,
entails the construction of an $n\times T$ probability matrix to capture the
likelihood of each solution to all the $T$ probabilistic models [32]. Overall,
this requires $\mathcal{O}(dnT)$ computational steps for a variable-wise
factored distribution model, in addition to the complexity of executing the EM
algorithm itself. The cost for learning _optimal_ transfer coefficient values
is that AMTEA does not scale efficiently when the number of source task-
instances grows to hundreds and beyond.

The lack of scalability of the AMTEA was tackled in [33] via a source
selection algorithm that runs in $\mathcal{O}(T)$ to choose only one source
model at a time for stacked density estimation. This reduces the computational
steps required for constructing the probability matrix to $\mathcal{O}(dn)$,
which is a significant speedup when there are thousands of source models
available. The selection strategy is formulated based on a popular variant of
the multi-armed bandit problem, known as the adversarial MAB [39] which can be
solved to optimality using the _Exponential-weight algorithm for Exploration
and Exploitation_ (EXP3) [40]. In this setting, each source corresponds to an
arm of a bandit whose reward, when chosen (pulled), is proportional to its
level of similarity to the target. A source model which can generate fitter
individuals, as evaluated by the target objective function, receives a higher
reward measure and is more likely to be chosen in future generations. However,
as was noted in Section I, the uniformly random selection of just a single
source at initial stages of the MAB often hinders the algorithm from quickly
converging to the most relevant source, especially when related sources are
sparse. An extensive series of experiments and analyses to evaluate the above
algorithms and claims will be carried out in Section IV. We denote the MAB-
enabled AMTEA developed in [33] as MAB-AMTEA for the remainder of the paper.

There is another class of sequential transfer methods that builds a single
layer mapping function to inject solutions of past search experiences into the
current target population while the optimization search progresses [7]. The
mapping function is built each time knowledge transfer occurs. Given two
solution populations (one pertaining to a previously solved source task and
the other to the target problem) both of which consist of $n$ solutions of $d$
dimensions, a basic implementation requires $\mathcal{O}(nd^{2}+d^{3})$
computational steps to construct the mapping function. (Detailed computational
analyses are not presented here for the sake of brevity.) The above process,
however, is not scalable when the number of sources is large (i.e., $T\gg 1$),
as it needs to be repeated per source to build the corresponding mapping
function; this makes the complexity scale as $\mathcal{O}(T(nd^{2}+d^{3}))$.
In addition, memory consumption is another resource bottleneck as it is
required to archive the solutions data of all source instances for all
generations, which can quickly become intractable. Although the challenge of
multiple sources was addressed in [8] by proposing a source selection
mechanism to form a single population to construct the mapping function, the
memory consumption bottleneck remains. In contrast, in the probabilistic
model-based sequential transfer methods, we only need to store the learned
search distribution models, comprising only few distribution parameters.
Finally, note that the existing single layer autoencoder method only applies
to continuous search spaces.

##  III Scalable Transfer Evolutionary Optimization

The main motivation behind proposing the sTrEO is to _simultaneously_ achieve
scalability and online learning agility. For any transfer evolutionary
algorithm, these two measures can be defined as follows:

Definition 1 (Scalability in sTrEO): This represents internal algorithmic
efficiency. It is measured by the time complexity, with respect to the number
of sources, of each iteration of the source-target similarity learning
procedure.

Definition 2 (Online Learning Agility in sTrEO): This represents algorithmic
effectiveness or convergence rate. It is measured by the number of iterations
taken by the source-target similarity learning procedure to correctly identify
those sources that are most related to the target task.

Based on these two definitions, we find that the existing AMTEA tends to
compromise on scalability in favor of online learning agility, whereas the
MAB-AMTEA tends to compromise online learning agility in favor of scalability.

The sTrEO comprises two co-evolving species for joint evolutions in the space
of source knowledge and in the search space of solutions to the target
problem. The proposed co-evolutionary transfer mechanism enables efficient and
effective utilization of the learned knowledge beyond 1000 source task-
instances by applying a two-membered evolution strategy, i.e., (1+1)-(ES),
with a novel mutation function capable of adjusting the level of transfer in
accordance with the relatedness of sources to the target. The advantage of the
(1+1)-ES compared to other population-based evolutionary algorithms is that
evolution is carried out with only one individual, eliminating the complexity
of evaluating and evolving an entire population. This property is in line with
the paper’s objective to ensure scalability in sTrEO. In this work, the
species to evolve the solutions to the target problem is just a canonical EA
(although any other preferred algorithm can be used). Fig. 1 depicts a
flowchart illustrating the steps of knowledge transfer in the proposed
framework. The next two sections describe the components of sTrEO in detail.

Figure 1: Flowchart of the sTrEO. Unlike the AMTEA algorithm [32] which
incorporates computationally intensive stacked density estimation, the sTrEO
uses a fast (1+1)-ES algorithm to learn the transfer coefficients.

###  III-A Source Knowledge Evolution in sTrEO

The core component of sTrEO is the source-target similarity learning module
which is based on the (1+1)-ES. In the (1+1)-ES, one solution is evolved per
generation by being mutated. The fitness of the two solutions (i.e., the
parent and its offspring) is compared and the best of the two is chosen as the
individual for the next generation. In our setting, the _chromosome_ is
encoded as the transfer coefficients in the mixture model and the _fitness_ is
defined as the mean fitness of candidate solutions generated from the
corresponding mixture model and evaluated by the objective function of the
target problem. The algorithm evolves for one generation every time it is
launched by the target EA, the frequency of which is determined by a _transfer
interval_ (denoted by $\Delta$ generations in our setting – see Procedure 2).

In the standard (1+1)-ES, the parent is mutated according to a mutation
radius, a random variable following a normal distribution. In this paper,
however, we propose a different mutation mechanism according to the
characteristics of the transfer optimization paradigm as formulated in (3).
Given that
$\int_{\mathcal{X}}f(\boldsymbol{x}).p(\boldsymbol{x}).d\boldsymbol{x}$
indicates the expected objective value of a search distribution model
$p(\boldsymbol{x})$ against an objective function $f(\boldsymbol{x})$ over a
search space $\mathcal{X}$, we rephrase the formulation in (3) as follows,

$\begin{split}\max_{w_{1},\dots,w_{T-1},w_{T},p_{T}(\boldsymbol{x})}&w_{1}.E_{\boldsymbol{x}\sim
p_{1}^{*}(\boldsymbol{x})}\big{[}f_{T}(\boldsymbol{x})\big{]}+\dots\\\
&+w_{T-1}.E_{\boldsymbol{x}\sim
p_{T-1}^{*}(\boldsymbol{x})}\big{[}f_{T}(\boldsymbol{x})\big{]}\\\
&+w_{T}.E_{\boldsymbol{x}\sim
p_{T}(\boldsymbol{x})}\big{[}f_{T}(\boldsymbol{x})\big{]},\end{split}$ (4)

where $E_{\boldsymbol{x}\sim
p_{s}^{*}(\boldsymbol{x})}[f_{T}(\boldsymbol{x})]$ is the expected fitness of
an optimized source probabilistic model $p_{s}^{*}(\boldsymbol{x})$ relative
to the target objective function $f_{T}(\boldsymbol{x})$. Also note that
$\sum_{i=1}^{T}w_{i}=1$ and $w_{i}\geq 0$, $\forall i\in\\{1,\dots,T\\}$.

As the overall objective in (4) is formulated as that of maximization, a
higher expected value for each model should be reinforced with a higher
transfer coefficient. This forms the basis for our novel mutation method as a
means of guiding the evolution toward maximizing positive transfer by giving
higher weights to related sources as well as suppressing negative transfer by
neutralizing weights to unrelated ones. We implement this by defining a
mutation vector of size $T$ such that the first $T-1$ elements correspond to
the source models and the last refers to the target. Each entry in the
mutation vector estimates the expected fitness of its corresponding
probabilistic model. This is done by recording the up-to-date average fitness
of candidate solutions that have been generated from the model and evaluated
by the target objective function during the course of source-target similarity
learning. Note that as the knowledge extraction progresses, the samples
generated from the models accumulate, leading to more accurate estimations of
their expected fitness. After mutation is carried out per generation, a new
mixture model is formed from which a sample population is generated for
knowledge transfer. For clarity, we present the details of the (1+1)-ES based
source-target similarity learning module in pseudocode in Procedure 1 for the
case of a maximization problem.

Input: Optimized source models
$p^{*}_{1}(\boldsymbol{x}),\dots,p^{*}_{T-1}(\boldsymbol{x})$, temperature
$\lambda$, learning rate $\eta$, neutralization threshold $\varepsilon$,
target task $\mathcal{T}_{T}$, transfer counter $t$, target population
$P_{t}$, mean target fitness $\bar{f}_{T,t}$;

1 if  _$t==0$_ then

2 Initialize transfer coefficients $w_{t}[1:T]$ with $1/T$;

3 Initialize mutation vector $\pi[1:T]$ with zeroes;

4 Build target model $p_{T,t}(\boldsymbol{x})$ using $P_{t}$;

5 Form mixture model $M_{t}$ from
$p^{*}_{1}(\boldsymbol{x}),\dots,p^{*}_{T-1}(\boldsymbol{x})$,
$p_{T,t}(\boldsymbol{x})$ and $w_{t}[1:T]$;

6 Generate candidate transfer solutions $X_{t}$ from $M_{t}$ using the Monte
Carlo sampling method;

7 Evaluate solutions in $X_{t}$ using target objective function
$f_{T}(\boldsymbol{x})$ and record the mean fitness as $\bar{f}_{t}$;

8

9else

10 for  _$s=1$ to $T-1$_ do

11 $\pi[s]\leftarrow$ average fitness of candidate solutions in
$\bigcup_{i=0}^{t-1}X_{i}$ that have been sampled from
$p^{*}_{s}(\boldsymbol{x})$;

12

13 $\pi[T]\leftarrow\bar{f}_{T,t}$;

14 for  _$i=1$ to $T$_ do

15 $\pi^{\prime}[i]\leftarrow\pi[i]/\textrm{max}(\pi[1:T])$;

16

17 for  _$i=1$ to $T$_ do

18 $\pi^{\prime\prime}[i]\leftarrow
e^{\frac{\pi^{\prime}[i]}{\lambda}}/\sum_{j=1}^{T}e^{\frac{\pi^{\prime}[j]}{\lambda}}$;

19 $w^{\prime}[i]\leftarrow(1-\eta)\times
w_{t-1}[i]+\eta\times\pi^{\prime\prime}[i]$;

20

21 for  _$i\leftarrow 1$ to $T$_ do

22 if  _$w^{\prime}[i]\leq\varepsilon$_ then Neutralize $w^{\prime}[i]$ by $0$
;

23

24 for  _$i\leftarrow 1$ to $T$_ do

25 $w^{\prime\prime}[i]\leftarrow w^{\prime}[i]/\sum_{j=1}^{T}w^{\prime}[j]$;

26

27 Build target model $p_{T,t}(\boldsymbol{x})$ using $P_{t}$;

28 Form mixture model $M_{t}$ from
$p^{*}_{1}(\boldsymbol{x}),\dots,p^{*}_{T-1}(\boldsymbol{x})$,
$p_{T,t}(\boldsymbol{x})$ and $w^{\prime\prime}[1:T]$;

29 Generate candidate transfer solutions $X_{t}$ from $M_{t}$ using the Monte
Carlo sampling method;

30 Evaluate solutions in $X_{t}$ using target objective function
$f_{T}(\boldsymbol{x})$ and record the mean fitness as $\bar{f}^{\prime}$;

31 if  _$\bar{f}^{\prime}\geq\bar{f}_{t-1}$_ then

32 $w_{t}[1:T]\leftarrow w^{\prime\prime}[1:T]$;

33 $\bar{f}_{t}\leftarrow\bar{f}^{\prime}$;

34 else

35 $w_{t}[1:T]\leftarrow w_{t-1}[1:T]$;

36 $\bar{f}_{t}\leftarrow\bar{f}_{t-1}$;

37

38

return _$X_{t}$_

Procedure 1 (1+1)-ES Based Similarity Learning

As already stated, Procedure 1 is called by the target EA each time knowledge
transfer occurs. This is traced by a _transfer counter_ $(t)$ which is input
to the procedure and indicates the current generation of the learning process.
Accordingly, $t=0$ represents the initialization phase (lines 2–7) in which
the initial chromosome is formed by assigning identical values (here, $1/T$)
to the transfer coefficients. This implies that each source model, as well as
the initial target model, has an equal probability to transfer candidate
solutions to the target optimization algorithm. These individuals are
evaluated by the target objective function and the mean fitness is recorded as
the fitness of the initial chromosome.

For the case of $t>0$, the similarity learning process proceeds with updating
the mutation vector (lines 9–11). As already discussed, each entry in the
mutation vector estimates the expected fitness of its corresponding model
relative to the target problem and is measured by taking the average fitness
of candidate solutions that have been sampled from that model. The average
fitness to a source model is updated each time a new solution is added. This
is done incrementally in a constant time without the need to keep the previous
solutions in memory. Assume that the mutation entry $\pi[s]$, corresponding to
the source model $p^{*}_{s}(\boldsymbol{x})$, holds the average fitness over
the first $i-1$ solutions; the updated average after adding the $i$th
candidate solution $\boldsymbol{x}_{i}$ sampled from
$p^{*}_{s}(\boldsymbol{x})$ is calculated as follows,

$\pi[s]\leftarrow\pi[s]+\frac{f_{T}(\boldsymbol{x}_{i})-\pi[s]}{i}.$ (5)

Note that unlike the source probabilistic models which remain fixed during the
target optimization, the target model is non-stationary and is rebuilt each
time the source-target similarity learning procedure is launched. This hinders
the incremental update of the average fitness (as done for the source models)
from being applied to the target. However, since the solutions to build the
target model are evaluated in the main sTrEO procedure before being passed to
the (1+1)-ES, it is possible to compute their mean fitness $\bar{f}_{T,t}$
beforehand and pass it along with the target population $P_{t}$ to Procedure
1.

Thereafter, a two-stage transformation is carried out on the mutation vector
to help online source-target similarity to be captured more efficiently and
effectively. This is realized by applying the _maximum absolute scaling_ and
_softmax_ functions, respectively (lines 13 and 15). Here, the softmax
function is used with _temperature_ $(\lambda)$, a hyper-parameter to affect
the final generated probabilities. Lowering the temperature imposes more
contrast across sources based on their relevance to the target problem.
Eventually, mutation is carried out in line 16 to generate the offspring from
the parent chromosome and mutation vector. A _learning rate_ ($\eta$) in the
interval $[0,1]$ is used to determine the step-size of transfer coefficient
updates in the offspring.

The updated transfer coefficients in the offspring form a new mixture model
that should be used to generate new candidate solutions. This, however, is
deferred until a neutralization function is carried out on each element of the
offspring (line 18). If the value is below a positive neutralization threshold
($\varepsilon$), then the entry (which entails the transfer coefficient to a
source model) is neutralized to zero, meaning that the corresponding source is
identified unrelated and hence, should not be sampled for the remaining
generations. The rationale behind such adjustment lies in the Monte Carlo
sampling method being used, as it ensures that at least one sample is
generated from every source model whose corresponding transfer coefficient is
positive (no matter how close the value is to zero). Consequently, in
situations where the number of sources is significantly greater than the
population size, there could be no chance for those models with a slightly
larger transfer coefficient to have their sample(s) chosen as candidate
solutions for transfer. In this regard, neutralizing the sources with
extremely low transfer coefficients is deemed an effective strategy to remedy
this undesirable property.

The last part of the code, i.e., lines 25–30, deals with evolution in which
the parent $w_{t-1}[1:T]$ at iteration $t-1$ is replaced with the offspring
$w^{\prime\prime}[1:T]$ if its fitness $\bar{f}_{t-1}$ is not better than the
offspring’s fitness $\bar{f}^{\prime}$. Note that all solutions in $X_{t}$
(line 23) are returned to the main sTrEO procedure (line 31) to guide the
target search process.

###  III-B Target Solutions Evolution in sTrEO

Our proposed (1+1)-ES can be incorporated as a nested module within any
canonical or state-of-the-art EA to optimize the target task. Procedure 2
presents such integration for a canonical genetic algorithm (CGA) in
pseudocode. In this setting, _transfer interval_ ($\Delta$) is the frequency
of calling the source-target similarity learning module in number of
generations. Upon the call, the (1+1)-ES advances for one generation.

According to the procedure, after the initial population is configured and
evaluated (lines 1 and 2), the iterative routine to optimize the target
solutions follows two different branches of evolution. Whenever knowledge
transfer occurs, the offspring is formed from the candidate solutions returned
by Procedure 1 (lines 6–9). Otherwise, it is generated by applying the common
reproduction operators (line 11). After being evaluated, the offspring is
combined with the current population to form the next generation by using a
selection mechanism (lines 12 and 13). Note that before Procedure 1 is
launched in line 8, the mean fitness of solutions in the current population is
computed in line 7 and passed as the input parameter ($\bar{f}_{T,t}$) along
with the transfer counter $t$ to Procedure 1. The above steps continue until
some stopping criteria are eventually met.

Input: Target task $\mathcal{T}_{T}$, transfer interval $\Delta$;

Output: Optimized target probabilistic model;

1 Configure initial population $P_{0}$ at random;

2 Evaluate solutions in $P_{0}$;

$i\leftarrow 0$ ;

/* generation counter */

$t\leftarrow 0$ ;

/* transfer counter */

3 while  _stopping criteria not satisfied_ do

4 if  _$mod(i,\Delta)==0$ and $i>1$_ then

5 $\bar{f}_{T,t}\leftarrow$ mean fitness of solutions in $P_{i}$;

6 Call Procedure 1 to form offspring $O$;

7 $t\leftarrow t+1$;

8

9 else

10 Generate offspring $O$ by reproduction of $P_{i}$;

11

12 Evaluate solutions in $O$;

13 Select next population $P_{i+1}$ from $P_{i}\cup O$;

14 $i\leftarrow i+1$;

Procedure 2 Pseudocode of sTrEO for a CGA

###  III-C Complexity Comparison of sTrEO

The learning process of the transfer coefficients in the sTrEO is carried out
by the mutation mechanism of the (1+1)-ES. To this end, the $T$ entries in the
mutation vector are updated each time a new candidate solution is added from
the mixture model. According to (5), this is done in a constant time per added
solution, which, overall, requires $\mathcal{O}(n)$ computational steps for
$n$ solutions. (Note that computing the mean fitness of the target population,
to update the last entry of the mutation vector, also requires
$\mathcal{O}(n)$ steps for a population size of $n$.) Thereafter, the two-
stage transformation as well as the generation of the offspring (that encodes
the updated transfer coefficients) are carried out in $\mathcal{O}(T)$. Thus,
the total complexity of the mutation mechanism becomes $\mathcal{O}(n+T)$. As
is clear, the (1+1)-ES, and hence the sTrEO as a whole, scales much more
efficiently than the existing AMTEA with the learning complexity
$\mathcal{O}(dnT)$.

##  IV Experimental Study

We conducted extensive experiments to assess the performance of sTrEO with
regard to _scalability_ and _online learning agility_ across a set of
practically motivated discrete and continuous optimization examples. Following
our complexity analysis in Section II-B, we should note that the single layer
autoencoder method proposed in [7] and [8] requires archiving the solutions
data of all source instances for all generations, to construct the mapping
function whenever the source-target similarity learning procedure is launched.
This entails a significantly large and growing memory cost for evaluation
scenarios with 1000 sources and beyond. As a more practically feasible
alternative, we compare sTrEO with state-of-the-art probabilistic model-based
transfer methods that only need to store the learned search distribution
models, which comprises only few distribution parameters and hence consumes
low memory. Our comparative evaluations are accordingly conducted against
AMTEA [32] and the MAB-enabled AMTEA (i.e., MAB-AMTEA) [33] methods, along
with a number of modern solvers without transfer capability. This includes a
canonical GA (CGA) enhanced with a local solution repair heuristic for
discrete optimization and two powerful variants of the recently proposed
_natural evolution strategies_ (NESs) [36], namely sNES and xNES, for
continuous examples.

###  IV-A Experimental Setup

All the compared algorithms were implemented in Python 3.7111The source code
is available at https://github.com/erfanMhi/Transfer-Optimization. and run on
a 64-bit Intel(R) Core${}^{\textrm{TM}}$ i7-7700HQ with 4 cores and 8 logical
processors. The OS was Ubuntu 20.04 with 16GB memory. Throughout all
experiments, we used an _elitist_ selection strategy in the three transfer
evolutionary algorithms, i.e., AMTEA, MAB-AMTEA and sTrEO, as well as the CGA.
The (unified) search space representation together with the choice of
probabilistic models were determined according to the characteristics of the
underlying problem. For discrete optimization, the following general settings
were adopted in our compared algorithms:

  1. 1.

Representation: binary coded.

  2. 2.

Population size: $50$.

  3. 3.

Maximum function evaluations: $5000$.

  4. 4.

Evolutionary operators:

    1. (a)

uniform crossover with probability $\rho_{c}=1$,

    2. (b)

bit-flip mutation with probability $\rho_{m}=1/d$, where $d$ is the chromosome
length.

  5. 5.

Probabilistic model: univariate marginal frequency (factored Bernoulli
distribution) [41].

On the other hand, for the chosen set of continuous optimization examples, the
following configuration was used:

  1. 1.

Representation: real-valued coded.

  2. 2.

Population size: $50$.

  3. 3.

Maximum function evaluations: $5000$.

  4. 4.

Evolutionary operators for AMTEA, MAB-AMTEA and sTrEO:

    1. (a)

simulated binary crossover [42] with $\rho_{c}=1$ and distribution index
$\eta_{c}=10$,

    2. (b)

polynomial mutation [43] with $\rho_{m}=1/d$ ($d$ is the chromosome length)
and distribution index $\eta_{m}=10$.

  5. 5.

Probabilistic model: multivariate Gaussian distribution [44].

For fairness of comparison, we considered identical population size and
maximum function evaluations for both sNES and xNES algorithms. The other
parameters of the two solvers were configured with default settings from [45].
Note that the above configuration was adopted following the experimental study
carried out in [32] for the assessment of the AMTEA approach. With regard to
assessing the MAB-AMTEA, there is an egalitarianism factor $\gamma$ in the
EXP3 that was set to $0.1$ according to [33].

As can be recalled from Section III, we introduced four hyper-parameters to
control the sTrEO as follows:

  * •

Temperature $(\lambda)$ affects the final probabilities generated by the
softmax function in the mutation vector in the (1+1)-ES algorithm, contrasting
source models based on their relevance to the target problem.

  * •

Learning rate $(\eta)$ determines the step-size of transfer coefficient
updates in the (1+1)-ES algorithm.

  * •

Neutralization threshold $(\varepsilon)$ is the minimum value of the transfer
coefficient for any source task to be considered for knowledge extraction in
the (1+1)-ES algorithm.

  * •

Transfer interval $(\Delta)$ is the frequency of launching the nested (1+1)-ES
algorithm in the main target procedure.

Sensitivity analyses were conducted to identify an appropriate yet general
setting for each hyper-parameter. The relevant experimental study is presented
in Section S.I in the supplemental material. The resultant configuration is
shown in Table I. Note that the neutralization threshold ($\varepsilon$) is a
function of $T$ which is the total number of probabilistic models including
the target model. Lastly, we should note that the setting for the transfer
interval also applies to both AMTEA and MAB-AMTEA.

TABLE I: Hyper-parameter setting for the (1+1)-ES. Hyper-parameter |  Setting
---|---
Temperature $(\lambda)$ |  $0.01$
Learning rate $(\eta)$ |  $0.9$
Neutralization threshold $(\varepsilon)$ |  $\frac{10^{-2}}{T}$
Transfer interval $(\Delta)$ |  $2$

###  IV-B The Discrete 0/1 Knapsack Problem

The knapsack problem (KP) is a well-known NP-hard problem in combinatorial
(discrete) optimization and has been studied extensively by the operations
research community. There are many variations of the problem with applications
in supply chain and logistics optimization, recommender systems, wireless
communications and investment decision making, among many others. The basic
version of the problem is the 0/1 KP in which there are $d$ number of items
(representing the problem dimensionality), each with a value $v_{i}$ and a
weight $w_{i}$, and a knapsack of a finite capacity $C$. The objective is to
find a subset of items such that they can be placed into the knapsack while
their total value is maximized. We can formulate the problem mathematically as
follows,

$\displaystyle\begin{gathered}\max\sum_{i=1}^{d}v_{i}x_{i}\\\ \textrm{s.t.
}\sum_{i=1}^{d}w_{i}x_{i}\leq C,\textrm{ and
}x_{i}\in\\{0,1\\},\end{gathered}$ (8)

where, $x_{i}$ is a binary decision variable and equals $1$ if the $i$th item
is selected and $0$, otherwise. It should be noted that solving KP instances
using EAs may cause the capacity constraint to be violated for some
individuals during the course of evolution. On such occasions, a repair
mechanism is invoked to satisfy the constraint in accordance with Dantzig’s
greedy approximation algorithm [46].

We generate synthetic KP instances with same characteristics as [32] and [33].
Depending on the relationships between $w_{i}$ and $v_{i}$, the instances are
randomly generated following three categories: (1) _uncorrelated_ (un), where
$w_{i}=$ uniformly random real number $[1,10]$ and $v_{i}=$ uniformly random
real number $[1,10]$; (2) _weakly correlated_ (wc), where $w_{i}=$ uniformly
random real number $[1,10]$ and $v_{i}=w_{i}+$ uniformly random real number
$[-5,5]$ (if, for some $i$, $v_{i}\leq 0$, the value is ignored and sampling
is repeated until $v_{i}>0$); and (3) _strongly correlated_ (sc), where
$w_{i}=$ uniformly random real number $[1,10]$ and $v_{i}=w_{i}+5$. The second
categorization defines two types of knapsacks: (1) _restrictive capacity_
(rc), where $C=20$; and (2) _average capacity_ (ac), where
$C=0.5\sum_{i=1}^{d}w_{i}$.

The knapsack problem types introduced above are representatives of _composite
recommendations_ [35] where each recommendation comprises a set of items with
a value (rating) and a cost. Any recommended set of items is associated with a
maximum total cost (budget) specified by the user where the constraint on the
maximum number of items recommended can model the restrictive knapsack. In
this setting, every query raised by any user is deemed to be an optimization
problem instance. We define a $d=1000$-D KP configuration in which the target
is “KP_uc_ac” and the source instance types are “KP_uc_rc”, “KP_wc_rc”,
“KP_sc_rc” and “KP_sc_ac”. Here, the related source type is “KP_sc_ac”
implying that a relatively large number of items need to be selected as also
must be done for the target.

(a) Convergence trends (250 related)

(b) Convergence trends (40 related)

(c) Convergence times (250 related)

(d) Convergence times (40 related)

Figure 2: Averaged performance results over 30 independent runs for the 0/1
knapsack problem with 1000 source instances. Convergence trends relative to
the number of function evaluations for (a) 250 related sources and (b) 40
related sources. Convergence trends relative to sTrEO’s convergence time for
(c) 250 related sources and (d) 40 related sources. The shaded region
indicates standard deviations either side of the mean.

(a) AMTEA’s learned $w_{s}$’s (250 related)

(b) sTrEO’s learned $w_{s}$’s (250 related)

(c) AMTEA’s learned $w_{s}$’s (40 related)

(d) sTrEO’s learned $w_{s}$’s (40 related)

Figure 3: Learned transfer coefficients of AMTEA and sTrEO while solving the
0/1 knapsack problem with 1000 sources. The target is “KP_uc_ac” and the
source types are “KP_uc_rc”, “KP_wc_rc”, “KP_sc_rc” and “KP_sc_ac”. (a)
AMTEA’s learned $w_{s}$’s with 250 related sources. (b) sTrEO’s learned
$w_{s}$’s with 250 related sources. (c) AMTEA’s learned $w_{s}$’s with 40
related sources. (d) sTrEO’s learned $w_{s}$’s with 40 related sources.
Results were averaged over 30 independent runs. The shaded region indicates
standard deviations either side of the mean.

Two evaluation scenarios were defined to investigate the performance of sTrEO
with respect to scalability and online learning agility. The scenarios are
described as follows:

  * •

_Scenario (A):_ where the number of sources is $1000$ with $250$ instances of
the related type and $750$ instances equally distributed among the three
unrelated types (the source-target relatedness ratio is $0.25$).

  * •

_Scenario (B):_ where the number of sources is $1000$ with only $40$ instances
of the related type and $960$ instances equally distributed among the three
unrelated types (the source-target relatedness ratio is $0.04$).

All source instances were first optimized by a binary CGA where the final
derived solutions were used to construct the probabilistic models. We then
compared the performance of our proposed sTrEO with CGA, AMTEA, MAB-AMTEA for
both evaluation scenarios. The averaged results obtained over 30 independent
runs are shown in Fig. 2. With respect to convergence efficiency, Figs. 2(a)
and 2(b) present the convergence trends of the compared algorithms for
Scenario (A) with 250 related sources and Scenario (B) with 40 related
sources, respectively. It can be seen from the convergence trends that
utilization of relevant knowledge from previously solved experiences in
essence does improve optimization efficiency in the target problem. The
effectiveness in learning source-target similarities, is more noticeable for
AMTEA and sTrEO given that both acquire a steeper convergence curve than MAB-
AMTEA in early function evaluations. The reason for such different convergence
trends lies in how agile the online source-target similarity learning
mechanism of the compared methods is to discern related sources and exploit
useful knowledge accordingly. We can therefore conclude that MAB-AMTEA fails
to reach that level of agility as opposed to AMTEA and sTrEO. This is more
evident for Scenario (B) given sparsity of relevant sources. The advantage of
such capability (i.e., to achieve convergence in fewer number of function
evaluations) would be more significant for applications where the evaluation
of the objective function is very costly.

(a) Kinematic Arm

(b) 10 joints

(c) 20 joints

Figure 4: (a) A planar robotic arm with three joints (and equal links) [47].
The objective is to find the angle of each joint (here,
$\alpha_{1},\alpha_{2},\alpha_{3}$) such that the end-effector is as close as
possible to a predefined target in the plane. Heatmaps of source-target
relatedness for diverse combinations of $L$ and $\alpha_{\textrm{max}}$,
ranging between $(0,\sqrt{2})$ and $(0,1]$, respectively, for (b) $10$ joints
and (c) $20$ joints. According to the sidebar on the right which marks the
fitness range, the hotter cells indicate more relatedness to the target (as
their mean fitness values are greater) whereas the colder ones show less or no
relatedness.

We also present the convergence trend of the three compared TrEO methods
within the convergence time of sTrEO as shown in Figs. 2(c) and 2(d) for
Scenarios (A) and (B), respectively. While the MAB-AMTEA is able to converge
within this time limit222Note that the rationale behind proposing MAB-AMTEA in
[33] is to tackle the scaling burden of AMTEA when exposed to big task-
instances., AMTEA falls much behind the other two and requires a considerably
longer time to eventually converge to optimality, particularly for Scenario
(B) with the fewer number of relevant sources. The above observations indicate
that neither AMTEA nor MAB-AMTEA are able to ensure scalability as well as
online learning agility _simultaneously_. The AMTEA lacks scalability due to
its computationally intensive EM-based source-target similarity learning
module whereas the MAB-AMTEA’s source selection strategy, based on the EXP3,
is not effective to quickly identify and utilize related sources. Lastly, we
present the trajectory of the learned transfer coefficients of AMTEA and sTrEO
(aggregated per source knapsack type) in Fig. 3. As can be seen from Figs.
3(a) to 3(d), sTrEO can learn qualitatively similar trends of transfer
coefficient values as AMTEA. (Recall that AMTEA is provably optimal whereas
sTrEO follows a randomized (1+1)-ES procedure.) The results show that despite
compromising on optimality, sTrEO achieves comparable performance, while
simultaneously achieving significantly lower computational cost.

###  IV-C Robotic Arm with Variable Morphology

We consider a planar robotic arm adopted from [47] as our second case study.
In this setting, there is an arm of length $L$ with $d$ joints as equal as the
number of its links. (Here $d$ specifies the dimensionality of the problem.)
Each joint can rotate to a maximum angle $\alpha_{\textrm{max}}$, encoded in
$(0,1]$, which is the same for all joints. Further, all the links have the
identical length (here, $L^{\prime}$). The problem objective is to find the
angle of each joint of the robot (i.e., $\alpha_{1},\dots,\alpha_{d}$) such
that the tip of the arm (i.e., the end-effector) is as close as possible to a
predefined target in the plane (see Fig. 4(a)).

We identify a task $\mathcal{T}$ by a particular combination of $L$ and
$\alpha_{\textrm{max}}$ in which a candidate solution is encoded by a vector
$\boldsymbol{\alpha}=\alpha_{1},\dots,\alpha_{d}$. The objective function
$f(\boldsymbol{\alpha},\mathcal{T}_{L,\alpha_{\textrm{max}}})$ to evaluate the
solution $\boldsymbol{\alpha}$ to the task
$\mathcal{T}_{L,\alpha_{\textrm{max}}}$ computes the Euclidean distance from
the tip position $p_{d}$ to the target position $T$. The $p_{d}$ can be
obtained recursively as follows [47]:

$M_{0}=I,$ (9)
$M_{i}=M_{i-1}\cdot\begin{pmatrix}\cos{\alpha^{\prime}_{i}}&-\sin{\alpha^{\prime}_{i}}&0&L^{\prime}\\\
\sin{\alpha^{\prime}_{i}}&\cos{\alpha^{\prime}_{i}}&0&0\\\ 0&0&1&0\\\
0&0&0&1\end{pmatrix},$ (10) $p_{i}=M_{i}\cdot(0,0,0,1)^{\intercal},$ (11)

where,
$\alpha^{\prime}_{i}=2\pi\cdot\alpha_{\textrm{max}}\cdot(\alpha_{i}-0.5)$,
$\forall i\in\\{1,\dots,d\\}$ and $L^{\prime}=L/d$. Given the above, the
objective function, which calculates the distance between the end of the last
link and the target position, can be presented as,

$f(\boldsymbol{\alpha},\mathcal{T}_{L,\alpha_{\textrm{max}}})=-\parallel
p_{d}-T\parallel.$ (12)

Here, we arbitrary set the target $T$ to $(1,1)$ in the plane. Note that the
objective function is negated in (12) so that the problem can be treated as
one of maximization.

We consider two different scenarios with $10$ and $20$ joints in the
experiments. The target task is defined as $\mathcal{T}_{\sqrt{2},1}$ for both
settings, ending up with the largest solution space possible as each joint can
rotate from $\scalebox{0.5}[1.0]{$-$}\pi$ to $\pi$. To identify the sources
and their relatedness to the target, we defined $1000$ source instances with
diverse combinations of $L$ and $\alpha_{\textrm{max}}$, ranging between
$(0,\sqrt{2})$ and $(0,1]$, respectively. One of the sources was first
optimized by a continuous CGA where the final derived solutions were used to
build the probabilistic model. The probabilistic models of the remaining
sources were built after successively utilizing the AMTEA to optimize one
source instance by exploiting the already solved ones. We then sampled $100$
solutions from each source model and evaluated them using the objective
function of the target task. The average objective value to each source forms
a cell of a heatmap, as shown in Figs. 4(b) and 4(c) for $10$ and $20$ joints,
respectively. Here, the hotter cells indicate more relatedness to the target
(as their mean fitness values are greater) whereas the colder ones show less
or no relatedness. Having identified how source-target relatedness is shaped
for each scenario, we randomly chose $15$ instances with $0<L<\sqrt{2}$ and
$\alpha_{\textrm{max}}=1$ as _related_ and $985$ ones with $0<L<\sqrt{2}$ and
$0.18<\alpha_{\textrm{max}}<0.26$ as _unrelated_ to form a total of $1000$
sources per scenario. We followed the same procedure, as already outlined
above, to build the probabilistic models of the sources.

Given that the source-target similarity learning module described in Procedure
1 is for the case of a maximization problem, we need some refinements to apply
sTrEO for the examples whose underlying optimization problem is one of
minimization and $\scalebox{0.5}[1.0]{$-$}f_{T}(\boldsymbol{x})$ is
alternatively being used. The first amendment is on the initial values of the
mutation vector. Rather than setting all the values to zeroes, we initialize
the mutation vector with a _lower bound_ on the fitness value of the target
problem. For the robotic arm case study, this was set to the fitness value of
the worst feasible solution to the target, which is
$\scalebox{0.5}[1.0]{$-$}2\sqrt{2}$ when the the tip of the arm falls in the
opposite direction to the target position. Such adjustment led to more
effective exploitation of related sources as derived from our preliminary
experiments. The second amendment is to shift the values of the mutation
vector to the range $[0,+\infty)$ before applying the maximum absolute scaling
function in line 13 in Procedure 1. This is done by adding all entries by the
absolute value of their minimum.

(a) Convergence trends (10 joints)

(b) Convergence trends (20 joints)

(c) Convergence times (10 joints)

(d) Convergence times (20 joints)

Figure 5: Averaged performance results over 30 independent runs for the
robotic arm example. The target task is $\mathcal{T}_{\sqrt{2},1}$. There are
1000 source instances, 15 of which are related. Convergence trends relative to
the number of function evaluations for (a) 10 joints and (b) 20 joints.
Convergence trends relative to sTrEO’s convergence time for (c) 10 joints and
(d) 20 joints. The shaded region indicates standard deviations either side of
the mean.

The performance of sTrEO was compared with sNES and xNES, as algorithms
without transfer capability, in addition to AMTEA and MAB-AMTEA for both 10-
and 20-joint evaluation scenarios. A penalty function is embedded in all the
compared algorithms to penalize those solutions that violate the
$\alpha_{\textrm{max}}$ constraint. The averaged results obtained over 30
independent runs are shown in Fig. 5. With regard to convergence efficiency,
Figs. 5(a) and 5(b) present the convergence trends of the compared algorithms
for $10$ and $20$ joints, respectively. Both plots strongly advocate the
advantage of knowledge transfer to improve optimization efficiency, making
possible the convergence to optimality within a limited computational budget.
Aside from that, we can notice a small spike in averaged objective values in
early function evaluations of sTrEO, further validating our previous findings
on online learning agility of the nested (1+1)-ES relative to sparsity of
related sources. Similar to the previous case study, we analyzed the
scalability of sTrEO against AMTEA and MAB-AMTEA by presenting the convergence
trend of the three algorithms within STrEO’s convergence time, as shown in
Figs. 5(c) and 5(d) for 10 and 20 joints, respectively. Interestingly, while
consistent results can be observed given the computational efficiency of
sTrEO, we can notice that the MAB-AMTEA, despite being scalable, fails at
establishing optimality within STrEO’s convergence time. This indicates that
the bandit-based source selection mechanism to stack only a single source
model to the target each time the similarity learning procedure is launched is
not effective to quickly utilize relevant sources to ensure optimality.

(a) Convergence trends

(b) Convergence times

Figure 6: Averaged performance results over $30$ independent runs for the
20-joint robotic arm example. The target task is $\mathcal{T}_{\sqrt{2},1}$.
There are 10000 source instances, 150 of which are related. Convergence trends
relative to (a) number of function evaluations and (b) sTrEO’s convergence
time. The shaded region indicates standard deviations either side of the mean.

Further experiments were carried out in Section S.II in the supplemental
material to investigate the performance of sTrEO for more than 1000 source
task-instances on the robotic arm with 20 joints. We leave out the details
herein for the sake of brevity and present the results (averaged over 30
independent runs) for the total of 10000 sources with 150 related instances in
Fig. 6. With respect to convergence efficiency, we can see from Fig. 6(a) that
both AMTEA and sTrEO are able to utilize related sources in early function
evaluations, further validating their online learning agility when exposed to
big source task-instances with sparse related sources. With regard to
scalability of the three compared TrEO algorithms, Fig. 6(b) shows their
convergence trend within sTrEO’s convergence time. It can be observed that
unlike AMTEA, sTrEO’s computational complexity is as efficient as MAB-AMTEA
(despite the latter’s failure in converging to optimality). AMTEA requires
much longer time to converge to optimality. Following the above analysis, we
can conclude that our proposed sTrEO is able to _simultaneously_ ensure
scalability and online learning agility _beyond_ 1000 source task-instances.

###  IV-D Double Pole Balancing Controller System

Double pole balancing is a prototypical control problem commonly used as a
case study for neuro-evolutionary and reinforcement learning algorithms. In
this setting, two poles are hinged at the same point to a wheeled cart on a
finite length track. The goal is to keep both poles balanced indefinitely by
applying a force to the cart at regular intervals without causing the cart to
move beyond the track boundaries. The task is more difficult than the basic
single pole problem due to nonlinear interactions incurred between the two
poles [48].

Six variables are defined to represent the state of the system: the angle of
each pole from vertical, the angular velocity of each pole, the position of
the wheeled cart on the track, and the velocity of the cart [49]. Regarding
the length of the two poles, the long one is fixed to $1$ meter whereas the
short one is variable (denoted by $l$) and indicates a task $e_{l}$ under
evaluation. The system is simulated according to the steps instructed in [32].
In this setting, a feedforward neural network (FNN), whose structure remains
fixed during the simulation, is used to output a force to the wheeled cart
periodically. The conditions for the system failure are either the cart goes
out of the track boundaries or one of the two poles loses its balance and
drops beyond a certain degree from the vertical. Here, a candidate chromosome
represents the connection weights of neurons of the FNN controller and is
assessed by measuring the number of time steps elapsed before the system
fails. Clearly, the solution quality (fitness) is higher for longer time
steps. We assert that a task is solved if a solution could be found such that
its fitness is greater than a specified number of time steps. Following [32],
this value was set to $100,000$ time steps in our experiments, which is over
$30$ minutes in simulated time. The architecture of the FNN controller is
identical to one applied in [32], i.e., a two-layer network with ten hidden
neurons and no bias parameters. This forms a total of 70 weights encoded in
the solution chromosome of the evolutionary optimizer.

An established fact concerning the double pole system is that the problem
becomes harder to solve when the two poles are very close in length (here,
$l$, the length of the shorter pole, approaches $1$m, which is the length of
the longer pole). Previous studies suggest incremental learning techniques in
which the length of the shorter pole is increased very gradually and then the
resultant problem is solved incrementally [49]. The analogy between such
incremental problem solving and transfer optimization paradigm was realized in
[32] to successfully apply the AMTEA to solve more difficult variants of the
problem by utilizing the solutions to easier solved ones. Accordingly, we
consider this practical problem as our third case study to assess how
effective our proposed sTrEO is at solving increasingly intractable variants
of this problem. In this regard, we aim at tackling $e_{0.825}$ as the target
problem by building up source task-instances with an ascending order of
difficulty starting from $e_{0.1}$ through $e_{0.775}$.

TABLE II: Performance comparison of sTrEO against sNES, xNES, AMTEA and MAB-AMTEA for the double pole balancing problem with $l=0.825$. Methods |  Successes |  Function Evaluations
---|---|---
sNES |  $0/50$ |  NA
xNES |  $0/50$ |  NA
AMTEA |  $34/50$ |  $3739\pm 939$
MAB-AMTEA |  $7/50$ |  $4156\pm 972$
sTrEO |  $35/50$ |  $3108\pm 993$

(a) AMTEA’s learned $w_{s}$’s

(b) sTrEO’s learned $w_{s}$’s

Figure 7: Learned transfer coefficients of (a) AMTEA and (b) sTrEO for the
double pole balancing problem with $l=0.825$. Results were averaged over
successful runs. The shaded region indicates standard deviations either side
of the mean.

To construct the optimized source probabilistic models, we first utilized a
continuous CGA to solve $e_{0.1}$. Thereafter, the AMTEA was applied to solve
the next instances in ascending order of $l$ by utilizing the previously
solved ones. Following [32], we adopt success rate as the performance metric
for our experimental study. It is measured by counting the number of runs that
each method is able to solve the problem relative to the total number of runs.
We compared sTrEO with sNES, xNES, AMTEA and MAB-AMTEA by launching each for
50 independent runs. Table II shows the success rate as well as the number of
function evaluations averaged over successful runs for the compared
algorithms. According to the table, neither sNES nor xNES are able to achieve
success in any of their 50 independent runs, revealing the inherent difficulty
of $e_{0.825}$. Conversely, both AMTEA and sTrEO can achieve significantly
higher success rates but with noticeably different number of function
evaluations, with that of sTrEO being fewer. The MAB-AMTEA, on the other hand,
succeeded for only 7 runs, requiring a considerably higher number of
evaluations than AMTEA and, in particular, sTrEO. Such notable performance of
sTrEO is mainly due to online learning agility of its (1+1)-ES based source-
target similarity leaning module, as showcased for the other two case studies.
Lastly, we present the learned transfer coefficients of AMTEA and sTrEO
averaged over their successful runs for seven mostly related sources in Figs.
7(a) and 7(b), respectively. By observing the two trajectories, we can
conclude that sTrEO is able to learn qualitatively similar trends of transfer
coefficient values as AMTEA but with significantly lower computational cost.

##  V Conclusion

This paper proposed a novel approach for scalable transfer evolutionary
optimization, _simultaneously_ overcoming two critical shortcomings of today’s
transfer evolutionary optimization frameworks, namely (1) lack of
_scalability_ when faced with a growing number of source task-instances and
(2) lack of _online learning agility_ against sparsity of relevant sources to
the target task. While applications of existing algorithms are limited to tens
of source tasks, in this paper, we took a quantum leap forward to handle
scenarios beyond 1000 source task-instances. We devised a scalable transfer
evolutionary optimization framework, under the label of sTrEO, which comprises
two co-evolving species for joint evolutions in the space of source knowledge
and in the search space of solutions to the target problem. We were able to
empirically verify the efficiency and effectiveness of sTrEO from two aspects
of scalability and online learning agility across a set of practically
motivated discrete and continuous optimization examples. Such notable
performance arises due to,

  1. 1.

the scalability of the (1+1)-ES algorithm nested in sTrEO with the number of
source instances, as only one individual evolves per generation and mutation
is the sole reproduction operation;

  2. 2.

the novel mutation mechanism employed in the (1+1)-ES that quickly captures
source-target similarities during the course of optimization. This is realized
by estimating the expected fitness of source probabilistic models relative to
the target objective function, enabling their exploration and exploitation;

  3. 3.

the proposed neutralization strategy in the (1+1)-ES that effectively filters
out unrelated sources.

Notably, estimating the expected fitness of each source probabilistic model
relative to the target objective function enables source-target similarity
matching to be carried out in an offline mode (as was done for the robotic arm
example to construct the similarity heatmaps) given a unified search space and
known target objective function.

As future work, we intend to generalize sTrEO to a wider variety of real-world
optimization problems in domains of manufacturing and operations research
characterized by different solution representations; e.g., graph-based
representations, scheduling problems, etc. In all such cases, sTrEO would be
designed to be immersed in and leverage environments with as many as millions
of prior optimization experiences (e.g., those derived from historical
databases of interconnected, distributed micro-factories). We will also
investigate how our proposed transfer optimization framework can be extended
to support _evolutionary multitasking_ where mutual exchange of knowledge
takes place among a set of tasks being simultaneously solved [50, 51].
Notably, there is growing interest in large-scale multitasking where task
numbers in the order of tens, hundreds or even thousands jointly occur [52,
53], hence, providing a stage for our scalable transfer methods to excel at
addressing tractability concerns.

## References

  * [1] Y.-S. Ong and A. Gupta, “Air 5: Five pillars of artificial intelligence research,” _IEEE Transactions on Emerging Topics in Computational Intelligence_ , vol. 3, no. 5, pp. 411–415, 2019.
  * [2] A. Gupta, Y.-S. Ong, and L. Feng, “Insights on transfer optimization: Because experience is the best teacher,” _IEEE Transactions on Emerging Topics in Computational Intelligence_ , vol. 2, no. 1, pp. 51–64, 2017.
  * [3] J. C. Wong, A. Gupta, and Y.-S. Ong, “Can transfer neuroevolution tractably solve your differential equations?” _IEEE Computational Intelligence Magazine_ , vol. 16, no. 2, pp. 14–30, 2021.
  * [4] K. C. Tan, L. Feng, and M. Jiang, “Evolutionary transfer optimization-a new frontier in evolutionary computation research,” _IEEE Computational Intelligence Magazine_ , vol. 16, no. 1, pp. 22–33, 2021.
  * [5] A. Gupta and Y.-S. Ong, _Memetic Computation: The Mainspring of Knowledge Transfer in a Data-Driven Optimization Era_. Springer, 2018, vol. 21.
  * [6] A. T. W. Min, Y.-S. Ong, A. Gupta, and C.-K. Goh, “Multiproblem surrogates: Transfer evolutionary multiobjective optimization of computationally expensive problems,” _IEEE Transactions on Evolutionary Computation_ , vol. 23, no. 1, pp. 15–28, 2017.
  * [7] L. Feng, Y.-S. Ong, S. Jiang, and A. Gupta, “Autoencoding evolutionary search with learning across heterogeneous problems,” _IEEE Transactions on Evolutionary Computation_ , vol. 21, no. 5, pp. 760–772, 2017.
  * [8] J. Zhang, W. Zhou, X. Chen, W. Yao, and L. Cao, “Multi-source selective transfer framework in multi-objective optimization problems,” _IEEE Transactions on Evolutionary Computation_ , 2019.
  * [9] L. Feng, Y.-S. Ong, M.-H. Lim, and I. W. Tsang, “Memetic search with interdomain learning: A realization between cvrp and carp,” _IEEE Transactions on Evolutionary Computation_ , vol. 19, no. 5, pp. 644–658, 2014\.
  * [10] L. Feng, Y.-S. Ong, A.-H. Tan, and I. W. Tsang, “Memes as building blocks: a case study on evolutionary optimization+ transfer learning for routing problems,” _Memetic Computing_ , vol. 7, no. 3, pp. 159–180, 2015.
  * [11] M. A. Ardeh, Y. Mei, and M. Zhang, “A novel genetic programming algorithm with knowledge transfer for uncertain capacitated arc routing problem,” in _Pacific Rim International Conference on Artificial Intelligence_. Springer, 2019, pp. 196–200.
  * [12] R. Lim, Y.-S. Ong, H. T. H. Phan, A. Gupta, and A. N. Zhang, “Can route planning be smarter with transfer optimization?” in _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ , 2019, pp. 318–319.
  * [13] M. Jiang, Z. Huang, L. Qiu, W. Huang, and G. G. Yen, “Transfer learning-based dynamic multiobjective optimization algorithms,” _IEEE Transactions on Evolutionary Computation_ , vol. 22, no. 4, pp. 501–514, 2017.
  * [14] X.-F. Liu, Z.-H. Zhan, T.-L. Gu, S. Kwong, Z. Lu, H. B.-L. Duh, and J. Zhang, “Neural network-based information transfer for dynamic optimization,” _IEEE transactions on neural networks and learning systems_ , 2019.
  * [15] M. Jiang, Z. Wang, S. Guo, X. Gao, and K. C. Tan, “Individual-based transfer learning for dynamic multiobjective optimization,” _IEEE Transactions on Cybernetics_ , 2020.
  * [16] F. Zhang, Y. Mei, S. Nguyen, M. Zhang, and K. C. Tan, “Surrogate-assisted evolutionary multitask genetic programming for dynamic flexible job shop scheduling,” _IEEE Transactions on Evolutionary Computation_ , 2021.
  * [17] F. Zhang, Y. Mei, S. Nguyen, K. C. Tan, and M. Zhang, “Multitask genetic programming-based generative hyperheuristics: A case study in dynamic scheduling,” _IEEE Transactions on Cybernetics_ , 2021.
  * [18] M. Iqbal, W. N. Browne, and M. Zhang, “Extracting and using building blocks of knowledge in learning classifier systems,” in _Proceedings of the 14th annual conference on Genetic and evolutionary computation_ , 2012, pp. 863–870.
  * [19] ——, “Reusing building blocks of extracted knowledge to solve complex, large-scale boolean problems,” _IEEE Transactions on Evolutionary Computation_ , vol. 18, no. 4, pp. 465–480, 2013.
  * [20] M. Iqbal, B. Xue, H. Al-Sahaf, and M. Zhang, “Cross-domain reuse of extracted knowledge in genetic programming for image classification,” _IEEE Transactions on Evolutionary Computation_ , vol. 21, no. 4, pp. 569–587, 2017\.
  * [21] A. T. W. Min, R. Sagarna, A. Gupta, Y.-S. Ong, and C. K. Goh, “Knowledge transfer through machine learning in aircraft design,” _IEEE Computational Intelligence Magazine_ , vol. 12, no. 4, pp. 48–60, 2017.
  * [22] L. Feng, Y. Huang, I. W. Tsang, A. Gupta, K. Tang, K. C. Tan, and Y.-S. Ong, “Towards faster vehicle routing by transferring knowledge from customer representation,” _IEEE Transactions on Intelligent Transportation Systems_ , 2020.
  * [23] Y. Bi, B. Xue, and M. Zhang, “Learning and sharing: A multitask genetic programming approach to image feature learning,” _arXiv preprint arXiv:2012.09444_ , 2020.
  * [24] A. T. W. Min, A. Gupta, and Y.-S. Ong, “Generalizing transfer bayesian optimization to source-target heterogeneity,” _IEEE Transactions on Automation Science and Engineering_ , 2020.
  * [25] T. T. Joy, S. Rana, S. Gupta, and S. Venkatesh, “A flexible transfer learning framework for bayesian optimization with convergence guarantee,” _Expert Systems with Applications_ , vol. 115, pp. 656–672, 2019.
  * [26] T. G. Karimpanal, S. Rana, S. Gupta, T. Tran, and S. Venkatesh, “Learning transferable domain priors for safe exploration in reinforcement learning,” in _2020 International Joint Conference on Neural Networks (IJCNN)_. IEEE, 2020, pp. 1–10.
  * [27] S. J. Louis and J. McDonnell, “Learning with case-injected genetic algorithms,” _IEEE Transactions on Evolutionary Computation_ , vol. 8, no. 4, pp. 316–328, 2004.
  * [28] P. Cunningham and B. Smyth, “Case-based reasoning in scheduling: reusing solution components,” _International Journal of Production Research_ , vol. 35, no. 11, pp. 2947–2962, 1997.
  * [29] M. Kaedi and N. Ghasem-Aghaee, “Biasing bayesian optimization algorithm using case based reasoning,” _Knowledge-Based Systems_ , vol. 24, no. 8, pp. 1245–1253, 2011.
  * [30] S. Didi and G. Nitschke, “Multi-agent behavior-based policy transfer,” in _European Conference on the Applications of Evolutionary Computation_. Springer, 2016, pp. 181–197.
  * [31] S. Friess, P. Tiňo, S. Menzel, B. Sendhoff, and X. Yao, “Improving sampling in evolution strategies through mixture-based distributions built from past problem instances,” in _International Conference on Parallel Problem Solving from Nature_. Springer, 2020, pp. 583–596.
  * [32] B. Da, A. Gupta, and Y.-S. Ong, “Curbing negative influences online for seamless transfer evolutionary optimization,” _IEEE transactions on cybernetics_ , vol. 49, no. 12, pp. 4365–4378, 2019.
  * [33] M. Shakeri, A. Gupta, Y.-S. Ong, X. Chi, and A. Z. NengSheng, “Coping with big data in transfer optimization,” in _2019 IEEE International Conference on Big Data (Big Data)_. IEEE, 2019, pp. 3925–3932.
  * [34] L. Feng, L. Zhou, J. Zhong, A. Gupta, Y.-S. Ong, K.-C. Tan, and A. K. Qin, “Evolutionary multitasking via explicit autoencoding,” _IEEE transactions on cybernetics_ , vol. 49, no. 9, pp. 3457–3470, 2019.
  * [35] M. Xie, L. V. Lakshmanan, and P. T. Wood, “Breaking out of the box of recommendations: from items to packages,” in _Proceedings of the fourth ACM conference on Recommender systems_ , 2010, pp. 151–158.
  * [36] D. Wierstra, T. Schaul, T. Glasmachers, Y. Sun, J. Peters, and J. Schmidhuber, “Natural evolution strategies,” _The Journal of Machine Learning Research_ , vol. 15, no. 1, pp. 949–980, 2014.
  * [37] P. Smyth and D. Wolpert, “Stacked density estimation,” in _Advances in neural information processing systems_ , 1998, pp. 668–674.
  * [38] T. K. Moon, “The expectation-maximization algorithm,” _IEEE Signal processing magazine_ , vol. 13, no. 6, pp. 47–60, 1996.
  * [39] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire, “Gambling in a rigged casino: The adversarial multi-armed bandit problem,” in _Proceedings of IEEE 36th Annual Foundations of Computer Science_. IEEE, 1995, pp. 322–331.
  * [40] ——, “The nonstochastic multiarmed bandit problem,” _SIAM journal on computing_ , vol. 32, no. 1, pp. 48–77, 2002.
  * [41] H. Mühlenbein, “The equation for response to selection and its use for prediction,” _Evolutionary Computation_ , vol. 5, no. 3, pp. 303–346, 1997\.
  * [42] K. Deb, R. B. Agrawal _et al._ , “Simulated binary crossover for continuous search space,” _Complex systems_ , vol. 9, no. 2, pp. 115–148, 1995.
  * [43] K. Deb and D. Deb, “Analysing mutation schemes for real-parameter genetic algorithms,” _International Journal of Artificial Intelligence and Soft Computing_ , vol. 4, no. 1, pp. 1–28, 2014.
  * [44] C. B. Do, “The multivariate gaussian distribution,” 2008.
  * [45] T. Schaul, J. Bayer, D. Wierstra, Y. Sun, M. Felder, F. Sehnke, T. Rückstieß, and J. Schmidhuber, “PyBrain,” _Journal of Machine Learning Research_ , vol. 11, pp. 743–746, 2010.
  * [46] Z. Michalewicz and J. Arabas, “Genetic algorithms for the 0/1 knapsack problem,” in _International Symposium on Methodologies for Intelligent Systems_. Springer, 1994, pp. 134–143.
  * [47] J.-B. Mouret and G. Maguire, “Quality diversity for multi-task optimization,” _arXiv preprint arXiv:2003.04407_ , 2020.
  * [48] F. Gomez, J. Schmidhuber, and R. Miikkulainen, “Accelerated neural evolution through cooperatively coevolved synapses,” _Journal of Machine Learning Research_ , vol. 9, no. May, pp. 937–965, 2008.
  * [49] F. J. Gomez and R. Miikkulainen, “Solving non-markovian control tasks with neuroevolution,” in _IJCAI_ , vol. 99, 1999, pp. 1356–1361.
  * [50] Y.-S. Ong and A. Gupta, “Evolutionary multitasking: a computer science view of cognitive multitasking,” _Cognitive Computation_ , vol. 8, no. 2, pp. 125–142, 2016.
  * [51] K. K. Bali, A. Gupta, Y.-S. Ong, and P. S. Tan, “Cognizant multitasking in multiobjective multifactorial evolution: Mo-mfea-ii,” _IEEE Transactions on Cybernetics_ , 2020.
  * [52] Y. Huang, L. Feng, A. Qin, M. Chen, and K. C. Tan, “Towards large-scale evolutionary multi-tasking: A gpu-based paradigm,” _IEEE Transactions on Evolutionary Computation_ , 2021.
  * [53] Z. Liang, X. Xu, L. Liu, Y. Tu, and Z. Zhu, “Evolutionary many-task optimization based on multi-source knowledge transfer,” _IEEE Transactions on Evolutionary Computation_ , 2021.

|  Mojtaba Shakeri received the PhD degree in Computer Engineering from the
Nanyang Technological University, Singapore in 2013. He has been a Scientist
in the Singapore Institute of Manufacturing Technology, a research institute
in Singapore’s Agency for Science, Technology and Research (A*STAR) from 2019
to 2022. He was also an assistant professor in the Islamic Azad University,
Qazvin Branch and later in the University of Guilan, Iran, engaged with
teaching AI-related courses for both bachelor and master students for nearly
six years. He has supervised over 50 master dissertations in both
universities. His core competencies are in combinatorial optimization with
applications for supply chains and operations research mainly by developing
nature-inspired evolutionary algorithms and mathematical models.
---|---
|  Erfan Miahi is an MSc student at the University of Alberta and the
Reinforcement Learning and Artificial Intelligence lab. He received the
Bachelor’s degree in Computer Engineering from the University of Guilan in
2020. Erfan has diverse research experience in the field of artificial
intelligence, ranging from developing deep learning algorithms for medical
image analysis to fundamental research in reinforcement learning and
evolutionary optimization. His research areas of interest are reinforcement
learning and representation learning.
---|---
|  Abhishek Gupta received the PhD degree in Engineering Science from the
University of Auckland, New Zealand, in 2014. He is currently a Scientist and
Technical Lead in the Singapore Institute of Manufacturing Technology, a
research institute in Singapore’s Agency for Science, Technology and Research
(A*STAR). Abhishek has diverse research experience in computational science,
ranging from mathematical and numerical modelling in engineering to topics in
computational intelligence. He is an editorial board member of the IEEE
Transactions on Emerging Topics in Computational Intelligence, Complex &
Intelligent Systems journal, the Memetic Computing journal, and the Springer
book series on Adaptation, Learning, and Optimization.
---|---
|  Yew-Soon Ong (M’99-SM’12-F’18) received the Ph.D. degree in artificial
intelligence in complex design from the University of Southampton, U.K., in
2003. He is President’s Chair Professor in Computer Science at Nanyang
Technological University (NTU) and Chief Artificial Intelligence Scientist of
the Agency for Science, Technology and Research Singapore. At NTU, he serves
as co-Director of the Singtel-NTU Cognitive & Artificial Intelligence Joint
Lab. His research interest is in artificial and computational intelligence. He
is founding Editor-in-Chief of the IEEE Transactions on Emerging Topics in
Computational Intelligence and associate editor of IEEE Transactions on Neural
Networks & Learning Systems, IEEE Transactions on Cybernetics, IEEE
Transactions on Artificial Intelligence.
---|---

Scalable Transfer Evolutionary Optimization: Coping with Big task-instances -
Supplemental Material
By Mojtaba Shakeri, Erfan Miahi, Abhishek Gupta and Yew-Soon Ong

##  S.I Hyper-Parameter Sensitivity Analysis

We carried out the sensitivity analysis for the four hyper-parameters of the
sTrEO. Each hyper-parameter is treated individually by fixing the value of the
others to the setting chosen for the experiments in the paper. Table S.1 shows
different settings used for each hyper-parameter. Note that the neutralization
threshold $\varepsilon$ is a function of $T$ which is the total number of
probabilistic models including the target model. Figs. S.1 to S.4 shows the
best objective value of sTrEO (averaged over 30 independent runs) relative to
changes in the setting of each hyper-parameter. Two variations of the 0/1
knapsack problem (1000 sources with 250 and 40 related sources) as well as
five variations of the robotic arm example (10 joints with 1000 sources and 15
related sources, 20 joints with 1000, 2000, 5000 and 10000 sources with 15,
30, 75, 150 related sources, respectively) were considered for the analysis.

TABLE S.1: Settings for the sensitivity analysis. The setting in bold was chosen for the experiments in the paper. Hyper-parameter |  Settings
---|---
Temperature $(\lambda)$ |  $0.001,0.002,\mathbf{0.01},0.02,0.1,1$
Learning rate $(\eta)$ |  $0.5,0.7,0.8,0.85,\mathbf{0.9},0.95,0.99,1$
Neutralization threshold $(\varepsilon)$ |  $\frac{10^{-5}}{T},\frac{10^{-4}}{T},\frac{10^{-3}}{T},\frac{\mathbf{10^{-2}}}{\boldsymbol{T}},\frac{10^{-1}}{T},\frac{1}{T}$
Transfer interval $(\Delta)$ |  $\mathbf{2},4,6,8,10$

The impact of _temperature_ ($\lambda$) on the performance of sTrEO is shown
in Fig. S.1 for both knapsack and robotic arm examples. Given a fixed time
budget (which is sTrEO’s convergence time following the setting in Table I),
Figs. 1(a) and 1(b) show the best objective value achieved for different
settings of $\lambda$ for knapsack and robotic arm examples, respectively. As
can be seen, setting the hyper-parameter in $[0.001,0.02]$ yields superior
results for both variations of the knapsack problem. For the robotic arm
example, however, the range increases to $[0.001,0.1]$. Based on the above
analysis, the appropriate setting of $\lambda$ should lie in $[0.001,0.02]$,
which we set $\lambda=0.01$ in the experiments.

(a) Knapsack

(b) Robotic arm

Figure S.1: Sensitivity analysis of _temperature_ ($\lambda$) for (a) two
variations of the 0/1 knapsack problem (1000 sources with 250 and 40 related
sources) and (b) five variations of the robotic arm example (10 joints with
1000 sources and 15 related sources, 20 joints with 1000, 2000, 5000 and 10000
sources and 15, 30, 75, 150 related sources, respectively). The shaded region
indicates standard deviations either side of the mean.

The impact of _learning rate_ ($\eta$) on the performance of sTrEO is shown in
Fig. S.2 for both knapsack and robotic arm examples. As can be seen from Fig.
2(a), setting the hyper-parameter in $[0.9,0.99]$ yields superior results for
both variations of the knapsack problem. For the robotic arm example, however,
the range is in $[0.8,0.9]$ according to Fig. 2(b). Based on the above
analysis, we set $\eta=0.9$ in the experiments.

(a) Knapsack

(b) Robotic arm

Figure S.2: Sensitivity analysis of _learning rate_ ($\eta$) for (a) two
variations of the 0/1 knapsack problem (1000 sources with 250 and 40 related
sources) and (b) five variations of the robotic arm example (10 joints with
1000 sources and 15 related sources, 20 joints with 1000, 2000, 5000 and 10000
sources and 15, 30, 75, 150 related sources, respectively). The shaded region
indicates standard deviations either side of the mean.

The impact of _neutralization threshold_ ($\varepsilon$) on the performance of
sTrEO is shown in Fig. S.3 for both knapsack and robotic arm examples. As can
be seen from Fig. 3(a) setting the hyper-parameter around $\frac{10^{-2}}{T}$
yields superior results for both variations of the knapsack problem. This,
however, is broader for the robotic arm example in
$[\frac{10^{-5}}{T},\frac{10^{-2}}{T}]$ following Fig. 3(b). Based on the
above analysis, we set $\varepsilon=\frac{10^{-2}}{T}$ in the experiments.

(a) Knapsack

(b) Robotic arm

Figure S.3: Sensitivity analysis of _neutralization threshold_ ($\varepsilon$)
for (a) two variations of the 0/1 knapsack problem (1000 sources with 250 and
40 related sources) and (b) five variations of the robotic arm example (10
joints with 1000 sources and 15 related sources, 20 joints with 1000, 2000,
5000 and 10000 sources and 15, 30, 75, 150 related sources, respectively). The
shaded region indicates standard deviations either side of the mean.

Lastly, the impact of _transfer interval_ ($\Delta$) on the performance of
sTrEO is shown in Fig. S.4 for both knapsack and robotic arm examples. As can
be seen from Fig. 4(a), setting $\Delta=2$ yields superior results for both
variations of the knapsack problem. This, however, increases to $[2,4]$ for
the robotic arm example following Fig. 4(b). Based on the above analysis, we
set $\Delta=2$ in the experiments.

(a) Knapsack

(b) Robotic arm

Figure S.4: Sensitivity analysis of _transfer interval_ ($\Delta$) for (a) two
variations of the 0/1 knapsack problem (1000 sources with 250 and 40 related
sources) and (b) five variations of the robotic arm example (10 joints with
1000 sources and 15 related sources, 20 joints with 1000, 2000, 5000 and 10000
sources and 15, 30, 75, 150 related sources, respectively). The shaded region
indicates standard deviations either side of the mean.

##  S.II Further Experiments

We carried out further experiments to assess the performance of sTrEO beyond
1000 source task-instances by keeping the number of related sources fixed and
increasing the number of unrelated sources. To this end, we set up an
evaluation scenario on the more complex 20-joint robotic arm example by
starting with 150 related sources and gradually increasing the number of
unrelated sources from 850 to 9850. That is, the experiment starts with 1000
sources of which 150 instances are related. We then increase the total number
of sources to 2000, 5000 and 10000 while keeping the number of related source
instances to 150, thereby reaching the same source-target relatedness ratio of
$0.015$ that we considered in Section IV-C. We used the same setting as in
Table I in the experiments. The assessment is from two aspects of _online
learning agility_ and _scalability_ by comparing with the two existing TrEO
methods, AMTEA and MAB-AMTEA.

(a) 1000 sources (150 related)

(b) 2000 sources (150 related)

(c) 5000 sources (150 related)

(d) 10000 sources (150 related)

Figure S.5: Further experiments on _online learning agility_ of sTrEO for the
20-joint robotic arm example with (a) 1000, (b) 2000, (c) 5000 and (d) 10000
sources. The number of related sources is fixed to 150. The shaded region
indicates standard deviations either side of the mean.

(a) 1000 sources (150 related)

(b) 2000 sources (150 related)

(c) 5000 sources (150 related)

(d) 10000 sources (150 related)

Figure S.6: Further experiments on _scalability_ of sTrEO for the 20-joint
robotic arm example with (a) 1000, (b) 2000, (c) 5000 and (d) 10000 sources.
The number of related sources is fixed to 150. The shaded region indicates
standard deviations either side of the mean.

Fig. S.5 shows the convergence trends of the three algorithms (averaged over
30 independent runs) with regard to the number of function evaluations, an
empirical way to evaluate online learning agility. As can be seen from the
figure, despite the growing difference between the number of unrelated and
related sources, both AMTEA and sTrEO are able to learn and utilize relevant
knowledge in early generations of evolution to converge to optimality. This is
however more evident for sTrEO as it acquires a steeper convergence curve,
particularly for 5000 and 10000 sources. On the contrary, MAB-AMTEA fails at
effectively utilizing relevant sources as it is not able to converge to
optimality within the computational budget of 5000 evaluations. With respect
to scalability, Fig. S.6 shows the convergence trend of the algorithms within
sTrEO’s convergence time. It can be observed that unlike AMTEA, sTrEO’s
computational complexity is as efficient as MAB-AMTEA even for the extreme
case of 10000 source instances (despite the latter’s failure in converging to
optimality). AMTEA requires much longer time to converge to optimality.
Following the above analysis, we conclude that sTrEO is able to
_simultaneously_ ensure scalability and online learning agility _beyond_ 1000
source task-instances.

Fig. S.7 shows the impact of the ratio of source-target relatedness on sTrEO’s
online learning agility, and hence its performance. Fig. 7(a) depicts the
convergence trends of sTrEO relative to the number of function evaluations
whereas Fig. 7(a) presents the convergence trends within sTrEO’s convergence
time taken for the case of 1000 sources with 150 related instances. As can be
seen, sTrEO is sensitive to sparsity of related sources. As the number of
unrelated sources increases, the algorithm requires more generations (Fig.
7(a)), and hence more time (Fig. 7(b)), to learn related sources, through
launching the (1+1)-ES based source-target similarity learning procedure,
impeding convergence to optimality. This is better visualized in Fig. S.8
which depicts the trajectory of learned transfer coefficients aggregated per
related and unrelated source instances, respectively, for different source-
target relatedness ratios.

(a) Convergence trends

(b) Convergence times

Figure S.7: The impact of the ratio of source-target relatedness on sTrEO’s
performance in terms of (a) number of function evaluations and (b) execution
time. The number of related sources is fixed to 150. The shaded region
indicates standard deviations either side of the mean.

(a) relatedness ratio =$0.15$

(b) relatedness ratio =$0.075$

(c) relatedness ratio =$0.03$

(d) relatedness ratio =$0.015$

Figure S.8: Learned transfer coefficients of sTrEO given _sparsity_ of related
sources for the 20-joint robotic arm example with (a) 1000, (b) 2000, (c) 5000
and (d) 10000 sources. The number of related sources is fixed to 150. The
shaded region indicates standard deviations either side of the mean.