Abstract
As a new and promising swarm intelligence algorithm, brain storm optimization (BSO) has drawn more attention of researches and has been successfully applied to solve the real-world optimization problems. However, too many parameters make the algorithm more complex and greatly limit the convergence performance. Thus, this paper proposed a novel BSO variant, named self-adaptive BSO with pbest guided step-size (SPBSO), in which a simple self-adaptive strategy is employed to choose a creating strategy in a random manner rather than depending on several adjustable parameters. In addition, the pbest guided step-size and dynamic clustering number are used to accelerate the convergence speed. The experimental studies have been tested on a set of widely used benchmark functions (including the CEC 2014 problems). Experimental results and comparison with the state-of-the-art BSO variants and some recently proposed PSO and DE algorithms, have proved that the proposed algorithm is competitive.
Introduction
Brain storm optimization (BSO) algorithm proposed by [22] is a new and promising optimization algorithm, inspired by the brainstorming process of human being. In original BSO, three operations, i.e., clustering, creation and selection, are used to search the global optimum. Due to its simple concept and effectiveness for complex optimization problems, BSO has attracted much attention in nature-inspird optimization community and has been successfully applied to solve several kinds of real-world problems [13, 24]. A set of experimental studies in [32, 33] show that BSO is competitive to some popular evolutionary algorithms, such as particle swarm optimization (PSO) and differential evolution (DE).
In BSO algorithm, the creating strategy plays an important role in determining the performance, but there exist four strategies and we need to choose the most appropriate strategy in the evolution process to ensure the success of the algorithm. Moreover, three crucial parameters involved to determine the suitable strategy, i.e., Pone-cluster, Pone-center, and Ptwo-centers, which may significantly influence the optimization performance of the BSO. Generally, it is required to perform some trial-and-error searches to tune these parameter values. However, this work is not a good idea and time-consuming. As we all known, self-adaptive method refers to those rules that mainly utilize the feedback from the search process such as fitness values to guide the updating of strategies and has proven to be very efficient and effective. Likewise, the performance of BSO is also influenced by the fixed schedule for updating the step-size.
Motivated by these observations, a novel BSO variant, named self-adaptive BSO with pbest guided step-size (SPBSO), in which a simple self-adaptive strategy is employed to choose a suitable creating strategy in a random manner rather than depending on several adjustable parameters. In addition, the pbest guided step-size and dynamic clustering number are used to accelerate the convergence speed. The distinct advantage of this work is that the proposed SPBSO algorithm needs few parameters (only population size NP) to set can has faster convergence rates. The experimental studies have been tested on a set of widely used benchmark functions (including the CEC 2014 problems).
The rest of this paper is structured as follows. In Section 2, the original BSO algorithm is introduced briefly. Section 3 surveys some recently related works. Section 4 presents the details of the our proposed BSO variant, called SPBSO. Experimental results and analysis are described in Section 5. Section 6 concludes the work.
Brain storm optimization
The original BSO is a population-based algorithm developed by [22] to mimic the human brainstorming process. In BSO, a population with NP ideas {idea1, idea2, …, idea
NP
} is randomly sampled in the search space, where NP is the population size, and each idea represents a candidate solution. At any iteration, BSO conducts clustering, creation, and selection to seek optimal solution. The details of these basic operations are described as follows [22, 32]. Randomly select a cluster k, nidea
i
= center
k
Randomly select an idea r1 in cluster k, nidea
i
= idear1
Randomly select two clusters k and j, nidea
i
= r × center
k
+ (1 - r) × center
j
, where r ∈ [0, 1] is a uniformly distributed random number Randomly select two ideas r1 and r2 in cluster k and j, respectively, There are three parameters Pone-cluster, Pone-center, and Ptwo-centers as shown in Algorithm 1 to determine one of strategies. However, a plenty of experimental studies in [33] shown that these parameters are sensitive and choosing the suitable values are a challenge work for different problems. After that, a step-size parameter ξ and Gaussian distribution is used to perturb the generated nidea
i
.
Selection for a strategy to create new idea in BSO
For the sake of novel concept and promising computational efficiency, much effort has been done to enhance the performance of the original BSO algorithm and several variants have been proposed. These works can be classified into the following three categories. Introduction of other clustering method instead of the k-mean approach to ease the computational burden [3–6, 35]. For example, [32] employed a simple grouping method (SGM) to replace the k-mean in their modified BSO algorithm (MBSO). Experiment study to investigate the influences of SGM indicates that the CPU time used SGM is usually faster 2–3 times than used original k-mean. [5] presented a modified Affinity Propagation (AP) clustering method to group ideas without the number of clusters beforehand. [35] used k-medians algorithm to improve the efficiency of the original BSO algorithm, in which the idea in the cluster nearest from the calculated median/mean replaced the median/mean as the cluster center. [3] replaced the k-mean algorithm with a random grouping strategy to decrease the time complexity. [6] introduced the agglomerative hierarchical clustering in to BSO, in which the prespecified number of clusters is not required. Recently, [4] proposed dynamic clustering strategy to improve the clustering method, which periodically executes the k-mean clustering. Beside trying to replace the k-mean algorithm, [23] eliminates the clustering strategy in BSO and splits the ideas into two classes, i.e., elitist and normal class. Experimental results verified the effectiveness and efficiency of the new strategy. New idea creation strategy to improve the search efficiency [8, 34]. For example, [34] modified the step-size according to the dynamic range of ideas on each dimension. In addition, the new ideas are generated in a batch-mode and then selected into the next generation. [28] presented an advanced discussion mechanism-based BSO (ADMBSO), in which the inter-and intra-cluster discussions are elaborately designed to control local and global search ability, respectively. [8] proposed a modified step-size equation, in which the proportional to the search space size, i.e., new parameter α, is introduced to multiply the factor ξ. Recently, inspired by PSO algorithm, [9] also proposed a global-best BSO (GBSO), which incorporated the global-best information in the update equation. [26] proposed a learning strategy to improve the population diversity, in which all ideas are ranked from the best to the worst based on fitness values. Hybridization of BSO with other techniques [2, 29]. For example, [14] combined BSO with teaching-learning-based optimization (TLBO) to solve the optimal power flow problem. [2] hybridized BSO with differential evolution (DE) algorithm, in which the DE strategy is utilized in the ideas generation to make BSO jump out of stagnation. [12] integrated the simulated annealing (SA) process into the BSO algorithm to replace the creating operator. [11] combined BSO with discrete particle swarm optimization (DPSO) for traveling salesman problem (TSP). [29] introduced a chaotic operation to the BSO to help ideas search the whole searching space.
Recently, Cheng et al. in [7] presented a comprehensive survey on the progress of BSO, so further information can reference them. It is necessary to emphasize that the works of this paper belongs to the new idea creation strategy and we aim to self-adaptively adjust the creating strategy to suit different landscapes.
Self-adaptive brain storm optimization with pbest guided step-size (SPBSO)
In this section, we present an improved BSO (SPBSO), in which self-adaptive selection of creating strategy is employed with the aim of increasing the adaptability to different problems. Furthermore, pbest guided step-size and dynamic clustering number are proposed to enhance the search ability. The details of the three main components and the framework of SPBSO will be described.
Self-adaptive adjustment for creating strategy
In BSO algorithm, the creating strategy plays an important role in determining the performance, but there exist four strategies and we need to choose the most appropriate strategy in the evolution process to ensure the success of the algorithm. Moreover, three crucial parameters involved to determine the suitable strategy, i.e., Pone-cluster, Pone-center, and Ptwo-centers, which may significantly influence the optimization performance of the BSO. Generally, it is required to perform some trial-and-error searches to tune these parameter values. However, this work is not a good idea and time-consuming. As we all known, self-adaptive method refers to those rules that mainly utilize the feedback from the search process such as fitness values to guide the updating of strategies and has proven to be very efficient and effective [1, 25].
Ref. [20] proposed a self-adaptive DE (SaDE), in which the mutation strategy was adaptively chosen from a candidate pool that consists of four strategies with diverse characteristics. The select rule was based on the probability of choosing that calculated by the success and failure memories. Furthermore, the control parameter F was sampled by normal distribution with mean value 0.5 and standard deviation 0.3. Meanwhile, the control parameter CR was adaptive adjusted by a historical memory mechanism. [19] proposed a novel DE variant, named CUDE. As the main contributions in CUDE, commensal learning is introduced to adaptively choose a suitable combination of mutation strategy and parameter settings together for each individual at each generation. [1] presented a novel approach named jDE to self-adapt control parameters F and CR. In jDE, these two control parameters are encoded at the individual level. Furthermore, [25] proposed a novel multi-strategy ensemble ABC (MEABC) algorithm. In MEABC, a pool of distinct solution search strategies coexists throughout the search process and competes to produce offspring.
Motivated by these observations, this paper proposes a self-adaptive method for creating strategy, which adaptively selects the proper one from the four creating strategies throughout the search process and eliminates all the parameters. As illustrated in Algorithm 2, when the new idea is worse than the current idea, i.e., f (nidea i ) > = f (idea i ), it means that the current creating strategy has a lower chance to generate better new idea and the adjustment is need. Then the randomly selection for creating strategy is performed to achieve self-adaptive adjustment. Otherwise, when the new idea is better than the current idea, i.e., f (nidea i ) < f (idea i ), it means that the current strategy is suitable for the search.
The self-adaptive adjustment for creating strategy
The self-adaptive adjustment for creating strategy
Compared with the classical BSO algorithm, the selection of creating strategies is based on the feedback during the search process, i.e., the quality of the new idea, rather than the parameters. As we all known, the evolution process of different problem may be different. So using the fixed parameters to select creating strategies for all problems is not a good idea. In the case, this self-adaptive method enables the algorithm can fit into the different problems. Moreover, this method is simple and easy to implement.
The clustering number NC plays an important role to affect the search ability of BSO algorithm. A large value of NC makes the algorithm divides more clusters using k-means. It turns out that the BSO algorithm have better exploration ability and can increase the population diversity. A large value of NC is need in the start-up phase. In contrast, a small value of NC enables the algorithm divides less clusters and focuses on exploitation. A small value of NC suits for the last phase.
In this paper, a dynamic clustering number strategy is proposed to update NC and the formula as shown in Equation 4. In the new dynamic clustering number strategy, NC
l
and NC
u
represent the lower and upper bound of NC respectively. Based on the logarithmic sigmoid transfer function, NC will drop down from NC
u
to NC
l
. After surveying the related literatures and running some initial experimentation over numerical benchmarks, the NC
l
and NC
u
are set to 10 and 5 respectively.
where Iter is the current iteration number and MaxIter is the maximum number of iterations. According to the new strategy, initially, the value of NC is larger, which will focus on exploration and constantly explore new effective area. As the evolution of the population continues to conduct, the value of NC gradually decrease, which focus on exploitation and search for the optimal solution.
In the original BSO, the new idea nidea i is created using Gaussian distribution according Equation 2, in which the step-size parameter ξ (Equation 1) plays key role. However, the step-size ξ is always between 0 and 1 regardless of the actual search space size. Moreover, the step-size ξ uses a fixed logarithmic sigmoid transfer function based on the generation, and the fixed function will make the evolution process of different problem to be same.
To overcome these problems, this paper proposed a pbest guided step-size, in which the pbest information of the population is introduced. The new pbest guided step-size enables the different problems to have different updating paths for step-size and can be formulated as follows:
where idea pbest is a randomly chosen idea within top p individuals according to the objective value and the p decreases linearly from NP to 1 based on the generation. The pbest guided step size can make the population will not convergent to the same best idea. Moreover, if the best information of population utilized directly, the algorithm will lack of global search ability and easy gets stuck into local optimum. Therefore, This strategy can be able to overcome the shortcoming of premature convergence and accelerate convergence speed.
Algorithm 3 describes the pseudocode of SPBSO. By comparison with the original BSO algorithm, there are three major differences in the SPBSO. The first difference is the using of dynamic clustering number at Step 5. The second difference is the using of self-adaptive adjustment for creating strategy. At the initial stage, Step 2 initializes the creating strategy S in a random manner, then in the cycle, Step 27 self-adaptively adjusts the creating strategy based on the quality of the new idea during the search process. The last difference is the using of pbest guided step-size to generate the new idea at Step 25.
The Proposed SPBSO Algorithm
The Proposed SPBSO Algorithm
Benchmark functions and experimental setting
Test suite with thirteen benchmark functions
Test suite with thirteen benchmark functions
In this section, the proposed SPBSO algorithm is compared with four other BSO variants, including the original BSO [22], MBSO [32], GBSO [9], and SMBSO [33], to verify the quality of the new algorithm.
Comparison of SPBSO with original BSO
The parameters used in original BSO follow [22], that is, NP = 100, NC = 5, Pone-cluster = 0.8, Pone-center = 0.4, and Ptwo-centers = 0.5. The parameters used in SPBSO are only needed to consider NP, we use the same parameter values as the original BSO.
The results achieved by BSO and SPBSO at D = 30 for the test suite are summarized in Table 2, where “Ave Err” and “Std Dev” indicate the mean and standard deviation of the function error values obtained in 30 runs, respectively. The best results are shown in Evolutionary processes of BSO and SPBSO on eight representative benchmark functions at D=30. Experimental results of original BSO and SPBSO for all test functions at D=30
Experimental results of MBSO, GBSO, SMBSO, and SPBSO for all test functions at D=30
Experimental results of MBSO, GBSO, SMBSO, and SPBSO for all test functions at D=30
From the results, it can be seen that SPBSO achieves best results on 9 out of 13 test functions, and SMBSO gets 5 best results, but MBSO and GBSO have no best one. For the comparison of SPBSO with MBSO, both of them win 4 among the total 8 functions. SPBSO outperforms GBSO on 6 out of 8 functions. SMBSO gets better results than SPBSO on 4 functions, while SPBSO achieves more accurate solution on 8 functions and all the two competitor find the global optimum on the function f6. It demonstrates that SPBSO is the best one among the four BSO algorithms.
As we all known, PSO and DE are the most popular evolutionary algorithms, which have fast convergence and good search abilities. In this section, SPBSO compares with four recently proposed state-of-the-art PSO and DE algorithms, including comprehensive learning PSO (CLPSO) [17], fully informed particle swarm (FIPS) [18], self-adaptive DE (SaDE) [20], and orthogonal crossover based DE (OXDE) [27]. The parameter settings of these four contestant algorithms are the same as that of their original literature, but the MaxFEs in all of these algorithms was set to 2E5.
Experimental results of CLPSO, FIPS, SaDE, OXDE and SPBSO for all test functions at D=30
Experimental results of CLPSO, FIPS, SaDE, OXDE and SPBSO for all test functions at D=30
Average rankings obtained through Friedman test
Statistical distributions of four creating strategy of SPBSO in evolution process on four representative test functions.
Summary of the CEC 2014 test functions
Summary of the CEC 2014 test functions
In this section, SPBSO is compared with three other published evolutionary algorithms on CEC 2014 at D = 30, i.e., non-uniform mapping in real-coded genetic algorithms (NRGA) [31], fitness classification constraint DE (FCDE) [15], and partial opposition-based adaptive DE (POBL-ADE) [10]. It is necessary to emphasize that the experimental results of NRGA, FCDE, and POBL-ADE are directly taken from their original literatures to ensure the comparison fair. For these competitors, the same maximum number of function evaluations (MaxFEs) 3E5 is used at D = 30 as the terminate condition of the algorithms.
Experimental results of classical BSO and SBSO for all test functions at D=30
Average rankings obtained through Friedman test
As mentioned previously, the four creating strategies are the key component of the BSO algorithm and the self-adaptive strategy makes the adaptability of the proposed SPBSO algorithm to various problems increased. The aim of the section is to analyze the role of the four creating strategies in the evolution process for different test functions. To this end, we count up the number of each creating strategy chosen in the evolution process for each test function. Figure 2 shows the statistical distributions of the four creating strategies on four representative test functions.
By carefully reviewing Figure 2, one can note that the distributions of the four creating strategies have nothing in common with each other on four representative test functions. Owing to the fact that different test functions have different suitable creating strategy on different evolution stages. As a result, the four creating strategies may give rise to different roles and different roles in a problem maintain different interests in various aspects of the evolution process. For example, in Figure 2(a) exhibits the distribution of creating strategies for function f1 and it notes that strategy 3, 1, and 4 are the first three used. But from Figure 2(d), the distribution of the four creating strategies is same. Moreover, Figure 2(a) is similar to 2(b). In all subgraph, the most used strategy is 3. Therefore, the above experimental results and analysis verify the roles of the proposed self-adaptive adjustment for creating strategy.
Conclusion
BSO algorithm is a recently invented evolutionary algorithm and powerful for the global optimization. However, too many parameters make the algorithm very complex and greatly limit the convergence performance. To overcome this problem, a novel self-adaptive BSO with pbest guided stepsize (SPBSO) is presented, in which a simple self-adaptive strategy is employed to choose a suitable creating strategy in a random manner rather than depending on several adjustable parameters and eliminates three parameters (i.e.,Pone-cluster, Pone-center, and Ptwo-centers). In addition, the pbest guided step-size and dynamic clustering number are proposed to enhance the convergence performance.
The experimental studies in this paper are conducted on a set of test functions including the CEC 2014 complex test functions. The performance of SPBSO is investigated by comparing with original BSO algorithm and three recently proposed BSO variants (i.e., GBSO, MBSO, and SMBSO). SPBSO is also compared with four recently proposed PSO and DE algorithms (i.e., CLPSO, FIPS, SaDE, OXDE). In addition, SPBSO is compared with NRGA, FCDE, POBL-ADE on the CEC 2014 benchmark problems. Fortunately, the results show that SPBSO achieves more accurate solution and wins over the compared algorithms. But beyond that, the role analysis of the self-adaptive adjustment for creating strategy is experimentally studied.
Footnotes
Acknowledgments
This work is supported by the National Natural Science Foundation of China (No.61763019), the Science and Technology Plan Projects of Jiangxi Provincial Education Department (No.GJJ161076, No.GJJ161072).