Evolutionary Bacterial Foraging Algorithm to solve constraint numerical optimization problems

Abstract

A version of Modi ed Bacterial Foraging Optimization Algorithm to solve Constraints Numerical Optimization is tested. The proposal uses mutation operator, skew mechanism and local search operator. To prove the e ectiveness of the mechanism and adaptations proposed, 24 well-known test problems are solved along set experiments. Performance measures are used for validating results obtained by the proposal and they are compared against state-of-the-art algorithms. The results show that the proposed algorithm is able to generate feasible solutions within of feasible region with few evaluations and improves them over the generations. Moreover, the results are competitive against the comparison algorithms based on performance measures found in the literature. Bacterial foraging optimization, mutation operator, swarm intelligence, Constrained optimization, premature convergence.

-

Recently nature-inspired meta-heuristic algorithms have gained popularity solving Constrained Numerical Optimization Problems (CNOPs). These algorithms were created in order to solve unconstrained optimization problems, but nevertheless the main feature of the real world problems are the constraints. In answer to this, many constraintshandling techniques have emerged, and have been added to nature-inspired algorithms in several proposals. In [ 20 ] the di erent techniques found in the specialized literature were grouped in twelve groups, which are based on Penalty functions, Decoders, Special Operators and Separation of objective function and constraints, Feasibility rules, Stochastic ranking, -constrained method, Novel penalty functions, Novel special operators, Multi-objective concepts, and Ensemble of constraint-handling techniques. The nature-inspired meta-heuristic algorithms have been divided in two classes 1) the Evolutionary Algorithms (EAs) that emulate the evolution of species and the survival of the ttest, and 2) the Swarm Intelligence Algorithms (SIAs) which have the capability of emulate the collaborative behavior of some simple species searching for food or shelter [ 8 ]. Some well-known EAs are Genetic Algorithms (GAs) [ 6 ], Evolution Strategies (ES) [ 27 ], Evolutionary Programming [ 9 ], Genetic Programming (GP) [ 14 ] and Di erential Evolution (DE) [ 25 ]. Some SIAs are the Particle Swarm Optimization (PSO) [ 13 ] and the Ant Colony Optimization (ACO) [ 5 ], these last algorithms have gained popularity for their great performance in solving CNOP. In 2002 other SIA was proposed by Passino [ 23 ] called Bacterial Foraging Optimization (BFOA), which emulates the behavior of bacteria E.Coli in the search of nutrients in its environment. This behavior is summarize in four process (1) chemotaxis (swim-tumble movements), (2) swarming (communication between bacteria), (3) reproduction (cloning of the best bacteria) and (4) elimination-dispersal (replacement of the worst bacteria). In BFOA each bacterium tries to maximize its obtained energy per each unit of time spent on the foraging process while avoiding noxious substances. BFOA was used initially to solve unconstrained optimization problems, however, more recently proposals add some constraints-handling technique to solve CNOPs, where the penalty function is the most used [ 10 ].

Further investigations have address the fact that BFOA is particularly sensitive to the step size parameter, a recent study of the step size was reported in [ 11 ], where di erent approaches were compared and the dynamic control mechanism was found to be slightly superior to static, random, and adaptive versions. In [ 21 ] BFOA was adapted in the proposal called Modi ed Bacterial Foraging Optimization Algorithm (MBFOA) to solve CNOPs. The proposal inherits the four processes of BFOA, however, them are divided as independent processes that interact sequentially, therefore the parameters that determine the number of swim, number of tumble and the swarming loop were eliminated. Moreover, The feasible rules, proposed by Deb [ 3 ], are used as a constrainthandling technique. Unlike of BFOA where the step size is static, in MBFOA the step size (used in the swim movements) was adapted according the boundary of the decision variables.

The aim of this paper is tested a version of MBFOA which used mechanisms based on evolutionary operators, Skew mechanism for the initial swarm and Local Search Operator called Evolutionary MBFOA (EMBFOA) in 24 well-known test problems. The results obtained will be compared against what is currently the most successful and well-known algorithm of the state of the art: Memetic-SAMSDE [ 7 ]. We evaluate our results with performance measures found in the literature. An advantage of the new proposal is that it uses the same parameter values for all test problems. It is the rst time that the mutation is used as swim operator.

