Improving Brain Storm Optimization Algorithm
via Simplex Search

arXiv:1712.03166v1 [cs.NE] 24 Oct 2017

Wei Chen1 , YingYing Cao1 , Yifei Sun2,3 , Qunfeng Liu1 , and Yun Li1
1

3

School of Computer Science and Network Security, Dongguan University of
Technology, Dongguan, China
2
Key Laboratory of Modern Teaching Technology, Ministry of Education
School of Physics and Information technology, Shaanxi Normal University, Xi’an,
China
liuqf@dgut.edu.cn,liy@dgut.edu.cn

Abstract. Through modeling human’s brainstorming process, the brain
storm optimization (BSO) algorithm has become a promising population based evolution algorithm. However, BSO is often good at global
exploration but not good enough at local exploitation, just like most
global optimization algorithms. In this paper, the Nelder-Mead’s Simplex (NMS) method is adopted in a simple version of BSO. Our goal
is to combine BSO’s exploration ability and NMS’s exploitation ability
together, and develop an enhanced BSO via a better balance between
global exploration and local exploitation. Large number of experimental
results are reported, and the proposed algorithm is shown to perform
better than both BSO and NMS.
Keywords: Brain Storm Optimization, Nelder-Mead Simplex method,
Balance between Global Exploration and Local Exploitation, Visualizing
Confidence Intervals

1

Introduction

The Brain Storm Optimization (BSO) algorithm is a kind of evolution algorithm
based on brainstorming process [13, 14]. Since its proposal, BSO has become
a promising population-based swarm intelligence algorithm, and has attracted
more and more theoretical and practical researches [3,5,6,15–17]. An important
progress of BSO is to transform operations in the solution space to operations in
the objective space [16]. The new version of BSO is easier in implementation, and
lower in computational resources on the clustering strategy at each iteration [16].
In this paper, we refer BSO to BSO in the objective space, unless otherwise
stated.
In the BSO algorithm [16], the population evolutes via updating each individual at each iteration. Specifically, the whole population is firstly classified
into two categories, the best 20% individuals are included in the elites set, while
the others are included in the normals set. Then one or two parent individuals
are selected randomly from either or both sets, new child individual is generated
through combining these selected parent individuals linearly and then add some

2

W. Chen et al.

white noises. If the new child individual is better than the original one, it will
be accepted in the new population. Repeating such process, BSO can approach
the optima as iterations increasing.
In our recent paper [2], a simplified BSO (SimBSO) algorithm is developed
through abandoning the categories of elites and normals. The main difference between BSO and SimBSO is that each member or individual is equal in SimBSO,
while the elites are biased in BSO. Besides its simple structure and easiness of
implementation, SimBSO is also shown to be more efficient than BSO on some
popular benchmark sets.
However, our numerical experiments have shown that both BSO and SimBSO
are good at global exploration but not good enough at local exploitation [2].
Actually, this issue is true for almost all global optimization algorithms. A nature
way to overcome the issue is to combine a local solver with a global optimization
algorithm to balance between global exploration and local exploitation [9, 10].
In this paper, the Nelder-Mead Simplex (NMS) algorithm [12], which is one
of the most well-known derivative-free optimization algorithm for local optimization, is adopted in SimBSO. NMS is often efficient in finding a good local
optimum, but may be stagnated there and can not find the global optimum. Our
goal is to enhance both SimBSO and NMS through their suitable combination.
Specifically, SimBSO is executed for just one iteration (update the population
only once), and then the best found position is regarded as a start point for NMS.
Given a small budget of computational cost, NMS is executed, and the found
best position is then returned back to update the best individual of population.
Repeat this process until the stopping condition satisfied. Since SimBSO is good
at global exploration and NMS is good at local exploitation, our strategy can
be interpreted as a repeated process including “finding a good local area” and
“exploiting the local area”.
The obtained algorithm, Simplex-BSO, is shown to perform better than both
NMS and SimBSO on some popular benchmark sets. The additional parameter,
computational cost for NMS’s local search, is shown numerically to be insensitivity.
The remainder of this paper is organized as follows. In Section 2, the BSO
and SimBSO algorithms are reviewed briefly. Then the Simplex-BSO algorithm
is developed in section 3. Large number of experimental results are reported in
Section 4. Finally, conclusions are drawn in section 5.

2
2.1

Brain storm optimization
Brain storm optimization in the objective space

The brain storm optimization algorithm in objective space (abbreviated as BSO)
was proposed in 2015 [16]. The procedure is listed in Algorithm 1.
In the BSO algorithm [16], the initialized population is often randomly generated. In the main loop of the algorithm, there are four components including
“Classification (Line 3 in Algorithm 1)”, “Disruption (Line 4 in Algorithm 1)”,

