arXiv:1008.0549v1 [math.OC] 3 Aug 2010
ar
X
iv
:1
00
8.
05
49
v1
[
m
at
h.
O
C
]
3
A
ug
2
01
0 Test Problems in Optimization
Xin-She Yang
Department of Engineering, University of Cambridge,
Cambridge CB2 1PZ, UK
Abstract
Test functions are important to validate new optimization algorithms
and to compare the performance of various algorithms. There are many
test functions in the literature, but there is no standard list or set of test
functions one has to follow. New optimization algorithms should be tested
using at least a subset of functions with diverse properties so as to make
sure whether or not the tested algorithm can solve certain type of opti-
mization efficiently. Here we provide a selected list of test problems for
unconstrained optimization.
Citation detail:
X.-S. Yang, Test problems in optimization, in: Engineering Optimization: An Introduc-
tion with Metaheuristic Applications (Eds Xin-She Yang), John Wiley & Sons, (2010).
http://arxiv.org/abs/1008.0549v1
In order to validate any new optimization algorithm, we have to validate it against
standard test functions so as to compare its performance with well-established or existing
algorithms. There are many test functions, so there is no standard list or set of test functions
one has to follow. However, various test functions do exist, so new algorithms should be
tested using at least a subset of functions with diverse properties so as to make sure whether
or not the tested algorithm can solve certain type of optimization efficiently.
In this appendix, we will provide a subset of commonly used test functions with simple
bounds as constraints, though they are often listed as unconstrained problems in literature.
We will list the function form f(x), its search domain, optimal solutions x
∗
and/or optimal
objective value f
∗
. Here, we use x = (x1, …, xn)
T where n is the dimension.
Ackley’s function:
f(x) = −20 exp
[
−
1
5
√
√
√
√
1
n
n
∑
i=1
x2i
]
− exp
[ 1
n
n
∑
i=1
cos(2πxi)
]
+ 20 + e, (1)
where n = 1, 2, …, and −32.768 ≤ xi ≤ 32.768 for i = 1, 2, …, n. This function has the
global minimum f
∗
= 0 at x
∗
= (0, 0, …, 0).
De Jong’s functions: The simplest of De Jong’s functions is the so-called sphere function
f(x) =
n
∑
i=1
x2i , −5.12 ≤ xi ≤ 5.12, (2)
whose global minimum is obviously f
∗
= 0 at (0, 0, …, 0). This function is unimodal and
convex. A related function is the so-called weighted sphere function or hyper-ellipsoid
function
f(x) =
n
∑
i=1
ix2i , −5.12 ≤ xi ≤ 5.12, (3)
which is also convex and unimodal with a global minimum f
∗
= 0 at x
∗
= (0, 0, …, 0).
Another related test function is the sum of different power function
f(x) =
n
∑
i=1
|xi|i+1, −1 ≤ xi ≤ 1, (4)
which has a global minimum f
∗
= 0 at (0, 0, …, 0).
Easom’s function:
f(x) = − cos(x) cos(y) exp
[
− (x− π)2 + (y − π)2
]
, (5)
whose global minimum is f
∗
= −1 at x
∗
= (π, π) within −100 ≤ x, y ≤ 100. It has many
local minima. Xin-She Yang extended in 2008 this function to n dimensions, and we have
f(x) = −(−1)n
(
n
∏
i=1
cos2(xi)
)
exp
[
−
n
∑
i=1
(xi − π)2
]
, (6)
whose global minimum f
∗
= −1 occurs at x
∗
= (π, π, …, π). Here the domain is −2π ≤
xi ≤ 2π where i = 1, 2, …, n.
Equality-Constrained Function:
f(x) = −(
√
n)n
n
∏
i=1
xi, (7)
subject to an equality constraint (a hyper-sphere)
n
∑
i=1
x2i = 1. (8)
The global minimum f
∗
= −1 of f(x) occurs at x
∗
(1/
√
n, …, 1/
√
n) within the domain
0 ≤ xi ≤ 1 for i = 1, 2, …, n.
Griewank’s function:
f(x) =
1
4000
n
∑
i=1
x2i −
n
∏
i=1
cos(
xi√
i
) + 1, −600 ≤ xi ≤ 600, (9)
whose global minimum is f
∗
= 0 at x
∗
= (0, 0, …, 0). This function is highly multimodal.
Michaelwicz’s function:
f(x) = −
n
∑
i=1
sin(xi) ·
[
sin(
ix2i
π
)
]2m
, (10)
where m = 10, and 0 ≤ xi ≤ π for i = 1, 2, …, n. In 2D case, we have
f(x, y) = − sin(x) sin20(x
2
π
)− sin(y) sin20(2y
2
π
), (11)
where (x, y) ∈ [0, 5] × [0, 5]. This function has a global minimum f
∗
≈ −1.8013 at
x
∗
= (x
∗
, y
∗
) = (2.20319, 1.57049).
Perm Functions:
f(x) =
n
∑
j=1
{
n
∑
i=1
(ij + β)
[
(
xi
i
)j − 1
]}
, (β > 0), (12)
which has the global minimum f
∗
= 0 at x
∗
= (1, 2, …, n) in the search domain −n ≤ xi ≤ n
for i = 1, …, n. A related function
f(x) =
n
∑
j=1
{
n
∑
i=1
(i+ β)
[
x
j
i − (
1
i
)j
]}2
, (13)
has the global minimum f
∗
= 0 at (1, 1/2, 1/3, …, 1/n) within the bounds −1 ≤ xi ≤ 1 for
all i = 1, 2, …, n. As β > 0 becomes smaller, the global minimum becomes almost indistin-
guishable from their local minima. In fact, in the extreme case β = 0, every solution is also
a global minimum.
Rastrigin’s function:
f(x) = 10n+
n
∑
i=1
[
x2i − 10 cos(2πxi)
]
, −5.12 ≤ xi ≤ 5.12, (14)
whose global minimum is f
∗
= 0 at (0, 0, …, 0). This function is highly multimodal.
Rosenbrock’s function:
f(x) =
n−1
∑
i=1
[
(xi − 1)2 + 100(xi+1 − x2i )2
]
, (15)
whose global minimum f
∗
= 0 occurs at x
∗
= (1, 1, …, 1) in the domain −5 ≤ xi ≤ 5 where
i = 1, 2, …, n. In the 2D case, it is often written as
f(x, y) = (x− 1)2 + 100(y − x2)2, (16)
which is often referred to as the banana function.
Schwefel’s function:
f(x) = −
n
∑
i=1
xi sin
(
√
|xi|
)
, −500 ≤ xi ≤ 500, (17)
whose global minimum f
∗
≈ −418.9829n occurs at xi = 420.9687 where i = 1, 2, …, n.
Six-hump camel back function:
f(x, y) = (4− 2.1×2 +
1
3
x4)x2 + xy + 4(y2 − 1)y2, (18)
where −3 ≤ x ≤ 3 and −2 ≤ y ≤ 2. This function has two global minima f
∗
≈ −1.0316 at
(x
∗
, y
∗
) = (0.0898,−0.7126) and (−0.0898, 0.7126).
Shubert’s function:
f(x) =
[
n
∑
i=1
i cos
(
i+ (i+ 1)x
)]
·
[
n
∑
i=1
i cos
(
i+ (i+ 1)y
)]
, (19)
which has 18 global minima f
∗
≈ −186.7309 for n = 5 in the search domain −10 ≤ x, y ≤ 10.
Xin-She Yang’s functions:
f(x) =
(
n
∑
i=1
|xi|
)
exp
[
−
n
∑
i=1
sin(x2i )
]
, (20)
which has the global minimum f
∗
= 0 at x
∗
= (0, 0, …, 0) in the domain −2π ≤ xi ≤ 2π
where i = 1, 2, …, n. This function is not smooth, and its derivatives are not well defined at
the optimum (0, 0, …, 0).
A related function is
f(x) = −
(
n
∑
i=1
|xi|
)
exp
(
−
n
∑
i=1
x2i
)
, −10 ≤ xi ≤ 10, (21)
which has multiple global minima. For example, for n = 2, we have 4 equal minima
f
∗
= −1/
√
e ≈ −0.6065 at (1/2, 1/2), (1/2,−1/2), (−1/2, 1/2) and (−1/2,−1/2).
Yang also designed a standing-wave function with a defect
f(x) =
[
e−
∑
n
i=1
(xi/β)
2m
− 2e−
∑
n
i=1
x2
i
]
·
n
∏
i=1
cos2 xi, m = 5, (22)
which has many local minima and the unique global minimum f
∗
= −1 at x
∗
= (0, 0, …, 0)
for β = 15 within the domain −20 ≤ xi ≤ 20 for i = 1, 2, …, n.
The location of the defect can easily be shift to other positions. For example,
f(x) =
[
e−
∑
n
i=1
(xi/β)
2m
− 2e−
∑
n
i=1
(xi−π)
2
]
·
n
∏
i=1
cos2 xi, m = 5, (23)
has a unique global minimum f
∗
= −1 at x
∗
= (π, π, …, π)
Yang also proposed another multimodal function
f(x) =
{[
n
∑
i=1
sin2(xi)
]
− exp(−
n
∑
i=1
x2i )
}
· exp
[
−
n
∑
i=1
sin2
√
|xi|
]
, (24)
whose global minimum f
∗
= −1 occurs at x
∗
= (0, 0, …, 0) in the domain −10 ≤ xi ≤ 10
where i = 1, 2, …, n. In the 2D case, its landscape looks like a wonderful candlestick.
Most test functions are deterministic. Yang designed a test function with stochastic
components
f(x, y) = −5e−β[(x−π)2+(y−π)2] −
K
∑
j=1
K
∑
i=1
ǫije
−α[(x−i)2+(y−j)2], (25)
where α, β > 0 are scaling parameters, which can often be taken as α = β = 1. Here ǫij
are random variables and can be drawn from a uniform distribution ǫij ∼ Unif[0,1]. The
domain is 0 ≤ x, y ≤ K and K = 10. This function has K2 local valleys at grid locations
and the fixed global minimum at x
∗
= (π, π). It is worth pointing that the minimum fmin
is random, rather than a fixed value; it may vary from −(K2 + 5) to −5, depending α and
β as well as the random numbers drawn.
Furthermore, he also designed a stochastic function
f(x) =
n
∑
i=1
ǫi
∣
∣
∣
xi −
1
i
∣
∣
∣
, −5 ≤ xi ≤ 5, (26)
where ǫi (i = 1, 2, …, n) are random variables which are uniformly distributed in [0, 1]. That
is, ǫi ∼Unif[0, 1]. This function has the unique minimum f∗ = 0 at x∗ = (1, 1/2, …, 1/n)
which is also singular.
Zakharov’s functions:
f(x) =
n
∑
i=1
x2i +
(1
2
n
∑
i=1
ixi
)2
+
(1
2
n
∑
i=1
ixi
)4
, (27)
whose global minimum f
∗
= 0 occurs at x
∗
= (0, 0, …, 0). Obviously, we can generalize this
function as
f(x) =
n
∑
i=1
x2i +
K
∑
k=1
J2kn , (28)
where K = 1, 2, …, 20 and
Jn =
1
2
n
∑
i=1
ixi. (29)
References
[1] D. H. Ackley, A Connectionist Machine for Genetic Hillclimbing, Kluwer Academic
Publishers, 1987.
[2] C. A. Floudas, P. M., Pardalos, C. S. Adjiman, W. R. Esposito, Z. H. Gumus, S. T.
Harding, J. L. Klepeis, C. A., Meyer, C. A. Scheiger, Handbook of Test Problems in
Local and Global Optimization, Springer, 1999.
[3] A. Hedar, Test function web pages, http://www-optima.amp.i.kyoto-u.ac.jp
/member/student/hedar/Hedar files/TestGO files/Page364.htm
[4] M. Molga, C. Smutnicki, “Test functions for optimization needs”,
http://www.zsd.ict.pwr.wroc.pl/files/docs/functions.pdf
[5] X.-S. Yang, “Firefly algorithm, Lévy flights and global optimization”, in: Research and
Development in Intelligent Systems XXVI, (Eds M. Bramer et al.), Springer, London,
pp. 209-218 (2010).
[6] X.-S. Yang and S. Deb, “Engineering optimization by cuckoo search”, Int. J. Math.
Modeling and Numerical Optimization, 1, No. 4, 330-343 (2010).
[7] X.-S. Yang, “Firefly algorithm, stochastic test functions and design optimization”, Int.
J. Bio-inspired Computation, 2, No. 2, 78-84 (2010).