Self-adaptive bacterial foraging algorithm based on estimation of distribution

Abstract

Bacteria foraging optimization (BFO) algorithm is easy to fall into the local optimal solution and slow in convergence. In this paper, we have come up with a self-adaptive bacterial foraging algorithm based on estimation of distribution to overcome the mentioned shortages. First, in the chemotactic operator, the swimming step size of bacterium is adaptively adjusted by its fitness value and bacteria move in a random direction. Second, the bacteria obtain the probability of replication based on the fitness value. We choose half of the population for replication by the roulette wheel method. Finally, the possibility of elimination-dispersal is adjusted by the fitness value. Selected bacteria are dispersed to the new locations produced by BOX-Muller formula. Compared with some relative heuristic algorithms on finding the optimal value of ten benchmark functions, the proposed algorithm shows higher convergence speed and accuracy.

Keywords

Bacteria foraging optimization algorithm self-adaptive estimation of distribution benchmark function

1 Introduction

In 2002, Passino [12] put forward a bacteria foraging optimization (BFO) algorithm for optimization problems by the aid of the foraging behavior of Escherichia coli in human intestinal tract. Although BFO algorithm is superior to some other algorithms, it needs to be improved in terms of convergence speed and global search capability since it is really easy to fall into the local optimal solution and slow in convergence. Since then, many scholars have paid attention to BFO algorithm. Mishra [11] proposed fuzzy bacterial foraging in 2005, using fuzzy theory to choose optimal step size, while its performance depends on the selection of membership function. To speed up the convergence, Amin and Ehsan et al. [5] added a fitness function after the swimming of bacteria to calculate the next direction. In application, the fusion of BFO algorithm and other algorithms also have achieved good results. Kim and Abraham et al. [6] proposed GABFO algorithm by introducing crossover operator and mutation operator into BFO algorithm. To improve the performance of the algorithm, many scholars improved its adaptability. Datta, Misra et al. [3] and Majhi, Panda et al. [10] gave the ability of adaptively adjusting step size to bacteria according to the energy bacteria acquired in the whole life cycle. Dasgupta and Biswas [2] advanced a new BFO algorithm based on self-adaptive step size method to improve the fixed step size. Chen and Zhu [1] studied the influence of step size to self-adaptive BFO algorithm. If step size is too big, the ability of local search will be decreased. If step size is too small, the global search ability will be decreased. Based on self-adaptive step size method, Tong [16] introduced the roulette wheel selection into the reproduction operator.

In recent years, BFO algorithm was often applied in various fields with other algorithms. Ofosu et al. [13] used BFO algorithm to obtain optimal PI gains for fuzzy-PI controller and solved the difficulties that the proportional integral and derivative controllers could not overcome. Xiong et al. [17] proposed a risk-based multi-objective optimal allocation model and solved the formulated multi-objective optimization problem by combining the gradient particle swarm optimization algorithm and bacterial foraging algorithm, which decrease the risks of distributed generation and is conducive to the promotion and use of distributed generation. In computing integrals, many primitive functions of integrable functions are not elementary functions. Guo and Zhou [4] used BFO algorithm and the trapezoid quadrature formula to do that. The simulation results are really better than the results using the basic theorem of calculus. Kora et al. [7] combined bacterial foraging and particle swarm optimization to detect the abnormal cardiac beats. This method effectively improves the accuracy of the test results and also greatly helps the medical industry. It can be seen from those studies, BFO algorithm is an algorithm favored by various fields because of its good performance. Therefore, the improvement of BFO algorithm is also necessary for us, so that BFO algorithm may have better applications.

The main aim of this paper is to improve the bacterial foraging algorithm to promote the use of this algorithm in more fields. In the process we improved this algorithm, we find that self-adaptive adjusting various probabilities used in the algorithm and using BOX-Muller formula can reduce the double calculation of the algorithm and improve the effectiveness of proposed algorithm. The article is divided into the following sections: Section 2 introduces the bacteria foraging optimization algorithm. Section 3 describes estimation of distribution algorithm. Section 4 details the improved bacteria foraging optimization algorithm. The experimental analysis is conducted in Section 5. Finally, conclusion is given in Section 6.

2 Bacteria foraging optimization algorithm