A Simplex-BSO via Visualizing Confidence Intervals

3

Algorithm 1: Brain Storm Optimization (BSO).
1
2
3

4
5
6
7
8

Initialization: generate the initial population randomly and evaluate them;
while stopping conditions do not hold do
Classification: classify all solutions into two categories according to their
fitness values: the best 20% individuals are called “elites” and the others
“normals”;
Disruption: select an individual from the population randomly, and change
its value in a randomly selected dimension;
New individual generation: select one or two individuals from elitists or
normal to generate a child;
Generate a new child by add a white noise to the child’s each dimension;
Record the new child if it is better than the current individual;
Update: update the whole population;

“New individual generation (Line 5-7 in Algorithm 1)” and “Population updating (Line 8 in Algorithm 1)”. In “Classification” stage, the individuals are
classified into two clusters according to their fitness values, the best 20% individuals are clustered as “elitists and the remaining as “normals. The operation
“Disruption” is utilized to increase the population diversity, which is executed
usually with a small probability and one individual’s value in one random dimension will be replaced by a random number. The “Disruption” strategy is
often helpful for individuals to ‘jump out’ of the local optima.
The most important component of BSO is how to generate new individuals. One or two individuals are selected randomly from “elitists” or “normals”
or both, and then the selected individuals are combined linearly to generate a
new individual by adding different white noises in its different dimensions. The
variances of these white noises are controlled by the following step-size function
ξ(t) = logsig

0.5 × T − t 
× rand(t),
c

(1)

where logsig() is a logarithmic sigmoid function, T and t are the maximum and
current number of iterations, respectively, c is a coefficient to change logsig()
function’s slope, and rand() return a random value between 0 and 1.
The operation “Population updating” is utilized to keep good solutions. The
new individual generated in the above stage will be recorded if its fitness value
is better than the current given individual. But the current individual will not
be replaced until all new individuals are generated and evaluated (see Algorithm
1). In other words, new individuals are all generated from the old population,
and the whole population will be updated at the end of iteration [16].
2.2

Simplified BSO

Recently, a very simple version of BSO (SimBSO) is proposed in [2], where the
classification of “elites” and “normals” is abandoned. Therefore, the obtained

4

W. Chen et al.

SimBSO algorithm can be regarded as a brainstorming model in which each
member or individual is equal. Although there is no elites to lead local exploitation, SimBSO still performs well on some popular benchmark sets. The procedure
of SimBSO algorithm is listed in Algorithm 2, see [2] for more details.

Algorithm 2: Simplified Brain Storm Optimization (SimBSO).
1
2
3
4
5
6

Initialization: generate the initial population randomly;
while stopping conditions do not hold do
for each individual in the population do
Select three individuals from the population randomly, and generate a
child by combining them linearly;
Generate a new child by add a white noise to the child’s each dimension;
Update the current individual if the new child is better;

Compared with BSO, the clustering operation, the disruption operation are
abandoned and the population is updated timely in SimBSO. Therefore, SimBSO
is very simple and easy to implement. Another important property of SimBSO
is that it is a pure global search algorithm, i.e., there is no local search operation
in this algorithm. Hence, SimBSO is very suitable for combination with some
local solver.

3

An improved Brain Storm Optimization Algorithm
based on Nelder-Mead’s simplex search

In this section, the Nelder-Mead’s simplex method is introduced into SimBSO
to enhance its local exploitation ability. Firstly, we briefly review the NMS algorithm [12].
3.1

Nelder-Mead Simplex Algorithm

The NMS algorithm was proposed by Nelder and Mead in 1965 [12], and it
is still one of the best derivative-free optimization algorithm. The authors are
trying to minimize the function f (x) for x ∈ Rn . Their current test points are
x1 , x2 , · · ·, xn+1 . The procedure is listed in Algorithm 3. The algorithm takes the
N + 1 test points in the N-dimension space to form a simplex, and extrapolates
the behavior of the objective function measured at each test point. Then try to
get a better point through reflection (Line 4-5 in Algorithm 3), expansion (Line
6-10 in Algorithm 3), contraction (Line 11-21 in Algorithm 3) on the worst
point, and use it to replace the worst point to form a new simplex. Or shrink
(Line 22 in Algorithm 3) to the best to form a new simplex. The algorithm has
fast convergence speed and strong local search ability. When dealing with high
dimensional problems, it cost a minimum time to search the local optimization.

A Simplex-BSO via Visualizing Confidence Intervals

Algorithm 3: Nelder-Mead Simplex (NMS).
1
2
3
4

5

6
7
8

9
10

11
12
13
14

15
16
17
18
19

20
21

22

