Journal of Artificial Intelligence

Year: 2011 | Volume: 4 | Issue: 4 | Page No.: 207-219
DOI: 10.3923/jai.2011.207.219

Adaptation Schemes of Chemotactic Step Size of Bacterial Foraging Algorithm for Faster Convergence

H. Supriyono and M.O. Tokhi

Abstract: This study presents development of a new approach involving adaptable chemotactic step size in Bacterial Foraging Algorithm (BFA). Standard BFA only offers a constant chemotactic step size for all nutrient values. The chemotactic step size can be made adaptive, i.e., the chemotactic step size is changed in a certain manner. The objective of the study is to investigate adaptation schemes in the BFA so that the chemotactic step size may change depending on the nutrient value. The adaptation mechanism is made by incorporating nutrient value of every bacterium into three functions, namely linear function, quadratic function and exponential function and by using a fuzzy adaptation scheme. In the full BFA algorithm, the proposed approach will be used as vary the chemotactic step size. Test results with benchmark functions show that BFA with the proposed adaptable chemotactic step size is able to converge faster to the global optimum and to achieve better optimum value than that achieved by standard BFA.

Keywords: faster convergence, Adaptive bacterial foraging, adaptable chemotactic step size, fuzzy adaptation and biological-inspired optimization

INTRODUCTION

Bacterial Foraging Algorithm (BFA) has emerged as a relatively new biologically-inspired optimization method (Passino, 2002) and it has attracted significant attention of researchers. The BFA has been developed based on foraging strategies of E. coli bacteria. In general, E. coli bacteria always try to find a place which has high level of nutrition and avoid a place which has noxious substance. The BFA has been successfully applied in several application areas, such as optimisation of Unified Power Flow Controller (UPFC) (Tripathy et al., 2006), optimisation of active power filter for load compensation (Mishra and Bhende, 2007), null steering of linear antenna arrays (Guney and Basbug, 2008), optimising PD-PI controller for an inverted pendulum system (Jain and Nigam, 2008), calculating accurately the resonance frequency of rectangular micro-strip antenna (Gollapudi et al., 2008), designing multiple optimal Power System Stabilizers (PSS) (Das et al., 2008), tuning parameters of both single-input and dual-input Sugeno Fuzzy Logic (SFL) based PSS (Ghoshal et al., 2009) and optimisation of real power loss and voltage stability (Tripathy and Mishra, 2007).

In the BFA (Passino, 2002), the mechanism representing the way how foraging proceeds can be subdivided into four steps, namely chemotaxis, swarming, reproduction and elimination and dispersal. From the optimization point of view, consider that it is desired to find the minimum of J (θ)ε^p, where there is no measurement or there is no analytical description of the gradient Δ J(θ). Here, ideas from bacterial foraging can be used to solve this non gradient optimization problem. First, suppose that θ is the position of a bacterium and J (θ) represents the combined effects of attractants and repellants from the environment, with, for example, J (θ)<0, J (θ) = 0 and J (θ)>0 indicating that the bacterium at location θ is in nutrient-rich, neutral and noxious environments, respectively. Chemotaxis is such a foraging behaviour that bacteria try to climb up the nutrient concentration (find lower and lower values of J (θ)), avoid noxious substances and search for ways out of neutral media (avoid being at positions θ where J (θ)≥0) optimally by implementing a type of biased random walk.

To find places with high nutrient level with original BFA (Passino, 2002), here referred as standard BFA (SBFA), bacteria use random walk with certain constant value for whole computational process regardless of the nutrient value. The bigger step size the faster bacterium will climb down the hill. However, a mathematical analysis of the chemotactic step in SBFA based on classical gradient descent search approach Dasgupta et al. (2009) suggests that chemotaxis employed by SBFA usually results in sustained oscillation when close to the global optimum, especially on flat landscape nutrient media. In order to damp the oscillation, very small chemotactic step size is needed around the global optimum. Thus big step size will result bacterium to oscillate around the optimum point and probably miss the optimum value. Small step size will ensure the bacterium to find the optimum value but will require large number of iterations to find the optimum.

A suitable strategy to overcome this problem is to apply big step size when the cost function value is large so that the bacterium climbs down the hill faster and then apply very small step size when the bacterium is near the optimum point to ensure the bacterium is able to find the optimum point. Thus, the chemotactic step size can be made adaptive, i.e. the value of chemotactic step size changed based on the nutrient value; if the nutrient value is high then the step size is big and if the nutrient value is low then the step size is small. By applying this mechanism, the adaptive BFA (ABFA) will be faster in convergence and will also be able to reach the global optimum.

