Benchmarking Projection-Based Real Coded Genetic
Algorithm on BBOB-2013 Noiseless Function Testbed
Babatunde A. Sawyerr

Aderemi O. Adewumi

Montaz M. Ali

Department of Computer
Sciences
University of Lagos
Lagos, Nigeria

School of Mathematics,
Statistics and Computer
Science
University of KwaZulu-Natal
Westville, South Africa

School of Computational andApplied Mathematics
University of The
Witwatersrand
Johannesburg, South Africa

bsawyerr@unilag.edu.ng

Adewumia@ukzn.ac.za

ABSTRACTIn this paper, a real-coded genetic algorithm (RCGA) which
incorporates an exploratory search mechanism based on vector projection termed projection-based RCGA (PRCGA) isbenchmarked on the noisefree BBOB 2013 testbed. It is anenhanced version of RCGA-P in [22, 23]. The projection operator incorporated in PRCGA shows promising exploratory
search capability in some problem landscape. PRCGA isequipped with a multiple independent restart mechanism
and a stagnation alleviation mechanism. The maximum
number of function evaluations (#F Es) for each test run
is set to 105 times the problem dimension. PRCGA shows
encouraging results on several problems in the low and moderate search dimensions. It is able to solve each type of problem with the dimension up to 40 with lower precision but
not all the functions to the desired level of accuracy of 10−8
especially for high conditioning and multi-modal functions
within the specified maximum #F Es.

Categories and Subject Descriptors
G.1.6 [Numerical Analysis]: Optimization—global optimization, unconstrained optimization; F.2.1 [Analysis of
Algorithms and Problem Complexity]: Numerical Algorithms and Problems

Keywords
Benchmarking, Black-box optimization, Real-coded Genetic
Algorithm, Projection

1.

INTRODUCTION

Genetic algorithms (GAs) are a class of stochastic algorithms based on the notion of natural selection and natural
genetics by Charles Darwin. The simple genetic plan wasdeveloped in 1975 by John Holland [18]. GAs later became
popular largely due to the outstanding work of the students

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
GECCO’13 Companion, July 6–10, 2013, Amsterdam, The Netherlands.
Copyright 2013 ACM 978-1-4503-1964-5/13/07 ...$15.00.

Montaz.Ali@wits.ac.za

of Holland especially Kenneth De Jong [10] and David Goldberg [14]. Subsequently, several variants of GAs have beenused to solve many real-world optimization problems arisingfrom diverse fields [2, 11, 14, 20].
The simple GA consists of a set of binary strings of potential solutions called chromosomes, a selection operator, acrossover operator and a mutation operator. The selection
operator selects solutions for mating based on the principleof ‘survivial of the fittest.’ The crossover operator generates new solution pairs by mixing the genetic materials of
the selected parent chromosomes. The mutation operator isapplied, with low probability, to the population of chromosomes to prevent premature convergence of the solutions tolocal optimum [14].
Binary string GAs, also known as Binary-coded genetic
algorithms (BCGAs) are robust search algorithms that havebeen successfully used to solve several challenging problems
but are computationally expensive in solving continuous andlarge scale optimization problems [13].
Real-coded genetic algorithms (RCGAs) are RCGAs withreal-valued chromosomes. They are designed to tackle theproblems encountered by BCGAs in the continuous parameter optimization domain. Recent works on RCGAs can befound in [1, 2, 7, 8, 9, 19, 20]. Despite the advantages of
RCGAs in the continuous parameter domain they are stillsusceptible to the problem of premature convergence, therefore hybridization has been employed by researchers to prevent RCGAs from falling into premature convergence [3, 5,
6].
The projection-based exploration search method designed
for RCGA in [22, 23] is based on the concept of orthogonal
projection of a vector x on a vector y. Figure 1 provides
an illustration of projecting a vector x on another vector y,a well known concept in linear algebra but relatively new
to the field of evolutionary computation. For a detailed description of this concept see [23].
In this paper, an enhanced projection-based RCGA wasdeveloped using the well-known tournament selection, blendα crossover and non-uniform mutation operators to drive thegenetic search.

2. PRCGA ALGORITHM
PRCGA consists of five operators namely; tournament selection, blend-α crossover, non-uniform mutation, projection and a stagnation alleviation mechanism. The outline of
PRCGA is shown in Algorithm 1.

vidual is selected and assigned to P̂t , the mating pool. This
procedure is repeated m times to populate P̂t . All individual in Pt have the probability of been selected several times,
i.e., tournament selection with replacement was used.
Algorithm 1. The PRCGA Algorithm
Input: Fitness function f ; Parameters
Output: Best solution xbest ; f (xbest )1. Initialize Pt=0 , Pt = {x1,t , x2,t , . . . , xN,t } from S
2. f (xi,t ) = evaluate(Pt ), {1 ≤ i ≤ N }3. While not stopping condition, do steps 4 - 12
4. ζt = σ(f (Pt )), if ζt ≤ ǫ do step 5 else step 6
5. P̂t = perturb(Pt )Figure 1: Projection of vector x on vector y

6. P̂t = tournamentSelection(Pt )The notations used are defined as:
Let x∗ be the global minimizer of the objective function,f : S ⊂ ℜn → ℜ if f (x∗ ) ≤ f (x), ∀x ∈ S. The pointTx = x1 , x2 , . . . , xn
∈ ℜn . The domain of S, is definedby specifying upper uj and lower lj limits of each j thjjjcomponent of x, i.e., l ≤ x ≤ u and lj , uj ∈ ℜ, j =1, 2, . . . , n. Without loss of generality, only minimization
problems are considered since maximizing f is equivalent tominimizing −f .
Pt denotes the population of solutions at time t, N is thenumber of solutions in Pt i.e. the population size, σ(f (Pt ))represents the standard deviation function, ζt is the standard deviation of the fitness values f (Pt ) of all solutions
xi,t , ∈ Pt , P̂t is the mating pool containing the parent solutions, Ct is the population of offspring solutions obtained after applying crossover on the parents in P̂t , pc is the crossoverprobability, Mt is the resultant population of solutions after
applying mutation on Ct , pm is the mutation probability,
Φt is the population of solutions obtained after projection
has been applied to Mt and ǫ = 10−12 , a very small positive
value.
For each genetic run in Algorithm 1, P0 is initialized fromthe search space S and the fitness value f (xi,t ), ∀xi,t ∈ P0
is calculated. At each time step t, the population diversityof Pt is measured by calculating the standard deviation ζt
as follows
ζt = σ(f (Pt )).

(1)

If ζt ≤ ǫ and the global optimum has not been found,then 90% of Pt is refreshed with newly generated solutions
using the function perturb(Pt ). Pt is refreshed by sorting
the solutions according to their fitness values and preserving
the top 10% of Pt . The remaining 90% of Pt are replacedwith uniformly generated random values from the interval[−4, 4]D . The resultant population is the mating pool, P̂t ={x1,t , x2,t , . . . , xm,t }, where m is the size of the mating pooland m ≤ N . On the other hand, if ζt > ǫ then tournament
selection is applied on Pt to create the mating pool P̂t .
Tournament selection was used to select ηtour number ofsolutions uniformly at random from Pt , where ηtour is thetournament size, ηtour < N . The fitness values of the selected individuals in ηtour are compared and the best indi-

7. Ct = blend-αCrossover(Pˆt , pc )8. Mt = non-uniformMutation(Ct , pm )9. Φt = projection(Mt )10. f (xi,t ) = evaluate(Φt )11. Pt+1 = replace(Pt ,Φt )12. t = t + 1
13. end while

Blend-α crossover is carried out on a pair (xi,t , xk,t ) whena randomly generated number µ, (0 ≤ µ ≤ 1) is greaterthan the specified crossover probability threshold, i.e., µi >pc . Blend-α crossover uniformly draws the new pair of offspring (c1,t , c2,t ) from the interval [min(xji,t , xjk,t ) − α ∗ dj ,max(xji,t , xjk,t ) + α ∗ dj ] as follows
cj1,t = (min(xji,t , xjk,t ) − α ∗ dj , max(xji,t , xjk,t ) + α ∗ dj )cj2,t = (min(xji,t , xjk,t ) − α ∗ dj , max(xji,t , xjk,t ) + α ∗ dj ), (2)where (1 ≤ k ≤ N ), α = 0.3 + 0.2 × z, z is a uniform random
number drawn from the interval [0, 1], dj = xji,t − xjk,t .
The new pair (c1,t , c2,t ) is then copied to the set Ct , otherwise the pair (xi,t , xk,t ) is copied to Ct .
Then the non-uniform mutation [20] is applied to the components of each member of Ct with probability, pm as follows
 jci,t + ∆(t, uj − cji,t ) if τ ≤ 0.5,
mji,t =
(3)
cji,t − ∆(t, cji,t − lj ) otherwise.
where τ is a uniformly distributed random number in theinterval [0, 1]. uj and lj are the upper and lower boundaries
of x ∈ S, respectively. The function ∆(t, uj − cji,t ) given
below takes a value in the interval [0, y]t∆(t, y) = y(1 − r (1− T ) )β ,(4)where r is a uniformly distributed random number in theinterval [0, 1], T is the maximum number of generations andβ is a parameter that determines the non-uniform strength

of the mutation operator. The mutated individual mi,t isthen copied to the set Mt , otherwise ci,t is copied to Mt .
Projection operation is used to generate Φt from Mt byrandomly taking a pair of solutions, (mi,t , mk,t ), for eachmi,t ∈ Mt and a projected solution ωi,t ∈ Φt is created.
This operation works by comparing the fitness of the two
selected parents and the weaker parent is projected onto thebetter parent so that the resultant offspring will be derived
along the path of the better parent as follows:
If f (mi,t ) is better than f (mk,t ) then,

ωi,t =

mTk,t mi,t
mTk,t mi,t
m
=
mi,t
i,t
mTi,t mi,tkmi,t k2
kmk,t k cos(θ)
mi,t=kmi,t k(5)

Finally, elitism is used to replace the worst point(s) in Pt+1
with the best solution(s) in Pt because the replacement strategy used is the generational model [10].

EXPERIMENTAL PROCEDURE

The experimental setup was carried out according to [15]on the benchmark functions provided in [12, 17]. Two independent restart strategies were used for PRCGA in thiswork. For each restart strategy, the genetic run is initiatedwith an initial population P0 which is uniformly and randomly sampled from the search space [−4, 4]D .
Whenever the restart conditions are met, the algorithm
is reinitialized and restarted without using any informationfrom the previous run. The first restart strategy used determines if the best solution obtained so far did not vary bymore than 10−12 during the last (50 + 25 × D) generations
as in [4] while the second restart condition is when the maximum number of generations is satisfied and ftarget is notfound.

4.

The CPU timing experiment was conducted for PRCGA
using the same independent restart strategies on the function f8 for a duration of 30 seconds on an AMD Turion(tm)II Ultra Dual-Core mobile M 620 CPU processor, running
at 2.50GHz under a 32-bit Microsoft Windows 7 Professional service pack 1 with 2.75GB RAM usable and Matlab
7.10(R2010a).
The time per function evaluation was 7.1, 7.5, 6.9, 6.9, 7.1
and 8.0 times 10−5 seconds for PRCGA in dimensions 2, 3, 5,
10, 20 and 40 respectively.

6. RESULTS

Note that the projected vector ωi,t (the offspring) will be in
the same direction as mi,t unless π2 < θ < 3π
in which case2
the angle θ between the two vectors is such that cos(θ) < 0.
As a result, the projected vector is in the opposite direction (the reflection of mi,t about the origin). Hence Φt ={ω1,t , ω2,t , . . . , ωN,t }.
jSometimes the components ωi,tof the trial point ωi,t may
fall outside the search space S. In such cases, the correj
sponding component ωi,t
is regenerated. After the projected
vector is generated, its fitness value f (ωi,t ) is determined
and a new population, Pt+1 , is created with xi,t , where,ωi,t if f (ωi,t ) < f (mi,t ), mi,t ∈ Mt
xi,t =(6)
mi,t otherwise.

3.

5. CPU TIMING EXPERIMENTPARAMETER SETTINGS

The parameters used for the proposed version of PRCGA
are: Population size is dimension dependent with population size of min(100, 10 × D), maximum number of evaluation #F Es = 105 × D , tournament size ηtour = 3, crossover
rate pc = 0.8, mutation rate pm = 0.15, the non-uniformity
factor for the mutation β = 15. The parameter setting mentioned above was used for all functions. The crafting effort
is CrE = 0 [15].

The results of PRCGA from experiments carried out according to [15] on the benchmark functions given in [12, 17]
are presented in Figures 2, 3, 4 and 5 and in Table 1.
Figure 2 shows the performance of PRCGA on all thebenchmark functions with dimensions 2, 3, 5, 10, 20 and 40.
PRCGA performed quite well on separable functions f1 −f4 and Gallagher’s Gaussian 101-me Peaks Function f21 ,which is a multi-modal function with weak global structure.
PRCGA showed some encouraging performance in solving
problems f6 − f7 in dimensions 2 − 10, while it could notachieve the desired precision of 10−8 beyond dimension 3 in
Rastrigin Function f15 and Weierstrass Function f16 neither
could it achieve the desired precision beyond dimension 5 in
Schaffers F7 f17 and Schwefel Function f20 .
Some functions that prove to be hard and laborious for
PRCGA are Ellipsoidal Function f10 , Discus f11 and Lunacek bi-Rastrigin Function f24 . Apart from these functions, PRCGA performed reasonably well with low levels of
precision on majority of the test functions.
By comparing the performance of PRCGA with previous GAs benchmarked on these test functions, DBRCGA [4]outperformed PRCGA probably due to the direction-based
crossover used in DBRCGA while PRCGA performed better
than the variant of RCGA in [24] and simpleGA [21].
From all the results presented above, it can be seen thatGAs are able to exploit the separability properties of thetest functions but are not able to navigate through deceptive, highly multimodal, highly rugged functions and nonseparable quadratic functions with local irregularities.

7. CONCLUSION
The benchmarking of PRCGA, a real-coded genetic algorithm based on vector projection on noiseless black-box
optimization tesbed has shown the strength and weaknessesof the algorithm. PRCGA has produced some impressive
results and shown to be better than some other variants of
RCGA [21, 24]. The performance of PRCGA on BBOB-2013
shows that PRCGA is an improvement over RCGA-P which
could not achieve the desired precision of 10−8 in most of thetest functions. Further modifications to RCGA are needed
and are currently being carried out based on the observed
weaknesses of PRCGA.
From the performance of PRCGA, it is obvious that in its
current state it cannot compete with the current state-ofthe-art evolutonary algorithms such as the variants of CMAES in [16]. Research is under way to improve PRCGA sothat it can comfortable solve most if not all the BBOB-2013
test functions.

1 Sphere

2 Ellipsoid separable
4

4
3

-8
-5
-3
-2
-1
0
1
10

2
1
0

2

3

6 1
5

14

5
20
5 Linear slope
5

2

40
4

13

4
3
2
1
0
2

6
5
4
3
2
1
0
2

3

3

61
5
4
3
2
1
0

1

2

3

5

5

10

20

19 Rosenbrock rotated
2
4

5

10

20

13 Sharp1 ridge

2

2

5

10

20

3

6
5
4
3
2
1
0
2

3

62
5
4
3
2
1
0

1

40

2

57
4
3
2
1
0

40
6

13

2

6

5

10

3

5

10

10 Ellipsoid

20

5

3

5

40

20

40

9

10

9

20
8

2

3

2

2

3

6
5
4
3
2
1
0

1

0

0

0

6
5
4
3
2
1
0

5

13

2

10

20

40

3

5

6

10

20

40

20

2

11

9

5

10

20

15 Rastrigin 1

2

6
5
4
3
2
1
0

3

5

10

20

22 Gallagher
1 21 peaks
1
3

2

3

5

10

20

40

3

40

2

8

6
58
4
3
2
1
0

40

2

14

2

6
5 14
4
3
2
1
0
2

3
4

5

10

23
Katsuuras
1
12

20
4

3
4

3

2 3

10

20

5

10

12 Bent2 cigar
2

5

10

20
3

20

5
4
3
2
1
0

6

20

14

14

6

5 11

5

-8
-5
-3
-2
-1
0
1

1
0

20

40

13

5
3
10
20
40
24
Lunacek bi-Rastrigin
1
1

2

10

1

40

10

3

5

40

5

4

3

3

40

14

2

40

163 Weierstrass
7

20 Schwefel
x*sin(x)
3

40
1

5

8 Rosenbrock1 original
1
1

8

5
4
3
2
1
0

12

3
1

2

40

3

5

1

3

10

11 Discus
1

12

14

6
5
4
3
2
1
0

10

14

5

40

2

2

21 Gallagher 101 peaks
1
2

20

4 Skew Rastrigin-Bueche8
11 separ

5
4
3
2
1
0

5
2 3
10
20
40
19 Griewank-Rosenbrock
F8F2
3

1

2

10

3

3

2

14

5

7 Step-ellipsoid
2

9

4

4

3

3

62
5
4
3
2
1
0

40

18 Schaffer
F7, condition
1000
1
1
2

2
5
4
3
2
1
0

10

10

12

1

14 Sum3of different powers
11

3 Rastrigin separable
5

5
4
3
2
1
0

40

3

57

4

20

6 Attractive
1 sector
2
10

5

17 Schaffer
F7, condition
10
2
4
5

2

40

1

4

10

5
4
3
2
1
0

2

3

5

10

20

40

Figure 2: Expected number of f -evaluations (ERT, lines) to reach fopt + ∆f ; median number of f -evaluations(+) to reach the most difficult target that was reached not always but at least once; maximum number off -evaluations in any trial (×); interquartile range with median (notched boxes) of simulated runlengths toreach fopt + ∆f ; all values are divided by dimension and plotted as log10 values versus dimension. Shown are∆f = 10{1,0,−1,−2,−3,−5,−8} . Numbers above ERT-symbols (if appearing) indicate the number of trials reaching
the respective target. The light thick line with diamonds indicates the respective best result from BBOB-2009
for ∆f = 10−8 . Horizontal lines mean linear scaling, slanted grid lines depict quadratic scaling.

D=5

1.0
0.8

proportion of trials

proportion of trials

0.6

0.8

0.6

1
4
2
3
log10 of
FEvals / DIM
f6-9,5-D
1: 4/4-1: 3/4-4: 2/4-8: 2/4

5-6 -4 -2

0 2 4
log10 of Df

0.6

1
4
2
3
log10 of FEvals / DIM
1: 5/5 f10-14,5-D-1: 3/5-4: 3/5-8: 0/5

5-6 -4 -2

0 2 4
log10 of Df

6

f6-9,5-D
8

0.6

1
4
2
3
log10 of FEvals / DIM
1: 5/5 f15-19,5-D-1: 4/5-4: 2/5-8: 1/5

5-6 -4 -2

0 2 4
log10 of Df

f10-14,5-D
6 8

0.6

1
4
2
3
log10 of FEvals / DIM
1: 5/5 f20-24,5-D-1: 4/5-4: 3/5-8: 3/5

5-6 -4 -20 2log10 of Df

0.6-6 -4 -2

0 2 4
log10 of Df

1
4
2
3
log10 of FEvals / DIM
1: 5/5 f15-19,20-D-1: 2/5-4: 0/5-8: 0/5

5-6 -4 -2

0 2 4
log10 of Df

1
4
2
3
log10 of FEvals / DIM
1: 5/5 f20-24,20-D-1: 0/5-4: 0/5-8: 0/5

5-6 -4 -2

0 2 4
log10 of Df

1
4
2
3
log10 of FEvals / DIM
1: 23/24 f1-24,20-D-1: 11/24-4: 5/24-8: 3/24

5-6 -4 -2

0 2 4
log10 of Df

1

5-6 -4 -2

0 2 4
log10 of Df

f6-9,20-D
6 8

f10-14,20-D
6 8

f15-19,20-D
6 8

0.2

1
4
2
3
log10 of FEvals / DIM
1: 24/24 f1-24,5-D-1: 19/24-4: 15/24-8: 10/24

5-6 -4 -20 2log10 of Df

f20-24,5-D
4 6 8

0.00
1.0
0.8

0.6

0.4

f20-24,20-D
6 8

0.4

0.2

0.00

5

0.4

proportion of trials

0.6

0.00
1.0
0.8

0.2

0.8

4
2
3
log10 of FEvals / DIM
1: 4/5 f10-14,20-D-1: 3/5-4: 0/5-8: 0/5

f1-5,20-D
6 8

0.2

f15-19,5-D
4 6 8

0.4

0.00
1.0

0 2 4
log10 of Df

0.4

proportion of trials

0.6

0.0
1.0
0.8

0.2

0.8

-6 -4 -2

0.2

0.4

0.00
1.0

5

0.4

proportion of trials

0.6

0.0
1.0
0.8

0.2

0.8

1
4
2
3
log10 of FEvals / DIM
1: 4/4 f6-9,20-D-1: 2/4-4: 1/4-8: 0/4

0.2

0.4

0.00
1.0

D = 200.4

proportion of trials

0.6

0.00
1.0
0.8

0.2

0.8

f1-5,20-D

0.2

f1-5,5-D
6 8

0.4

0.00
1.0

1: 5/5-1: 4/5-4: 4/5-8: 3/5

0.4

proportion of trials

0.00
1.0
proportion of trials

misc. moderate fcts

f1-5,5-D

0.2

proportion of trials

ill-conditioned fcts

1: 5/5-1: 5/5-4: 5/5-8: 4/5

0.4

proportion of trials

multi-modal fcts

0.6

proportion of trials

weak structure fcts
all functions

0.8

proportion of trials

separable fcts

1.0

0.2

1

4
2
3
log10 of FEvals / DIM

5-6 -4 -2

0 2 4
log10 of Df

f1-24,5-D
6 8

0.00

4
2
3
log10 of FEvals / DIM

f1-24,20-D
6 8

Figure 3: Empirical cumulative distribution functions (ECDF), plotting the fraction of trials with an outcome
not larger than the respective value on the x-axis. Left subplots: ECDF of the number of function evaluations(FEvals) divided by search space dimension D, to fall below fopt + ∆f with ∆f = 10k , where k is the first value
in the legend. The thick red line represents the most difficult target value fopt + 10−8 . Legends indicate foreach target the number of functions that were solved in at least one trial within the displayed budget. Right
subplots: ECDF of the best achieved ∆f for running times of 0.5D, 1.2D, 3D, 10D, 100D, 1000D, . . . function
evaluations (from right to left cycling cyan-magenta-black. . . ) and final ∆f -value (red), where ∆f and Df
denote the difference to the optimal function value. Light brown lines in the background show ECDFs for∆f = 10−8 of all algorithms benchmarked during BBOB-2009.

5-D

20-D

1e+1
1e+0
1e-1
1e-2
1e-3
1e-5
1e-7
#succ 1e+1
1e+0
1e-1
1e-2
1e-3
1e-5
1e-7
#succ
∆f
11
12
12
12
12
12
12
f15/15
43
43
43
43
43
43
43
15/15
1
4.1(7)
25(12)
48(18)
83(24)
166(65)352(453) 1757(3289)15/15 36(6)72(7)
120(27)
182(45)287(152) 1166(1000) 6963(6562) 15/15
f2
83
87
88
89
90
92
94
f15/15
385
386
387
388
390
391
393
15/15
2
13(4)
37(61)
52(88)
80(97)
353(339)
747(1082)1101(1453)15/15101(96)200(92)332(267)699(791) 1402(1249)5402(5111)17479(18440) 4/15
f3
716
1622
1637
1642
1646
1650
1654
f15/15
5066
7626
7635
7637
7643
7646
7651
15/15
3
1.3(0.6)
7.1(5)
17(18)
19(19)
19(19)
23(24)
26(24) 15/15 3.1(0.7)
8.8(4)
11(4)
18(19)
19(19)
68(70)
275(267)
5/15
f4
809
1633
1688
1758
1817
1886
1903
f15/15
4722
7628
7666
7686
7700
7758
1.4e5
9/15
4
2.0(1)
11(8)32(34)
33(32)
34(31)
46(41)
55(55) 15/15 5.6(2)15(7)
20(12)
21(12)
29(26)
193(169)
50(49)
0/15
f5
10
10
10
10
10
10
10
f15/15
41
41
41
41
41
41
41
15/15
5
318(422) 1999(2627)4233(3688) 11021(9942)70495(79261)∞∞2.7e50/1512433(16425)
∞
∞
∞
∞
∞
∞1.1e6
0/15
f6
114
214
281
404
580
1038
1332
f15/15
1296
2343
3413
4255
5220
6728
8409
15/15
6
7.1(3)
202(355) 243(357)328(386)
410(442)362(312) 337(233) 10/15461(775) 2044(2523)4301(4653)∞∞∞∞2.0e6
0/15
f7
24
324
1171
1451
1572
1572
1597
f15/15
1351
4274
9503
16523
16524
16524
16969
15/15
7
9.4(5)
17(17)
22(22)
40(65)
45(64)
45(68)
46(67) 14/15513(801)
∞
∞
∞
∞
∞
∞1.1e6
0/15
f8
73
273
336
372
391
410
422
f15/15
2039
3871
4040
4148
4219
4371
4484
15/15
8
11(4)
518(811) 9455(11234) 8747(9309)16854(19258)∞∞5.0e50/151117(1472) 1580(1768)2138(2475) 6823(7474)6759(7822)∞∞2.0e6
0/15
f9
35
127
214
263
300
335
369
f15/15
1716
3102
3277
3379
3455
3594
3727
15/15
9
11(5)
957(744)∞∞∞∞∞5.0e50/15688(798) 4338(4514)∞∞∞∞∞2.0e6
0/15
f10
349
500
574
607
626
829
880
f15/15
7413
8661
10735
13641
14920
17073
17476
15/15
10
5553(6452)
∞
∞
∞
∞
∞
∞5.0e5
0/15
∞
∞
∞
∞
∞
∞
∞2.0e6
0/15
f11
143
202
763
977
1177
1467
1673 f15/15
1002
2228
6278
8586
9762
12285
14831
15/15
11
1331(1728)
∞
∞
∞
∞
∞
∞2.8e50/1512668(13322)
∞
∞
∞
∞
∞
∞2.0e6
0/15
f12
108
268
371
413
461
1303
1494 f15/15
1042
1938
2740
3156
4140
12407
13827
15/15
12
214(615)296(609) 1403(1719) 2982(3388) 4280(5081)∞∞2.6e50/15214(226) 1202(1551)2842(3285)∞∞∞∞2.0e6
0/15
f13
132
195
250
319
1310
1752
2255 f13
15/15 652
2021
2751
3507
18749
24455
30201
15/15
118(3)
697(1004)2369(2864) 2342(2568) 1742(1845)∞∞3.0e50/15848(1547) 2814(3522)4952(5411)∞∞∞∞2.0e6
0/15
f14
10
41
58
90
139
251
476
f14
15/15 75
239
304
451
932
1648
15661
15/15
1.1(1)
6.8(3)15(3)52(4)
580(784) 6773(7095) ∞3.4e5
0/15 12(5)
16(4)
23(6)
126(102) 2131(1910)∞∞2.0e6
0/15
f15
511
9310
19369
19743
20073
20769
21359 f15
14/15 30378
1.5e5
3.1e5
3.2e5
3.2e5
4.5e5
4.6e5
15/15
23(24)
157(181)∞∞∞∞∞2.8e50/15925(1152)
∞
∞
∞
∞
∞
∞2.0e6
0/15
f16
120
612
2662
10163
10449
11644
12095 f16
15/15 1384
27265
77015
1.4e5
1.9e5
2.0e5
2.2e5
15/15
3.0(2)
40(27)
46(59)
34(44)
139(161)∞∞3.4e5
0/15 4.8(2)
∞
∞
∞
∞
∞
∞2.0e6
0/15
f17
5.2
215
899
2861
3669
6351
7934 f17
15/15 63
1030
4005
12242
30677
56288
80472
15/15
1.9(2)
2.9(2)
7.2(10)23(30)
64(89)
78(75)
77(76)
2/15 2.6(2)490(971) 1170(1457)∞∞∞∞1.7e6
0/15
f18
103
378
3968
8451
9280
10905
12469 f15/15
621
3972
19561
28555
67569
1.3e5
1.5e5
15/15
18
2.5(3)
3.4(2)
23(31)
48(59)
205(245)∞∞2.7e5
0/15 3.9(1)515(566)∞∞∞∞∞1.6e6
0/15
f19
1
1
242
1.0e5
1.2e5
1.2e5
1.2e5 f15/15
1
1
3.4e5
4.7e6
6.2e6
6.7e6
6.7e6
15/15
19
14(12)
502(302)
55(5)
∞
∞
∞
∞2.5e50/15199(20)931(428)0.35(0.2)∞∞∞∞2.0e6
0/15
f20
16
851
38111
51362
54470
54861
55313 f14/15
82
46150
3.1e6
5.5e6
5.5e6
5.6e6
5.6e6
14/15
20
4.9(4)
25(44)
44(49)
33(36)
31(34)
31(32)
31(31)
3/15 11(5)10(16)∞∞∞∞∞1.8e6
0/15
f21
41
1157
1674
1692
1705
1729
1757 f14/15
561
6541
14103
14318
14643
15567
17589
15/15
21
2.9(4)
31(71)
38(77)
39(76)
42(80)
52(78)
70(79) 13/15
1215(1783) 3803(4344)∞∞∞∞∞2.0e6
0/15
f22
71
386
938
980
1008
1040
1068 f22
14/15 467
5580
23491
24163
24948
26847
1.3e5
12/15
3.3(3)
109(243) 298(347)
416(496)420(473)888(901) 2323(2395) 1/15867(1787) 1121(1382)∞∞∞∞∞1.6e6
0/15
f23
3.0
518
14249
27890
31654
33030
34256 f23
15/15 3.2
1614
67457
3.7e5
4.9e5
8.1e5
8.4e5
15/15
1.9(2)
39(50)
201(209)∞∞∞∞1.9e5
0/15 2.0(1)2615(2716)∞∞∞∞∞1.1e6
0/15
f24
1622
2.2e5
6.4e6
9.6e6
9.6e6
1.3e7
1.3e7 f24
3/15 1.3e6
7.5e6
5.2e7
5.2e7
5.2e7
5.2e7
5.2e7
3/15
6.5(2)
3.0(4)∞∞∞∞∞3.2e5
0/15 21(23)
∞
∞
∞
∞
∞
∞2.0e60/15∆ff1

Table 1: Expected running time (ERT in number of function evaluations) divided by the best ERT measured
during BBOB-2009. The ERT and in braces, as dispersion measure, the half difference between 90 and
10%-tile of bootstrapped run lengths appear in the second row of each cell, the best ERT in the first. The
different target ∆f -values are shown in the top row. #succ is the number of trials that reached the (final)
target fopt + 10−8 . The median number of conducted function evaluations is additionally given in italics, if
the target in the last column was never reached. Bold entries are statistically significantly better (according
to the rank-sum test) compared to the best algorithm in BBOB-2009, with p = 0.05 or p = 10−k when thenumber k > 1 is following the ↓ symbol, with Bonferroni correction by the number of functions.

8.

ACKNOWLEDGEMENTS

This work was funded by The University of KwazuluNatal during the postdoctoral study of the first author at
The School of Mathematics, Statistics and Computer Science, University of Kwazulu-Natal, South Africa. The firstauthor would like to thank The University of Lagos for her
support during this research work.

9.

REFERENCES[1] M. M. Ali and A. Törn. A population set-based global
optimization algorithms: some modifications andnumerical studies. Computers & Operations Research,
31(10):1703–1725, 2004.
[2] T. Back. Evolutionary algorithms in theory andpractice: Evolution strategies, evolutionary
programming, genetic algorithms. Oxford University
press, New York, 1996.
[3] R. Chelouah and P. Siarry. Genetic and nelder-meadalgorithms hybridized for a more accurate global
optimization of continuous multiminima functions.
European Journal of Operational Research,
148(2):335–348, 2003.

[4] Y.-C. Chuang and C.-T. Chen. Black-box
optimization benchmarking for noiseless function
testbed using a direction-based rcga. In GECCO(Companion), pages 167–174, 2012.
[5] K. Deep and K. N. Das. Quadratic approximation
based hybrid genetic algorithm for function
optimization. Applied Mathematics and Computation,
203:86–98, 2008.
[6] K. Deep and Dipti. A new hybrid self organizing
migrating genetic algorithm for function optimization.
In D. Srinivasan and L. Wang, editors, 2007 IEEE
Congress on Evolutionary Computation, pages
2796–2803, Singapore, 25-28 September 2007. IEEE
Computational Intelligence Society, IEEE Press.
[7] K. Deep and M. Thakur. A new crossover operator forreal coded genetic algorithms. Applied Mathematics
and Computation, 188:895–911, 2007.
[8] K. Deep and M. Thakur. A new mutation operator forreal coded genetic algorithms. Applied Mathematics
and Computation, 193:211–230, 2007.
[9] K. Deep and M. Thakur. A real coded multi parent

f 1–f 24 in 5-D, maxFE/D=100004
best
10%
25%
med 75%
90%
0.77
0.91
1.5
2.4
3.3
7.1
1.5
2.6
3.4
3.7
5.6
16
2.8
3.4
6.9
8.5
12
42
3.9
5.8
15
43
64
4.2e2
2.3
27
39
1.3e2 4.4e2 8.6e2
9.9
37
54
2.3e2 2.2e3 3.0e3
9.7
26
1.3e2 5.7e2 8.8e3 2.6e4
3e4
5e4
5e4
6e4
9e4
1e5
f 1–f 24 in 20-D, maxFE/D=100007
best
10%
25%
med 75%
90%
0.50
2.9
7.1
24
40
40
1.3
4.5
7.0
13
1.3e2 2.0e2
4.3
6.1
8.8
16
30
2.7e2
3.9
5.4
20
52
1.1e2 4.7e2
0.35 24
1.2e2 3.3e2 5.9e2 2.4e3
5.8
42
2.9e2 1.1e3 3.3e3 5.6e3
34
1.1e2 7.9e2 5.2e3 9.2e3 1.8e4
4e4
5e4
7e4
1e5
1e5
1e5

Figure 4: ERT loss ratio versus the budget (bothin number of f -evaluations divided by dimension).
The target value ft for a given budget FEvals is thebest target f -value reached within the budget by
the given algorithm. Shown is the ERT of the given
algorithm divided by best ERT seen in GECCOBBOB-2009 for the target ft , or, if the best algorithm reached a better target within the budget,the budget divided by the best ERT. Line: geometric mean. Box-Whisker error bar: 25-75%-ile withmedian (box), 10-90%-ile (caps), and minimum andmaximum ERT loss ratio (points). The vertical line
gives the maximal number of function evaluations
in a single trial in this function subset. See also
Figure 5 for results on each function subgroup.
genetic algorithms for function optimization. Applied
Mathematics and Computation, 1(2):67–83, 2008.
[10] K. A. DeJong. An analysis of the behavior of a class ofgenetic adaptive systems. PhD thesis, University ofMichgan, Ann Arbor, MI, USA, 1975.
[11] A. P. Engelbrecht. Fundamental of computational
swarm intelligence. John Wiley & Sons, Ltd, West
Sussex, England, 2005.
[12] S. Finck, N. Hansen, R. Ros, and A. Auger.
Real-parameter black-box optimization benchmarking
2009: Presentation of the noiseless functions.
Technical Report 2009/20, Research Center PPE,2009. Updated February 2010.
[13] D. Goldberg. Real-coded genetic algorithms, virtualalphabets, and blocking. Complex Systems,
5(2):139–168, 1991.

log10 of ERT loss ratio

2
1
0
-1
-2
4
3
2
1
0
-1
-2
4

1
4
2
3
log10 of FEvals / dimension
f10-14

3
2
1
0
-1
-2
4

1
4
2
3
log10 of FEvals / dimension
f15-19

3
2
1
0
-1
-2
4

2
1
0
-1
1
4
2
3
log10 of FEvals / dimension

0
-1

5

1
4
2
3
log10 of FEvals / dimension
f6-9

5

1
4
2
3
log10 of FEvals / dimension
f10-1451423
log10 of FEvals / dimension
f15-1951423
log10 of FEvals / dimension
f20-2451423
log10 of FEvals / dimension

5

3
2
1
0
-1

3
2
1
0
-1

3
2
1
0
-1
-2
4

1
4
2
3
log10 of FEvals / dimension
f20-24

3

-2

1

-2
4

5

f1-5

2

-2
4

5

20-D

3

-2
4

1
4
2
3
log10 of FEvals / dimension
f6-9
log10 of ERT loss ratio

log10 of ERT loss ratio

separable fcts
5

4

f1-5

log10 of ERT loss ratio

142
3
log10 of FEvals / dimension

5-D

log10 of ERT loss ratio#FEs/D
2
10
100
1e3
1e4
1e5
1e6
RLUS /D

20-D

log10 of ERT loss ratio#FEs/D
2
10
100
1e3
1e4
1e5
1e6
RLUS /D

5-2

moderate fcts

142
3log10 of FEvals / dimension-1

log10 of ERT loss ratio

5-D

0

ill-conditioned fcts-2

1

log10 of ERT loss ratio-13

multi-modal fcts

02

log10 of ERT loss ratio

1

4

weak structure fcts

2

f1-24

3

log10 of ERT loss ratio

4

f1-24

3

log10 of ERT loss ratio

log10 of ERT loss ratio

4

3
2
1
0
-1
-2

Figure 5: ERT loss ratios (see Figure 4 for details).
Each cross (+) represents a single function, the lineis the geometric mean.
[14] D. E. Goldberg. Genetic algorithms in search,
optimization, and machine learning. Addison-Wesley,
Reading, Massachusetts, 1989.
[15] N. Hansen, A. Auger, S. Finck, and R. Ros.
Real-parameter black-box optimization benchmarking
2012: Experimental setup. Technical report, INRIA,
2012.
[16] N. Hansen, A. Auger, R. Ros, S. Finck, and P. Pošı́k.
Comparing results of 31 algorithms from the black-box
optimization benchmarking bbob-2009. In Proceedingsof the 12th annual conference companion on Genetic
and evolutionary computation, GECCO ’10, pages
1689–1696, New York, NY, USA, 2010. ACM.
[17] N. Hansen, S. Finck, R. Ros, and A. Auger.
Real-parameter black-box optimization benchmarking

2009: Noiseless functions definitions. Technical Report
RR-6829, INRIA, 2009. Updated February 2010.
[18] J. H. Holland. Adaptation in natural and artificial
systems, An introductory analysis with applications tobiology, control and artificial intelligence. MIT press,
Cambridge, Massachusetts, 1975.
[19] P. Kaelo and M. M. Ali. Integrated crossover rules inreal coded genetic algorithms. European Journal ofOperational Research, 176:60–76, 2007.
[20] Z. Michalewicz. Genetic algorithms + data structures= evolution programs. Springer-Verlag, Berlin
Heidelberg, N.Y., 1996.
[21] M. Nicolau. Application of a simple binary genetic
algorithm to a noiseless testbed benchmark. In
GECCO (Companion), pages 2473–2478, 2009.

[22] B. A. Sawyerr. Hybrid real coded genetic algorithms
with pattern search and projection. PhD thesis,
University of Lagos, Lagos, Nigeria, 2010.
[23] B. A. Sawyerr, M. M. Ali, and A. O. Adewumi. A
comparative study of some real coded genetic
algorithms for unconstrained global optimization.
Optimization Methods and Software, 26(6):945–970,
2011.
[24] T.-D. Tran and G.-G. Jin. Real-coded genetic
algorithm benchmarked on noiseless black-box
optimization testbed. In GECCO (Companion), pages
1731–1738, 2010.