The document is organized as follows: Section 2 brie y describes the EMBFOA. Section 3 presents and compares the results obtained by proposal and another state-of-the-art algorithms. Finally, Section 4 presents the general conclusions and future works. 2

Evolutionary Modi ed Bacterial Foraging Algorithm Evolutionary Modi ed Bacterial Foraging Algorithm is an algorithm derived from MBFOA in order to improve the performance in constrained spaces. Four modi cations are made: (1) a skew mechanism for the initial swarm of bacteria is applied, (2) two swim operators are applied in the chemotaxis process to improve the exploration and exploitation of the bacteria; one of them uses a random step size easy to implement and other one use mutation, (3) the elimination-dispersal process is adapted to preserve the diversity of the swarm, and (4) a local search operator is added.

In BFOA, MBFOA and EMBFOA a bacterium i represents a potential solution to the CNOP (i.e., a n-dimensional real-value vector identi ed as x), and it is de ned as i(j,G), where j is its chemotaxis loop index and G is the current cycle of the algorithm. Skew mechanism for the initial swarm: The initial swarm of Sb bacteria is formed from three groups. The rst group is formed of bacteria randomly skewed towards the lower limit of the decision variables. The second group is formed of bacteria randomly skewed towards the upper limit of the decision variables. Finally, a group of randomly located bacteria without skew, as in the original MBFOA, is used. The formulas to set the limits for the rst and second group per variable are presented in Equations 1 and 2.

[Li; Li + ((Ui

Li)=ss)] [Ui ((Ui

Li)=ss); Ui] (1) (2) where ss is the skew size (ss > 1), for which large values increase the skew e ect and small values decrease the skew e ect. The aim of this skew in the initial swarm, combined with the two swim operators and the random stepsize control, is to avoid the swarm of bacteria converging prematurely (behavior observed in the original MBFOA caused by its swarming , reproduction process and the xed stepsize), and improve the exploration and exploitation of the search space in the initial phase of the search. Chemotaxis: In this process two swims are interleaved, in each cycle only one of the exploitation swim or exploration swim is performance. The process starts with the exploitation swim (classical swim). However, a bacterium will not necessarily interleave exploration and exploitation swims, because if the new position of a given swim, i(j + 1; G) has a better tness (based on the feasibility rules) than the original position i(j; G), another similar swim in the same direction will be carried out in the next cycle. Otherwise, a new tumble for the other swim will be computed. The process stops after Nc attempts. The exploration swim uses the mutation between bacteria and is computed as indicated in Equation 3: i(j + 1; G) = i(j; G) + ( 1)( 1r(j; G) 2r(j; G)) where 1r(j; G) and 2r(j; G) are two di erent randomly selected bacteria from the swarm. is an user-de ned parameter used in the swarming that de nes the closeness of the new position of a bacterium with respect to the position of the best bacterium, in this operator, 1 is a positive control parameter for scaling the di erent vectors into (0,1], i.e., it scales the area where a bacterium can move.

The exploitation swim is computed as indicated in Equation 4:

i(j + 1; G) = i(j; G) + C(i; G) (i) where (i) is calculated with the original BFOA Equation 5 and C(i; G) is the random stepsize of each bacterium update in each generation with the Equation 6. (i) =

(i) p T (i) (i) C(i; G) = R (i) where (i) is a uniformly distributed random vector of size n with elements within the [ -1,1 ]. where (i) is a randomly generated vector of size n with elements within of the range of the each decision variable: [U pperk; Lowerk], k = 1; ::::n, and R is an user-de ned parameter to scale the stepsize, this value should be close to zero, eg. 5.00E-04. The initial C(i; 0) is generated using (i). This random stepsize allows that the bacteria can move in di erent direction into of the search space and avoids the premature convergence as is suggest in [ 12 ].

It is important to remark that the exploration swim (Equation 3) performs larger (3) (4) (5) (6) movements due the mutation operator which used bacteria randomly. On the other hand, the exploitation swim (Equation 4) generates small movements using the random stepsize in the search process.

