Nikolaus Hansen 
  
Steffen Finck 
  
Raymond Ros 
  
Anne Auger 
  
  
  
  
Real-Parameter Black-Box Optimization Benchmarking 2009: Noisy Functions Definitions

Keywords: optimization, evolutionary algorithms, benchmarking, black-box

Quantifying and comparing performance of optimization algorithms is one important aspect of research in search and optimization. However, this task turns out to be tedious and difficult to realize even in the single-objective case -at least if one is willing to accomplish it in a scientifically decent and rigorous way. The BBOB 2009 workshop will furnish most of this tedious task for its participants: (1) choice and implementation of a well-motivated real-parameter benchmark function testbed, (2) design of an experimental set-up, (3) generation of data output for (4) post-processing and presentation of the results in graphs and tables. What remains to be done for the participants is to allocate CPU-time, run their favorite black-box real-parameter optimizer in a few dimensions a few hundreds of times and execute the provided post-processing script afterwards. In this report, the testbed of noisy functions is defined and motivated.

Introduction

In the following the benchmark functions with noise are defined (for a graphical presentation see [START_REF] Finck | Real-parameter black-box optimization benchmarking 2009[END_REF]). For a general motivation of the choice of functions compare [START_REF] Finck | Real-parameter black-box optimization benchmarking 2009[END_REF][START_REF] Hansen | Real-parameter black-box optimization benchmarking 2009: Noiseless functions definitions[END_REF].

Symbols and Definitions

Used symbols and definitions of, e.g., auxiliary functions are given in the following. Vectors are typeset in bold and refer to column vectors.

⊗ indicates element-wise multiplication of two D-dimensional vectors, ⊗ :

R D ×R D → R D , (x, y) → diag(x) × y = (x i × y i ) i=1,...,D
. denotes the Euclidean norm, x 2 = i x 2 i .

[.] denotes the nearest integer value 0 = (0, . . . , 0) T all zero vector 1 = (1, . . . , 1) T all one vector Λ α is a diagonal matrix in D dimensions with the ith diagonal element as λ ii = α

1 2 i-1 D-1 f pen : R D → R, x → 100 D i=1 max(0, |x i | -5) 2
1 + -a D-dimensional vector with entries of -1 or 1 both drawn equal probability.

Q, R orthogonal (rotation) matrices. For each function instance in each dimension a single realization for respectively Q and R is used. Rotation matrices are generated from standard normally distributed entries by Gram-Schmidt orthogonalization. Columns and rows of a rotation matrix form an orthogonal basis.

R see Q T β asy : R D → R D , x i → x 1+β i-1 D-1 √ xi i if x i > 0 x i otherwise , for i = 1, . . . , D.
T osz : R n → R n , for any positive integer n, maps element-wise

x → sign(x) exp (x + 0.049 (sin(c 1 x) + sin(c 2 x))) with x = log(|x|) if x = 0 ∈ R otherwise , sign(x) =      -1 if x < 0 0 if x = 0 1 otherwise , c 1 = 10 if x > 0 5.5 otherwise and c 2 = 7.9 if x > 0 3.1 otherwise
x opt optimal solution vector, such that f (x opt ) is minimal.

General Setup

Search Space All functions are defined and can be evaluated over R D , while the actual search domain is given as [-5, 5] D . The value for f opt is drawn from a cauchy distributed random variable, with roughly 50% of the values between -100 and 100. The value is rounded after two decimal places and the maximum and minimum are set to 1000 and -1000 respectively. In the function definitions a transformed variable vector z is often used instead of the argument x. The vector z has its optimum in z opt = 0, if not stated otherwise.

Boundary Handling On all functions a penalty boundary handling is applied as given with f pen (see section 0.1).

Linear Transformations Linear transformations of the search space are applied to derive nonseparable functions from separable ones and to control the conditioning of the function.

