Competition on Dynamic Optimization Problems Generated by Generalized Moving Peaks Benchmark (GMPB)

Search spaces of many real-world optimization problems are dynamic in terms of the objective function, the number of variables, and/or constraints [3, 4]. Optimization problems that change over time and need to be solved online by an optimization method are referred to as dynamic optimization problems (DOPs) [5]. To solve DOPs, algorithms not only need to find desirable solutions but also to react to the environmental changes in order to quickly find a new solution when the previous one becomes suboptimal [6].

To comprehensively evaluate the effectiveness of algorithms designed for DOPs, a suitable benchmark generator is crucial. Commonly used and well-known benchmark generators in this domain use the idea of having several components that form the landscape. In most existing DOP benchmarks, the width, height, and location of these components change over time [7]. One of the benchmark generators that is designed based on this idea is the Moving Peaks Benchmark (MPB) [8], which is the most widely used synthetic problem in the DOP field [7, 6, 4]. Each component in MPB is formed by usually a simple peak whose basin of attraction is determined using a $\max(\cdot)$ function.

Despite the popularity of the traditional MPB, landscapes generated by this benchmark consist of components that are smooth/regular, symmetric, unimodal, separable [9], and easy-to-optimize, which may not be the case in many real-world problems. In [1], a generalized MPB (GMPB) is proposed which can generate components with a variety of characteristics that can range from unimodal to highly multimodal, from symmetric to highly asymmetric, from smooth to highly irregular, and with different variable interaction degrees and condition numbers. GMPB is a benchmark generator with fully controllable features that helps researchers to analyze DOP algorithms and investigate their effectiveness in facing a variety of different problem characteristics.

The baseline function of GMPB is¹¹1Herein, we focus on fully non-separable problem instances which are constructed by Eq. (1). Those readers who are interested in partially/fully separable problems (i.e., composition based functions), refer to [1].:

where $\mathbb{T}(\mathbf{y},k):\mathbb{R}^{d}\mapsto\mathbb{R}^{d}$ is calculated as:

where $\mathbf{x}$ is a solution in $d$-dimensional space, $m$ is the number of components, $\mathbf{R}_{k}^{(t)}$ is the rotation matrix of $k$th component in the $t$th environment, $\mathbf{W}_{k}^{(t)}$ is a $d\times d$ diagonal matrix whose diagonal elements show the width of $k$th component in different dimensions, $y_{j}$ is $j$th dimension of $\mathbf{y}$, and $\eta_{k,l\in\{1,2,3,4\}}^{(t)}$ and $\tau^{(t)}_{k}$ are irregularity parameters of the $k$th component.

For each component $k$, the rotation matrix $\mathbf{R}_{k}$ is obtained by rotating the projection of $\mathbf{x}$ onto all $x_{p}$-$x_{q}$ planes by a given angle $\theta_{k}$. The total number of unique planes which will be rotated is ${d\choose 2}=\frac{d(d-1)}{2}$. For rotating each $x_{p}$-$x_{q}$ plane by a certain angle ($\theta_{k}$), a Givens rotation matrix $\mathbf{G}_{(p,q)}$ must be constructed. To this end, first, $\mathbf{G}_{(p,q)}$ is initialized to an identity matrix $\mathbf{I}_{d\times d}$; then, four elements of $\mathbf{G}_{(p,q)}$ are altered as:

where $\mathbf{G}_{(p,q)}(\mathfrak{i},\mathfrak{j})$ is the element at $\mathfrak{i}$th row and $\mathfrak{j}$th column of $\mathbf{G}_{(p,q)}$. $\mathbf{R}_{k}$ in the $t$th environment is calculated by:

where $\mathcal{P}$ contains all unique pairs of dimensions defining all possible planes in a $d$-dimensional space. The order of the multiplications of the Givens rotation matrices is random. The reason behind using (7) for calculating $\mathbf{R}$ is that we aim to have control on the rotation matrix based on an angle severity $\tilde{\theta}$. Note that the initial $\mathbf{R}^{(0)}_{k}$ for problem instances with rotation property is obtained by using the Gram-Schmidt orthogonalization method on a matrix with normally distributed entries.