Swarming: In the half cycle of the chemotaxis process the swarming operator is applied with the Equation 7, where is an user-de ned parameter positive into (1, 2]. However, in this proposal if a solution violates the boundary of decision variables, unlike of MBFOA, a new solution xi is generated randomly which is bounded by lower and upper limits Li xi Ui.

i(j + 1; G) = i(j; G) + ( B(G) i(j; G)) (7) where i(j + 1; G) is the new position of bacterium i, i(j; G) is the current position of bacterium i, B(G) is the current position of the best bacterium in the swarm so far at generation G, and de nes the closeness of the new position of bacterium i with respect to the position of the best bacterium B(G). The attractor movement applies twice in a chemotaxis loop, while in the remaining steps the tumble-swim movement is carried out.

Reproduction: To reduce premature convergence due to bacteria duplication, The reproduction takes place only at certain cycles of the algorithm (de ned by the RepCycle parameter) deleting the Sr worst bacteria and duplicating the remaining Sb-Sr. Elimination-dispersal: To preserver and increase the diversity of swarm, the eliminationdispersal process takes place at certain cycles of the search process de ned by the EliCycle user-de ned parameter. The number of bacteria to eliminate-dispersal is dened by the user in the parameter Se. In this proposal, the diversity of swarm is necessary because the mutation is e ective when there is already some level of diversity in the existing swam. Moreover, the generation of new bacteria avoids the premature convergence.

Local Search Operator: Sequential Quadratic Programming (SQP) [ 24 ] is incorporated into EMBFOA as a local search operator in order to help the algorithm to generate better results and based on the improved behavior observed by memetic algorithms [ 22 ]. SQP is also used once in the middle of the search process. However, the user can de ne the frequency of usage of the local search operator by de ning the parameter local search frequency LSG. The structure of EMBFOA is showed in the Figure 1.

Results and analysis In this section are presented and compared the results obtained by EMBFOA in the CEC2006 benchmark against MBFOA and Memetic-SAMSDE which is one the best state-of-the-art algorithms for solving this benchmark. EMBFOA was coded in Matlab R2009b, and run on a PC with a 3.5 Core 2 Duo Processor, 4GB RAM, and Windows 7.

The 95%-con dence Wilcoxon Signed Rank Test (WSRT) [ 2 ] suggested for natureinspired algorithms comparison in [ 4 ] is used as the statistical test to validate the di erences in the samples of runs. The scores are based on the best tness value of each algorithm in each test problem.

The input parameter values used by MBFOA are: Sb=40, Nc=20, Sr=2, R=1.20E-03 and =1.5. For EMBFOA the parameters are: Sb= 40, Nc= 20, Sr= 2, R= 1.20E03, = 1.5, RepCycle= 100, EliCycle= 50, LSG= 1 and (GM AX=2) generations, M axLS= 5,000 Fes and ss= 8; they were ne-tuned by the iRace tool [ 16 ]. The iRace obtained ve possible values for each parameter and the average of the ve values was used. In this case, the only xed parameter were GM AX according to the termination condition of the maximum number of evaluations (Max FEs) of CEC2006 benchmark, and the maximum number of evaluations for the local search operator M axLS which is 5; 000 evaluations. 24 well-known CNOPs found in [ 15 ] were used in the experiments. Max Fes allowed for each one of the 24 test problems was 240,000 evaluations. The tolerance for equality constraints was set to " = 1E 04, this value is proposed in the specialized literature of nature-inspired algorithms to solve CNOPs [ 1, 19, 20 ].

