Problem Definitions and Evaluation Criteria for

the CEC 2010 Competition on Constrained Real-

Parameter Optimization

R. Mallipeddi, P. N. Suganthan
[email protected], [email protected]

Nanyang Technological University, Singapore

Technical Report

April, 2010
Introduction

Most real world optimization problems have constraints of different types (e.g., physical,
time, geometric, etc.) which modify the shape of the search space. During the last couple of
decades, a wide variety of metaheuristics have been designed and applied to solve
constrained optimization problems [1]. Evolutionary algorithms and most other
metaheuristics, when used for optimization, naturally operate as unconstrained search
techniques. Therefore, they require an additional mechanism to incorporate constraints into
their fitness function.

Historically, the most common approach to incorporate constraints (both in evolutionary

algorithms and in mathematical programming) is the penalty functions, which were originally
proposed in the 1940s and later expanded by many researchers. Penalty functions have, in
general, several limitations. Particularly, they are not a very good choice when trying to solve
problem in which the optimum is on the boundary between the feasible and the infeasible
regions or when the feasible region is disjoint. Additionally, penalty functions require a
careful fine-tuning to determine the most appropriate penalty factors to be used with our
metaheuristics. Researchers have also proposed a number of other approaches to handle
constraints such as the self-adaptive penalty, epsilon constraint handling and stochastic
ranking. Additionally, the analysis of the role of the search engine has also become an
interesting research topic in the last few years. For example, evolution strategies (ES),
evolutionary programming (EP), differential evolution (DE) and particle swarm optimization
(PSO) have been found advantageous by some researchers over other metaheuristics such as
the binary genetic algorithms (GA).

In CEC06 [2], 24 benchmark functions have been presented which have 2-20 dimensions and
are not easily scalable. In addition, CEC 2006 benchmark has been solved satisfactorily by
several methods. Therefore, it has become impossible to demonstrate the superior
performance of newly designed algorithms. CEC05 [3] presents some of the scalable bound
constrained problems. In [4] author proposed a test-case generator for constrained parameter
optimization problems. In [5] the authors generated some scalable constrained problems. In
this report, we present 18 benchmark functions which are scalable. The mathematical
formulas and properties of these functions are described in Section 1. In Section 2, the
evaluation criteria are given. A suggested format to present the results is given in Section 3.

1. Definitions of the Function Suite

In this section, 18 optimization problems with constraints are described. They are all
transformed into the following format:

Minimize: f ( X ), X = ( x1 , x 2 ,..., x n ) and X ∈ S … (1)

g i ( X ) ≤ 0, i = 1,..., p
subject to:
h j ( X ) = 0, j = p + 1,..., m
… (2)
Usually equality constraints are transformed into inequalities of the form
h j ( X ) − ε ≤ 0 , for j = p + 1,..., m … (3)
A solution X is regarded as feasible if 0 , for 1, … , and h j ( X ) − ε ≤ 0 , for
j = p + 1,..., m . In this special session is set to 0.0001.
A constrained problem, in which the feasible patches are parallel to the axes (Figure 1), can
be solved better by algorithms employing line search or difference of two or more solution
vectors (such as DE). Therefore, to avoid the test problems from being biased to a particular
class of algorithms, we rotate the constraints in most of the test problems. The effect of
constraints can be observed in Figures 1 & 2. In Figure 2, it can be observed that the points
A, B, C, and D have been rotated in the clockwise direction.

10

6
A B
4

2
Axis 2

-2

-4
C
D
-6

-8

-10
-10 -8 -6 -4 -2 0 2 4 6 8 10
Axis 1

Figure 1: Contour plot without rotation

10

6
A
4

2 B
Axis 2

-2
D
-4
C
-6

-8

-10
-10 -8 -6 -4 -2 0 2 4 6 8 10
Axis 1

Figure 2: Contour plot with rotation

 D D
C01 ∑ cos 4 ( z i ) − 2∏ cos 2 ( z i )
i =1
Min f ( x) = − i =1
z = x−o
D

∑ iz
i =1
2
i

D
g1 ( x) = 0.75 − ∏ z i ≤ 0
i =1
D
g 2 ( x) = ∑ z i − 7.5D ≤ 0
i =1