The objective of the study in this research is to investigate adaptation schemes in the BFA so that the chemotactic step size may change depending on the nutrient value. Four approaches based on linear function, quadratic function, exponential function and fuzzy logic are presented. In the full BFA algorithm, the four proposed approaches will be used as the new chemotactic step size instead of constant value. In order to validate their effectiveness, the proposed adaptation mechanism are tested to find global optimum point of several well-known benchmark functions. The performance of BFA with adaptable chemotactic step size is then compared to that of SBFA. The comparison is made based on the convergence and optimum nutrient value achieved (accuracy).

ADAPTABLE CHEMOTACTIC STEP SIZE OF BFA

The basic assumption used in the development of BFA with adaptable chemotactic step size (ABFA) in this work is that the global minimum solution of the nutrient media has to be non-negative. By using this assumption, when the nutrient value is high it means the bacteria are still far away from the global minimum position so that big step size is needed to approach the global minimum faster while when the nutrient value is low it means the bacteria are close to the global minimum value thus small step size is needed so that bacteria will not miss the global minimum point.

Linearly adaptive bacterial foraging algorithm: The adaptation mechanism in the linearly ABFA (LABFA) uses linear function of nutrient value of every bacterium for updating the chemotactic step size. The use of simple linear function for updating chemotactic step size of BFA has been reported by researchers previously (Majhi et al., 2009; Pandi et al., 2009; Dasgupta et al., 2009). The novelty in the current work is that tuneable maximum step size is introduced instead of unity and tuneable scaling factor to control the gradient of the chemotactic step size. By using this strategy, the “gradient” of chemotactic step size can be made steeper so that faster convergence is achieved. The proposed linear adaptive chemotactic step size is formulated as follows:

where, C_al (i) is linearly adaptive chemotactic step for every bacterium, c_max is tune-able maximum chemotactic step size, b is tuneable positive factor and d is tuneable positive scaling factor. Using such a formulation, the chemotactic step size will change in the range of [0, c_max] linearly depending on the nutrient (cost function) value as:

Quadratic adaptive bacterial foraging algorithm: The adaptation mechanism formulated in Eq. 1 can be accelerated by boosting |J (i)| term in quadratic manner. The quadratic ABFA (QABFA) uses a quadratic function of nutrient value of every bacterium for updating the chemotactic step size. The chemotactic step size is thus formulated as:

where, C_aq (i) is quadratic adaptive step size for every bacterium, g is tuneable scaling factor and J (i) is the nutrient value for every bacterium. The quadratic function of |J (i)| will result in extremely big denominator value of:

for large |J (i)| and this in turn will make this function equal to zero and then C_aq (i) will be equal to c_max. In this case, the chemotactic step size will change in a quadratic manner depending on the nutrient value in the range of [0, c_max].

Exponentially adaptive bacterial foraging algorithm: The adaptation mechanism of LABFA formulated in Eq. 1 can be further accelerated by applying an exponential function of the nutrient media. The exponential function of nutrient value is bigger than quadratic function of nutrient media used in the adaptation mechanism of QABFA formulated in Eq. 2. Thus, the use of exponential function of nutrient media will result bigger chemotactic step size for the same nutrient media than LABFA and QABFA. The exponentially ABFA (EABFA) uses an exponential function for updating the chemotactic step size, as follows:

where, C_ae (i) is exponentially adaptive step for every bacterium. The same as LABFA and QABFA, bigger |J (i)| will make the value of de^g|J (i)| very large and as a result the value of:

will become very small or approach zero and this in turn will make C_ae (i) approach c_max. On the contrary, if |J (i)| is very small or near zero then the value of de g|J (i)| will be very small as a result of which the value of:

will be very big and this in turn will make C_ae (i) approach zero. Thus, the chemotactic step size is changed exponentially according to nutrient value in the range [0, c_max].

Chemotactic step size adaptation using fuzzy logic: The chemotactic step size may also be adapted in relation to the nutrient value using a non-mathematical based approach such as using Fuzzy Logic (FL). It is noticed from the literature that Mishra (2005) proposed the use of a Sugeno type FL with four trapezoidal membership functions for adaptation scheme of chemotactic step size. In the current work Mamdani-type FL is used instead of Sugeno-type, making the chemotactic step size of every bacterium dependent on its own nutrient value rather than minimum value and also instead of using trapezoidal membership function, here Gaussian membership function is used because it is able to represent uncertainty in measurements more adequately (Kreinovich et al., 1992). Because of its advantages such as intuitive, widespread acceptance and well suited to human input (Sivanandam et al., 2007), Mamdani fuzzy model with Centre of Area (COA) defuzzification method is used in this work.

Thus, fuzzy logic construction for adaptable chemotactic step size, depicted in Fig. 1, is a one-input one-output fuzzy model as follows: the input of fuzzy logic is the absolute of nutrient media value of every bacterium (|J (i)|) and its output is the fuzzy adaptable chemotactic step size of every bacterium (C_af (i)).

