key: cord-0047467-awz7ol11
authors: Cao, Weifu; Tan, Yingshi; Huang, Miaojia; Luo, Yuxi
title: Adaptive Bacterial Foraging Optimization Based on Roulette Strategy
date: 2020-06-22
journal: Advances in Swarm Intelligence
DOI: 10.1007/978-3-030-53956-6_27
sha: b30345658ebb8ea86982d8eedd3ee4c51ac4ac6e
doc_id: 47467
cord_uid: awz7ol11

Bacterial foraging optimization has drawn great attention and has been applied widely in various fields. However, BFO performs poorly in convergence when coping with more complex optimization problems, especially multimodal and high dimensional tasks. Aiming to address these issues, we therefore seek to propose a hybrid strategy to improve the BFO algorithm in each stage of the bacteria’s’ foraging behavior. Firstly, a non-linear descending strategy of step size is adopted in the process of flipping, where a larger step size is given to the particle at the very beginning of the iteration, promoting the rapid convergence of the algorithm while later on a smaller step size is given, helping enhance the particles’ global search ability. Secondly, an adaptive adjustment strategy of particle aggregation is introduced when calculating step size of the bacteria’s swimming behavior. In this way, the particles will adjust the step size according to the degree of crowding to achieve efficient swimming. Thirdly, a roulette strategy is applied to enable the excellent particles to enjoy higher replication probability in the replication step. A linear descent elimination strategy is adopted finally in the elimination process. The experimental results demonstrate that the improved algorithm performs well in both single-peak function and multi-peak function, having strong convergence ability and search ability.

The past decades have witnessed numerous researchers sought different methods to tackle optimization problems. Mathematics methodology used to be a relatively good technique to solve these problems but its limitations turn out to be obvious as more and more practical optimization problems involve complexity, multi-minimum, strong constraint, non-linearity and a lot of variables and modeling difficulty. The traditional mathematics methodology is incapable of reaching the optimum in a reasonable computation time. Hence, developing new approaches has become one of the most important research directions. In recent years, a number of metaheuristics inspired from nature and biology has appealed numerous researches and have developed and come to widely used in different practice problems [1] . For example, genetic algorithm (GA) [2] , is a probabilistic search algorithm, mimick-ing nature selection and biology evolution mechanism; particle swarm optimization (PSO) [3] , is developed based on the swarming strategies of bird flocking and fish schooling.

Bacterial foraging optimization (BFO) [4] , proposed by Passino is also belongs to this bio-mimetic algorithms group. It mimics the foraging strategy of Escherichia coli bacteria, involving four key processes, namely, chemotaxis, swarming, reproduction and elimination-dispersal steps, encouraging BFO to search the global optimum more efficiently than the traditional mathematical methods. BFO algorithm has been effectively applied to solve practical optimization problems in different fields, such as PID controller design [5] , dynamic environment optimization [6] ,image processing [7, 8] , vehicle routing [9] , and machine learning [10] . Once emerged, BFO has been widely applied to various single-objective optimization problems [11] [12] [13] [14] and multi-objective optimization problems [15] .

