The Moving Peaks Benchmark

Jürgen Branke
Institute AIFB, University of Karlsruhe
D-76128 Karlsruhe, Germany
Email: branke@aifb.uni-karlsruhe.de

December 1999

With the aim to bridge the gap between very complex, hard to understand real-world problems and all too simple toy problems, Branke [2,1] suggested a problem with a multidimensional landscape consisting of several peaks, where the height, the width and the position of each peak is altered slightly every time a change in the environment occurs. Independently, a similar benchmark has been proposed by Morrison and DeJong in [3].

The Moving Peaks benchmark as presented here is based on the benchmark proposed in [2], incorporates aspects from [3] and adds a few new ones.

Note that a small change in the landscape may have two consequences: sometimes it may be sufficient to adapt the current solution to reach the new optimum, and sometimes it may be necessary to switch to another, previously slightly inferior but now better solution. The former happens e.g. when the optimum shifts slightly, the latter happens when the height of the peaks changes such that a different peak becomes the maximum peak. In these cases, the EA basically has to ``jump'', or cross a valley, to reach the new maximum peak.

A test function with n dimensions and mpeaks can be formulated as:

$$\begin{eqnarray*}F(\vec{x},t)& =& \max( B(\vec{x}), \max_{i=1 \ldots m} P(\vec{x},h_i(t),w_i(t), \vec{p}_i(t))) \end{eqnarray*}$$

where $B(\vec{x})$ is a time-invariant ``basis'' landscape, and P is the function defining a peak shape, where each of the m peaks has its own time-varying parameters height (h), width (w), and location ($\vec{p}$).

The coordinates, the height and the width of each peak are initialized according to an in-built random number generator.

Then, every $\Delta e$evaluations the height and width of every peak are changed by adding a random gaussian variable. The location of every peak i is moved by a vector $\vec{v_i}$ of fixed length s in a random direction (for $\lambda = 0$) or a direction depending on the previous direction (for $\lambda > 0$).

Overall, the parameter s allows to control the severity of a change, $\Delta e$will determine the frequency of change, $\lambda$ allows to control whether the changes exhibit a trend.

More formally, a change of a single peak can be described as

$$\begin{eqnarray*}\sigma & \in & N(0,1)\\ h_i(t) & = & h_i(t-1) + height\_sever... ... \sigma\\ \vec{p_i}(t) & = & \vec{p_i}(t-1) + \vec{v_i}(t) \\ \end{eqnarray*}$$

The shift vector $\vec{v_i}$ is a linear combination of a random vector $\vec{r}$ and the previous shift vector $\vec{v_i}(t-1)$, and normalized to length s, i.e.

$$\begin{eqnarray*}\vec{v_i}(t)&=&\frac{s}{\vert\vec{r}+\vec{v_i}(t-1)\vert}((1-\lambda) \vec{r}+ \lambda \vec{v_i}(t-1)) \end{eqnarray*}$$

The random vector $\vec{r}$ is created by drawing random numbers for each dimension and normalizing its length to s.

The function's complexity may easily be scaled by increasing the number of dimensions and/or the number of peaks, or by using complex peak- and base-functions.

To allow replication, the exact test function from [2] is using a separate random number generator. The C-code can be downloaded from
http://www.aifb.uni-karlsruhe.de/$\sim$jbr/MovPeaks.html.