Initialization: generate the initial test points;
while stopping conditions do not hold do
Order: order the n + 1 vertices to satisfy f (x1 ) ≤ f (x2 ) ≤ · · · ≤ f (xn+1 );
Reflection: compute
the reflection point xr = (1 + α)x̄ − αxn+1 with α > 0,
P
where x̄ = n
i=1 xi /n is the centroid of the n best points.
if f (x1 ) ≤ f (xr ) < f (xn ), then
obtain a new simplex by replacing the worst point xn+1 with the
reflected point xr and go to step 1;
Expansion: if f (xr ) < f (x1 ), then
compute the expanded point xe = x̄ + γ(xr − x̄) with γ > 1,
if f (xe ) < f (xr ), then
obtain a new simplex by replacing the worst point xn+1 with the
expanded point xe and go to step 1;
else
obtain a new simplex by replacing the worst point xn+1 with the
reflected point xr and go to step 1;
Contraction: if f (xr ) ≥ f (xn ), then
if f (xr ) < f (xn+1 ), then
compute contracted point xc = (1 − β)x̄ + βxr ,
if f (xc ) < f (xr ), then
obtain a new simplex by replacing the worst point xn+1 with
the contracted point xc and go to step 1. Contract outside
else
continue with Shrink
else if f (xr ) ≥ f (xn+1 ), then
compute contracted point xcc = (1 − β)x̄ + βxn+1 ,
if f (xc ) < f (xn+1 ), then
obtain a new simplex by replacing the worst point xn+1 with
the contracted point xcc and go to step 1. Contract inside
else
continue with Shrink
Shrink: calculate the n points vi = x1 + (xi − x1 )/2, and calculate
f (vi ), i = 2, · · ·, n + 1. The simplex at the next iteration is x1 , v2 , · · ·, vn+1

5

6

W. Chen et al.

3.2

An improved BSO Algorithm based on Nelder-Mead’s simplex
search

In this subsection, the NMS algorithm is introduced into SimBSO, and our
mail goal is to combine the local exploitation ability of NMS and the global
exploration ability of SimBSO. We call the obtained algorithm Simplex-BSO,
and list its procedure in Algorithm 4.

Algorithm 4: Simplex Brain Storm Optimization (Simplex-BSO).
1
2
3
4
5

6

Initialization: generate the initial population randomly;
while stopping conditions do not hold do
Global search: update the whole population according to the SimBSO
algorithm. Identify the best individual x0 ;
while search cost less than 50*length(x0 ) do
Local search: exploit the search area around x0 through executing the
′
NMS algorithm. Let x0 be the found best point;
′

Update: Update the population via replacing x0 by x0 .

In each iteration of Simplex-BSO, the SimBSO algorithm is executed firstly
and then the best found position x0 is used as a starting point for NMS’s search.
The NMS algorithm then begins to search the local area around x0 , after consuming 50n (n is the dimension of problem) computational cost, the found new
′
best position x0 is returned back to replace x0 . Repeat such process until the
sopping conditions hold.
On one hand, SimBSO’s global search helps to provide a good starting point
for NMS, which has a significant influence on the performance of the NMS
method. On the other hand, NMS is an efficient local solver and can accelerate the local exploitation. Therefore, our strategy provides a better balance
between global exploration and local exploitation than SimBSO or NMS alone.
An additional parameter, 50n, is employed to balance SimBSO’s global search
cost and NMS’s local search cost. In other words, in each iteration of SimplexBSO, one iteration of SimBSO and 50 iterations of NMS are included. Such an
allocation guarantees a good local exploitation by NMS. In next section, the
sensitivity analysis of this parameter is presented, and the results show that it
is insensitivity.

4

Experimental results

In this section, the Simplex-BSO is compared numerically with the following
algorithms:
– NMS: an algorithm based on Nelder-Mead’s simplex search [12];

A Simplex-BSO via Visualizing Confidence Intervals

7

– BSO: BSO in the objective space [16];
– SimBSO: a simplified BSO proposed in [2].
Two popular benchmark sets including the Hedar set [7] and the CEC2017
set [1] are adopted in this paper. Totally, 114 problems are tested. Since there are
large number of test data gathered during our test process, the recently proposed
VCI method [8] is adopted to analyze the data.
4.1

The VCI method

The VCI method [8] is extended from the data profile technique [11] and the
performance profile technique [4], which are standard analysis methods for comparing deterministic optimization algorithms. Through visualizing confidence
intervals of the best objective function values found as computational cost increasing, the VCI method is shown to be convenient for benchmarking stochastic
global optimization algorithms, especially when the set of benchmark functions
or the number of algorithms is large [8]. It is also proposed to replace the traditional statistic test based methods [8].
Suppose there is a set S of optimization solvers needed to be compared numerically, and a set P of benchmark problems is selected. Then given any budget
of function evaluations µf , run each solver s ∈ S on each problem p ∈ P for nr
times, and record the found best function values. After all tests finished, a 4-D
matrix H with size µf × nr × np × ns is obtained, where the 4-tuple element
H(k, r, j, i) denotes the found best function value during k function evaluations
at the r-th run when test the i-th solver on the j-th problem.
The matrix H is then used to generate a sample mean matrix H
nr
1 X
H(k, r, j, i)
nr r=1