For each component $k$, the height, width vector, center, angle, and irregularity parameters change from one environment to the next according to the following update rules:

where $\mathcal{N}(0,1)$ is a random number drawn from a Gaussian distribution with mean 0 and variance 1, $\mathbf{c}_{k}$ shows the vector of center position of the $k$th component, $\mathbf{r}$ is a $d$-dimensional vector of random numbers generated by $\mathcal{N}(0,1)$, $\|\mathbf{r}\|$ is the Euclidean length (i.e., $l_{2}$-norm) of $\mathbf{r}$, $\frac{\mathbf{r}}{\|\mathbf{r}\|}$ generates a unit vector with a random direction, $\tilde{h}$, $\tilde{w}$, $\tilde{s}$, $\tilde{\theta}$, $\tilde{\eta}$, and $\tilde{\tau}$ are height, width, shift, angle, and two irregularity parameters’ change severity values, respectively, $w_{k,j}$ shows the width of the $k$th component in the $j$th dimension, and $h_{k}$ and $\theta_{k}$ show the height and angle of the $k$th component, respectively.

Outputs of equations (8) to (13) are bounded as follows: $h_{k}\in[h_{\mathrm{min}},h_{\mathrm{max}}]$, $w_{k}\in[w_{\mathrm{min}},w_{\mathrm{max}}]^{d}$, $\mathbf{c}_{k}\in[Lb,Ub]^{d}$, $\tau\in[\tau_{\mathrm{min}},\tau_{\mathrm{max}}]$, $\eta_{1,2,3,4}\in[\eta_{\mathrm{min}},\eta_{\mathrm{max}}]$, and $\theta_{k}\in[\theta_{\mathrm{min}},\theta_{\mathrm{max}}]$, where $Lb$ and $Ub$ are maximum and minimum problem space bounds. For keeping the above mentioned values in their bounds, a Reflect method is utilized. Assume $a^{(t+1)}=a^{(t)}+b$ represents one of the equations (8) to (13). The output based on the reflect method is:

Table I shows the parameter settings of GMPB. By changing the number of dimensions, shift severity value, the number of components, and change frequency, the difficulty level of the generated problem instances can be adjusted. Every $\vartheta$ fitness evaluations, the center position, height, width vector, angle, and irregularity parameters of each component change using the dynamics presented in (8) to (13).

To measure the performance of algorithms in solving the problem instances generated by GMPB, the offline-error [10] ($E_{\mathrm{O}}$) and the average error of the best found solution in all environments, i.e., the best error before change, ($E_{\mathrm{BBC}}$) [11] are used as the performance indicators. $E_{\mathrm{O}}$ is the most commonly used performance indicator in the literature [12]. This approach calculates the average error of the best found position over all fitness evaluations using the following equation:

where $\mathbf{x}^{\star(t)}$ is the global optimum position at the $t$th environment, $T$ is the number of environments, $\vartheta$ is the change frequency, $\varphi$ is the fitness evaluation counter for each environment, and $\mathbf{x}^{*((t-1)\vartheta+\varphi)}$ is the best found position at the $\varphi$th fitness evaluation in the $t$th environment.

$E_{\mathrm{BBC}}$ is the second commonly used performance indicator in the field [12]. $E_{\mathrm{BBC}}$ only considers the last error before each environmental change (i.e., at the end of each environment):

where $\mathbf{x}^{*(t)}$ is the best found position in $t$th environment which is fetched at the end of the $t$th environment.

GMPB is a featured component of EDOLAB [2], a comprehensive MATLAB²²2Version R2020b and later optimization platform designed for both educational and experimental purposes in dynamic environments. EDOLAB hosts an array of 25 evolutionary dynamic optimization algorithms. Researchers are encouraged to utilize the guidelines in [2] to integrate their own algorithms into EDOLAB. This allows for an extensive evaluation of their algorithms’ performance against a variety of problem instances created by dynamic optimization benchmark generators, including GMPB. The source code of EDOLAB is readily available and can be accessed at here.

We also provided another source code that visualizes 2-dimensional landscapes generated by GMPB which can be found in [13]. Using this source code, researchers can observe the impacts of different parameter settings on morphological characteristics of the problems generated by GMPB.