Optimization of Benchmark Functions using VTS-ABC Algorithm

Optimization of Benchmark Functions using VTS-ABC Algorithm Performance Optimization of Benchmark Functions using VTS-ABC Algorithm Twinkle Gupta  and Dharmender Kumar Abstract  A new variant based on tournament selection called VTS-ABC algorithm is provided in this paper. Its performance is compared with standard ABC algorithm with different size of data on several Benchmark functions and results show that VTS-ABC provides better quality of solution than original ABC algorithm in every case. Keywords— Artificial Bee Colony Algorithms, Nature-Inspired Meta-heuristics,Optimizations, Swarm Intelligence Algorithms, Tournament selection. NOMENCLATURE ABC – Artificial Bee Colony ACO – Ant Colony Optimization BFS – Blocking Flow-Shop Scheduling DE – Differential Evolution EA – Evolutionary Algorithm GA – Genetic Algorithm MCN – Maximum Cycle Number PSO – Particle Swarm Optimization TS – Tournament size TSP – Travelling Salesman Problem 1.INTRODUCTION For optimization problems, various algorithms havebeendesigned which are basedonnature-inspiredconcepts [1].Evolutionary algorithms(EA) and swarmoptimizationalgorithmsare two different classes in which nature inspired algorithms are classified.Evolutionary algorithms like Geneticalgorithms (GA)andDifferentialevolution (DE) attempt to carry out the phenomenon ofnaturalevolution [2]. However, a swarm like ant colony, a flock of birds can be described as collection of interacting agents and their intelligence lieintheir way of interactions with other individuals andtheenvironment [3]. Swarm optimization includes Particle swarm optimization (PSO) modelon socialbehaviorofbirdflocking [4], Antcolony optimization (ACO) model on swarmofants and Artificial Bee Colony (ABC) model on the intelligent foraging behaviour of honey bees [5]. Some important characteristics of ABC algorithm which makesitmoreattractivethanotheroptimizationalgorithms are: Employs only three control parameters (population size, maximum cycle number and limit) [6]. Fastconvergencespeed. Quite simple, flexible and robust [7] [8]. Easyintegrationwithotheroptimizationalgorithms. Therefore, ABC algorithm is a very popular nature inspired meta-heuristic algorithm used to solve various kinds of optimization problems. In recent years, ABC has earned so much popularity and used widely in various application such as: Constrained optimization, Image processing, Clustering, Engineering Design, Blocking flow shop scheduling (BFS), TSP, Bioinformatics, Scheduling and many others [9]-[18].Similar to other stochastic population-based approaches like GA, Ant Colony etc. ABC algorithm also applied Roulette Wheel selection mechanism which chooses best solution always with high selection pressure and leads the algorithm into premature convergence. With ever-growing size of dataset, optimization of algorithm has become a big concern. This calls for a need of better algorithm. The aim of this paper is to create such an algorithm named VTS-ABC algorithm. This new variant is based on tournament selection mechanism and selects variable tournament size each time in order to select the employed bees sharing their information with onlooker bees. Onlooker bees select solution from selected tournament size of solutions with less selection pressure so that high fitness solutions can’t dominate and give better quality of solutions with large data set as well. A worst solution is also replaced by better solution generated randomly in each cycle. Rest of the paper is divided in different sections as follows: Introduction to standard ABC algorithm is described in section 2. Section 3 describes the proposed VTS-ABC algorithm. Experiments and its simulation results to show performance on several Benchmark functions are described in section 4 and in the last; Conclusion of the paper is discussed. 2.ARTIFICIAL BEE COLONY ALGORITHM In 2005, Karaboga firstly proposed Artificial Bee Colony algorithm for optimizing numerical problems [19] which includes employed bees, onlooker bees and scouts. The bee carrying out search randomly is known as a scout. The bee going to the food source visited by it before and sharing its information with onlooker bees is known as employed bee and the bee waiting on the dance area called onlooker bee. ABC algorithm as a collective intelligence searching model has three essential components: Employed bees, Unemployed bees (onlooker and scout bees) and Food sources. In the view of optimization problem, a food source represents a possible solution. The position of a good food source indicates the solution providing better results to the given optimization problem. The quality of nectar of a food source represents the fitness value of the associated solution. Initially, a randomly distributed food source position of SNsize, the size of employed bees or onlooker bees is generated. Each solution xi is a D-dimensional vector that represents the number of optimized parameters and produced usingthe equation 1: where,xmaxandxminare the upper and lower bound of the parameterxi,respectively and j denotes the dimension. The fitness of food sources to find the global optimal is calculated by the following formula: where, fm(xm)is the objective function value of xm. Then the employed bee phase starts. In this phase, each employed bee xi finds a new food source viin its neighborhood using the equation 3: where, t: Cycle number; : Randomly chosen employed bee and k is not equal to i ; ( ): A series of random variable in the range [-1, 1]. The fitness of new solution produced is compared with that of current solution and memorizes the better one by means of a greedy selection mechanism. Employed bees share their information about food sources with onlooker bees waiting in the hive and onlooker bees probabilistically choose their food sources using fitness based selection technique such as roulette wheel selection shown in equation 4: where, Pi: Probability of selecting the ith employed bee, S: Size of employed bees, ÃŽ ¸i: Position of the ith employed bee and F : Fitness value. Afterthatonlookerbeescarried outrandomly searchintheirneighborhood similar to employed bees and memorize the better one. Employed bees whose solutions can’t be improved through a predetermined number of cycles, called limit, become scouts and their solutions are abandoned. Then, they find a new random food source position using the following equation 5: Where, r: A random number between 0 and 1 and these steps are repeated through a predetermined number of cycles called Maximum Cycle Number (MCN). 3.PROPOSED WORK: VTS-ABC ALGORITHM In every meta-heuristic algorithm mainly two factors need to be balanced for global optimization outcome i.e. Exploration and Exploitation but ABC is a poor balance of these two factors. Various variants of ABC have been modelled for its improvement in different phases by number of researchers like Sharma and Pant have proposed a variant of ABC called RABC for solving the numerical optimization problem [20] and Tsai et al. have presented an interactive ABC optimization algorithm to solve combinational optimization problem [21] in which the concept of universal gravitational force for the movement of onlooker bees is introduced to enhance the exploration ability of the ABC algorithm. D. Kumar and B. Kumar also reviewed various papers on ABC and give a modified RABC algorithm based on topology for optimization of benchmark functions [22] [23]. Intelligence of ABC algorithm mainly depends upon the communication between individual agents. Employed beesshare their information with onlooker bees waiting in the hive and flow of this information from one individual to another depends on the selection mechanism used. Different selection schemes select different individuals to share the information which affect the communication ability of individuals and primarily the outcome of the algorithm. ABC algorithm uses Roulette wheel selection mechanism in which each onlooker bee selects the food source based on certain probability. Each onlooker bee selects the best food source with high selection pressure and lead to premature convergence. To overcome this problem, its new variant is proposed in which Tournament Selection method is applied based on Cycle number and number of employed bees. In Tournament selection, a tournament size (TS) is chosen to select the number of employed bees sharing the information with onlooker bees. For better exploration, TS=2 i.e. Binary Tournament is applied in early stages and for better exploitation, variable tournament size is applied based on the current cycle number (CYL) and size of employed bee in middle stages. As the stages grow, this method works similar to Roulette wheel method in the end. Hence, the selection pressure is less in early stages and more in final stages which provide us better quality of solution. As variable size of tournament is used at different stages of the algorithm, hence the algorithm named VTS-ABC (Variable Tournament Size Artificial Bee Colony) algorithm. Method used for calculating TS is shown in equation 6 and equation 7: If SN >= 20 If SN Where Here, two equations are shown for calculating tournament size of tournament selection method. The purpose of using these two equations is to increase the speed of algorithm. When the size of employed bee i.e. given population of food source positions is small like 10, a solution can be easily found by changing the tournament size by 1 but as the size grows i.e. when best food source position is to be found in large set of population for example when SN=40 or more than 40, increasing size of tournament by 1 and 2 only is a very tedious task as it will take more time to run the algorithm. Hence, in order to increase speed of algorithm, the tournament size based on current cycle and size of population is increased. One more concept is applied to increase its convergence speed. At each iteration or cycle, a new solution is generated randomly similar to scout and its fitness value is calculated. Greedy selection mechanism is applied between new solution and worst one and the better solution is memorized. Hence, it helps in finding good quality of solution as well as improving the convergence speed and provides better balance between exploration and exploitation. 4.experiments and simulation results 4.1 Benchmark Functions The Benchmark Functions used to compare the performance of VTS-ABC algorithm with original ABC algorithm are illustrated below: Sphere Function: Schwefel Function: Griewank Function: Where Ackley Function: Here, ObjVal is the function value calculated for each food source position. A food source is represented by X and population size is taken of n*p matrix where n is the no. of possible food source positions and p represents the dimension of each position. 4.2 Performance Measures Simulation Result The experimental results of VTS-ABC and ABC algorithm in MATLAB are taken under the parameter of size of food source positions (n*p) i.e. different size of population with different dimensions are taken to run and compare both algorithms. MCN is set as 2000 and each algorithm is run for 3 iteration i.e. Runtime=3. Limit for scouts is set equals to 300. In order to provide the quantitative assessment of the performance of an optimization algorithm, Mean of Global Minimum i.e. mean of minimum objective function value at each cycle of all iterations are taken as performance measure whose values are shown in table1and figure 1-4. Table1: Mean of Global minimum on different size of data Fig. 1: Mean of Sphere function values on different size of data Fig. 2: Mean of Schwefel function values on different size of data Fig. 3: Mean of Griewank function values on different size of data Fig. 4: Mean of Ackley function values on different size of data Figure 1 to 4 show simulation results of ABC and VTS-ABC algorithm with different size of data on Sphere, Schwefel, Griewank, Ackley respectively and reveal that VTS-ABC algorithm provides us better quality of solution than original ABC algorithm by minimizing objective function value or producing higher fitness solutions. 5. DISCUSSION AND CONCLUSION In this paper, a new algorithm VTS-ABC is presented. In this algorithm, firstly variable tournament size (TS) is applied to select the food source position for onlooker bees which helps to achieve diversity in solution. Then to increase convergence speed, a new solution is generated in each cycle which replaced the worst one. In order to demonstrate the performance of proposed algorithm, it is applied on several Benchmark functions with different size of data set as input. Simulation results show that it provides better quality of solution than original ABC algorithm in every case. Therefore, it can be applied in different fields of optimization with large and higher dimensions data set efficiently. References Yugal Kumar and Dharmender Kumar, â€Å"Parametric Analysis of Nature Inspired Optimization Techniques†International Journal of Computer Applications, vol. 32, no. 3, pp. 42-49, Oct. 2011. P. J. Angeline, J. B. Pollack and G.M. Saunders, â€Å"An evolutionary algorithm that constructs recurrent neural networks,† Neural Networks in IEEE Transactions on, vol. 5, no. 1, 1994, pp. 54-65. J. Kennedy and R. Eberhart, â€Å"Particle swarm optimization,† in Proceedings of IEEE international conference on neural networks, 1995, vol. 4, pp. 1942–1948. E. Bonabeau, M. Dorgio, and G. Theraulaz, â€Å"Swarm intelligence: from neural network to artificial intelligence,† NY: oxford university press, New York, 1999. D. Karaboga, â€Å"An idea based on honey bee swarm for numerical optimization,† Techn.Rep. TR06, Erciyes Univ. Press, Erciyes, 2005. D. Karaboga and B. Akay, â€Å"A comparative study of artificial bee colony algorithm,† Applied Mathematics and Computation, vol. 214, no. 1, pp. 108–132, 2009. R. S. Rao, S. V. L. Narasimham, and M. Ramalingaraju, â€Å"Optimization of distribution network configuration for loss reduction using artificial bee colony algorithm,† International Journal of Electrical Power and Energy Systems Engineering, vol. 1, no.2, pp. 116–122, 2008. A. Singh, â€Å"An artificial bee colony algorithm for the leaf-constrained minimum spanning tree problem,† Applied Soft Computing, vol. 9, no. 2, pp. 625–631, Mar. 2009. D. Karaboga and B. Basturk, â€Å"Artificial bee colony (ABC) optimization algorithm for solving constrained optimization problems,† in Foundations of Fuzzy Logic and Soft Computing, Springer, 2007, pp. 789–798. C. Chidambaram and H. S. Lopes, â€Å"A new approach for template matching in digital images using an Artificial Bee Colony Algorithm,† in World Congress on Nature Biologically Inspired Computing, 2009. NaBIC 2009, IEEE, 2009, pp. 146–151. N. K. Kaur Mann, â€Å"Review Paper on Clustering Techniques,† Global Journal of Computer Science and Technology, vol. 13, no. 5, 2013. S. Okdem, D. Karaboga, and C. Ozturk, â€Å"An application of Wireless Sensor Network routing based on Artificial Bee Colony Algorithm,† in 2011 IEEE Congress on Evolutionary Computation (CEC), 2011, pp. 326–330. T. K. Sharma, M. Pant, and J. C. Bansal, â€Å"Some modifications to enhance the performance of Artificial Bee Colony,† in 2012 IEEE Congress on Evolutionary Computation (CEC), 2012, pp. 1–8. L. Bao and J. Zeng, â€Å"Comparison and analysis of the selection mechanism in the artificial bee colony algorithm,† in Hybrid Intelligent Systems, 2009. HIS’09. Ninth International Conference on, 2009, vol. 1, pp. 411–41. C. M. V. Benà ­tez and H. S. Lopes, â€Å"Parallel Artificial Bee Colony Algorithm Approaches for Protein Structure Prediction Using the 3DHP-SC Model,† in Intelligent Distributed Computing IV, M. Essaaidi, M. Malgeri, and C. Badica, Eds. Springer Berlin Heidelberg, 2010, pp. 255–264. D. L. Gonzà ¡lez-à lvarez, M. A. Vega-Rodrà ­guez, J. A. Gà ³mez-Pulido, and J. M. Sà ¡nchez-Pà ©rez, â€Å"Finding Motifs in DNA Sequences Applying a Multiobjective Artificial Bee Colony (MOABC) Algorithm,† in Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics, C. Pizzuti, M. D. Ritchie, and M. Giacobini, Eds. Springer Berlin Heidelberg, 2011, pp. 89–100. L. Wang, G. Zhou, Y. Xu, S. Wang, and M. Liu, â€Å"An effective artificial bee colony algorithm for the flexible job-shop scheduling problem,† Int J Adv Manuf Technol, vol. 60, no. 1–4, pp. 303–315, Apr. 2012. S.-W. Lin and K.-C. Ying, â€Å"Increasing the total net revenue for single machine order acceptance and scheduling problems using an artificial bee colony algorithm,† J Oper Res Soc, vol. 64, no. 2, pp. 293–311, Feb. 2013. D. Karaboga, â€Å"An idea based on honey bee swarm for numerical optimization,† Techn.Rep. TR06, Erciyes Univ. Press, Erciyes, 2005. T. K. Sharma, M. Pant, and J. C. Bansal, â€Å"Some modifications to enhance the performance of Artificial Bee Colony,† in 2012 IEEE Congress on Evolutionary Computation (CEC), 2012, pp. 1–8. TSai, Pei-Wei, et al. , Enhanced artificial bee colony optimization.International Journal of Innovative Computing, Information and Control,vol. 5, no. 12, 2009, pp.5081-5092. B. K. Verma and D. Kumar, â€Å"A review on Artificial Bee Colony algorithm,† International Journal of Engineering Technology, vol. 2, no. 3, pp. 175–186, 2013. D. Kumar and B. Kumar, â€Å"Optimization of Benchmark Functions Using Artificial Bee Colony (ABC) Algorithm,† IOSR Journal of Engineering, vol. 3, no. 10, pp. 09-14, October 2013.