(2)

nr
2

1 X
H(k, r, j, i) − H(k, j, i)
nr − 1 r=1

(3)

H(k, j, i) =
2
and a sample variance matrix SH

2
SH
(k, j, i) =

for each algorithm i = 1, ..., ns on each problem j = 1, ..., np with k = 1, ..., µf
function evaluations according to the following equations [8]. The confidence
upper bound matrix Hupper and the confidence lower bound matrix Hlower are
then defined as follows
Hupper (k, j, i) = H(k, j, i) +

2SH (k, j, i)
,
√
nr

(4)

Hlower (k, j, i) = H(k, j, i) −

2SH (k, j, i)
.
√
nr

(5)

8

W. Chen et al.

In [8], the data profile technique [11] is adopted to analyze H, Hupper and
Hlower statistically. The data profile is a cumulative distribution function defined
for any solver s ∈ S as the following cumulative distribution function


tp,s
1
size p ∈ P :
≤κ
(6)
ds (κ) =
|P|
Dp + 1
where |P| denotes the number of test problems, Dp is the dimension of the problem p, and size{} returns the size of a set. In (6), tp,s is the number of function
evaluations needed for solver s to find a position x such that the convergence
condition
f (x0 ) − f (x) ≥ (1 − τ )(f (x0 ) − fL )
(7)
holds, where x0 is the starting point, τ > 0 is a tolerance and fL is the smallest
objective function value obtained by any solver within µf of function evaluations.
tp.s = ∞ if the condition (7) does not satisfy after µf function evaluations.
Roughly speaking, the VCI method adopts the data profile technique twice
to benchmark stochastic optimization algorithms. Specifically, the data profile
technique is used to analyze H firstly. From the generated data profiles, a winner
solver can be determined in the sense of best average performance. Then the data
profile technique is used to analyze Hupper and Hlower — the winner solver’s
Hupper and the other solvers’ Hlower . The purpose is to confirm that the winner
solver performs the best in the sense of the worst deviation.
In summary, the VCI method possesses several advantages than the traditional methods (e.g., statistic test based methods) [8], and is very convenient for
our purpose.
4.2

Numerical comparison on the Hedar test set

In this subsection, we present the numerical results on the Hedar test set [7]. Table 1 shows the function names, dimensions, Characteristic, search regions and
their minimal function values. There are 7 unimodal functions and 28 multimodal
functions in Hedar test set. Since some functions have variant dimensions, there
are 16 unimodal problems and 52 multimodal problems in total. In our experiments, 50 independent runs are executed for each problem, and all algorithms
stops only when 20,000 function evaluations are consumed on the Hedar test set.
Firstly, we compare Simplex-BSO with SimBSO. The experimental results
are showed in Fig.1. The data profiles when comparing SimBSO’s average with
Simplex-BSO’s are presented in the left subfigure of Fig.1. Significant performance difference is observed. For example, Simplex-BSO can solve about 70%
problems with very small computational cost (no more than 1000 at the horizontal axis), and finally solve about 81% problems. However, SimBSO only solves
about 20% and 66%, respectively. In order to confirm Simplex-BSO’s advantage,
its confidence upper bounds (worst performance) are compared with SimBSO’s
lower bounds (best performance), the results are presented in the right subfigure. We see that Simplex-BSO’s confidence upper bound also “performs” better,

A Simplex-BSO via Visualizing Confidence Intervals

9

Table 1. Information about the Hedar test set.

Function
Beale
Matyas
Sphere
Sum squares
Trid
Trid
Zakharov
Ackley
Bohachevsky 1
Bohachevsky 2
Bohachevsky 3
Booth
Branin
Colville
Dixson Price
Easom
Goldstein and Price
Griewank
Hartman 3
Hartman 6
Hump
Levy
Michalewics
Michalewics
Michalewics
Perm
Powell
Power sum
Rastrigin
Rosenbrock
Schwefel
Shekel 5
Shekel 7
Schkel 10
Shubert