x ∈ [0,10] D

C02 Min f ( x) = max( z ) z = x − o , y = z − 0 .5

1
[ ]
D
g1 ( x) = 10 − ∑ zi2 − 10 cos(2πz i ) + 10 ≤ 0
D i =1

g 2 ( x) =
1 D 2
[
∑ z i − 10 cos(2πz i ) + 10 − 15 ≤ 0
D i =1
]
h( x ) =
1 D 2
[
∑ yi − 10 cos(2πyi ) + 10 − 20 = 0
D i =1
]
x ∈ [−5.12, 5.12] D

D −1

C03 Min f ( x ) = ∑ (100( z i2 − z i +1 ) 2 + ( z i − 1) 2 ) z = x − o

i =1
D −1
h( x) = ∑ ( z i − z i +1 ) 2 = 0
i =1

x ∈ [−1000, 1000] D

C04 Min f ( x) = max( z ) z = x−o

1 D
h1 ( x) = ∑ ( z i cos( z i ) ) = 0
D i =1
D / 2 −1
h2 ( x) = ∑ (z
i =1
i − z i +1 ) 2 = 0
D −1
h3 ( x) = ∑ (z
i = D / 2 +1
2
i − z i +1 ) 2 = 0
D
h4 ( x) = ∑ z = 0
i =1

x ∈ [−50, 50] D
C05 Min f ( x) = max( z ) z = x−o
1 D
h1 ( x) = ∑ (− z i sin( z i ) ) = 0
D i =1
1 D
h2 ( x ) = ∑ (− z i cos(0.5 z i ) ) = 0
D i =1
x ∈ [−600, 600] D

C06 Min f ( x) = max( z )

z = x − o, y = ( x + 483.6106156535 − o) M − 483.6106156535
1 D
h1 ( x) = ∑ (− yi sin( yi ) ) = 0
D i =1
1 D
h2 ( x) = ∑ (− yi cos(0.5 yi ) ) = 0
D i =1
x ∈ [−600, 600] D

D −1

C07 Min f ( x) = ∑ (100( z i2 − z i +1 ) 2 + ( z i − 1) 2 )

i =1

z = x + 1 − o, y = x − o
1 D 2 1 D
g ( x) = 0.5 − exp(−0.1 ∑
D i =1
y i ) − 3 exp( ∑ cos(0.1 y )) + exp(1) ≤ 0
D i =1
x ∈ [−140, 140]D

D −1
C08 Min f ( x) = ∑ (100( z i2 − z i +1 ) 2 + ( z i − 1) 2 )
i =1

z = x + 1 − o, y = ( x − o ) M
1 D 2 1 D
g ( x) = 0.5 − exp(−0.1 ∑
D i =1
y i ) − 3 exp( ∑ cos(0.1 y )) + exp(1) ≤ 0
D i =1
x ∈ [−140, 140] D

D −1
C09 Min f ( x) = ∑ (100( z i2 − z i +1 ) 2 + ( z i − 1) 2 )
i =1

z = x + 1-o, y = x-o
D
h( x ) = ∑ ( y sin(
i =1
y i )) = 0

x ∈ [−500, 500] D
 D −1
C10 Min f ( x) = ∑ (100( z i2 − z i +1 ) 2 + ( z i − 1) 2 )
i =1

z = x + 1 − o, y = (x-o)M
D
h( x ) = ∑ ( y sin(
i =1
y i )) = 0

x ∈ [−500, 500] D

1 D
C11 Min f ( x) = ∑ (− z i cos(2 z i ))
D i =1
z = ( x-o) M , y = x + 1 − o
D −1
h( x) = ∑ (100( y i2 − y i +1 ) 2 + ( y i − 1) 2 ) = 0
i

x ∈ [−100, 100] D

C12 Min f ( x) = ∑ ( z i sin( z i )) z = x−o

i =1
D −1
h( x) = ∑ ( z i2 − z i +1 ) 2 = 0
i =1
D
g ( x) = ∑ ( z − 100 cos(0.1z ) + 10) ≤ 0
i =1

x ∈ [ −1000, 1000] D

