Quantum Artificial Bee Colony Algorithm for Numerical Function Optimization

International Journal of Computer Applications (0975 – 8887) Volume 93 – No 9, May 2014 Quantum Artificial Bee Colony Algorithm for Numerical Function Optimization Nizar Hadi Abbas, Ph.D Haitham Saadoon Aftan Electrical Engineering Electrical Engineering Department Department College of Engineering College of Engineering University of Baghdad, Iraq. University of Baghdad, Iraq. ABSTRACT This paper focuses on the ABC algorithm which is a The Artificial Bee Colony (ABC) algorithm is a swarm population-based meta-heuristic approach originally proposed intelligence based algorithm, which simulate the foraging by D. Karaboga [4]. It simulates foraging behavior of honey behavior of honey bee colonies. It has been widely applied to bee swarm. ABC has been used to solve many optimization solve the real-world problem. However, ABC has good problems. Several studies have been made to compare of ABC exploration but poor exploitation abilities, and its convergence with the performance of other algorithms such as Genetic speed is also an issue in some cases. In order to overcome Algorithm (GA), ACO and Differential Evolution (DE) [5]. these issues, this paper presents a new metaheuristic algorithm Several unimodal/multimodal benchmarks functions have called Quantum Artificial Bee Colony (QABC) algorithm for been used to evaluate the performance of ABC. These studies global optimization problems inspired by quantum physics have been revealed that ABC algorithm can achieve better concepts. Simulations are conducted on a suite of results and it is more efficient than other algorithms. unimodal/multimodal continuous benchmark functions. The However, the main issue in ABC algorithm is that it is good at results demonstrate the good performance of the QABC exploration but poor at exploitation. The convergence is also algorithm in solving complex numerical optimization an issue in some cases. The exploration is defined as the problems when compared with other popular algorithms. ability to independently seeking for the global optimum, while the exploitation is defined as the ability to apply the existing General Terms knowledge to look for better solutions [1]. Bio-inspired algorithm, Numerical optimization, meta- In order to find the optimal tradeoff between exploration and heuristics. exploitation, several modified version of ABC have been proposed in the literature, such as gbest guided ABC (GABC) Keywords [6] and I-ABC [7]. Inspired by PSO, GABC takes advantages Artificial bee colony algorithm, Swarm intelligence, Quantum of the information collected from the global best (gbest) physics, Benchmark functions. solution to improve the exploitation capability of the standard ABC algorithm. L. Guoqiang et al. [7], proposed an improved 1. INTRODUCTION ABC algorithm called I-ABC. In I-ABC, the inertial weight In the last two decades, there has been an increasing interest and acceleration coefficients were introduced to modify the in the field of bio-inspired computation specially swarm based search process. In addition to the further balancing of search algorithms. Some of these algorithms gained much popularity processes, the modification forms of the employed bees and because of their versatility, flexibility and powerful adaptive the onlooker ones are different in the second acceleration search technique and efficient in solving practical nonlinear coefficient. problems. There are two noteworthy features of swarm based algorithms are decentralized control and self-organization that In this paper, a new modified version of the ABC algorithm lead to a distinguished behavior [1]. This behavior is a called Quantum Artificial Bee Colony (QABC) Algorithm is property that appears through interactions among system proposed. QABC exploits the quantum physics concepts to component, and it is impossible to be achieved by any of the construct a new update equation which balances between components of the system acting alone. Several possible exploration and exploitation capabilities to achieve better approaches of bio-inspired algorithms have been reported in results. This algorithm is applied to several benchmark literature, and some popular approaches are Particle Swarm functions to compare its performance with other algorithms. Optimization (PSO) [2], Ant Colony Optimization (ACO) [3] and Artificial Bee Colony (ABC) [4] strategies. All these The remainder of this paper is organized as follows: section 2 techniques have shown their robustness and if properly describes the standard ABC algorithm; section 3 describes the developed and tuned, have also shown relatively fast behavior of the bee in the proposed algorithm; Section 4 convergence. describes the proposed QABC algorithm, and the simulation results are shown in section 5. Finally, section 6 concludes the Despite the popularity and success of bio-inspired computing, paper. there remain many challenging issues such as gaps between theory and practice, classifications, parameter tuning, lack of truly large-scale real-world applications and the selection of 2. Standard ABC Algorithm the appropriate algorithm for specific problem [1]. The artificial bee colony algorithm is a robust, straightforward, population based and a stochastic optimization algorithm. ABC algorithm was proposed by D. 28  International Journal of Computer Applications (0975 – 8887) Volume 93 – No 9, May 2014 Karaboga [4]. In the ABC algorithm, the colony of artificial predetermined number of cycles, the food source should be bees is classified into three groups: employed bees, onlookers abandoned. The predetermined number of cycles is an and scouts. The employed bees constitute half of the important control parameter in ABC algorithm, which is population, and the onlookers constitute the remaining half. called “limit” for abandonment. Suppose that the abandoned The position of a food source corresponds to a feasible source is and , then the scout finds a new solution in search space of the optimization problem, and the food source to be replaced with . This operation can be quality of each food source is represented by its nectar defined as [8]: amount. The number of the food sources equals to the number of employed bees. When a food source has been abandoned by bees, the abandoned employed bee would become a scout [4]. After each new source position produced, it can be evaluated by the artificial bee, and its fitness is compared with In the beginning, the ABC algorithm produces a randomly that of its previous one. If the new food source equals or is distributed initial population of SN food source positions, better than the old one, it would be replaced with the previous where SN is the size of food sources. Every solution one in its memory. Otherwise, the old one is retained in its is a D-dimensional vector, where D denotes memory. In other words, a greedy selection mechanism is the number of decision variables. In the subsequent steps, the employed as the selection operation between the old and the population of solutions is subject to repeated cycles of the new one. The main steps of the ABC algorithm are outlined in search phases of employed bees, onlookers and scouts. An Algorithm 1[8]. employed bee could produce a modification on the solution in its memory depending on local information and test its fitness value of the new source. If the fitness value of the new one is Algorithm 1: Artificial Bee Colony Algorithm better than that of the previous one, the employed bee would memorize the new position and forget the previous one. Initialize food sources; Otherwise, it keeps the position of the previous one in its memory. When all employed bees complete the search Repeat while Termination criteria is not meet process, they will share the information about nectar amounts Step 1: Employed bee phase for computing new food and positions of food sources with onlookers. An onlooker evaluates the nectar information which is owned by all sources. employed bees, and then chooses a food source with a Step 2: Onlooker bees phase for updating the location probability which is related to the nectar amount. As in the case of the employed bee, the onlooker can produce a of food sources based on their amount of nectar. modification on the position in its memory and check the nectar amount of the candidate source. If the nectar amount is Step 3: Scout bee phase for searching about new food more than that of the previous one, the bee would memorize sources in place of rejected food sources. the new position and forgets the previous one. Step 4: Memorize the best food source identified so far. An onlooker chooses a food source completely depending on the probability value associated with the food source , End of while which is calculated by the following formula [8]: Output: The best solution obtained so far. 3. Bees in Quantum Delta Potential Field Where denotes the fitness value of the ith solution which In the concepts of Newtonian mechanics, the particle is is proportional to the nectar amount of the food source in the described by its velocity vector v and position vector x. Where ith position. For the sake of producing a new food position v and x determine the trajectory of the particle. The particle from the previous one, the ABC could adopt the following moves along a predictable trajectory in Newtonian mechanics, modification form [8]: but this is not the case in quantum mechanics. In quantum physics, the term trajectory is meaningless, because x and v of a particle cannot be determined simultaneously according to Where and are randomly Heisenberg's uncertainty principle. Hence, if individual generated index, and k are different from j. is random particles in an ABC system have quantum behavior, the ABC variable in the interval [-1,1]. It can control to produce a new algorithm is bound to work in a different manner. In this food source around and represent the comparison of two paper, motivated by the work done in the philosophy of PSO food positions visually by a bee. As can be seen from Eq. (2), with delta potential of QPSO proposed in [9] and [10], a new as the difference between the parameter and decreases, modified ABC approach with bees having quantum behavior the perturbation on the position is also decreased. Thus, is proposed. when the search approaches to the optimum solution in the In a quantum model of ABC, each bee represents a particle search space, the step size is adaptively reduced. If a which has a state depicted by wave function , instead parameter value produced by the operation exceeds its of position and velocity. The dynamic behavior of the bee is predetermined limit, it is set to its limit value. different from that of the bee in standard ABC algorithm; in that the accurate values of x and v cannot be calculated The food source which is abandoned by the bees would be simultaneously. The probability density function of bee replaced with a new food source found by scouts. In ABC position is . The update equation can be found as algorithm, the foraging behavior is simulated by randomly follows: producing a position and replacing the abandoned one with a new one. If a position cannot be improved further through a 29  International Journal of Computer Applications (0975 – 8887) Volume 93 – No 9, May 2014 In this algorithm, the delta potential is used and its equation is To change the variance of the distribution so that the as follows: algorithm can achieve the optimization task effectively let: (4) ci= (17) Where is a positive value and is Dirac delta function. is multiplied by in element wise manner The wave function of a particle in delta potential is Substituting ci in Eq. (14) yields: represented by the following formula [11]: (5) (18) Where is the reduced Plank constant, is the mass of the where k is uniform random variable between 0 and 1. particle and E is the energy of the particle. Motivated by the Eberhart’s PSO convergence analysis, Let 4. Quantum Artificial Bee Colony (QABC) the center of the potential be around position defined by It can be seen from Eq. (18) that the high best fitness [12]: motivates exploitation since the variance of the distribution becomes smaller while the variance increases as the term (6) and this motivates the exploration. Further, a new parameter which controls how many Where is the ith bee best position in the jth dimension of dimension to be changed for each bee in each iteration, called the hyperspace and is value of jth dimension of the bees’ modification rate (MR). Eq. (18) can be used in employed global best position. are random variables in the phase and in onlooker phase or in the onlooker phase only. range (0,1]. The procedure for implementing the QABC is given by the following steps, Then Eq. (4) becomes, Step 1: The user must choose the key parameters that control (7) the QABC, namely population size of particles, boundary constraints of optimization variables, modification rate (MR), Where z=x-p tuning vector ( ) and the stop criterion (tmax). Replace x with z in Eq. (5) then: Step 2: Initialize a population (array) of food sources with random positions in the n-dimensional problem space using a (8) uniform probability distribution function. Hence, the probability of finding particle Q(z) in any position Step 3: Evaluate the fitness value of each food source. can be obtained: Step 4: Update the positions of the employed bees using Eq. Since Q (z) = , (9) (2) then evaluate their fitness again. Step 5: Using greedy selection to choose the best position Q(z)= (10) between the current and the updated position. To obtain the position value from this distribution, Smirnov Step 6: Distribute the onlookers on the food sources according transform is used to their fitness using wheel selection rule. The cumulative distribution function F(z) is: Step 7: Generate a new position for each onlooker using Eq. (18) then evaluate the fitness. F(z)= (11) Step 8: Apply the greedy selection to choose the best position between the current food source position and the updated F(z)= (12) position found by the onlookers. Let u = rand (0, 1), then Substitute Eq. (7) into Eq. (12) Step 9: In the scout phase, replace the abandoned food source yields: by randomly generated position. v =P (13) Step 10: Repeat 4-9 until the stopping condition is satisfied. let = then Eq. (13) becomes: 5. Simulation Results and Discussions vi =Pi (14) 5.1 Benchmark Functions Let equals to the mean of best SN/2 positions: A function is multimodal if it has two or more local optima. A function of variables is separable if it can be rewritten as a (15) sum of functions of just one variable [8]. Nonseparable functions are difficult and the problem is even more difficult Let (16) if the function is also multimodal. The algorithm must be able to avoid the regions around local minima in order to cover all Where is vector of tuning factor in decreasing order. and converge to the global minima. The most complex case appears when the local optima are randomly distributed in the Where: search space. The dimensionality of the search space is another important factor in the complexity of the problem. In general, the complexity increases with the dimensionality. 30  International Journal of Computer Applications (0975 – 8887) Volume 93 – No 9, May 2014 Some of the optimization benchmark functions were used to The function has many local maxima and local minima. validate and compare the performance of the QABC Because the location of the global minimum value near the algorithm. The used functions have diverse properties; boundary and the existence of the second best minimum therefore, they are useful to test the proposed QABC value far from the global minimum, this problem is algorithm without biasing. The functions are as follows: difficult for algorithm with poor exploration mechanism. 5.1.1 Griewank function 5.1.6 Colville Function It is a multimodal, continuous, differentiable and non- This function is multimodal continuous and differentiable separable function. Its global minimum value is 0 and located whose global optimal value is 0 and located t at .The range of the decision variables is [- . The range of the decision variables is [ 10, 10] 600,600]. Griewank function is highly unimodal when the [13]. dimensionality is less than 30 [12]. (19) 5.1.2 Rastrigin function It is a multimodal, continuous, differentiable and separable (24) function. The global minimum of the function is 0 and located at .the initialization range of the decision 5.1.7 Zakharov Function variables is [-15, 15] [12]. It is multimodal, non-separable continuous and differentiable function. The global minimum of the function is 0 and located at .the initialization range of the decision The cosine term generates many local minima. The minima variables is [-5, 10] [13]. are uniformly distributed. 5.1.3 Rosenbrock function It is a unimodal, continuous, differentiable and non-separable function [12]. 5.1.8 Powell Singular Function It is unimodal, continuous, differentiable and non-separable function whose global optimal value is 0 and located t Subject to . . The range of the decision variables is The global minimum of Rosenbrock function is located inside [−4, 5] [13]. a narrow and long valley that has parabolic shape. Because it is hard to obtain the global minimum value, the variables are highly dependent, and the gradients usually do not direct towards global minimum, this function is used often to test the The mean function and the standard deviation values of the performance of the optimization algorithms. minimum solutions found by the QABC algorithm in different dimensions have been computed. The mean and the standard 5.1.4 Ackley function deviations of the function values obtained by the QABC are It is a multimodal, continuous, differentiable and non- compared to the results obtained by other algorithms in [7] separable function whose global optimal value is 0 and and [12] as shown in Table 1. located at . The range of the decision variables is [−32.768, 32.768] [12]. 5.2 Simulation Parameters The following simulation parameters are adopted for QABC: The exponential terms produces many local minima.  The size of colony (SN) = 6. Algorithms that depend on the gradient on their work can  Number of Employed bees = Number of Onlooker bees easily trapped in local minima. Hence, only the algorithm SN/2. with good exploration and exploitation capability can find the  The maximum number of cycles for foraging = 2000. global minimum value.  Runtime = 100  Limit = 70 5.1.5 Schwefel function  MR = 0.1 It is a multimodal, continuous, differentiable and separable  = varies linearly with the iteration from 1.2 to 0.8 function whose global optimal value is 0 and located Simulation setting for ABC, PSO, GABC are as in [7] and . The range of the [12]. decision variables is [−500, 500] [12]. 5.3 Simulation Results The results of QABC with the simulation parameters discussed in section 5.2 are shown in Table 1. Table 1 shows the mean values and the standard deviation achieved by each algorithm for different functions and dimensions. Table 2 31  International Journal of Computer Applications (0975 – 8887) Volume 93 – No 9, May 2014 shows the significant of QABC results compared to the others. 6. Conclusion In Table 2, ‘+’ indicates that the QABC is better than all the In this paper, a new modified version of ABC algorithm is others, ‘=’ indicates that QABC equals to at least one of the introduced. The newly suggested strategy used in onlooker other algorithm and ‘-’ indicates that QABC is worse than at bee phase. Furthermore, the proposed algorithm modifies the least one of the other algorithm. QABC outperforms the update equation of the ABC in order to balance between the others in 11 out of 18 cases as shown in Table 2. The results exploration and exploitation of the search mechanism. obtained demonstrate the superiority of QABC over ABC, PSO and GABC. Table 1: Comparison of the Results obtained by QABC algorithm and other algorithms. ABC PSO GABC QABC Fun. D Mean SD Mean SD Mean SD Mean SD 10 3.7196e-3 8.8334e-8 0.079393 0.033451 6.0279e-4 2.3313e-3 8.8334e-8 1.8151e-7 F1 20 3.8168e-3 8.8334e-8 0.30565 0.025419 6.9655e-4 2.2609-3 0 0 30 1.1971e-2 1.9763e-2 0.011151 0.014209 1.0470e-3 2.7482e-3 0 0 10 0 0 2.6559 1.3896 0 0 0 0 F2 20 1.4052e-11 4.0524e-11 12.059 3.3216 3.3165e-2 1.8165e-1 0 0 30 0.45305 0.51495 32.476 6.9521 2.1733 1.0728 0 0 10 1.1114 1.7952 4.3713 2.3811 1.6769 2.9037 0.0114638 0.0503656 F3 20 4.5509 4.8776 77.382 94.901 7.47961 19.092 0.00887047 0.0115089 30 48.0307 46.65676 402.54 633.65 25.7164 31.75811 0.0041108 0.00390255 10 2.8343e-9 2.5816e-9 9.8499E-13 9.6202E-13 2.7533e-14 3.35832e-15 0 0 F4 20 2.7591e-5 2.1321e-5 1.1778E-6 1.584E-6 7.7828e-10 2.9817e-10 0 0 30 4.7018e-2 3.3957e-2 1.4917E-6 1.861E-6 1.11137e-4 3.8873e-5 0 0 10 1.9519 1.3044 161.87 144.16 1.27E-09 4E-12 1.27E-09 4E-12 F5 20 7.285 2.9971 543.07 360.22 0.000255 0 0.0002546 0 30 13.5346 4.9534 990.77 581.14 0.000382 1E-12 0.00038182 1E-12 F6 4 0.014938 0.007364 0 0 0.0929674 0.066277 0.001254 0.00125632 F7 10 0.013355 0.004532 0 0 0.0002476 0.000183 0 0 F8 24 9.703771 1.547983 0.00011004 0.000160 0.0031344 0.000503 0.000376 0.002264 Table 2: Summary of the results. Fun. F1 F2 F3 F4 F5 F6 F7 F8 D 10 20 30 10 20 30 10 20 30 10 20 30 10 20 30 4 10 24 QABC Performance + + + = + + + + + + + + = = = - = - The bee in the QABC is considered to behave like a quantum International Symposium on Micro Machine and Human particle in a delta potential well. Moreover, the modified Science, Nagoya, Japan, vol. 1, pp. 39-43. 1995. strategy is applied to solve 8 well-known benchmark functions. The obtained result shows that the QABC is [4] D. Karaboga, “An Idea based on Honey Bee Swarm for superior to the ABC, PSO and GABC. The proposed Numerical Optimization,” Technical Report, Erciyes algorithm can be applied for optimization problems with University, Engineering Faculty, Computer Engineering different properties. Additionally, it can escape the local Department, pp. 1-10, 2005. minima and converge to the global minima efficiently. [5] K.V. Price, R. M. Storn, and J. A. Lampinen, “Differential Evolution: A Practical Approach to Global optimization,” Springer-Verlag, Berlin, Germany, 2005. 7. REFERENCES [6] Z. Guopu, and S. Kwong, “Gbest-guided Artificial Bee [1] X. S. Yang, Z. H. Cui, R. B. Xiao, A. H. Gandomi, and Colony Algorithm for Numerical Function M. Karamanoglu, “Swarm Intelligence and Bio-Inspired Optimization,” Applied Mathematics and Computation, Computation,” Elsevier, Waltham, Mass, USA, 2013. vol. 217, pp. 3166-3173, 2010. [2] M. Dorigo, G. D. Caro, and L. M. Gambardella, “Ant [7] L. Guoqiang, P. Niu, and X. Xiao, “Development and Algorithms for Discrete Optimization,” Artificial Life, Investigation of Efficient Artificial Bee Colony vol. 5, no. 2, pp.137-172, 1999. Algorithm for Numerical Function Optimization,” Applied Soft Computing, vol. 12, no. 1, pp. 320-332, [3] R. C. Eberhart, and J. Kennedy, “A New Optimizer using 2012. Particle Swarm Theory,” In Proceedings of the Sixth 32  International Journal of Computer Applications (0975 – 8887) Volume 93 – No 9, May 2014 [8] D. Karaboga, and B. Basturk, “A Powerful and Efficient [11] D. Griffiths, and E. G. Harris, “Introduction to Quantum Algorithm for Numerical Function Optimization: Mechanics,” Prentice Hall, New Jersey, USA, vol.2, Artificial Bee Colony (ABC) Algorithm,” Journal of 1995. Global Optimization, vol. 39, no. 3, pp.459-471, 2007. [12] D. Karaboga, and B. Akay, “A Comparative Study of [9] J. Sun, B. Feng, and W. Xu, “Particle Swarm Artificial Bee Colony Algorithm,” Applied Mathematics Optimization with Particles having Quantum Behavior,” and Computation, vol. 214, no.1, pp. 108-132, 2009. Congress on Evolutionary Computation, Portland OR, USA, vol. 1, pp. 325-331, 2004. [13] M. Jamil, and X. S. Yang, “A Literature Survey of Benchmark Functions for Gobal Optimization [10] J. Sun, W. Xu, B. Feng, “Adaptive Parameter Control Problems,” International Journal of Mathematical for Quantum-behaved Particle Swarm Optimization on Modeling and Numerical Optimization, vol.4, no. 2, pp. Individual Level,” IEEE International Conference on 150-194, 2013. Systems, Man and Cybernetics, Hawaii, USA, vol. 4, 2005. IJCATM : www.ijcaonline.org 33