Dimension n Characteristic
2
Unimodal
2
Unimodal
2,5,10,20
Unimodal
2,5,10,20
Unimodal
6
Unimodal
10
Unimodal
2,5,10,20
Unimodal
2,5,10,20
Multimodal
2
Multimodal
2
Multimodal
2
Multimodal
2
Multimodal
2
Multimodal
4
Multimodal
2,5,10,20
Multimodal
2
Multimodal
2
Multimodal
2,5,10,20
Multimodal
3
Multimodal
6
Multimodal
2
Multimodal
2,5,10,20
Multimodal
2
Multimodal
5
Multimodal
10
Multimodal
4
Multimodal
4,12,24,48
Multimodal
4
Multimodal
2,5,10,20
Multimodal
2,5,10,20
Multimodal
2,5,10,20
Multimodal
4
Multimodal
4
Multimodal
4
Multimodal
2
Multimodal

Search region
[−4.5, 4.5]2
[−8, 12.5]2
[−4.1, 6.4]n
[−8, 12.5]n
[−36, 36]6
[−100, 100]1 0
[−5, 10]n
[−15, 30]n
[−80, 125]2
[−80, 125]2
[−80, 125]2
[−100, 100]2
[−5, 10] ∗ [0, 15]
[−10, 10]4
[−10, 10]n
[−100, 100]2
[−2, 2]2
[−480, 750]n
[0, 1]3
[0, 1]6
[−5, 5]2
[−10, 10]n
[0, π]2
[0, π]5
[0, π]10
[−4, 4]4
[−4, 5]n
[0, 4]4
[−4.1, 6.4]n
[−5, 10]n
[−500, 500]n
[0, 10]4
[0, 10]4
[0, 10]4
[−10, 10]2

Minimal function value
0
0
0
0
-50
-200
0
0
0
0
0
0
0.397887357729739
0
0
-1
3
0
-3.86278214782076
-3.32236801141551
0
0
-1.80130341008983
-4.687658179
-9.66015
0
0
0
0
0
0
-10.1531996790582
-10.4029405668187
-10.5364098166920
-186.730908831024

10

W. Chen et al.
Data profiles,τ = 1e-7

1

SimBSO
Simplex-BSO

0.8
0.7
0.6
0.5
0.4
0.3

0.8
0.7
0.6
0.5
0.4
0.3

0.2

0.2

0.1

0.1

0

SimBSO-Lower
Simplex-BSO-Upper

0.9

Proportion of problems solved

Proportion of problems solved

0.9

Data profiles,τ = 1e-7

1

0
0

2000

4000

6000

8000

10000

Number of function evaluation/(dimension+1)

0

2000

4000

6000

8000

10000

Number of function evaluation/(dimension+1)

Fig. 1. Through the VCI method, data profiles resulted from comparing SimBSO and
Simplex-BSO on the Hedar test set. SimBSO’s average and Simplex-BSO’s are compared in the left subfigure, while SimBSO’s confidence lower bound and Simplex-BSO’s
confidence upper bound are compared in the right subfigure.

the performance difference is about 10% (=72%-62%). These results imply that
Simplex-BSO actually performs better than SimBSO.
Secondly, we compare Simplex-BSO with BSO. The experimental results are
showed in Fig.2. From the left subfigure of Fig.2, it shows that Simplex-BSO
performs much (about 38% performance difference) better than BSO in the sense
of average performance. We also see that Simplex-BSO’s confidence upper bound
also “performs” better than BSO’confidence lower bound. Hence it implies that
Simplex-BSO actually performs better than BSO, too.
Finally, we compare Simplex-BSO with NMS, and the experimental results
are showed in Fig.3. From the figure, we see that both the sample mean and the
confidence upper bound of Simplex-BSO perform much (more than 60% performance difference) better than NMS (note that it is deterministic). Therefore,
we can say that Simplex-BSO performs significantly better than NMS. In fact,
through the test data, many problems of the Hedar test set can not be solved
by the NMS algorithm. However, almost all of the problems can be solved by
Simplex-BSO.
From the above results, we found that Simplex-BSO performs very well on
the Hedar set, it possesses much better local exploitation ability than BSO and
SimBSO, and possesses better global exploration ability than NMS.

A Simplex-BSO via Visualizing Confidence Intervals

Data profiles,τ = 1e-7

1

0.8
0.7
0.6
0.5
0.4
0.3

BSO-Lower
Simplex-BSO-Upper

0.9

Proportion of problems solved

Proportion of problems solved

Data profiles,τ = 1e-7

1

BSO
Simplex-BSO

0.9

0.8
0.7
0.6
0.5
0.4
0.3

0.2

0.2

0.1

0.1

0

11

0
0

2000

4000

6000

8000

10000

0

Number of function evaluation/(dimension+1)

2000

4000

6000

8000

10000

Number of function evaluation/(dimension+1)

Fig. 2. Through the VCI method, data profiles resulted from comparing BSO and
Simplex-BSO on the Hedar test set. BSO’s average and Simplex-BSO’s are compared
in the left subfigure, while BSO’s confidence lower bound and Simplex-BSO’s confidence
upper bound are compared in the right subfigure.