1 D
C13 Min f ( x) = ∑ (− zi sin( zi ))
D i =1
z = x−o

1 D 2
g1 ( x) = −50 + ∑ zi ≤ 0
100 D i
50 D 1
g 2 ( x) = ∑
D i =1
sin( πz ) ≤ 0
50
D
z i2 D
z
g 3 ( x) = 75 − 50(∑ − ∏ cos( i ) + 1) ≤ 0
i =1 4000 i =1 i
x ∈ [ −500, 500] D
 D −1
C14 Min f ( x) = ∑ (100( z i2 − z i +1 ) 2 + ( z i − 1) 2 )
i =1

z = x + 1 -o, y = x-o
D
g1 ( x) = ∑ (− y i cos( y i )) − D ≤ 0
i =1
D
g 2 ( x) = ∑ ( y i cos( y i )) − D ≤ 0
i =1
D
g 3 ( x) = ∑ ( y i sin( y i )) − 10 D ≤ 0
i =1

x ∈ [−1000, 1000] D

D −1
C15 Min f ( x) = ∑ (100( z i2 − z i +1 ) 2 + ( z i − 1) 2 )
i =1

z = x + 1 -o, y = ( x-o) M
D
g1 ( x) = ∑ (− y i cos( y i )) − D ≤ 0
i =1
D
g 2 ( x) = ∑ ( y i cos( y i )) − D ≤ 0
i =1
D
g 3 ( x) = ∑ ( y i sin( y i )) − 10 D ≤ 0
i =1

x ∈ [−1000, 1000] D

D
z i2 D
z
C16 Min f ( x) = ∑ − ∏ cos( i ) + 1 z = x−o
i =1 4000 i =1 i

[ ]
D
g1 ( x) = ∑ z i2 − 100 cos(πz i ) + 10 ≤ 0
i =1
D
g 2 ( x) = ∏ z i ≤ 0
i =1
D
h1 ( x) = ∑ ( z i sin( z i )) = 0
i =1
D
h2 ( x) = ∑ (− z i sin( z i )) = 0
i =1

x ∈ [−10, 10] D
 D −1

C17 Min f ( x ) = ∑ ( z i − z i +1 ) 2 z = x−o

i =1
D
g1 ( x) = ∏ z i ≤ 0
i =1
D
g 2 ( x) = ∑ z i ≤ 0
i =1
D
h( x) = ∑ ( z i sin( 4 z i )) = 0
i =1

x ∈ [−10, 10] D

D −1
C18 Min f ( x) = ∑ ( z i − z i +1 ) 2 z = x−o
i =1

1 D
g ( x) = ∑ (− z i sin( z i )) ≤ 0
D i =1
1 D
h( x ) = ∑ ( z i sin( z i )) = 0
D i =1
x ∈ [−50, 50] D

| |
Table 1: Details of 18 test problems. D is the number of decision variables, | | is the

estimated ratio between the feasible region and the search space, I is the number of inequality
constraints, E is the number of equality constraints

Problem/Search Type of Number of Constraints Feasibility Region (ρ)

Range Objective E I 10D 30D
C01 2
Non Separable 0 0.997689 1.000000
[0,10] D
Non Separable
C02 1 2
D
Separable 0.000000 0.000000
[-5.12,5.12] Separable Separable
C03 1
Non Separable 0 0.000000 0.000000
[-1000,1000] D
Non Separable
4
C04
Separable 2 Non Separable, 2 0 0.000000 0.000000
[-50,50]D
Separable
C05 2
Separable 0 0.000000 0.000000
[-600,600] D
Separable
C06 2
D
Separable 0 0.000000 0.000000
[-600,600] Rotated
 C07 1
