A hybrid meta-heuristic algorithm based on ABC and Firefly algorithms

محورهای موضوعی : Evolutionary Computing

azita yousefi ¹ (payame noor university,tehran,iran.)
bita amirshahi ² (payame noor university,tehran.iran)

تاریخ دریافت : 1394/07/17 تاریخ پذیرش : 1394/11/22 تاریخ انتشار : 1394/08/10

کلید واژه: Exploration, ABC algorithm, Firefly algorithm, Onlooker bee, Employed bee,

چکیده مقاله :

Abstract— In this paper we have tried to develop an altered version of the artificial bee colony algorithm which is inspired from and combined with the meta-heuristic algorithm of firefly. In this method, we have tried to change the main equation of searching within the original ABC algorithm. On this basis, a new combined equation was used for steps of employed bees and onlooker bees. For this purpose, we had to define several new parameters for improving the quality of the proposed method. In this regard, we have introduced two new parameters to the method. The new method has been simulated within the software of MATLAB and it has also been run according to objective functions of SPHERE, GRIEWANK and ACKLEY. All these functions are standard evaluation functions that are generally used for meta-heuristic algorithms. Results that were yielded by the proposed method were better than the results of the initial algorithm and especially by increasing the number of variables of the problem, this improvement becomes even more significant. We have successfully established a better balance between concepts of exploration and exploitation, especially with increasing the repetition cycles, we have successfully controlled the concept of utilization with random parameters. Tests have been ran more than 500 times.

منابع و مأخذ:

[1] D. Karaboga., and B. Basturk., "A powerful and Efficient Algorithm for Numerical Function Optimization: Artificial Bee Colony (ABC) Algorithm" Journal of Global optimization vol. 39, pp. 459-471, November 2007.
[2] J.J. Liang., A.K. Qin, “Comprehensive Learning Particle Swarm Optimizer for Global Optimization of Multimodal Functions”, Proceedings of IEEE Transaction of Evolutionary Computation, vol. 10, No. 3, June 2006.
[3]Liang J, Lee C,” A Modification Artificial Bee Colony Algorithm for Optimization Problems”, Mathematical Problems in Engineering Volume 2015 (2015).
[4] B. Akay and D. Karaboga, “A modified Artificial Bee Colony algorithm for real-parameter optimization,” Information Sciences, vol. 192, pp. 120–142, 2012.
[5] HAI-BIN DUAN, CHUN-FANG XU, and ZHI-HUI XING,” A hybrid artificial bee colony optimization and quantum evolutionary algorithm for continuous optimization problems”2010.
[6] Hadidi, Kazemzade.," Structural optimization using artificial bee colony algorithm” 2nd International Conference on Engineering Optimization September 6 - 9, (2010), Lisbon, Portugal.
[7] W. Gao , S. Liu “ A modified artificial bee colony algorithm”.Computer & Operation Research. 39 , 3 , 687-697 ,2012.
[8] D. Karaboga, “An idea based on honey bee swarm fornumerical optimization”. Technical Report-TRO6. Kayseri, Turkey: Erciyes.
[9] Jing, Hong,” Improved Artificial Bee Colony Algorithm and Application in Path Planning of Crowd Animation” International Journal of Control and Automation Vol.8, No.3 (2015), pp.53-66.
[10] T. Chen, XU,” Solving a timetabling problem with an artificial bee colony algorithm” World Transactions on Engineering and Technology Education Vol.13, No.3, 2015.
[11] R. Poli, J. Kennedy, T. Blackwell, Particle swarm optimization: An overview (Springer Science and Business Media, LLC (2007).
[12] Pei-Wei TSai, Jeng-Shyang Pan, Bin-Yih Liao, Shu-Chuan Chu, Enhanced Artificial Bee Colony Optimization , International Journal of Innovative Computing, Information and Control, Volume 5, Number 12, December (2009).
[13] Yang, X. S. , Nature-Inspired Metaheuristic Algorithms, Luniver Press(2008).
[14] R. Khaze, I. maleki, S. Hojjatkhah and A.Bagherinia, EVALUATION THE EFFICIENCY OF ARTIFICIAL BEE COLONY AND THE FIREFLY ALGORITHM IN SOLVING THE CONTINUOUS OPTIMIZATION PROBLEM, International Journal on Computational Sciences & Applications (IJCSA) Vol.3, No.4, August 2013.
[15] X-S. Yang," Firefly Algorithm, L´evy Flights and Global Optimization" arXiv:1003.1464v1 [math.OC] 7 Mar (2010).
[16] A Hashmi, Nishant Goel, Shruti Goel, Divya Gupta,” Firefly Algorithm for Unconstrained Optimization” IOSR Journal of Computer Engineering (IOSR-JCE) e-ISSN: 2278-0661, p- ISSN: 2278-8727Volume 11, Issue 1,(2013).

متن کامل:



5

Journal of Advances in Computer Engineering and Technology

¹ 

A hybrid meta-heuristic algorithm based on ABC and Firefly algorithms

 

Received (Day Month Year)

Revised (Day Month Year)

Accepted (Day Month Year)

Abstract— In this paper we have tried to develop an altered version of the artificial bee colony algorithm which is inspired from and combined with the meta-heuristic algorithm of firefly. In this method, we have tried to change the main equation of searching within the original ABC algorithm. On this basis, a new combined equation was used for steps of employed bees and onlooker bees. For this purpose, we had to define several new parameters for improving the quality of the proposed method. In this regard, we have introduced two new parameters to the method. The new method has been simulated within the software of MATLAB and it has also been run according to objective functions of SPHERE, GRIEWANK and ACKLEY. All these functions are standard evaluation functions that are generally used for meta-heuristic algorithms. Results that were yielded by the proposed method were better than the results of the initial algorithm and especially by increasing the number of variables of the problem, this improvement becomes even more significant. We have successfully established a better balance between concepts of exploration and exploitation, especially with increasing the repetition cycles, we have successfully controlled the concept of utilization with random parameters. Tests have been ran more than 500 times.

 

Index Terms— ABC algorithm, Firefly algorithm, Onlooker bee, Employed bee, Exploration, Exploitation.

 

I.       INTRODUCTION

I

  n recent years several different algorithms have been proposed for solving of complex problems[1]. These algorithms include Genetics, Ant-Colony, Particle-Swarm and etc. finally, in the year 2005 a new algorithm was introduced by Karaboga and Basturk namely as artificial Bee Colony. Since this algorithm was highly simple and easy to use, therefore it attracted many attentions. Also in our research, the convergence speed of this algorithm has been under the focus. In order to obtain a suitable and desirable performance, the ability for investigating different sections of the space is highly important and crucial for exploration of global optimal sources and utilization of the knowledge of previous methods for finding a new solution[2].

  The ABC algorithm is a population-based algorithm with the advantages of finding global optimization solution, being simple and flexible, and using very few control parameters. The ABC algorithm has been applied to many real-world applications, for example, function optimization, real-parameter optimization, digital filter design, clustering, and neural network training[3][4]. Or a novel hybrid Artificial Bee Colony and Quantum Evolutionary Algorithm was proposed for solving continuous optimization problem by Hai-Bin & Et al[5].

   For this reason, in the proposed hybrid algorithm, a new equation is used in local searching for improvement of the above two features which has led to improvement in convergence speed and production of a significant outcome compared to the standard algorithm. The rest of the content of this article are as follow: the second section is concerned with a review on meta-heuristic algorithms. The third section includes the proposed algorithm, the fourth section includes the results of simulation and the fifth section includes the overall conclusions.

 

 

 

II.       Introduction to meta-heuristic algorithms

   Many of evolutionary algorithms are inspirations from nature. These algorithms start from an initial population of random solutions and move towards finding a better answer in each cycle[6]. The algorithm of ABC is a popular algorithm and as a result, the following lines provide a brief description of steps of this algorithm:

 

1-Initialization of parameters

2-Initialize random solutions and evaluate solutions.

3- Employed bee step

4-Selection planning probability

5- Onlooker bee step

6-Scout bee step[1][6]

 

   In first step, the parameters that are required by the algorithm and the problem are quantified. In the second step, the preliminary answers are randomly produced and evaluated; this is the primary population of the colony. In the next step which is concerned with initiation of repetition of algorithm, each of worker bees randomly select a neighbor and afterwards, through the following equation the new location will be estimated[6].                                                                                                                (1)

   ɸ is random value in the range of (-1, 1).[7][8]. If the value of the equation is larger than the current location of the bee, then the new location is replaced or else no changes are imposed. After execution of this act by the entire worker bees, a possibility function is calculated according the location value of each bee and respectively, each of onlooker bees select a location as their primary position through a random selection method and afterwards, the calculation of the new location is repeated similar to worker bees. A third type of bees namely as scouts are defined for replacement of the new random source with existing sources which have a low quality[8]. 

   The initialization of honey bees’ population in the classical ABC algorithm is made randomly and cannot be changed during new iterations, which may affect the uniformity of the initial solution and the algorithm performance on convergence speed. To deal with this shortcoming, an initialization method of the ABC based on chaos sequence were proposed by JING & HONG[9]. Another example of application of ABC is an efficient arrangement of teaching resources with ABC algorithm , including the allocation of times and classrooms for university courses [10].

 so in last years were proposed many versions of ABC algorithm.

 

   The Firefly algorithm was introduced by Dr. Xin She yang at Cambridge University in 2007 which was inspired by the mating or flashing behavior of fireflies. Although the algorithm has many similarities with other swarm based algorithms such as Particle Swarm Optimization [11], Artificial Bee Colony Optimization [12] and Ant Colony Optimization [13], the Firefly algorithm has proved to be much simpler both in concept and implementation. Researchers have used FA to solve the non-linear continuous functions. The results of the tests show that FA is fast enough in convergence toward the optimized solution and finds the optimized answer in a very short time[14].

  Also in the meta-heuristic algorithm of firefly, first an initial random population is generated and then, according to the following attraction equation(2), the new coordinates are calculated between each two fireflies and by moving towards each other, they endeavor for optimization of answers[15].

                     (2)

 and  are attract factor in r=0 and Environment absorption coefficient Respectively.[15][16]

                                                                  (3)

 

In the next section, we have proposed a method which is a combination of the aforementioned two algorithms. This new combined method tries to improve the efficiency of the artificial Bee-Colony algorithm through imposing alterations on calculations.

III.       proposed hybrid algorithm

   In this proposed hybrid method, a new combined equation is used for searching for food sources at the steps of employed bees and onlooker bees. This new equation is inspired from the manner of movement of fireflies towards each other. In addition, by introducing two new parameters effective on efficiency of the algorithm and also by imposing some alterations, the equations which are used in the firefly method are applied in Artificial Bee-Colony algorithm.

The glittering of the firefly or in other words its attraction is dependent on the rate of lighting and the interval between light signals. According to this fact, the factor of attraction in bees is considered as the qualification of the explored answer by a certain bee. In spite of having a significantly smaller population of bees, the proposed method is able to obtain far more desirable answers than the standard algorithm in a suitable run time.

   In the altered search equation, each of the bees are subjected to pairwise comparisons with a percentage of the population of the colony and in case, the location value of bee ‘J’ was better than the location value of the bee ‘i’, the norm distance between two bees is calculated and ultimately, the new location for flying is calculated according to equation 4.

                                 (4)

If '  was better than   ,the bee of 'i' move to new calculated situation otherwise it remains in the previous position. This method is also used in the onlooker bees. ' or ‘0’ is a balancing parameter with "1" value. Attractiveness of bees is determined with equation '5'. The third equation in Eq. '4' is randomize with alpha parameters and 'e' is a random number with Uniform distribution between [-1,1].

 

                                                           (5)

 

   The effective parameters on convergence speed of this algorithm have also been defined as “Dg” and “L- UPG”. The first parameter is randomly defined in an interval in each repetition of the main loop of the program and further its value is determined and by multiplication of this value with the Alpha parameter, the alpha parameter for the next repetition is defined. The purpose of introducing this parameter is to control the alpha variable in each repetition. Also the second parameter leads to increase in the LIMIT parameter which increases the odds for finding optimized sources.

   The pseudo-code of the proposed algorithm is shown in the following.

 

                               Fig.1. pseudo code of proposed alg.

 

IV.       simulations and results

 

    Our hybrid algorithm has been tested on three objective functions that those are: Sphere, Griewank and Ackley. Tests have been ran for more than 500 times and the obtained results have also been compared with the outcomes of the primary artificail Bee-Colony algorithm in a similar situation. The number of variables of the problem were selected to be 5, 10, 20 and 30. Results are summarized in the following tables. It should be considered that the initial population of the proposed algorithm included 30 bees, while the standard algorithm’s initial population included 150 bees.the initial value of ' and '' are 1.

    In the tables values of “Best RES” , “Worst Res”, “Avg” and “Standard Deviation” means the best/worst/average achived values in running tests, and standard deviation is a measure of how spread out numbers are.

 

 

 

 

 

 

Table1. simulated results on Sphere func.

D		Result	Hybrid	ABC
5		Best Res.	1.12e-101	2.58e-48
		Worst Res.	2.34e-94	4.44e-42
		Avg.	4.12e-96	3.25e-44
		Standard deviation	2.72e-95	2.54e-42
10		Best Res	3.47e-99	1.57e-25
		Worst Res	3.71e-92	8.99e-24
		Avg	2.21e-93	6.39e-24
		Standard deviation	6.54e-93	4.21e-24
20		Best Res	1.25e-93	3.15e-12
		Worst Res	3.37e-39	6.25e-6
		Avg	2.22e-31	1.20e-6
		Standard deviation	1.78e-30	2.07e-6
30	Best Res.		1.46e-46	2.52
	Worst Res		7.66e-44	7.85
	Avg		1.53e-44	5.30
	Standard deviation		3.43e-44	3.11

 

 

 

 

 

 

Table2.  simulated results on Griewank func.

D		Result	Hybrid	ABC
5		Best Res	1.97e-2	7.52e-2
		Worst Res	1.89e-2	1.07e-1
		Avg.	1.65e-2	8.77e-2
		Standard deviation	1.14e-2	3.8e-1
10		Best Res	7.39e-2	3.88e-1
		Worst Res	3.54e-2	4.21e-1
		Avg	2.62e-2	3.76e-1
		Standard deviation	1.02e-2	1.10e-1
20		Best Res	1.11e-16	3.00e-1
		Worst Res	6.73e-2	6.30e-1
		Avg	5.36e-3	3.30e-1
		Standard deviation	5.72e-3	2.10e-1
30	Best Res		2.22e-16	1.50
	Worst Res		9.82e-3	3.45
	Avg		3.29e-3	2.34
	Standard deviation		4.93e-3	1.14

 

Table3.  simulated results on Ackley func.

D		Result	Hybrid	ABC
5		Best Res	7.99e-15	4.35e-14
		Worst Res	2.31e-14	8.88e-14
		Avg.	1.58e-14	1.26e-14
		Standard deviation	1.08e-14	2.07e-14
10		Best Res	7.39e-15	6.71e-10
		Worst Res	1.03e-13	1.32e-9
		Avg	1.09e-13	9.00e-10
		Standard deviation	1.69e-13	3.69e-10
20		Best Res	7.19e-14	1.36e-2
		Worst Res	2.24e-13	1.55e-2
		Avg	2.24e-13	1.56e-2
		Standard deviation	8.80e-14	1.76e-4
30	Best Res		1.74e-13	3.16
	Worst Res		1.67	3.70
	Avg		1.10	3.53
	Standard deviation		1.03	1.87e-1

 

V.       conclusion

According to previous studies , ABC and FA are efficient algorithms in different solving the continuous optimization problems.these algorithms use the quality parameters number the value of which could be settled easily.also the speed of convergence of ABC and FA is very high in probability of finding the global optimized answer.

    In comparison to the other Meta-Heuristic algorithms, ABC algorithm is a sample one to some extent because this algorithm just uses the three basic specifications of colony population, the maximum number of the repetitions and the abandonment factor. for this reason we decided study on hybrid new idea that inspired from two useful ABC and FA algorithms. so with Combination some section of firefly algorithm with ABC algorithm, we tried to achieve more efficiency method to solving continuous problem such as “Sphere” “Griewank” and “Ackley”.  Imposing alterations on the main search equation leads to increase in convergence speed and a better efficiency for the proposed algorithm. The population of the proposed method is also five times less than the standard algorithm, however the results yielded from this proposed algorithm are significantly better. Increasing the concept of exploitation in more cycles has had a positive effect on efficiency of the proposed algorithm.

1-       Obtained results in dimensions of 5 and 10, have a slight difference in Griewank function, however by increasing the number of variables of the problem to 20 and 30, better results are produced compared to the initial algorithm. for example in D=30, average value of our method is “3.29e-3” and average value of ABC is “2.34”.

2-       From the beginning of the work, significant differences were noticed in all dimensions between produced results of Sphere functions.

3-       Also in the third function, by increasing the number of variables, better results were obtained compared to the initial method. for example in D=20,average values are,”2.24e-13” and “1.56e-2”.that this difference is considerable.

   In general, the two concepts of exploration and exploitation are crucially important in meta-heuristic algorithms and we have also tried to appropriately incorporate these concepts in our proposed method. In this regard, in the initial steps, the concept of exploration is stressed out more than the other concept and also through the application of the new equation, the concept of exploitation was provided with a better focus while searching.

 

 

 

 

 

 

 

 

 

 

 

References

[1]  D. Karaboga., and B. Basturk., "A powerful and Efficient Algorithm for Numerical Function Optimization: Artificial Bee Colony (ABC) Algorithm" Journal of Global optimization vol. 39, pp. 459-471, November 2007.

[2] J.J. Liang., A.K. Qin, “Comprehensive Learning Particle Swarm Optimizer for Global Optimization of Multimodal Functions”, Proceedings of IEEE Transaction of Evolutionary Computation, vol. 10, No. 3, June 2006.

[3]Liang J, Lee C,” A Modification Artificial Bee Colony Algorithm for Optimization Problems”, Mathematical Problems in Engineering
Volume 2015 (2015).

[4] B. Akay and D. Karaboga, “A modified Artificial Bee Colony algorithm for real-parameter optimization,” Information Sciences, vol. 192, pp. 120–142, 2012.

[5] HAI-BIN DUAN, CHUN-FANG XU, and ZHI-HUI XING,” A hybrid artificial bee colony optimization and quantum evolutionary algorithm for continuous optimization problems”2010.

[6] Hadidi, Kazemzade.," Structural optimization using artificial bee colony algorithm” 2nd International Conference on Engineering Optimization September 6 - 9, (2010), Lisbon, Portugal.

 [7] W. Gao , S. Liu “ A modified artificial bee colony algorithm”.Computer & Operation Research. 39 , 3 , 687-697 ,2012.

 [8] D. Karaboga, “An idea based on honey bee swarm fornumerical optimization”. Technical Report-TRO6. Kayseri, Turkey: Erciyes.

[9] Jing, Hong,” Improved Artificial Bee Colony Algorithm and Application in Path Planning of Crowd Animation” International Journal of Control and Automation Vol.8, No.3 (2015), pp.53-66.

[10] T. Chen, XU,” Solving a timetabling problem with an artificial bee colony algorithm” World Transactions on Engineering and Technology Education Vol.13, No.3, 2015.

[11] R. Poli, J. Kennedy, T. Blackwell, Particle swarm optimization: An overview (Springer Science and Business Media, LLC (2007).

[12] Pei-Wei TSai, Jeng-Shyang Pan, Bin-Yih Liao, Shu-Chuan Chu, Enhanced Artificial Bee Colony Optimization , International Journal of Innovative Computing, Information and Control, Volume 5, Number 12, December (2009).

[13] Yang, X. S. , Nature-Inspired Metaheuristic Algorithms, Luniver Press(2008).

[14] R. Khaze, I. maleki, S. Hojjatkhah and A.Bagherinia, EVALUATION THE EFFICIENCY OF ARTIFICIAL BEE COLONY AND THE FIREFLY ALGORITHM IN SOLVING THE CONTINUOUS OPTIMIZATION PROBLEM, International Journal on Computational Sciences & Applications (IJCSA) Vol.3, No.4, August 2013.

[15] X-S. Yang," Firefly Algorithm, L´evy Flights and Global Optimization" arXiv:1003.1464v1 [math.OC] 7 Mar (2010).

[16] A Hashmi, Nishant Goel, Shruti Goel, Divya Gupta,” Firefly Algorithm for Unconstrained Optimization” IOSR Journal of Computer Engineering (IOSR-JCE) e-ISSN: 2278-0661, p- ISSN: 2278-8727Volume 11, Issue 1,(2013).

 

 

---

[1]