Non-Linear Transformations and Symmetry Breaking In order to make relatively simple, but well understood functions less regular, on some functions non-linear transformations are applied in xor f -space. Both transformations T osz : R n → R n , n ∈ {1, D}, and T asy : R D → R D are defined coordinate-wise (see Section 0.1). They are smooth and have, coordinate-wise, a strictly positive derivative. They are shown in Figure 1. T osz is oscillating about the identity, where the oscillation is scale invariant w.r.t. the origin. T asy is the identity for negative values. When T asy is applied, a portion of 1/2 D of the search space remains untransformed.

Noise Models

In this benchmarking suite three different noise models are used. The first two, f GN () and f UN (), are multiplicative noise models while the third model, f CN (), is an additive noise model. All noise models are applied to a function value f under the assumption that f ≥ 0. All noise models reveal stochastic dominance between any two solutions and are therefore utility-free (see Appendix A).

Gaussian Noise

The Gaussian noise model is scale invariant and defined as

f GN (f, β) = f × exp(β N (0, 1)) . (1) 
The noise strength is controlled with β. The distribution of the noise is log-normal, thus no negative noise values can be sampled. For the benchmark functions with moderate noise β = 0.01, otherwise β = 1. For small values of β this noise model resembles f × (1 + β N (0, 1)).

Uniform Noise

The uniform noise model is introduced as a more severe noise model than the Gaussian and is defined as

f UN (f, α, β) = f × U(0, 1) β max 1, 10 9 f + ǫ α U (0,1)
.

(

) 2 
The noise model uses two random factors. The first factor is in the interval [0, 1], uniformly distributed for β = 1. The second factor, max(. . . ), is ≥ 1. The parameters α and β control the noise strength. For moderate noise α = 0.01 (0.49 + 1/D) and β = 0.01, otherwise α = 0.49 + 1/D and β = 1. Furthermore, ǫ is set to 10 -99 in order to prevent division by zero.

The uniform noise model is not scale invariant. Due to the last factor in Eq. ( 2) the noise strength increases with decreasing (positive) value of f . Therefore the noise strength becomes more severe when approaching the optimum.

Cauchy Noise

The Cauchy noise model represents a different type of noise with two important aspects. First, only a comparatively small percentage of function values is disturbed by noise. Second, the noise distribution is comparatively "weird". Large outliers occur once in a while, and because they stem from a continuous distribution they cannot be easily diagnosed. The Cauchy noise model is defined as

f CN (f, α, p) = f + α max 0, 1000 + I {U (0,1)<p} N (0, 1) |N (0, 1)| + ǫ , (3) 
where α defines the noise strength and p determines the frequency of the noise disturbance. In the moderate noise case α = 0.01 and p = 0.05, otherwise α = 1 and p = 0.2. The summand of 1000 was chosen to sample positive and negative "outliers" (as the function value is cut from below, see next paragraph) and ǫ is set to 10 -199 .

Final Function Value In order to achieve a convenient testing for the target function value, in all noise models 1.01 × 10 -8 is added to the function value and, if the input argument f is smaller than 10 -8 , the undisturbed f is returned. 