Non Separable 0 0.505123 0.503725
[-140,140] D
Separable
C08 1
D
Non Separable 0 0.379512 0.375278
[-140,140] Rotated
C09 1
Non Separable 0 0.000000 0.000000
[-500500] D
Separable
C10 1
D
Non Separable 0 0.000000 0.000000
[-500,500] Rotated
C11 1
Rotated 0 0.000000 0.000000
[-100,100] D
Non Separable
C12 1 1
D
Separable 0.000000 0.000000
[-1000,1000] Non Separable Separable
3
C13
Separable 0 2 Separable, 1 Non 0.000000 0.000000
[-500,500]D
Separable
C14 3
D
Non Separable 0 0.003112 0.006123
[-1000,1000] Separable
C15 3
Non Separable 0 0.003210 0.006023
[-1000,1000] D
Rotated
2
C16 2
Non Separable 1 Separable, 1 Non 0.000000 0.000000
[-10,10]D Separable
Separable
C17 1 2
Non Separable 0.000000 0.000000
[-10,10]D
Separable Non Separable
C18 1 1
D
Non Separable 0.000010 0.000000
[-50,50] Separable Separable

2. Performance Evaluation Criteria

Number of Problems: 18. Number or runs/trials: 25
Maximum Function Evaluations (Max_FES) = 200000 for 10D and 600000 for 30D
Population Size: You are free to have an appropriate population size to suit your algorithm
while not exceeding the Max FES.

2.1 Presentation of Statistics

Record the function value of for the achieved best solution X after 20000, 100000 and
200000 for 10D and 60000, 300000, 600000 for 30D. For each function, present the
following: best, median, worst result, mean value and standard deviation for the 25 runs.
Please indicate the number of violated constraints (including the number of violations by
more than 1, 0.01, and 0.0001) and the mean violations at the median solution.

∑ ∑

where
0
0 0

0
0 0
2.2 Feasibility Rate
Feasible Run: A run during which at least one feasible solution is found in Max FES.
Feasible Rate = (# of feasible runs) / Total runs.
The above quantity is computed for each problem separately.

2.3 Algorithm Complexity

a) 1 ∑ 1 /18. t1i is the computing time of 10000 evaluations for problem i.
b) 2 ∑ 2 /18. t2i is the complete computing time for the algorithm with 10000
evaluations for problem i.
The complexity of the algorithm is reflected by: T1; T2; and (T2-T1)/T 1

2.4 Parameters
We discourage participants searching for a distinct set of parameters for each
problem/dimension/etc. Please provide details on the following whenever applicable:
a) All parameters to be adjusted.
b) Corresponding dynamic ranges.
c) Guidelines on how to adjust the parameters.
d) Estimated cost of parameter tuning in terms of number of FEs.
e) Actual parameter values used.

2.5 Encoding
If the algorithm requires encoding, then the encoding scheme should be independent of the
specific problems and governed by generic factors such as the search ranges.

3. Presentation of Results
Participants are suggested to present their results in the following format:

PC Configure:
System: CPU: RAM:
Language: Algorithm:

Parameters Setting:
a) All parameters to be adjusted.
b) Corresponding dynamic ranges.
c) Guidelines on how to adjust the parameters.
d) Estimated cost of parameter tuning in terms of number of FEs.
e) Actual parameter values used.

Results Obtained
Table 2: Function Values Achieved When FES = 2 10 , FES = 1 10 , FES = 2 10
for 10D Problems C01-C06.
FEs C01 C02 C03 C04 C05 C06
Best 237.9718
Median 358.3837
worst 446.8061
2 10 c 2, 0, 0
5.3256
Mean 350.3861
std 103.2039
Best 152.1540
Median 291.1380
worst 386.3278
1 10 c 0, 2 ,0
4.12E-05
Mean 28.1940
std 101.189
Best -158.7482
Median -55.7482
worst 38.5729
2 10 c 0, 0, 0
0
Mean -69.0852
std 64.4877

Table 3: Function Values Achieved When FES = 2 10 , FES = 1 10 , FES = 2 10

for 10D Problems C07-C12.
FEs C07 C08 C09 C10 C11 C12
2 10 Best
 Median
worst
c

Mean
std
Best
Median
worst
1 10 c

Mean
std
Best
Median
worst
2 10 c

Mean
std

Table 4: Function Values Achieved When FES = 2 10 , FES = 1 10 , FES = 2 10

for Problems C13-C18 of 10D.
FEs C13 C14 C15 C16 C17 C18
Best
Median
worst
2 10 c

Mean
std
Best
Median
worst
1 10 c

Mean
std
Best
Median
2 10
worst
c
 Mean