The increasing interest for BFO has revealed that it is a promising, swarm-based optimization algorithm. However, there still exist several limitations in original BFO due to the fixed chemotaxis step-size, the less-efficient search direction for tumbling and the swarming strategy with a delay in approximating the global solution and a poor convergence rate, especially in tackling nonlinear, high-dimensional and multi-modal functions [1, [16] [17] [18] [19] . Many scholars proposed corresponding im-provement strategies based on these problems, mainly aiming at the two key steps of chemotaxis and replication. Some of the current researches of improving BFO could be described as follows:

With regards to the chemotaxis process, Panda and Naik (2015) [16] proposed a modified BFO algorithm called adaptive crossover BFO algorithm, which incorporated adaptive chemotaxis an d inherited the crossover mechanism of genetic algorithm. W. G. Zhao, L.Y. Wang (2016) [1] reported an effective bacterial foraging optimization (EBFO) where a gravitational search strategy is incorporated into the chemotaxis step to adjust its unit length according to the swarm information. L.L. Wanga et al. [17] (2018) developed a bare bones bacterial foraging optimization (BBBFO) algorithm in which a chemotactic strategy based on Gaussian distribution is incorporated into this method through making use of both the historical information of individual and the share information of group. C.C. Yang et al. (2016) designed a new bacterial foraging optimizer using new chemotaxis and conjugation strategies (BFO-CC). Via the new chemotaxis mechanism, each bacterium randomly selects a standard-basis-vector direction for swimming or tumbling. At the same time, the step size of each bacterium is adaptively adjusted based on the evolutionary generations and the information of the globally best individual, which readily makes the algorithm keep a better balance between a local search and global search and significantly improve convergence. B. Pang et al. (2019) [18] improved BFO algorithm (LPBFO) based on the Lévy flight step-size and particle swarm optimization (PSO) operator. During the chemotactic process in LPBFO, each bacterium selects one dimension for tumbling randomly. The step-size of each bacterium is determined by the stochastic flight lengths of the improved Lévy flight which can generate small step-size with high frequency and big step-size occasionally and the stochastic step-size is reduced adaptively based on the evolutionary generations, which makes the bacteria transform from global search to local search.

In the reproduction step, W. G. Zhao, L.Y. Wang (2016) [1] designed a swarm diversity strategy to enhance the reproduction mode depending on the swarm diversity. The simulation results show that the proposed algorithm is more effective than its competitors and can be extended to other global optimization problems. Liang and H.S. Tian (2016) [19] presents a hybrid algorithm based on the combination of BFO algorithm and PSO algorithm. Due to the random change of the direction of search, and the migration of bacteria by selective replication at a certain probability, results show that the improved hybrid algorithm is better than the basic PSO algorithm and the basic BFO algorithm. Besides, the convergence rate is fast and has good robustness. L.L. Wanga et al. [17] (2018) introduced the swarm diversity in the reproduction strategy to promote the exploration ability of the algorithm. The comparative results reveal that the proposed approach is more superior to its counterparts.

Overall, the current optimization algorithm of bacterial foraging focuses on proposing novel chemotaxis step strategies, but pays less attention to the reproduction process, especially to enhancing the influence of particles that perform well, so as to accelerate the convergence rate and improve the searching capacity of the particles.

To improve the original BFO for tackling complex optimization problems. We incorporate three strategies into the traditional BFO in each stage of the bacteria's foraging behavior, seeking to achieve a valid balance between the exploration and the exploitation during the life cycle of search for global optima. Firstly, to ensure the convergence performance and local mining abilities of the algorithm, a non-linear descending strategy of step size is adopted in the process of chemotaxis, where a larger step size is given to the particle at the very beginning of the iteration, promoting the rapid convergence of the algorithm and a smaller step size is given later on to help enhance the particles' local search ability. Secondly, an adaptive adjustment strategy of particle aggregation is introduced when calculating step size of the bacteria's swimming behavior. In this way, the particles will adjust the step size according to the degree of crowding to achieve efficient swimming. Thirdly, a roulette strategy is applied to enable the excellent particles to enjoy higher replication probability in the replication step. A linear descent elimination strategy is adopted finally in the elimination process, thus avoiding premature and a trap into local extremum. Various benchmark functions are considered to verify the performance of the proposed improved strategies, the comparative results demonstrate that the improved algorithm has a significant enhancement over the original BFO, especially in single-peak function and multi-peak function, having strong convergence ability and search ability.

Bacterial Foraging Optimization (BFO), a new swarm intelligence optimization algorithm proposed by Passino Kevin in 2002. The BFO algorithm simulates the foraging behavior of Escherichia coli in the human intestinal tract for mathematical modeling, so as to solve the optimization problem. Because of its simple structure and parallel processing, it has been widely used in many fields. According to the Theory of Bacterial Foraging, bacterial population has a strong tendency to nutrients. And every step of their movement is towards the position where they can get the maximum energy per unit time under the constraints of their own physiology and surrounding environment. Escherichia coli foraging behavior mainly includes four basic steps: Chemotaxis, Swarming, Reproduction, Elimination and dispersal.

Chemotaxis is a process that simulates Escherichia coli swimming and flipping. Escherichia coli migration can be divided into two processes: turnover and swimming, both of which are realized by flagella. If the flagella are counterclockwise rotation, Escherichia coli will be swimming; If the flagella were rotating clockwise, the bacteria would flip around in place looking for direction. After the bacteria find a new swimming direction by flipping, they will swim in that direction for the same length many times.

To define the direction of Chemotaxis, a unit length random direction is generated named ϕ(j). Then in computational Chemotaxis, the movement of the bacterium could be represented by formula (1)

where C(i) represents the size of the step taken in the random direction, θ i (j, k, l) is the i th bacterium at j th chemotactic, k th reproductive, and l th elimination and dispersal step.

In the process of bacteria approaching the optimal living environment, individuals of the colony release information, attractant and repellent, namely pheromone, to all other bacteria according to their current fitness value. This bacterium accepts the attractor and repulsor released by all other bacteria and modifies its adaptive value under the action of all its pheromones. Make sure to move to a better location for the local environment. In a colony, the calculation method of pheromone concentration between the above individuals can be expressed as formula (2)

where J cc (θ, P(j, k, l)) is a target function that changes with the population distribution state. When it is superimposed to the actual target function of the problem, it shows the trend of the relative distance between bacteria and the best individual.S is the size of the population;P indicates the dimensions of the optimization problem.

According to the principle of survival of the fittest, individuals with better performance (fitness) will reproduce, while those with poor performance will die.

First step of Reproduction's algorithm implementation is to calculate the health value, which is used to measure an individual's ability to explore. The health value of bacterium i determined as follows:

Then sorting the health values of the bacteria in descending order. The least half healthy bacteria die and the other half healthiest bacteria each split into two bacteria, which are placed in the same location. During the process of reproduction, the population of bacteria is constant.

The number of bacterial populations changes gradually over time or with changes in the environment, such as nutrient depletion. When an emergency occurs, bacteria in an area may be eliminated or dispersed to new areas. The last step of Standard BFO algorithm is the simulation of this process. Bacterial migration occurs according to a certain probability P ed , when a certain bacteria meets the migration conditions, the individual will be reallocated to another space.

In order to solve the problem of lack of learning direction and slow convergence speed in traditional bacterial foraging algorithm, this paper improve an adaptive bacterial foraging optimization algorithm based on roulette strategy (ARBFO) which improves BFO from chemotaxis, replication and elimination-diffusion. The ARBFO algorithm adopts roulette strategy and adaptive adjustment formula, which makes the algorithm have the ability of learning and adaptive adjustment to the environment. As a result, it accelerates the convergence speed and improves the search accuracy.

Chemotaxis step size controls the search range of the population. If the step size is not set properly, it will be trapped in local optimum or unable to converge to the optimal solution.

In the process of microbial foraging, the distance between each colony and the optimal solution in the initial population is larger, and the step size should be larger to help the rapid convergence of the microbial community. With the search, the distance between each colony and the optimal solution decreases, and the step size should be reduced at this time, so as to improve the accuracy of the microbial community search.

In this paper, two non-linear decreasing methods are used to adjust the step sizes of inversion and swimming in chemotaxis. In the process of inversion, with the increase of replication behavior, the newborn bacteria will search for a better range. At this time, the step size should be smaller to improve the search accuracy. The non-linear decline formula of step size should be adjusted:

Among them, K is the current number of replication, and Nre is the largest number of bacterial replication. With the increase of k, the step size will decrease.

In the course of swimming, a strategy of non-linear adaptive adjustment of step size is adopted. Considering the current iteration and the maximum iteration number, the number of chemotactic steps in a given range is changed. With the increase of iteration number, the step size shows a downward trend. This strategy advances according to the number of iterations and the current nutritional status of particles. Adaptive adjustment [21] , as follows:

In this formula, besides the classical adaptive adjustment strategy, the parameters J, J avg , J t . adjusted according to the microbial nutrition environment are introduced. The swimming step is adjusted by the overall weight, the average microbial nutrition value, and the individual optimal fitness value, which enhances the learning ability of the operator. With the increase of iteration times, the step size is as a whole. The step size decreases with the increase of nutrient value of the bacterial community search, so as to improve the accuracy of the later stage of the search.

Among them, J and J avg represent the current bacterial fitness and the average value of all bacteria respectively. J t is the optimal fitness value of the previous individual. K1 and K2 are normal numbers. They are adjusted adaptively according to the average value of bacterial nutrition and the optimal fitness value of the individual. After experiments, they are set to 2,0.4 respectively.

The replication strategy in the standard BFO algorithm, which retains half of the bacterial individuals with good fitness and eliminates the other half of the bacterial individuals with poor fitness, has not improved the optimal position of the current bacterial community; at the same time, this replication method reduces the diversity of the population in a half way by sacrificing the diversity of the population. The fast convergence of the algorithm can easily lead to the local optimum of the algorithm in the solution of high-dimensional and multi-peak functions.

In this paper, the roulette mechanism is used to improve the replication link in the flora foraging algorithm, improve the learning ability of the operator and improve the convergence speed. Roulette selection strategy, also known as proportional selection operator, has the basic idea that the probability of each individual being selected is proportional to the value of its fitness function.

If the population size is N and the fitness of individual Xi is f (xi), then the selection probability P (xi) of individual Xi is:

The roulette selection method can be realized by following process simulation:

(1) A uniformly distributed random number R is generated in [0,1].

(2) If r < q1, chromosome X1 is selected.

(3) If qk_1 < R < QK (2 < K < N), the chromosome XK is selected.

(4) Qi is called individual Xi (i = 1,2,… The cumulative probability of N) is calculated as follows:

In this process, the higher the fitness, the greater the chance that the particle will be selected, and vice versa, the smaller the chance that the particle will be selected. However, regardless of the fitness, the probability of being selected exists, allowing some particles with low nutritional value to survive. It is possible to improve the diversity of particles (Fig. 1 ).

Migration is the behavior that interferes with bacterial colonies and initializes the population randomly according to a certain probability. Migration probability describes the living environment of bacteria. Generally speaking, the change of nutrient value of bacterial colonies is not susceptible to the influence of bacteria, but decreases with the reproduction of bacteria. At the same time, the survival competition among bacteria has become more intense, and the more likely it is to disperse. In this paper, a linear decreasing adaptive regulation mechanism is adopted. According to the linear decreasing of iteration number, the improved migration step simulates the change of environment during a bacterial foraging process according to probability formula (8) . With the increase of iteration number, the migration probability decreases gradually, the chance of executing probability greater than the migration probability increases, and the bacteria are dispersed. The probability increases gradually to improve the diversity of particles and search accuracy.

Among them, Ped represents the probability of eliminating migration, ITER is the current number of iterations. Through this formula, the probability of eliminating migration can be adjusted adaptively according to the number of iterations to maximize the diversity of particles and search accuracy. 

To verify the performance of the improved algorithm (ARBFO), this article introduce Sphere, Schwefel, Rosenbrock, Rotated-Hyper-Ellipse, Beale, General rastrigrin, Ackley, Griewank, Alpine, Three-hump Camel [17, 20] ten typical benchmark functions to conduct simulated contrast experiment. The minimum of ten benchmark functions is 0. Among them, Sphere, Schwefel, Rosenbrock, Rotated-Hyper-Ellipse, Beale are unimodal functions, General rastrigrin, Ackley, Griewank, Alpine, Three-hump Camel are multimodal functions. And the Rotated-Hyper-Ellipse is the only rotated function.

The experimental environment is Inter(R) Core (TM) i5-7Y54 CPU @1.20 GHz, Windows 10,the running memory is 8BG, and it is completed under Matlab2018b.

To exam the performance of ARBFO, this article choose ASRBFO [21] , BFOLDC [22] and BFONDC [23] to conduct the simulated contrast experiment, and record the Table 1 shows the minimum value (Min), maximum value (Max), average value (Mean) and standard deviation (Std) of four algorithms in 10 benchmark functions. The dimension of the particles is 50, and the optimal results will be marked in bold. It can be seen from the data in Table 1 that, in terms of benchmark functions, ARBFO algorithm yields a compelling result in the convergence accuracy and stability of both unimodal functions and multimodal functions. Function 1-5 are unimodal functions and function 6-10 are multimodal functions. Figure 2 shows the fitness curve of four algorithms. Combined Fig. 2 with Table 1 , ARBFO outperforms other algorithms in functions 2, 4, 5, 6, 7, 9, and the optimization accuracy and stability of ARBFO algorithm are improved obviously. It is worth noticing that, the fitness curve of Rosenbrock has a breakpoint, because the ARBFO has converged to the minimum value of 0.

Compared with BFONDC algorithm, ARBFO fails to achieve the desired effect in convergence accuracy and stability. Therefore, future research will continue to improve ARBFO to better solve the existing problems on the part of the benchmark functions. The above analysis can prove that the proposed ARBFO algorithm in this paper demonstrates a far better convergence precision and optimal value than the BFO and it is an effective algorithm. 

In this paper, an adaptive mechanism and roulette strategy designed to improve the capacity of BFO is presented. The adaptive strategy is used to improve the search efficiency and accuracy in the process of tumbling, swimming, elimination and dispersal. Roulette strategy is adopted in the reproduction process to maximize the diversity of the group and avoid the algorithm falling into the local optimal value due to premature development. In tumbling, nonlinear descent strategy is adopted. In the early iterations particles are given larger step length, to prompt the algorithm to fast convergence, later particles will be given smaller step length, to strengthen the particles search precision. In swimming, step length calculation introduces nutritional value adaptive adjustment strategy, the particles will adaptively adjust step length according to the nutrition value, to realize efficient swimming. Roulette strategy is introduced in the reproduction process, therefore, the particles with better fitness value will have higher probability to reproduce, while the ones with worse fitness value have less chances to being selected, which enhances the diversity of particles and increases the search ability. In elimination and dispersal, the linear descending migration strategy is adopted to heighten the diversity of particles.

Ten benchmark functions has been used to test the performance of ARBFO in comparison with ASRBFO, BFOLDC and BFONDC. From the analysis and experiments, the result illustrates that this new algorithm outperforms the other four algorithms in convergence speed and accuracy in many cases, and it reach minimum value with Rosenbrock function. It can be concluded that ARBFO expressively improves the performance of BFO and lets out the better results on most optimization problems comparing with other BFO algorithms. However, more benchmark functions and practical application problems must be investigated in the future with ARBFO. The future work will underline more bio-heuristic mechanisms and application problems to entirely improve the performance of ARBFO.

An effective bacterial foraging optimizer for global optimization

Genetic Algorithms in Search, Optimization and Machine Learning

Particle swarm optimization

Biomimicry of bacterial foraging for distributed optimization and control

Biomimicry of bacterial foraging for distributed optimization and control

Bacterial foraging algorithm for dynamic environments

An adaptive bacterial foraging algorithm for fuzzy entropy based image segmentation

A novel bacterial foraging technique for edge detection

Adaptive comprehensive learning bacterial foraging optimization and its application on vehicle routing problem with time windows

Bacterial foraging based hyper-heuristic for resource scheduling in grid computing

Optimized relative transformation matrix using bacterial foraging algorithm for process fault detection

An optimal fuzzy system for edge detection in color images using bacterial foraging algorithm

Distribution network reconfiguration for power loss minimization using bacterial foraging optimization algorithm. IJEM-Int

Security constrained optimal power flow solution of wind-thermal generation system using modified bacteria foraging algorithm

An improved bacteria foraging optimization algorithm for high dimensional multi-objective optimization problems

A novel adaptive crossover bacterial foraging optimization algorithm for linear discriminant analysis based face recognition

A bare bones bacterial foraging optimization algorithm

Bacterial foraging optimization based on improved chemotaxis process and novel swarming strategy

An improved hybrid algorithm based on bacterial foraging and particle swarm optimization

Benchmark Functions for the CEC 2008 Special Session and Competition on Large Scale Global Optimization

A literature survey of benchmark functions for global optimisation problems

Adaptive structure-redesigned-based bacterial foraging optimization

Novel bacterial foraging optimization with time-varying chemotaxis step