Data profiles,τ = 1e-7

1

NMS
Simplex-BSO

0.8
0.7
0.6
0.5
0.4
0.3

0.8
0.7
0.6
0.5
0.4
0.3

0.2

0.2

0.1

0.1

0

NMS
Simplex-BSO-Upper

0.9

Proportion of problems solved

Proportion of problems solved

0.9

Data profiles,τ = 1e-7

1

0
0

2000

4000

6000

8000

10000

Number of function evaluation/(dimension+1)

0

2000

4000

6000

8000

10000

Number of function evaluation/(dimension+1)

Fig. 3. Through the VCI method, data profiles resulted from comparing Simplex-BSO
and NMS on the Hedar test set. Simplex-BSO’s average and NMS are compared in the
left subfigure, while Simplex-BSO’s confidence upper bound and NMS are compared
in the right subfigure.

12

4.3

W. Chen et al.

Numerical comparison on the CEC2017 test set

In this subsection, we present numerical results on the CEC2017 test set [1].
Totally, we have tested 46 problems, including all the 16 two-dimensional benchmark functions and 30 ten-dimensional benchmark functions. Specifically, there
are 6 unimodal functions, 14 simple multimodal functions, 10 hybrid functions,
and 16 composition functions. All benchmark functions are non-separable and
have the same search range [−100, 100]n (n stands for dimension) for convenient.
For each benchmark function in CEC2017 test set, all the tested algorithms will
be run 50 times and stopped only at the cost of 100,000 function evaluations. The
function names, dimensions, Characteristic and their minimal function values of
CEC2017 test set are shown in Table 2.
The compared experimental results between Simplex-BSO and BSO are presented in Fig.4. From the left subfigure in Fig.4, we see that Simplex-BSO’s average performs much (about 23% performance difference) better than BSO. However, from the right subfigure, Simplex-BSO’s upper bound “performs” worse
than BSO’s confidence lower bound. Therefore, we can not say that SimplexBSO performs significantly better than BSO. Similar results are obtained when
comparing Simplex-BSO and SimBSO, see Fig.5 for the results.

Data profiles,τ = 1e-7

1

BSO
Simplex-BSO

0.8
0.7
0.6
0.5
0.4
0.3

0.8
0.7
0.6
0.5
0.4
0.3

0.2

0.2

0.1

0.1

0
0

10000

20000

30000

40000

50000

Number of function evaluation/(dimension+1)

Fig. 4. Through
Simplex-BSO on
pared in the left
confidence upper

BSO-Lower
Simplex-BSO-Uppper

0.9

Proportion of problems solved

Proportion of problems solved

0.9

Data profiles,τ = 1e-7

1

0
0

10000

20000

30000

40000

50000

Number of function evaluation/(dimension+1)

the VCI method, data profiles resulted from comparing BSO and
the CEC2017 test set. BSO’s average and Simplex-BSO’s are comsubfigure, while BSO’s confidence lower bound and Simplex-BSO’s
bound are compared in the right subfigure.

A Simplex-BSO via Visualizing Confidence Intervals

13

Table 2. Information about the CEC’17 test suite.

Function
Dimension n Characteristic Minimal function value
Shifted and Rotated Bent Cigar
2,10
Unimodal
100
Function
Shifted and Rotated Sum of
2,10
Unimodal
200
Different Power Function
Shifted and Rotated Zakharov
2,10
Unimodal
300
Function
Shifted and Rotated Rosenbrocks
2,10
Multimodal
400
Function
Shifted and Rotated Rastrigins
2,10
Multimodal
500
Function
Shifted and Rotated Expanded
2,10
Multimodal
600
Scaffers F6 Function
Shifted and Rotated Lunacek
2,10
Multimodal
700
Bi Rastrigin Function
Shifted and Rotated Non2,10
Multimodal
800
Continuous Rastrigins Function
Shifted and Rotated Levy
2,10
Multimodal
900
Function
Shifted and Rotated Schwefels
2,10
Multimodal
1000
Function
Hybrid Function 1 (N=3)
10
Multimodal
1100
Hybrid Function 2 (N=3)
10
Multimodal
1200
Hybrid Function 3 (N=3)
10
Multimodal
1300
Hybrid Function 4 (N=4)
10
Multimodal
1400
Hybrid Function 5 (N=4)
10
Multimodal
1500
Hybrid Function 6 (N=4)
10
Multimodal
1600
Hybrid Function 6 (N=5)
10
Multimodal
1700
Hybrid Function 6 (N=5)
10
Multimodal
1800
Hybrid Function 6 (N=5)
10
Multimodal
1900
Hybrid Function 6 (N=6)
10
Multimodal
2000
Composition Function 1 (N=3)
10
Multimodal
2100
Composition Function 2 (N=3)
10
Multimodal
2200
Composition Function 3 (N=4)
2,10
Multimodal
2300
Composition Function 4 (N=4)
2,10
Multimodal
2400
Composition Function 5 (N=5)
2,10
Multimodal
2500
Composition Function 6 (N=5)
2,10
Multimodal
2600
Composition Function 7 (N=6)
2,10
Multimodal
2700
Composition Function 8 (N=6)
2,10
Multimodal
2800
Composition Function 9 (N=3)
10
Multimodal
2900
Composition Function 10 (N=3)
10
Multimodal
3000