Both the two Gaussian membership parameters (m₁,..., m₇ and σ₁,..., σ₇) for input and output were chosen by trial and error. Fuzzy logic produces output from the input by using human-like reasoning in the form of fuzzy rules which are constructed from a set of IF-THEN operations. Parameters which can be changed to get optimal fuzzy logic construction are fuzzy rules and the weight of every fuzzy rule output (usually between zero and one). The weight value determines the strength of the output of related fuzzy rule: when the weight is zero it means the output of the fuzzy rule is zero and when the output is one it means the output of fuzzy rule is in full scale. The fuzzy logic adaptable chemotactic step size can be formulated as:

where, C_af (i) is the fuzzy adaptable chemotactic step size for every bacterium, F(·) is a fuzzy logic mapping from cost function value as an input to step size as an output and |J (i)| is absolute of cost function of every bacterium. In the fuzzy logic structure, the universe of discourse of Gaussian membership functions of input and output is chosen adequately so that it is able to cover the range of both input and output. The general form of fuzzy rule for adaptation can be formulated as:

So that the output level of consequence part is B scaled by weight. Thus by using this strategy if |J (i)| is very big then C_af (i) is very big and if |J (i)| is very small then C_af (i) is very small or approaching zero so that bacteria would be able to approach the global optimum point without oscillation.

ABFA computation steps: The major computation steps of the proposed adaptive BFAs (ABFAs) are exactly the same as computation of SBFA (Passino, 2002). The difference in the ABFAs is that the chemotactic step size of bacteria in SBFA (C⁽ⁱ⁾) is replaced by adaptable chemotactic step size, i.e., C_al (i), C_aq (i), C_ae (i) and C_af (i) formulated in Eq. 1-4 for LABFA, QABFA, EABFA and FABFA, respectively. The detailed computation steps of ABFAs comprising bacterial population chemotaxis, swarming, reproduction, elimination and dispersal (initially, j = k = l = 0) in finding optimum value of nutrient media are given below (note that updates to the θⁱ automatically result in updates to P) (Passino, 2002):

This results in a step of size C_a (i) in the direction of the tumble for bacterium I. C_a (i) is equal to constant value for SBFA and equal to proposed adaptable chemotactic step size: C_al (i), C_aq (i),C_ae (i) and C_af (i) for LABFA, QABFA, EABFA and FABFA, respectively.

This results in a step of size C_a (i) in the direction of the tumble for bacterium i, C_a (i) is equal to constant value for SBFA and equal to the proposed adaptable chemotactic step size:C_al (i), C_aq (i),C_ae (i) and C_af (i) for LABFA, QABFA, EABFA and FABFA, respectively. Use this θⁱ (j+1, k, l) to compute the new J (i, j+1, k, l) as in sub step f above.

Reproduction: For the given k and l and for each I = 1, 2, 2=3,..., S, let:

Elimination-dispersal: For i = 1, 2, 3,...,S, with probability p_ed, eliminate and disperse each bacterium (this keeps the number of bacteria in the population constant).

RESULTS AND DISCUSSION

In order to evaluate and assess their performances, the proposed ABFAs are tested to find global optimum value of three classical well known benchmark test functions, commonly used in evaluation of new optimization algorithms. Thus the three benchmark test functions become nutrient media in which bacteria will find locations with highest nutrient value.

Test function 1: Rosenbrock function: The classical Rosenbrock function is formulated as:

In the tests the variables x_i-x_i-1 are in the range [-2.040, 2.048]. The 3D and 2D views of a two-variable Rosenbrock function are depicted in Fig. 2a-b.

It is noted that the global minimum of the Rosenbrock function lies inside a long-narrow-parabolic shaped valley. In this investigation, the Rosenbrock function is simulated for 2 dimensions. The global minimum point is J (x) equal to zero when x_i = x_i+1 equal to one. In these tests, all algorithms have used the parameters values:

The initial positions of bacteria were selected randomly across the nutrient media. Various chemotactic step size values were chosen by trial and error and then applied for SBFA and the best optimum nutrient value was achieved with a the step size equal to 0.0075. For LABFA, QABFA and EABFA, all parameters settings, i.e., c_max, b, d and g were chosen by trial and error. For FABFA, the fuzzy membership functions parameters, i.e., universe of discourse, m and σ were also chosen manually.

The numerical results shown in Table 1 demonstrate that, using adaptable chemotactic step size, all the four proposed algorithms outperformed the SBFA in reaching the optimum nutrient value and FABFA achieved the lowest nutrient value, i.e., 1.215x10^-1. Also, FABFA had the best mean and standard deviation of optimum value J. Because all BFAs use the same general parameters, the difference of nutrient value achieved is mainly caused by the chemotactic step size. The convergence plots in Fig. 3a show that all the four proposed algorithms were faster in convergence, since they could reach the optimum point using 9, 10, 7 and 26 steps for LABFA, QABFA, EABFA and FABFA, respectively than 54 steps of SBFA. Since the bacteria were initially placed randomly in the nutrient media, the nutrient value of each algorithm in the first step was different and the bacteria when running EABFA seemed to reach a location near the global minimum point while bacteria in QABFA fell far away from the global minimum. The best optimum nutrient value achieved by each algorithm is depicted in Fig. 3b.