std

Table 5: Function Values Achieved When FES = 6 10 , FES = 3 10 , FES = 6

10 for Problems C01-C06 of 30D.
FEs C01 C02 C03 C04 C05 C06
Best
Median
worst
6 10 c

Mean
std
Best
Median
worst
3 10 c

Mean
std
Best
Median
worst
c
6 10

Mean
std
std

Table 6: Function Values Achieved When FES = 6 10 , FES = 3 10 , FES = 6

10 for Problems C07-C12 of 30D.
FEs C07 C08 C09 C10 C11 C12
Best
Median
worst
6 10 c

Mean
std
Best
3 10
Median
 worst
c

Mean
std
Best
Median
worst
6 10 c

Mean
std

Table 7: Function Values Achieved When FES = 6 10 , FES = 3 10 , FES = 6 10

for Problems C13-C18 of 30D.
FEs C13 C14 C15 C16 C17 C18
Best
Median
worst
6 10 c

Mean
std
Best
Median
worst
3 10 c

Mean
std
Best
Median
worst
6 10 c

Mean
std

c is the number of violated constraints at the median solution: the sequence of three numbers
indicate the number of violations (including inequality and equalities) by more than 1.0, more
than 0.01 and more than 0.0001 respectively. is the mean value of the violations of all
constraints at the median solution. The numbers in the parenthesis after the fitness value of
the best, median, worst solution are the number of constraints which cannot satisfy feasible
condition at the best, median and worst solutions respectively. Sorting method for the final
results:
1. Sort feasible solutions in front of infeasible solutions;
2. Sort feasible solutions according to their function values f(x*)
3. Sort infeasible solutions according to their mean value of the violations of all constraints.

Algorithm Complexity
Table 8: Computational Complexity
T1 T2 (T2-T1)/T1

Convergence Graphs
The participants are expected to plot the convergence plots for the 10D and 30D problems of
C09, C10, C14, C15, C17 and C18. The plot should show only feasible solutions of the best
run out of the 25 runs.
Plot 1 – Convergence plot for 10D problems C09, C10, C14 and C15.
Plot 2 – Convergence plot for 30D problems C09, C10, C14 and C15.
Plot 3 – Convergence plot for 10D problems C17 and C18.
Plot 4 – Convergence plot for 30D problems C17 and C18.

Evaluation Criteria
1. The algorithms should not use explicit equations. Only the use of function calls is
allowed.
2. Gradients, etc. can only be computed numerically and the function evaluations consumed
in the process of gradient computations should be accumulated.
3. Evaluation of even one constraint function should be treated as one function evaluation.

References
[1] D. E. Goldberg, M. Samtani, “Engineering optimization via genetic algorithm”, Proc.
of 9th Conf. on Electronic Computation, pp. 471-482, University of Alabama, 1986.
[2] J. J. Liang, T. P. Runarsson, E. Mezura-Montes, M. Clerc, P. N. Suganthan, C. A.
 Coello Coello, and K. Deb, "Problem Definitions and Evaluation Criteria for the CEC
2006 Special Session on Constrained Real-Parameter Optimization," Technical
Report, Nanyang Technological University, Singapore. Available from
http://www3.ntu.edu.sg/home/EPNSugan/.
[3] P. N. Suganthan, N. Hansen, J. J. Liang, K. Deb, Y. –P. Chen, A. Auger, S. Tiwari,
Problem Definitions and Evaluation Criteria for the CEC 2005 Special Session on
Real-Parameter Optimization. in Technical Report. 2005. Nanyang Technological
University, Singapore, May 2005 AND KanGAL Report #2005005, IIT Kanpur, India.
Available from http://www3.ntu.edu.sg/home/EPNSugan/.
[4] Z. Michalewicz, K. Deb, and T. Stidsen, “Test-Case Generator for Nonlinear
Continuous parameter Optimization Techniques”, IEEE Transactions on Evolutionary
Computation, Vol. 4, No. 3, September 2000.
[5] R. Mallipeddi and P. N. Suganthan, “ Ensemble of Constraint Handling Techniques”,
IEEE Trans. on Evolutionary Computation, available online from IEEE Xplore.