In this experiment the performance of EMBFOA is compared against MBFOA and some EAs, such as Mememtic Self-Adaptive Multi-Strategy Di erential Evolution (MemeticSAMSDE) which is currently one of the best state-of-the-art algorithm for solving the set of test problems used in this paper. This algorithm also uses SQP as local search. Unlike the EMBFOA that uses SPQ only twice, in Memetic-SAMSDE is used each 50 generations. The Adaptive Penalty Formulation with GA (APF-GA) [ 28 ], the Modi ed Di erential Evolution (MDE) [ 18 ], the Adaptive Tradeo Model with evolution strategy (ATMES) [ 29 ], the Multimembered evolution strategy (SMES) [ 17 ], and the Stochastic ranking with evolution strategy (SR+ES) [ 26 ]. Even when ATMES, SMES and SR solved solely the rst 13 test problems a computation against them is shown. The number of evaluations computed by APF-GA and MDE was 500,000. SR+ES used 350,000 evaluations while for Memetic-SAMSDE, EMBFOA, ATMES and SMES used 240,000 evaluations. The number of independent runs used by EMBFOA, MemeticSAMSDE, ATMES, SMES and SR+ES was 30, and APF-GA and MDE used 25 independent runs. In the Table 1 the results of all algorithms for the 24 test problems are present whit the best solutions of each test problem is highlighted in bold. From the results obtained by each algorithm, the Wilcoxon Sign-Rank test suggest that there is signi cant di erence between EMBFOA and MBFOA and there is no signi cant difference between EMBFOA, Memetic-SAMSDE and MDE. However the last algorithm uses 500,000 evaluations which are the double evaluation used by EMBFOA. There is a signi cant di erence in favor of EMBFOA when it is compared against APF-GA, ATMES, SME and SR+ES. Moreover APF-GA and SR+ES used more number of evaluations than EMBFOA.

In this experiment the performance of EMBFOA was compared against ve state-ofthe-art nature-inspired algorithms used to solve CNOPs successfully, with the results this is the rst attempt to design a BFOA-based algorithm that uses mutation as swim operator. As future work, EMBFOA will be tested in more CNOPs and a study on the impact of the population size and the way it is generated over the performance of the algorithm, will be performed.

References