To begin with notice that we shall consider the minimization problem as follows, ${\begin{matrix} min f (x) \\ subject to : x \in D \subset R^{n} . \end{matrix}$ (1) We know there are many research on methods to solve the problem (1). As a new evolutionary algorithm, bacteria foraging optimization (BFO) algorithm is also a kind of globally random searching algorithm. BFO algorithm mainly includes three processes: chemotaxis, reproduction and elimination-dispersal.

The chemotaxis operator can be divided into two parts: choosing direction and flipping. In the chemotaxis operator, each bacterium chooses a random direction to move one step. The random direction can be expressed by $φ (i) = \frac{Z_{i} (j, k, l)}{\sqrt{Z_{i} (j, k, l)^{T} Z_{i} (j, k, l)}}$ (2) where $Z_{i} (j, k, l) = X_{i} (j, k, l) - X_{rand} (j, k, l),$ X_i (j, k, l) represents the position of the i-th bacterium in the j-th chemotaxis operator, the k-th reproduction operator and the l-th elimination-dispersal operator, and X_rand (j, k, l) represents a random position in the neighborhood of current individual. Then, the position of a bacterium can be adjusted by the formula $X_{i} (j + 1, k, l) = X_{i} (j, k, l) + Step * φ (i) .$ (3) A feasible solution is a vector in problem space. This vector is also used to represents the position of the bacterium. Chemotaxis process may be understood as generating a new position of the bacterium by walking a Step along a random direction from original position. If the fitness of the new position is better than original one, then keep the bacterium moving in the same direction until the algorithm reaches the number of flipping or the fitness cannot be improved. The chemotaxis operator only let bacterium maintain the original state or go to a better state to ensure that the population will not degenerate.

The reproduction operator plays a role in accelerating the optimization of the population in the entire algorithm. In the reproduction operator, all bacteria in the space are sorted by their fitness values. The whole population can be divided into two parts: good performance and poor performance. Half of bacteria with good performance are copied to replace those bacteria with poor performance. We can see that this method also has the disadvantage of reducing population diversity.

The last operator is elimination-dispersal. Randomly generate a number. If the number is smaller than the probability P_ed of elimination-dispersal, the bacterium will be dispersed to a new position generated randomly, otherwise the bacterium will maintain the original state. The procedure of elimination-dispersal provides more possibilities to jump out of the local optimal solution, but also increases the possibility of missing the global optimal solution.

3 Estimation of distribution algorithm

In this paper, the method of generating new individuals in literature has been quoted into the elimination-dispersal operator in order to improve the BFO algorithm.

Estimation of distribution algorithm (EDA) [8] is a stochastic optimization algorithm based on statistical principle. This algorithm predicts the best searching area by sampling the search space and statistical learning of the applied model and generates the next population according to the probability model.

First, EDA initializes the original population. Then, it chooses advantaged group and constructs probability model of the population. After that, this algorithm randomly samples in the search space and generates new population according to the sample. Finally, the algorithm determines whether the termination condition is satisfied. If so, it outputs the optimization result. Otherwise, it chooses advantaged population again.

Gauss probability model is widely used to improve continuous EDA. Sebag and Ducoulombier [15] proposed variable independent estimation of distribution algorithm based on Gauss distribution. In 2000, Larra and Etxeberria et al. [9] proposed univariate real number code estimation of distribution algorithm based on Gauss distribution. In addition, the stochastic hill climbing with learning by vectors of normal distribution (SHCLVND) algorithm [14] is also a stochastic optimization algorithm based on Gauss distribution. On this basis, Rudlof and Koppen [14] proposed the application of Gauss distribution model to generate new individuals.

4 Improved bacteria foraging optimization algorithm

To improve the convergence speed and accuracy of BFO algorithm, the proposed algorithm introduces self-adaptive method and estimation of distribution method into BFO algorithm. The core idea is adjusting step size by self-adaptive method in chemotaxis operator and producing new locations by estimation of distribution method in elimination-dispersal operator. Assumed that the fitness value of bacterium f (i) can be represented as $f (i) = \frac{1}{{value}_{benchmark}},$ (4) in which the value_benchmark represents the value of benchmark function. The purpose of this algorithm is to find bacteria with the biggest fitness value. Then We’ll give more details about it.

4.1 Chemotaxis operator

For the chemotaxis operator, the main improvement is to adjust the chemotaxis step size. Based on the existing research, the adaptive mechanism is introduced into the chemotaxis process and the chemotaxis step length is adjusted according to the fitness value of individual bacterium.

Compared with fixed step size, the new algorithm is adjust the step size according to the fitness value. If the fitness value is smaller than the average of all fitness value, we’ll keep the step size unchanged. If the fitness value is greater than the average fitness value, we’ll modify the step size according to the following formula $C^{i} (j + 1, k, l) = \frac{f_{best} - f_{i}}{f_{best} - f_{worst}} * C^{i} (j, k, l),$ (5) where Cⁱ (j, k, l) represents the step size in the j-th chemotaxis operator, the k-th reproduction operator and the l-th elimination-dispersal operator; f_best is the best of all fitness values; f_worst is the worst of all fitness values, f_i is the fitness value of the i-th bacterium. Adjusting step size is of great significance to chemotaxis operator. According to adjusting bacterial step size by their different status, their forage ability are also regulated. Poorly performing bacteria have larger step size. Because they are far from the optimal value, we need to speed them up. We replace the “Step” in (3) with the adjusted step size Cⁱ (j + 1, k, l). After that, the bacterium will generate a random direction as formula (2) and plug into (3). By this way, we can complete a chemotaxis operator for a bacterium.

4.2 Reproduction operator

The original reproduction operator directly ranks bacterial individuals according to fitness values and eliminates half of bacterial population with a bad fitness value, which may decreases the diversity of bacterial populations and kill some potential excellent individuals accidentally. The optimal fitness of the whole population remains unchanged which may slow down the convergence speed of the algorithm. Therefore, this algorithm adopt a new reproduction selection method.

First, we define the possibility of reproduction by the fitness value which can be expressed as follows $p (i) = \frac{f (i)}{\sum_{i = 1}^{n} f_{(} i)},$ (6) where f_i represents the fitness value of the i-th individual. The above formula can be adjusted according to specific problems. Here they are based on the following experiments. According to this formula, the bacteria with better fitness value have a greater possibility of reproduction.

Based on the possibility of reproduction, we will choose half of bacteria to copy and the rest of bacteria are replaced by new bacteria. In this way, the number of individuals in the bacterial population can remain the same. This replication method can not only make bacteria with better fitness value have greater possibilities to be replicated, but also give chance to the potential excellent individual to continue searching optimal solution.

4.3 Elimination-dispersal operator

Elimination-dispersal operator is the operator of this algorithm which can make the algorithm have global search ability. In the original bacterial foraging algorithm, elimination-dispersal operator has a fixed dispersal probability. If the corresponding random number produced by the bacterial individual is less than the probability, the bacterial individual will be dispersed to a random location in the space. Otherwise, no further processing will be done on the bacterium.

In the novel optimization algorithm, we use the estimation of distribution method in [14] to disperse individual bacteria. After chemotaxis and reproduction, each bacterial individual produces a corresponding random number and adjusts the dispersal probability adaptively according to the individual fitness value. The bacteria with better fitness value have less probabilities to disperse. Otherwise the dispersal probability will be amplified. Compared the random number with the adjusted dispersal probability, if the random number is less than the set dispersal probability, the dimensions of the bacteria’s position vector are independent of each other, and each dimension conforms to Gaussian distribution, we calculate the mean and standard deviation of each dimension of the bacterial population at first. Then, according to the BOX-Muller formula, we generate a random number consistent with Gauss distribution r_norm as follows, $r_{norm} = \sqrt{- 2 ln r_{1}} sin 2 π r_{2}$ (7) where r₁ and r₂ are random uniform distributed numbers on [0,1]. We take all the current bacteria as population and select the average of each dimension to form μ. The standard deviation of each dimension constitutes σ. They can be expressed as follows, $\begin{matrix} μ & = & (μ_{1}, μ_{2}, . . ., μ_{m}) \\ = & (\frac{\sum_{i = 1}^{n} X_{i 1}}{n}, \frac{\sum_{i = 1}^{n} X_{i 2}}{n}, \dots, \frac{\sum_{i = 1}^{n} X_{im}}{n}), \end{matrix}$ $\begin{matrix} σ & = & (σ_{1}, σ_{2}, \dots, σ_{m}) \\ = & (\sqrt{\frac{1}{n} \sum_{i = 1}^{n} (X_{i 1} - μ_{1})^{2}}, \sqrt{\frac{1}{n} \sum_{i = 1}^{n} (X_{i 2} - μ_{2})^{2}}, \\ \dots, \sqrt{\frac{1}{n} \sum_{i = 1}^{n} (X_{im} - μ_{m})^{2}}) \end{matrix}$ where m represents the number of dimension, X_ij represents the j-th component of the i-th bacterial location for i = 1, 2, ⋯ , n, j = 1, 2, ⋯ , m. Combining the mean μ and standard deviation σ, the new location of bacteria will be obtained by the following formulas $X_{μ, σ} = r_{norm} σ + μ$ (8)

According to this new dispersal method, bacteria aren’t dispersed to a completely random location. In the initial elimination-dispersal operator, the new location is completely random, which means there are a number of bacteria recover to initial conditions in each elimination-dispersal operator. This operation causes all previous work to invalid, which also causes the whole algorithm converge slowly.

4.4 Steps of improved bacteria foraging optimization algorithm

The improved algorithm consists of chemotaxis, reproduction and elimination-dispersal operators. The steps of self-adaptive bacteria foraging algorithm based on estimation of distribution (BFOED) can be described as follow:

Step 1: Initialize the population and set the parameters: chemotaxis time N_c, chemotaxis step N_s, reproduction time N_r, elimination-dispersal time N_ed, step size Step, the probability of elimination P_ed, population size N;

Step 2: Adjust bacterial step size by (5) and choose a random direction by (2);

Step 3: Move one step on the selected direction by (3) and calculate the new fitness value by benchmark function;

Step 4: Determine whether to continue chemotaxis. If the fitness value of new location is smaller that of initial location, turn back to Step 2 until the algorithm reaches the number of flipping or the fitness value cannot change. If the original value is smaller than the fitness value of new location, go to the next step;

Step 5: Define the possibility of reproduction by fitness value by (6);

Step 6: Choose half bacteria to reproduce and kill unselected bacteria;

Step 7: Adjust the possibility of elimination-dispersal P_ed by fitness value and produce a random number. If the random number is less than adjusted probability P_ed, bacterium goes to Step 8. Otherwise, bacterium goes to Step 9;

Step 8: Dispersal bacterium to new location produced by (7) and (8);

Step 9: Turn back to Step 1 until the algorithm reaches the number of iteration or get the optimal value.

Algorithm flow chart is as the following Algorithm 1.

Algorithm 1 Proposed algorithm
Procedure
Initialize the population and set the parameters:
N_c, N_s, N_r, N_ed, Step, P_ed, N.
Chemotaxis Operator:
iff (i) < average fitness value then
Adjust step size:
$C^{i} (j + 1, k, l) = \frac{f_{best} - f_{i}}{f_{best} - f_{worst}} * C^{i} (j, k, l)$
end if
Choose direction by (2)
Move
Reproduction Operator:
Adjust p_i: $p (i) = \frac{f (i)}{\sum_{i = 1}^{n} f_{(} i)}$
Reproduct
Elimination-dispersal Operator
Adjust P_ed
if random number < P_edthen
Obtain new location:
$r_{norm} = \sqrt{- 2 ln r_{1}} sin 2 π r_{2}$
X_μ,σ = r_normσ + μ
end if
Turn back to Chemotaxis Operator until the algorithm
reaches the number of iteration or get the optimal value.
end procedure

5 Experimental analysis

5.1 Benchmark functions and parameter setting

In order to test the performance of the improved algorithm, we select several benchmark functions and use the proposed algorithm to search the minimum value. Some of these functions have many local optimal values. With the increase of dimensions, the number of local optimal values increases exponentially, which also increases the difficulty of finding the minimum value. See Table 1 for the standard test functions.

Table 1
Benchmark functions

Function Mathematical expression Range of x_i Dimension Target value

f₁ (x) $\frac{1}{4000} \sum_{i = 1}^{n} x_{i}^{2} - \prod_{i = 1}^{n} \frac{cos x_{i}}{\sqrt{i}} + 1$ [-600, 600] n 0

f₂ (x) ${sin}^{2} (π (1 + \frac{x_{1} - 1}{4})) + \sum_{i = 1}^{n - 1} (\frac{x_{i} - 1}{4})^{2} \times$

$[1 + 10 {sin}^{2} (π (1 + \frac{x_{i} - 1}{4}) + 1)] + (\frac{x_{n} - 1}{4})^{2} [1 + {sin}^{2} (2 π (\frac{x_{n} - 1}{4}))]$ [-10, 10] n 0

f₃ (x) $\sum_{i = 1}^{n} | x_{i} |^{(i + 1)}$ [-1, 1] n 0

f₄ (x) $- 20 e^{- 0.2 \sqrt{(\sum_{i = 1}^{n} x_{i}^{2}) / n}} - e^{\frac{\sum_{i = 1}^{n} cos (2 π x_{i})}{n}} + 20 + e$ [-1, 1] n 0

f₅ (x) $- \sum_{i = 1}^{n} sin (x_{i}) {sin}^{20} (\frac{i x_{i}^{2}}{π}) + 9.66$ [0, π] 10 0

f₆ (x) $\sum_{i = 1}^{n} i x_{i}^{2}$ [-10, 10] n 0

f₇ (x) $0.26 (x_{1}^{2} + x_{2}^{2}) - 0.48 x_{1} x_{2}$ [-10, 10] 2 0

f₈ (x) $100 \sqrt{| x_{2} - 0.01 x_{1}^{2} |} + 0.01 | x_{1} + 10 |$ x₁ ∈ [-15, 5]

x₂ ∈ [-3, 3] 2 0

f₉ (x) $\sum_{i = 1}^{n} (x_{1} - x_{i})^{2} + (1 - x_{i})^{2}$ [-10, 10] n 0

f₁₀ (x) $\sum_{i = 1}^{n} | x_{i} |$ [-5.12, 5.12] n 0

Function	Mathematical expression	Range of x_i	Dimension	Target value
f₁ (x)	$\frac{1}{4000} \sum_{i = 1}^{n} x_{i}^{2} - \prod_{i = 1}^{n} \frac{cos x_{i}}{\sqrt{i}} + 1$	[-600, 600]	n	0
f₂ (x)	${sin}^{2} (π (1 + \frac{x_{1} - 1}{4})) + \sum_{i = 1}^{n - 1} (\frac{x_{i} - 1}{4})^{2} \times$
	$[1 + 10 {sin}^{2} (π (1 + \frac{x_{i} - 1}{4}) + 1)] + (\frac{x_{n} - 1}{4})^{2} [1 + {sin}^{2} (2 π (\frac{x_{n} - 1}{4}))]$	[-10, 10]	n	0
f₃ (x)	$\sum_{i = 1}^{n} \| x_{i} \|^{(i + 1)}$	[-1, 1]	n	0
f₄ (x)	$- 20 e^{- 0.2 \sqrt{(\sum_{i = 1}^{n} x_{i}^{2}) / n}} - e^{\frac{\sum_{i = 1}^{n} cos (2 π x_{i})}{n}} + 20 + e$	[-1, 1]	n	0
f₅ (x)	$- \sum_{i = 1}^{n} sin (x_{i}) {sin}^{20} (\frac{i x_{i}^{2}}{π}) + 9.66$	[0, π]	10	0
f₆ (x)	$\sum_{i = 1}^{n} i x_{i}^{2}$	[-10, 10]	n	0
f₇ (x)	$0.26 (x_{1}^{2} + x_{2}^{2}) - 0.48 x_{1} x_{2}$	[-10, 10]	2	0
f₈ (x)	$100 \sqrt{\| x_{2} - 0.01 x_{1}^{2} \|} + 0.01 \| x_{1} + 10 \|$	x₁ ∈ [-15, 5]
		x₂ ∈ [-3, 3]	2	0
f₉ (x)	$\sum_{i = 1}^{n} (x_{1} - x_{i})^{2} + (1 - x_{i})^{2}$	[-10, 10]	n	0
f₁₀ (x)	$\sum_{i = 1}^{n} \| x_{i} \|$	[-5.12, 5.12]	n	0

Population space is the same as problem space. In problem space, a feasible solution is a vector, so we use bacterial coordinates to represent a feasible solution. It can be understood that if a feasible solution is X = (x₁, x₂, ⋯ , x₂₅), then the corresponding bacterial coordinate is also X = (x₁, x₂, ⋯ , x₂₅). In order to better explain the corresponding relationship between problem space and population space, we give the Table 2.

Table 2

Corresponding relationship between problem space and population space

Problem space	Population space
the number of feasible solution	the number of bacteria
feasible solution	the location/gene of bacteria
the dimension of problem sapce	the dimension of population space

In this paper, genetic algorithm (GA), bacterial foraging optimization (BFO) algorithm [12], bacterial foraging optimization algorithm based on self-adaptive method (BFOSA) [16] and the algorithm proposed in this paper (BFOED) are used to optimize the above functions. We calculate the mean, standard deviation, minimum of the experimental results and analyze the performance of the algorithm according to the data.

In order to compare the optimization effects of different algorithms in the same situation, we need to set the parameters of the algorithm uniformly. In bacterial foraging algorithm, bacterial foraging algorithm based on self-adaptive method and the algorithm proposed in this paper, The initial population size P is 60, the dimension of the space bacteria search is 25, maximum steps of chemotaxis N_s is 4, the times of chemotaxis, reproduction and elimination and dispersal N_c, N_r, N_ed are equal to 40, 4, 2. According to the work principle of BFO, the total iteration is relevant to N_c, N_r, N_ed, can be represented as

$Iteration = N_{c} * N_{r} * N_{ed} .$ (9) Respectively, the initial probability of elimination and dispersal is 0.25. The bacterial step size is set according to the size of the search space. In genetic algorithm, the initial population is 60, the number of iterations is 320, the crossover rate P_c is 0.3, the mutation rate P_m is 0.1. In terms of parameter selection, we refer to [16] and make certain adjustments through multiple trials. The parameter settings of the algorithms are as Table 3.

Table 3

Parameter settings of algorithms

Parameter	GA	BFO	BEOSA	BFOED
Population	60	60	60	60
Number of iteration	320	320	320	320
N _c	Null	40	40	40
N _r	Null	4	4	4
N _ed	Null	2	2	2
N _s	Null	4	4	4
P _ed	Null	0.25	0.25	0.25
P _c	0.3	Null	Null	Null
P _m	0.1	Null	Null	Null

5.2 Simulation results

Different algorithms are good at solving different problems. We can not guarantee that the algorithm proposed in this paper is suitable for all benchmark functions. We use the algorithms to optimize the benchmark functions (where n = 25) for 30 times, from which we can choose the average best results μ, standard variances σ and best values as shown in Table 4 and rank-based results are provided in Tables 5 and 6.

Table 4
Average best results (μ), standard variances (σ) and best values of GA, BFO [12], BFOSA [16] and BFOED (this paper) on f₁ - f₁₀

Benchmark function Index GA BFO BEOSA BFOED

f ₁ μ 1.034076 6.415252 5.644328 2.831369

σ 0.011736 1.747696 1.348040 0.513447

best value 0.997795 3.807280 3.270630 2.17082

f ₂ μ 8.340657 50.365412 45.867302 8.049242

σ 4.453952 5.612227 7.849952 5.873341

best value 3.351077 41.515717 27.474264 3.291993

f ₃ μ 0.039896 0.667637 0.012347 0.001662

σ 0.034962 0.203835 0.004921 0.001450

best value 0.003299 0.372449 0.004554 0.000087

f ₄ μ 1.900343 3.292270 1.713329 0.713421

σ 0.324861 0.844704 0.318933 0.297655

best value 1.129876 3.175114 1.058814 0.399843

f ₅ μ 2.900671 6.050920 3.690154 3.661558

σ 0.785961 0.513260 0.594932 0.603064

best value 1.911252 5.007231 2.711976 2.121042

f ₆ μ 203.320540 8.163177 80.091047 53.742812

σ 120.180468 1.975618 13.661435 15.662812

best value 36.625644 3.751828 41.373973 19.914807

f ₇ μ 0.073049 0.009853 0.000006 0.000001

σ 0.145844 0.012926 0.000006 0.000002

best value 0.000807 0.000045 0.000000 0.000000

f ₈ μ 0.334014 0.136225 0.112654 0.102458

σ 0.305105 0.050832 0.027888 0.045923

best value 0.008920 0.044290 0.050513 0.004149

f ₉ μ 74.948307 5.066878 23.304368 25.764239

σ 37.138627 0.974220 5.503489 6.293086

best value 26.822400 3.543862 8.751187 14.619224

f ₁₀ μ 13.791007 7.738178 22.693582 7.709653

σ 2.805767 1.071886 2.442100 1.489897

best value 9.129609 5.586066 17.527981 5.499556

Benchmark function	Index	GA	BFO	BEOSA	BFOED
f ₁	μ	1.034076	6.415252	5.644328	2.831369
	σ	0.011736	1.747696	1.348040	0.513447
	best value	0.997795	3.807280	3.270630	2.17082
f ₂	μ	8.340657	50.365412	45.867302	8.049242
	σ	4.453952	5.612227	7.849952	5.873341
	best value	3.351077	41.515717	27.474264	3.291993
f ₃	μ	0.039896	0.667637	0.012347	0.001662
	σ	0.034962	0.203835	0.004921	0.001450
	best value	0.003299	0.372449	0.004554	0.000087
f ₄	μ	1.900343	3.292270	1.713329	0.713421
	σ	0.324861	0.844704	0.318933	0.297655
	best value	1.129876	3.175114	1.058814	0.399843
f ₅	μ	2.900671	6.050920	3.690154	3.661558
	σ	0.785961	0.513260	0.594932	0.603064
	best value	1.911252	5.007231	2.711976	2.121042
f ₆	μ	203.320540	8.163177	80.091047	53.742812
	σ	120.180468	1.975618	13.661435	15.662812
	best value	36.625644	3.751828	41.373973	19.914807
f ₇	μ	0.073049	0.009853	0.000006	0.000001
	σ	0.145844	0.012926	0.000006	0.000002
	best value	0.000807	0.000045	0.000000	0.000000
f ₈	μ	0.334014	0.136225	0.112654	0.102458
	σ	0.305105	0.050832	0.027888	0.045923
	best value	0.008920	0.044290	0.050513	0.004149
f ₉	μ	74.948307	5.066878	23.304368	25.764239
	σ	37.138627	0.974220	5.503489	6.293086
	best value	26.822400	3.543862	8.751187	14.619224
f ₁₀	μ	13.791007	7.738178	22.693582	7.709653
	σ	2.805767	1.071886	2.442100	1.489897
	best value	9.129609	5.586066	17.527981	5.499556

Table 5

Rank-based Results of GA, BFO, BFOSA and BFOED on f₁ - f₅

Benchmark function	Index	GA	BFO	BEOSA	BFOED
f ₁	μ	1	4	3	2
	σ	1	4	3	2
	best value	1	4	3	2
f ₂	μ	2	4	3	1
	σ	1	2	4	3
	best value	2	4	3	1
f ₃	μ	3	4	2	1
	σ	3	4	2	1
	best value	2	4	3	1
f ₄	μ	3	4	2	1
	σ	3	4	2	1
	best value	3	4	2	1
f ₅	μ	1	4	3	2
	σ	4	1	2	3
	best value	1	4	3	2

Table 6

Rank-based Results of GA, BFO, BFOSA and BFOED on f₆ - f₁₀

Benchmark function	Index	GA	BFO	BEOSA	BFOED
f ₆	μ	4	1	3	2
	σ	4	1	2	3
	best value	3	1	4	2
f ₇	μ	4	3	2	1
	σ	4	3	2	1
	best value	4	3	1	1
f ₈	μ	4	3	2	1
	σ	4	3	1	2
	best value	2	3	4	1
f ₉	μ	4	1	2	3
	σ	4	1	2	3
	best value	4	1	2	3
f ₁₀	μ	3	2	4	1
	σ	4	1	3	2
	best value	3	2	4	1

According to the Table 4, we can see that the results of BFOED is better than that of other algorithms for most benchmark functions. f₅, f₇, f₈ are low-dimensional benchmark functions. Among them, BFOED has the best optimization for f₇, f₈ in the four algorithms. The average optimal value of BFOED for f₅ is slightly less effective than GA, but the standard variance of BFOED is smaller. In other words, BFOED is more stable than GA for f₅. Other functions are high-dimensional benchmark functions, some of which have lots of local optimums that can increase the difficulty of searching global optimal value. For f₂, f₃, f₄, f₁₀, not only for the average value, but also for the best value, the result of BFOED is the best. For f₁, the optimized effect of BFOED is slightly worse than that of GA. In all results, the optimized effect of BFO for f₆ and f₉ is much better than that of the other three algorithms. According to the Tables 5 and 6, the optimization results of BFOED are the best in most cases. The capability of optimization of BFOED is still effective on the whole.

From the aspect of algorithm, BFOED strengthens the control of bacterial activities, including the adjustment of step size, the method of reproduction, P_ed and the new location generated in the elimination-dispersal operator. In each operator of proposed algorithm, BFOED always adjusts the features of each bacterium according to its states. However, the original algorithm does the same thing for all bacteria, so in each optimization process BFO is not flexible enough. This is why BFOED is more stable than other algorithms. After analyzing the improvement effect of BFOED, let’s analyze the convergence and stability of BFOED. This part mainly make analysis for benchmark function f₁ as a case.

Figures 1, 2 and 3 are the results of optimizing the benchmark function f₁ with BFO, BFOSA and BFOED, respectively. The time of chemotaxis is 30, the time of reproduction is 3, the time of dispersal is 2. Through Fig. 1, we can see that in the process of BFO optimization, there will be two places with great fluctuation in the optimization of bacterial population and there is a gap between the optimal value of the final optimization result and the overall average value. In other words, the overall optimization effect of BFO is not mature enough. Figure 2 is the optimization result of BFOSA for f₁. It can be seen that the average optimization value only fluctuates once and the fluctuation amplitude decreases. There is still a large gap between the optimal value and the overall average value. We think the reason for the upward oscillation is that the elimination-dispersal process of BFO and BFOSA initializing the positions of some bacteria results in the invalidation of the preliminary work of the algorithm, so the oscillation will appear in the figure. The second downward shock may due to the reproduction operator according to the position where it appears. The population performs the replication operation and accelerates the average optimization value of the population.

Fig. 1

BFO for f₁ (25 dimensions).

Fig. 2

BFOSA for f₁ (25 dimensions).

Fig. 3

BFOED for f₁ (25 dimensions).

Figure 3 is the optimization result of BFOED for f₁. Obviously, the optimization effect of BFOED for the overall average value is good and there is no fluctuation in the whole process. In the process of optimization, the global average value is continuously decreasing as the optimal value. In addition, the final optimal value and the overall average value almost coincide. The optimization of BFOED for f₁ not only eliminate the fluctuation in BFO, but also reduce the interval between the optimal value and the overall average value. It can also be seen that BFOED has good convergence and stability and can jump out of the local optimal solution. Table 7 is the specific data of Figs. 1 –3.

Table 7

Optimization results of f₁

Index	BFO	BFOSA	BFOED
Optimal value	6.203185	3.491023	2.314457
Average value	23.877046	18.412597	10.807722

In order to prove the BFOED has faster convergence speed than BFO and BFOSA, we give the line charts of the optimal results of BFO, BFOSA and BFOED, which record the optimal values every ten iterations.

The ten subgraphs of Figs. 4 –13 can not only reflect the convergence results of the three algorithms, but also reflect their convergence speed. The closer the broken line is to the x-axis, the faster the convergence speed is. From Figs. 4 –13, we can see that most of the broken lines of BFOED are located at the bottom of the image. It can be seen that BFOED has higher convergence rate under the same iteration number. The following Table 8 gives the average optimized value of BFOED optimizing the test function 100 times in 25-dimensional space and the average iteration number of reaching the average optimized value.

Fig. 4

Line chart of BFO, BFOSA and BFOED for f₁.

Fig. 5

Line chart of BFO, BFOSA and BFOED for f₂.

Fig. 6

Line chart of BFO, BFOSA and BFOED for f₃.

Fig. 7

Line chart of BFO, BFOSA and BFOED for f₄.

Fig. 8

Line chart of BFO, BFOSA and BFOED for f₅.

Fig. 9

Line chart of BFO, BFOSA and BFOED for f₆.

Fig. 10

Line chart of BFO, BFOSA and BFOED for f₇.

Fig. 11

Line chart of BFO, BFOSA and BFOED for f₈.

Fig. 12

Line chart of BFO, BFOSA and BFOED for f₉.

Fig. 13

Line chart of BFO, BFOSA and BFOED for f₁₀.

Table 8

The average optimized value and average iteration number of BFOED

Benchmark function	average optimized value	Average iteration number
f ₁	2.535705	210.28
f ₂	8.002942	189.55
f ₃	0.001030	182.43
f ₄	0.730965	219.11
f ₅	3.245844	209.03
f ₆	60.304624	161.00
f ₇	0.000001	81.29
f ₈	0.099876	94.90
f ₉	28.157269	176.67
f ₁₀	8.688440	209.14

The average iteration number is the average of iteration numbers at which the algorithm reaches the average optimization value for 100 times. From the Table 8, we can see that BFOED has the fastest convergence speed for f₇ and f₈. The average iteration number required is small. For other functions, the convergence speeds are relatively average. The average iteration number required for all functions is 173.709, which can guarantee the stability in the later period. On the whole, BFOED has good convergence.

5.3 Complexity analysis

The analysis of the computational complexity of the proposed algorithm is divided into time complexity and space complexity. We mainly draw a conclusion by comparing the average CPU computational time of different algorithms in 25 dimensions and the average CPU computational time of BFOED in different dimensions. The unit of CPU computational time is seconds. All algorithms are coded with Python and performed in a computer with Intel(R) Core(TM) i5-7200U CPU @2.50GHz(4 CPUs)∼2.70GHz and 8192MB RAM.

Table 9 is the result of the average CPU computational time of different algorithms in 25 dimensions. We can see that GA has the best average CPU computational time for each function and there is a gap between BFO and GA in average CPU computational time. This is because BFO, as a new intelligent optimization algorithm, has higher control power in the optimization process, so it takes longer. We know that the time complexity of the algorithm is closely related to the number of times the algorithm calls the objective function in the optimization process. Compared with BFO, BFOED calls the objective function more times, so BFOED has no advantage in time complexity and has higher time cost. Because f₅, f₇, f₈ have specific dimensions, we just test the other functions in different dimensions. In the Table 10, we can see that with the increase of dimensions, it is more difficult for the algorithm to find the optimal value, the optimal value that BFOED can obtain gradually becomes larger and the average CPU computational time also becomes longer. In addition to giving specific data, we can also use the following method to analyze the time complexity.

Table 9
Average CPU computational time of algorithms on f₁-f₁₀

Benchmark function GA BFO BEOSA BFOED

f ₁ 6.69 95.64 83.45 78.52

f ₂ 17.89 110.22 189.55 134.78

f ₃ 5.82 30.62 72.68 100.23

f ₄ 10.79 57.88 156.13 122.80

f ₅ 5.06 22.35 62.13 69.04

f ₆ 6.34 83.01 146.20 120.07

f ₇ 4.26 11.51 34.48 20.76

f ₈ 4.54 10.20 27.26 24.21

f ₉ 6.89 115.64 178.19 137.55

f ₁₀ 6.98 110.83 183.45 131.44

Benchmark function	GA	BFO	BEOSA	BFOED
f ₁	6.69	95.64	83.45	78.52
f ₂	17.89	110.22	189.55	134.78
f ₃	5.82	30.62	72.68	100.23
f ₄	10.79	57.88	156.13	122.80
f ₅	5.06	22.35	62.13	69.04
f ₆	6.34	83.01	146.20	120.07
f ₇	4.26	11.51	34.48	20.76
f ₈	4.54	10.20	27.26	24.21
f ₉	6.89	115.64	178.19	137.55
f ₁₀	6.98	110.83	183.45	131.44

Table 10

Optimization results in different dimensions

Function	Index	5 dimensions	10 dimensions	15 dimensions	20 dimensions	25 dimensions
f ₁	best value	0.146874	0.705081	1.038011	1.342265	2.17082
	average CPU time	20.02	36.08	56.80	67.35	78.52
f ₂	best value	0.002719	0.136640	0.931622	1.887576	3.291993
	average CPU time	40.57	76.84	100.30	125.49	140.78
f ₃	best value	0.000392	0.000569	0.000470	0.000456	0.000087
	average CPU time	39.03	54.48	75.70	88.29	100.23
f ₄	best value	0.018520	0.111262	0.280108	0.356075	0.399843
	average CPU time	38.34	57.11	83.59	108.67	122.80
f ₆	best value	0.004340	0.558100	1.587818	8.877949	19.914807
	average CPU time	37.01	61.22	83.63	106.67	120.07
f ₉	best value	0.006288	0.787767	3.174126	4.988301	14.619224
	average CPU time	41.19	62.25	87.40	119.10	137.55
f ₁₀	best value	0.147101	0.906829	2.511330	3.856690	5.499556
	average CPU time	40.57	64.33	89.86	102.83	131.44

The proposed algorithm mainly consists of five steps: initializing bacterial population, chemotaxis operator, replication operator, elimination-dispersal operator and stopping judgment. Assuming that the number of bacterial population is P, the maximum iteration number of the algorithm is T in the D dimensional search space. When initializing bacterial population, there are two cycles P and D, so the time complexity of initialization stage is O (P * D). In the process of chemotaxis, replication and elimination-dispersal, the algorithm includes three cycles P, D and T, so the time complexity of these three processes is O (P * D * T). For the process of jumping out of the loop, his time complexity is O (1). Therefore, the total time complexity of BFOED is O (P * D * T).

In BFOED, the number of individuals of bacterial population is P, and its space is D dimensional, so the space complexity of BFOED is O (P * D).

6 Conclusion

It is found that the optimization process of bacteria foraging optimization (BFO) algorithm is accompanied by oscillation phenomenon, and the final average optimal value is far from the optimal value, so it is meaningful to improve the BFO. Proposed algorithm (BFOED) effectively overcomes the shortcomings that BFO easily falls into the local optimal solution by introducing estimation of distribution method and self-adaptive mechanism.

The convergence speed of BFOED is significantly improved compared to BFO. BFOED much early reaches a stable state and quickly converges to the optimal solution. Embedding estimation of Gaussian distribution in the elimination and dispersion operator greatly speeds up the convergence speed of the algorithm and avoids inefficient search and invalidation of previous work. In addition, for the optimizations of high-dimensional multi-peak benchmark functions, the optimization results of BFOED are better than those of GA and BFO and its accuracy has been improved. Through the test of the function dimension, we find that the function dimension also has an impact on the optimization result of the algorithm. The higher the dimension, the more difficulty find the optimal solution with. In the future work, we plan to study the convergence of the BFOED from the perspective of a random process and make more comparisons with other algorithms.

Acknowledgments

This work is supported by the National Natural Science Foundation of China (Grant No. 61673011).

References

Chen

, Zhu

and Hu

, Self-adaptation in bacterial foraging optimization algorithm, Proceedings of the 3rd International Conference on Intelligent System and Knowledge Engineering, Xiamen, China, pp. 1027–1031, 2008.

Dasgupta

, Biswas

and Abraham

, Adaptive computational chemotaxis in bacterial foraging optimization: An analysis, IEEE Transactions on Evolutionary Computation 13(4) (2009), 919–941.

Datta

, Misra

I.S.

, Mangaraj

B.B.

, et al., Improved adaptive bacteria foraging algorithm in optimization of antenna array for faster convergence, Progress in Electromagnetics Research C 1(1) (2008), 143–157.

Guo

and Zhou

, Numerical integration based on bacterial foraging algorithm, Science and Technology Vision 10 (2019), 118–120.

Khodabakhshian

, Daryabeigi

and Moazzami

, A new optimization approach for multi-machine power system stabilizer design using a smart bacteria foraging algorithm, Simulation 89(9) (2013), 1041–1055.

Kim

D.H.

, Abraham

and Cho

J.H.

, A hybrid genetic algorithm and bacterial foraging approach for global optimization, Information Sciences 177(18) (2007), 3918–3937.

Kora

, Abraham

and Meenakshi

, Heart disease detection using hybrid of bacterial foraging and particle swarm optimization, Evolving Systems 11(1) (2020), 15–28.

Larrañaga

and Lozano

J.A.

, Estimation of distribution algorithms-A new tool for evolutionary computation, Boston: Springer, 2002.

Larrañaga

, Etxeberria

, Lozano

J.A.

, et al., Optimization in continuous domains by learning and simulation of Gaussian networks, Proceedings of the 2000 Genetic and Evolutionary Computation Conference Workshop Program, Las Vegas, pp. 201–204, 2000.

10.

Majhi

, Panda

, Majhi

, et al., Efficient prediction of stock market indices using adaptive bacterial foraging optimization (ABFO) and BFO based techniques, Expert Systems with Applications 36(6) (2009), 10097–10104.

11.

Mishra

, A hybrid least square-fuzzy bacterial foraging strategy for harmonic estimation, IEEE on Evolutionary Computation 9(1) (2005), 61–73.

12.

Passino

K.M.

, Biomimicry of bacterial foraging for distributed optimization and control, IEEE Control Systems Magazine 22(3) (2002), 55–67.

13.

Ofosu

R.A.

, Kamau

S.I.

, Nderu

J.N.

, et al., Determination of optimal PI gains for fuzzy-PI controller using bacterial foraging algorithm (BFA), IOSR Journal of Electrical and Electronics Engineering 11(2) (2016), 26–33.

14.

Rudlof

and Köppen

, Stochastic hill climbing with learning by vectors of normal distributions, Proceedings of First Online Workshop on Soft Computing 1996, Nagoya, pp. 60–70, 1996.

15.

Sebag

and A. Ducoulombier, Extending population-based incremental learning to continuous search spaces, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, pp. 418–427, 1998.

16.

Tong

, Bacteria foraging optimization algorithm based on self-adaptative method, Value Engineering 11 (2015), 194–197.

17.

Xiong

, Wu

, Li

, et al., Risk-based multi-objective optimization of distributed generation based on GPSO-BFA algorithm, IEEE Access 7 (2019), 30563–30572.

18.

Zhou

, Ling

and Luo

, Lévy flight trajectory-based whale optimization algorithm for engineering optimization, Engineering Computations 35(7) (2018), 2406–2428.