f XX (f, . . . ) ← f XX (f, . . . ) + 1.01 × 10 -8 if f ≥ 10 -8 f otherwise ( 
f 103 (x) = f CN (f sphere (x), 0.01, 0.05) + f pen (x) + f opt (103)
1.2 Rosenbrock

f rosenbrock (x) = D-1 i=1 100 z 2 i -z i+1 2 + (z i -1) 2 z = max 1, √ D 8 (x -x opt ) + 1 z opt = 1
Properties So-called banana function due to its 2-D contour lines as a bent ridge (or valley).

In the beginning, the prominent first term of the function definition attracts to the point z = 0. Then, a long bending valley needs to be followed to reach the global optimum. The ridge changes its orientation D -1 times.

in larger dimensions the function has a local optimum with an attraction volume of about 25% 2 Functions with severe noise 2.1 Sphere

f sphere (x) = z 2 z = x -x opt
Properties Presumably the most easy continuous domain search problem, given the volume of the searched solution is small (i.e. where pure monte-carlo random search is too expensive).

unimodal highly symmetric, in particular rotationally invariant 2.1.1 107 Sphere with gaussian noise

f 107 (x) = f GN (f sphere (x), 1) + f pen (x) + f opt (107) 
2.1.2 108 Sphere with uniform noise

f 108 (x) = f UN f sphere (x), 0.49 + 1 D , 1 + f pen (x) + f opt (108) 
2.1.3 109 Sphere with seldom cauchy noise

f 109 (x) = f CN (f sphere (x), 1, 0.2) + f pen (x) + f opt (109) 
2.2 Rosenbrock

f rosenbrock (x) = D-1 i=1 100 z 2 i -z i+1 2 + (z i -1) 2 z = max 1, √ D 8 (x -x opt ) + 1 z opt = 1
Properties So-called banana function due to its 2-D contour lines as a bent ridge (or valley).

In the beginning, the prominent first term of the function definition attracts to the point z = 0. Then, a long bending valley needs to be followed to reach the global optimum. The ridge changes its orientation D -1 times.

a local optimum with an attraction volume of about 25% 2.2.1 110 Rosenbrock with gaussian noise

f 110 (x) = f GN (f rosenbrock (x), 1) + f pen (x) + f opt (110)
2.2.2 111 Rosenbrock with uniform noise

f 111 (x) = f UN f rosenbrock (x), 0.49 + 1 D , 1 + f pen (x) + f opt (111) 
2.2.3 112 Rosenbrock with seldom cauchy noise

f 112 (x) = f CN (f rosenbrock (x), 1, 0.2) + f pen (x) + f opt (112) INRIA 2.3
Step ellipsoid

f step (x) = 0.1 max |ẑ 1 |/10 4 , D i=1 10 2 i-1 D-1 z 2 i ẑ = Λ 10 R(x -x opt ) zi = ⌊0.5 + ẑi ⌋ if ẑi > 0.5 ⌊0.5 + 10 ẑi ⌋/10 otherwise for i = 1, . . . , D,
denotes the rounding procedure in order to produce the plateaus.

z = Qz
Properties The function consists of many plateaus of different sizes. Apart from a small area close to the global optimum, the gradient is zero almost everywhere.

condition number is about 100

113

Step ellipsoid with gaussian noise

f 113 (x) = f GN (f step (x), 1) + f pen (x) + f opt (113) 

114

Step ellipsoid with uniform noise

f 114 (x) = f UN f step (x), 0.49 + 1 D , 1 + f pen (x) + f opt (114) 

115

Step ellipsoid with seldom cauchy noise

f 115 (x) = f CN (f step (x), 1, 0.2) + f pen (x) + f opt (115)
2.4 Ellipsoid

f ellipsoid (x) = D i=1 10 4 i-1 D-1 z 2 i z = T osz (R(x -x opt ))
Properties Globally quadratic ill-conditioned function with smooth local irregularities. 2.5 Different Powers

f diffpowers (x) = D i=1 |z i | 2+4 i-1 D-1 z = R(x -x opt )
Properties Due to the different exponents the sensitivity relation of the z i -variables continuously worsens when approaching the optimum.

119 Different Powers with gaussian noise

f 119 (x) = f GN (f diffpowers (x), 1) + f pen (x) + f opt (119) 
2.5.2 120 Different Powers with uniform noise

f 120 (x) = f UN f diffpowers (x), 0.49 + 1 D , 1 + f pen (x) + f opt (120) 
2.5.3 121 Different Powers with seldom cauchy noise

f 121 (x) = f CN (f diffpowers (x), 1, 0.2) + f pen (x) + f opt (121) 
3 Highly multi-modal functions with severe noise 3.1 Schaffer's F7

f schaffer (x) = 1 D -1 D-1 i=1 √ s i + √ s i sin 2 50 s 1/5 i 2 z = Λ 10 Q T 0.5 asy (R(x -x opt )) s i = z 2 i + z 2 i+1 for i = 1, . .

. , D

Properties A highly multimodal function where frequency and amplitude of the modulation vary.

conditioning is low 3.1.1 122 Schaffer's F7 with gaussian noise 

f 122 (x) = f GN (f schaffer (x), 1) + f pen (x) + f opt (122) 3 
f 124 (x) = f CN (f schaffer (x), 1, 0.2) + f pen (x) + f opt (124) 3.2 Composite Griewank-Rosenbrock f f8f2 (x) = 1 D -1 D-1 i=1 s i 4000 -cos(s i ) + 1 z = max 1, √ D 8
Rx + 0.5

s i = 100 (z 2 i -z i+1 ) 2 + (z i -1) 2 for i = 1, . . . , D z opt = 1
Properties Resembling the Rosenbrock function in a highly multimodal way.

125

Composite Griewank-Rosenbrock with gaussian noise , three optima have a value larger than 9

f 125 (x) = f GN (f f8f2 (x), 1) + f pen (x) + f opt (125) 3 
C i = Λ αi /α 1/4 i
where Λ αi is defined as usual (see Section 0.1), but with randomly permuted diagonal elements. For i = 2, . . . , 101, α i is drawn uniformly randomly from the set 1000 2 j 99 | j = 0, . . . , 99 without replacement, and α i = 1000 for i = 1.

the local optima y i are uniformly drawn from the domain [-4.9, 4.9] D for i = 2, . . . , 101 and y 1 ∈ [-4, 4] D . The global optimum is at x opt = y 1 .

Properties The function consists of 101 optima with position and height being unrelated and randomly chosen. 

Figure 1 :

 1 Figure 1: T osz (blue) and D-th coordinate of T asy for β = 0.1, 0.2, 0.5 (green)

3. 3

 3 Gallagher's Gaussian Peaks, globally rotatedf gallagher (x) = T osz 10y i ) T R T C i R(xy i )

  Symbols and Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.2 General Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.3 Noise Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 Functions with moderate noise 1.1 Sphere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1 101 Sphere with moderate gaussian noise . . . . . . . . . . . . . . . . . . . 1.1.2 102 Sphere with moderate uniform noise . . . . . . . . . . . . . . . . . . . . 1.1.3 103 Sphere with moderate seldom cauchy noise . . . . . . . . . . . . . . . . 1.2 Rosenbrock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 104 Rosenbrock with moderate gaussian noise . . . . . . . . . . . . . . . . . 1.2.2 105 Rosenbrock with moderate uniform noise . . . . . . . . . . . . . . . . . 1.2.3 106 Rosenbrock with moderate seldom cauchy noise . . . . . . . . . . . . .

	Contents
	0 Introduction
	0.1 . .
	3.1.1 122 Schaffer's F7 with gaussian noise . . . . . . . . . . . . . . . . . . . . . .
	3.1.2 123 Schaffer's F7 with uniform noise . . . . . . . . . . . . . . . . . . . . . .
	3.1.3 124 Schaffer's F7 with seldom cauchy noise . . . . . . . . . . . . . . . . . .
	3.2 Composite Griewank-Rosenbrock . . . . . . . . . . . . . . . . . . . . . . . . . . . .
	3.2.1 125 Composite Griewank-Rosenbrock with gaussian noise . . . . . . . . . .
	3.2.2 126 Composite Griewank-Rosenbrock with uniform noise . . . . . . . . . . .
	3.2.3 127 Composite Griewank-Rosenbrock with seldom cauchy noise . . . . . . .
	3.3 Gallagher's Gaussian Peaks, globally rotated . . . . . . . . . . . . . . . . . . . . .
	3.3.1 128 Gallagher's Gaussian Peaks 101-me with gaussian noise . . . . . . . . .
	3.3.2 129 Gallagher's Gaussian Peaks 101-me with uniform noise . . . . . . . . .
	3.3.3 130 Gallagher's Gaussian Peaks 101-me with seldom cauchy noise . . . . . .
	A Utility Functions

2 Functions with severe noise 2.1 Sphere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 107 Sphere with gaussian noise . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2 108 Sphere with uniform noise . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.3 109 Sphere with seldom cauchy noise . . . . . . . . . . . . . . . . . . . . . . 2.2 Rosenbrock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 110 Rosenbrock with gaussian noise . . . . . . . . . . . . . . . . . . . . . . 2.2.2 111 Rosenbrock with uniform noise . . . . . . . . . . . . . . . . . . . . . . . 2.2.3 112 Rosenbrock with seldom cauchy noise . . . . . . . . . . . . . . . . . . . 2.3 Step ellipsoid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 113 Step ellipsoid with gaussian noise . . . . . . . . . . . . . . . . . . . . . 2.3.2 114 Step ellipsoid with uniform noise . . . . . . . . . . . . . . . . . . . . . . 2.3.3 115 Step ellipsoid with seldom cauchy noise . . . . . . . . . . . . . . . . . . 2.4 Ellipsoid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1 116 Ellipsoid with gaussian noise . . . . . . . . . . . . . . . . . . . . . . . . 2.4.2 117 Ellipsoid with uniform noise . . . . . . . . . . . . . . . . . . . . . . . . 2.4.3 118 Ellipsoid with seldom cauchy noise . . . . . . . . . . . . . . . . . . . . . 2.5 Different Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.1 119 Different Powers with gaussian noise . . . . . . . . . . . . . . . . . . . . 2.5.2 120 Different Powers with uniform noise . . . . . . . . . . . . . . . . . . . . 2.5.3 121 Different Powers with seldom cauchy noise . . . . . . . . . . . . . . . . 3 Highly multi-modal functions with severe noise 3.1 Schaffer's F7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  condition number around the global optimum is about 30 same overall rotation matrix 3.3.1 128 Gallagher's Gaussian Peaks 101-me with gaussian noisef 128 (x) = f GN (f gallagher (x), 1) + f pen (x) + f opt (128)3.3.2 129 Gallagher's Gaussian Peaks 101-me with uniform noise f 129 (x) = f UN f gallagher (x), 0.49 + 1 D , 1 + f pen (x) + f opt (129) 3.3.3 130 Gallagher's Gaussian Peaks 101-me with seldom cauchy noise f 130 (x) = f CN (f gallagher (x), 1, 0.2) + f pen (x) + f opt (130)

RR n 6869

P F (x) (z) denotes the probability that F (x) ≤ z.RR n 6869

APPENDIX A Utility Functions

The objective when optimizing a noisy function is not immediately obvious. Function values are noisy by definition and the ordering of solutions is not unique, but depends on the realized random values. For this reason, often a utility is defined, which is a deterministic function over the search space. Let F : R D → R be the noisy function, i.e. for each x ∈ R D , F (x) is a random variable with values in R. Then a utility maps each F (x) to a real value and therefore, equivalently maps each x to this value. A typical utility is x → E(F (x)), where E denotes the expected value (remark that the expectation is not taken over x). The objective can now be clearly stated in that the utility shall be minimized. Most search procedures, like evolutionary algorithms, do not optimize for the expected value. Therefore, evaluating their performance with respect to the utility expected value could render benchmarking result rather meaningless.

In the given testbed, we have chosen to implement utility-free noisy functions. We call them utility-free, because any reasonable utility (any utility that is compliant with the minimization task) will eventually lead to the same result: the ordering between solutions will remain the same for all reasonable utility functions and in particular the global optimum will be the same. This property is provided by stochastic dominance between the F -distributions of any two solutions, x and y. For the cumulative distribution functions P of F (x) and F (y) holds either for all z ∈ R is P F (x) (z) < P F (y) (z), 1 or for all z ∈ R is P F (x) (z) > P F (y) (z), or F (x) and F (y) have the same distribution. Some compliant utility functions are given.

x → E(F (x)), the expected value of F (x).

x → E(g(F (x))), for any stricly increasing g : R → R. A generalization of the previous case.

any distribution percentile of F (x). let P p (F (x)) be the p%-pertentile of the distribution of F (x), then 100 p=0 w(p)P p (F (x)) is another possible utility, where w(p) ≥ 0. When w is dirac, the previous case is recovered.

The advantage of a utility-free testbed is that any minimization algorithm, independent of its explicitely or implicitely build-in utility, can be reasonably evaluated.