14

W. Chen et al.

1

Data profiles,τ = 1e-7
SimBSO
Simplex-BSO

0.8
0.7
0.6
0.5
0.4
0.3

0.8
0.7
0.6
0.5
0.4
0.3

0.2

0.2

0.1

0.1

0
0

10000

20000

30000

40000

Number of function evaluation/(dimension+1)

SimBSO-Lower
Simplex-BSO-Upper

0.9

Proportion of problems solved

Proportion of problems solved

0.9

Data profiles,τ = 1e-7

1

0
0

10000

20000

30000

40000

50000

Number of function evaluation/(dimension+1)

Fig. 5. Through the VCI method, data profiles resulted from comparing SimBSO and
Simplex-BSO of lower-dimensional problems on the CEC2017 test set. SimBSO’s average and Simplex-BSO’s are compared in the left subfigure, while SimBSO’s confidence
lower bound and Simplex-BSO’s confidence upper bound are compared in the right
subfigure.

A Simplex-BSO via Visualizing Confidence Intervals

15

Then we show the compared experimental results of 30-dimensional problems
between BSO and Simplex-BSO in Fig.6. 300,000 function evaluations are consumed on these problems. Simplex-BSO performs better than BSO and SimBSO
in the sense of average. significantly better than BSO.

Data profiles,τ = 1e-7

1

0.8
0.7
0.6
0.5
0.4
0.3

0.8
0.7
0.6
0.5
0.4
0.3

0.2

0.2

0.1

0.1

0
0

SimBSO
Simplex-BSO

0.9

Proportion of problems solved

Proportion of problems solved

0.9

Data profiles,τ = 1e-7

1

BSO
Simplex-BSO

0
2000

4000

6000

8000

10000

Number of function evaluation/(dimension+1)

0

2000

4000

6000

8000

10000

Number of function evaluation/(dimension+1)

Fig. 6. Through the VCI method, data profiles resulted from comparing Simplex-BSO’s
average with BSO’s (left subfigure), or SimBSO’s (right subfigure) of 30-dimensional
problems on the CEC2017 test set.

The results on the CEC2017 set show that Simplex-BSO performs better
than both BSO and SimBSO in the sense of average performance. However, if
taking the sample variance into account, we can not say Simplex-BSO performs
significant better.
4.4

Sensitivity analysis

In the Simplex-BSO algorithm, the computational cost for NMS’s local search
is set to 50n. In this subsection, we test its sensitivity on the Hedar test set (See
Table 1). Specifically, 25n, 40n, 50n, 60n, 75n are set respectively, and SimplexBSO’s performance are compared in Fig.7.
From Fig.7 we can see that Simplex-BSO performs similarly under the setting of five different parameter values. Specifically, Simplex-BSO with parameter value 50n performs slightly worse than Simplex-BSO with 60n, slightly
better than Simplex-BSO with 75n, and performs similar as Simplex-BSO with
25n, 40n. Therefore, we conclude that the parameter 50n is insensitive numerically.

Data profiles,τ = 1e-7

1

50n
25n

0.8
0.6
0.4
0.2
0
0

2000

4000

6000

8000

Proportion of problems solved

W. Chen et al.

Proportion of problems solved

16

0.6
0.4
0.2
0

10000

0

0.8
0.6
0.4
0.2
0
0

2000

4000

6000

8000

10000

Number of function evaluation/(dimension+1)

2000

4000

6000

8000

10000

Number of function evaluation/(dimension+1)
Proportion of problems solved

Proportion of problems solved

Data profiles,τ = 1e-7
50n
60n

50n
40n

0.8

Number of function evaluation/(dimension+1)
1

Data profiles,τ = 1e-7

1

Data profiles,τ = 1e-7

1

50n
75n

0.8
0.6
0.4
0.2
0
0

2000

4000

6000

8000

10000

Number of function evaluation/(dimension+1)

Fig. 7. Through the VCI method, data profiles resulted from comparing the computational cost 50 times the problem dimension with 25 times the problem dimension
(top left corner), or with 40 times the problem dimension (top right corner), or with
60 times the problem dimension (bottom left corner), or with 75 times the problem
dimension (bottom right corner) on the Hedar test set.