1. Carlos A. Coello Coello . Theoretical and Numerical Constraint Handling Techniques used with Evolutionary Algorithms: A Survey of the State of the Art . Computer Methods in Applied Mechanics and Engineering , 191 ( 11 -12): 1245 { 1287 , January 2002 .

2. G.W. Corde and D.I. Foreman . Nonparametric Statistics for Non-Statisticians: A Step-by-Step Approach . John Wiley, Hoboken, NJ, 2009 .

3. Kalyanmoy Deb . An E cient Constraint Handling Method for Genetic Algorithms . Computer Methods in Applied Mechanics and Engineering , 186 ( 2 /4): 311 { 338 , 2000 .

4. J. Derrac , S. Garc a , D. Molina, and F. Herrera . A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms . Swarm and Evolutionary Computation , 1 ( 1 ):3{ 18 , 2011 .

5. M. Dorigo , V. Maniezzo , and A. Colorni . The Ant System: Optimization by a Colony of Cooperating Agents . IEEE Transactions of Systems , Man and Cybernetics-Part B , 26 ( 1 ): 29 { 41 , 1996 .

6. A.E. Eiben and J. E. Smith . Introduction to Evolutionary Computing. Natural Computing Series . Springer Verlag, 2003 .

7. Saber M. Elsayed , Ruhul A. Sarker , and Daryl L. Essam . On an evolutionary approach for constrained optimization problem solving . Applied soft computing , 12 ( 0 ): 3208 { 3227 , 2012 .

8. Andries P. Engelbrecht . Computational Intelligence. An Introduction. John Wiley & Sons, 2nd edition , 2007 .

9. Lawrence J. Fogel . Intelligence Through Simulated Evolution. Forty years of Evolutionary Programming . John Wiley & Sons, New York, 1999 .

10. Betania Hernandez-Ocan~ a, Efren Mezura-Montes, and Pilar Pozos-Parra. A review of the bacterial foraging algorithm in constrained numerical optimization . In Proccedings of the Congress on Evolutionary Computation (CEC'2013) , pages 2695 { 2702 . IEEE, 2013 .

11. Betania Hernandez-Ocan~ a, Pilar Pozos-Parra, and Efren Mezura-Montes. Stepsize control on the modi ed bacterial foraging algorithm for constrained numerical optimization . In Proceedings of the 2014 Conference on Genetic and Evolutionary Computation , GECCO '14 , pages 25 { 32 , New York, NY, USA, 2014 . ACM.

12. Alireza Kasaiezadeh , Amir Khajepour, and Steven L. Waslander . Spiral bacterial foraging optimization method: Algorithm, evaluation and convergence analysis . Engineering Optimization , 46 ( 4 ): 439 { 464 , 2014 .

13. James Kennedy and Russell C. Eberhart . Swarm Intelligence. Morgan Kaufmann, UK, 2001 .

14. John R. Koza , Martin A. Keane , Matthew J. Streeter , William Mydlowec , Jessen Yu , and Guido Lanza . Genetic Programming IV: Routine Human-Competitive Machine Intelligence . Kluwer Academic Publishers, Hingham, MA, USA, 2003 .

15. J.J. Liang , Thomas Philip Runarsson, Efrn Mezura-Montes, Maurice Clerc, P.N. Suganthan , Carlos A. Coello Coello , and K. Deb . Problem de nitions and evaluation criteria for the cec 2006 special session on constrained real-parameter optimization . Technical report , School of EEE Nanyang Technological University, Singapore, September 2006 .

16. Manuel Lopez-Iban~ez, Jeremie Dubois-Lacoste, Thomas Sttzle, and Mauro Birattari . The irace package, iterated race for automatic algorithm con guration . Technical Report TR/IRIDIA/2011-004 , IRIDIA, Universite Libre de Bruxelles, Belgium, 2011 .

17. E. Mezura-Montes and Carlos A. Coello Coello. A simple multimembered evolution strategy to solve constrained optimization problems . Evolutionary Computation, IEEE Transactions on, 9 ( 1 ):1{ 17 , Feb 2005 .

18. E. Mezura-Montes , J. Velazquez-Reyes , and C.A. Coello Coello . Modi ed di erential evolution for constrained optimization . In Evolutionary Computation , 2006 . CEC 2006 . IEEE Congress on , pages 25 { 32 , 2006 .

19. Efren Mezura-Montes, editor. Constraint-Handling in Evolutionary Optimization , volume 198 of Studies in Computational Intelligence . Springer-Verlag, 2009 .

20. Efren Mezura-Montes and Carlos A. Coello Coello. Constraint-handling in natureinspired numerical optimization: Past, present and future . Swarm and Evolutionary Computation , 1 ( 4 ): 173 { 194 , 2011 .

21. Efren Mezura-Montes and Betania Hernandez-Ocan~a. Modi ed bacterial foraging optimization for engineering design . In Cihan H. Dagli and et al., editors, Proceedings of the Arti cial Neural Networks in Enginnering Conference (ANNIE'2009) , volume 19 of Intelligent Engineering Systems Through Arti cial Neural Networks , pages 357 { 364 , St . Louis, MO , USA, November 2009 . ASME Press.

22. Ferrante Neri and Carlos Cotta . Memetic algorithms and memetic computing optimization: A literature review . Swarm and Evolutionary Computation , 2 :1{ 14 , 2012 .

23. Kevin M. Passino . Biomimicry of bacterial foraging for distributed optimization and control . IEEE Control Systems Magazine , 22 ( 3 ): 52 { 67 , 2002 .

24. M. J. D. Powell . Algorithms for Nonlinear Constraints that use Lagrangian Functions . Mathematical Programming , 14 : 224 { 248 , 1978 .

25. K. Price , R. Storn , and J. Lampinen . Di erential Evolution: A Practical Approach to Global Optimization . Natural Computing Series . Springer-Verlag, 2005 .

26. T.P. Runarsson and Xin Yao . Stochastic ranking for constrained evolutionary optimization . Evolutionary Computation , IEEE Transactions on, 4 ( 3 ): 284 { 294 , Sep 2000 .

27. Hans-Paul Schwefel , editor. Evolution and Optimization Seeking. Wiley, New York, 1995 .

28. B. Tessema and G.G. Yen. An adaptive penalty formulation for constrained evolutionary optimization . Systems, Man and Cybernetics , Part A : Systems and Humans , IEEE Transactions on, 39 ( 3 ): 565 { 578 , May 2009 .

29. Yong Wang , Zixing Cai, Yuren Zhou , and Wei Zeng . An adaptive tradeo model for constrained evolutionary optimization . Evolutionary Computation , IEEE Transactions on, 12 ( 1 ): 80 { 92 , Feb 2008 .