Test Function 2: sphere function: The sphere function can be formulated as:

The characteristics of the sphere function is that it is continuous, convex and unimodal. In the tests carried out here the variables x_i are considered in the range [-5.12, 5.12]. The global minimum in this case is J (x) equal to zero which is reached when all variables x_i are equal to zero.

The 3D and 2D views of a two-variable sphere function are shown in Fig. 4. The plots show that the test function only has one valley with one global minimum point and there are no local minima. Thus, it is trivial for the algorithm (bacteria) to climb the downwards rather than to climb upwards of the valley. However, it is very difficult to find the global minimum value.

In the investigation, a five-dimension sphere function was used and all algorithms used the parameter values:

The initial positions of bacteria were selected randomly in the area of nutrient media. Various chemotactic step size values were chosen and applied in the simulation of SBFA and the best optimum nutrient value achieved was equal to 3.7057x10^-1 when the chemotactic step size was equal to 0.01. For LABFA, QABFA and EABFA, all parameter settings, i.e., c_max, b, d and g were chosen by trial and error. For FABFA, the fuzzy membership functions parameters, i.e., universe of discourse, m and σ were also chosen manually.

The results presented in Table 2 show that the four proposed algorithms outperformed the SBFA in finding the global optimum and the best nutrient value was achieved by LABFA, e.g., 1.3301x10^-1. Also, LABFA achieved the smallest mean optimum J (3.3956x10^-1), while EABFA has the best standard deviation value (1.7525x10^-1). The convergence plots presented in Fig. 5a show that all the four proposed algorithms were faster in convergence than SBFA with QABFA the fastest in convergence speed, only needed 95 steps to converge. The optimum J values by the algorithms achieved are depicted in Fig. 5b.

Test function 3: Rastrigin’s function 6: The general form of Rastrigin’s function 6 is given as:

This function only has one global minimum and many local minima (highly multimodal) with the locations of minima regularly distributed. The challenge with this test function is that since there are a lot of local minima, the algorithm is very risky to be trapped in one of local minima.

In the test, simulations were carried out with the variables x_i in the range [-5.12, 5.12]. The function has global minimum of J (x) equal to zero at x_i equal to zero. Figure 6 shows 3D and 2D plots of a two-variable Rastrigin’s function 6.

Here, the investigation was carried out for a 30-dimension of Rastrigin’s function. The general parameters of BFAs used in the simulation were:

The bacteria were initially placed randomly across the of nutrient media. Among various chemotactic step size values of SBFA used in the simulation, the best nutrient value, of 162.9286, was achieved when the chemotactic step size was equal to 0.025. All parameters and settings for LABFA, QABFA, EABFA and FABFA were chosen by trial and error.

The convergence plots in Fig. 7a show that all the five BFA algorithms had almost the same convergence speed and they converged in around 500 steps. The graphs after 500 steps were not exactly flat but were decreasing with only very small gradient. The most interesting point to note is that all the four proposed algorithms converged to lower nutrient value than SBFA. Numerical results presented in Table 3 show that all the four proposed algorithms were able to achieve better optimum values than that with SBFA with the best optimum J value achieved by FABFA (122.2388). FABFA also achieved the best mean J value (160.6510) while the best standard deviation of J was achieved by QABFA (17.7094). The optimum J values achieved by the algorithms are depicted in Fig. 7b.

CONCLUSIONS

Four novel approaches for adaptable chemotactic step size of BFA have been presented and discussed. The adaptation schemes based on three functions, namely linear, quadratic and exponential and on fuzzy logic have been investigated. It has been demonstrated with three commonly used benchmark test functions that BFA with all four proposed adaptation schemes can achieve better optimum, mean and standard deviation of test function J with faster convergence for all the benchmark functions. Since SBFA and all the four ABFAs used the same general parameters, the difference in their optimum J achieved and convergence speed must have resulted by the use of adaptable chemotactic step size. Also, because initial positions of bacteria were placed randomly in the nutrient media, although bacteria of SBFA fall in the location near the global minimum, by using bigger chemotactic step size, all four proposed algorithms have been able to converge faster than SBFA. Based on the results presented, all of the four proposed algorithms are potentially applicable to a widerange of applications efficiently in science and engineering.

ACKNOWLEDGMENT

Heru Supriyono acknowledges the financial support of Directorate General of Higher Education (Ditjen Dikti) of National Education Department of Republic of Indonesia and Muhammadiyah University of Surakarta (UMS), Indonesia.

REFERENCES