A Simplex-BSO via Visualizing Confidence Intervals

5

17

Conclusions

The Nelder-Mead’s simplex method is adopted into a simplified version of BSO to
accelerate the local exploitation. The obtained Simplex-BSO algorithm is shown
to perform better than these two original algorithms. This success owes to a
better balance between global exploration and local exploitation. The balance
parameter is shown numerically to be insensitive.
The recently proposed VCI method is adopted to analyze experimental results, and it is really helpful to present numerical results friendly and efficiently.

Acknowledgement
This work was supported by the National Natural Science Foundation of China
(No. 61773119), Natural Science Foundation of Guangdong Province, China
(No.2015A030313648), Fundamental Research Funds for the Central Universities (No. GK201603014), and Natural Science Basic Research Plan in Shaanxi
Province of China (No. 2017JQ6070).

References
1. Awad, N.H., Ali, M.Z., Liang, J.J., Qu, B.Y., Suganthan, P.: Problem definitions
and evaluation criteria for the cec 2017 special session and competition on single objective bound constrained real-paraeter numerial optimization. Tech. rep.,
Nanyang Technological University, Singapore (2016)
2. Cao, Y., Chen, W., Cheng, S., Sun, Y., Liu, Q., Li, Y., Shi, Y.: A simple brain
storm optimization algorithm via visualizing confidence intervals. In: Proceedings
of The 11th International Conference on Simulated Evolution and Learning, (SEAL
2017). pp. 1–12. Springer (2017)
3. Cheng, S., Qin, Q., Chen, J., Shi, Y.: Brain storm optimization algorithm: A review.
Artificial Intelligence Review p. in press (2016)
4. Dolan, E.D., Moré, J.: Benchmarking optimization software with performance profiles. Mathematical Programming 91, 201–213 (2002)
5. Duan, H., Li, S., Shi, Y.: Predator-prey brain storm optimization for dc brushless
motor. IEEE Transactions on Magnetics 49(10), 5336–5340 (October 2013)
6. Guo, X., Wu, Y., Xie, L.: Modified brain storm optimization algorithm for multimodal optimization. In: Tan, Y., Shi, Y., Coello, C.A.C. (eds.) Advances in Swarm
Intelligence, Lecture Notes in Computer Science, vol. 8795, pp. 340–351. Springer
International Publishing (2014)
7. Hedar, A.R.: Global optimization test problems, http://www-optima.amp.i.
kyoto-u.ac.jp/member/student/hedar/Hedar_files/TestGO.htm
8. Liu, Q., Chen, W.N., Deng, J.D., Gu, T., Zhang, H., Yu, Z., Zhang, J.: Benchmarking stochastic algorithms for global optimization problems by visualizing confidence
intervals. IEEE Transactioins on Cybernetics pp. 1–14 (2017)
9. Liu, Q., Cheng, W.: A modified direct algorithm with bilevel partition. Journal of
Global Optimization 60, 483–499 (2014)
10. Liu, Q., Zeng, J., Yang, G.: Mrdirect: A multilevel robust direct algorithm for
global optimization problems. Journal of Global Optimization 62, 205–227 (2015)

18

W. Chen et al.

11. Moré, J., Wild, S.: Benchmarking derivative-free optimization algorithms. SIAM
Journal on Optimization 20, 172–191 (2009)
12. Nelder, J.A., Mead, R.: A simplex method for function minimization. Computer
Journal 7, 308–313 (1965)
13. Shi, Y.: Brain storm optimization algorithm. In: Tan, Y., Shi, Y., Chai, Y., Wang,
G. (eds.) Advances in Swarm Intelligence, Lecture Notes in Computer Science, vol.
6728, pp. 303–309. Springer Berlin/Heidelberg (2011)
14. Shi, Y.: An optimization algorithm based on brainstorming process. International
Journal of Swarm Intelligence Research (IJSIR) 2(4), 35–62 (October-December
2011)
15. Shi, Y.: Developmental swarm intelligence: Developmental learning perspective of
swarm intelligence algorithms. International Journal of Swarm Intelligence Research (IJSIR) 5(1), 36–54 (January-March 2014)
16. Shi, Y.: Brain storm optimization algorithm in objective space. In: Proceedings of
2015 IEEE Congress on Evolutionary Computation, (CEC 2015). pp. 1227–1234.
IEEE, Sendai, Japan (2015)
17. Zhan, Z.H., Chen, W.N., Lin, Y., Gong, Y.J., long Li, Y., Zhang, J.: Parameter
investigation in brain storm optimization. In: 2013 IEEE Symposium on Swarm
Intelligence (SIS). pp. 103–110 (April 2013)

