Selected Heuristic Algorithms Analysis and Comparison in Solving Optimization Problems Bartłomiej Szlachta Kamil Rusin Łukasz Płaneta Faculty of Applied Mathematics Faculty of Applied Mathematics Faculty of Applied Mathematics Silesian University of Technology Silesian University of Technology Silesian University of Technology Kaszubska 23, 44-100 Gliwice, Poland Kaszubska 23, 44-100 Gliwice, Poland Kaszubska 23, 44-100 Gliwice, Poland Email: bartek01570@gmail.com Email: kamirus323@student.polsl.pl Email: luke.planeta@gmail.com Abstract—Three examples of heuristic algorithms: The Firefly minimum of cost we understand a point for which the value of Algorithm, The Artificial Bee Colony Algorithm and The Genetic function is the lowest. Heuristic algorithms are very useful for Algorithm, have been tested in regard to the ability of solving finding solutions to problems which are difficult to solve in a four testing cost functions. In this paper the algorithms are usual way. Heuristic algorithms can be seen as help which explained and the results are discussed and compared. randomize a definite number of points and move them in a specific way. As a result, the points group in the area of the Keywords—metaheuristics, heuristic algorithms, firefly minimum of the function. We will never be able to determine algorithm, artificial bee colony algorithm, genetic algorithm, the minimal value of the function. However, the determined optimization problem value should be precise enough. I. INTRODUCTION Each algorithm works in a different way, so one defined algorithm which is able to solve all the optimization problems Heuristic algorithms are often used for optimization does not exist. For different functions some of them perform purposes, when a space of solutions is complex and common better than others, so the testing results of vary from each other. methods are imprecise these algorithms may help. We can find It is our responsibility to choose an algorithm and its various application of heuristics in real world problems like coefficients to be the most suitable to find the best value of image processing [9], [10]; games playability [11]; cognitive objective function. The only way to choose them is to apply aspects of political sciences [12]; terminal slider control [13]; trial and error method. metal annihilating processes [14]. When it comes to the cost function, it is sometimes difficult or it is too time-consuming to find its minimum using mathematical methods. By the II. TESTING FUNCTIONS To check the results, we use four binary testing functions: 1) Rosenbrock function: Considered at a range from -3 to 3, it has a global minimum at f (1, 1) = 0 and is calculated as: (1) 2) Beale function: Considered at a range from -4.5 to 4.5, it has a global minimum at f (3, 0.5) = 0 and is calculated as: (2) 3) Himmelblau function: Considered at a range from -10 to 10, it has four global minimums: f (3, 2) = f (-2,805118, 3,131312) = f (-3,779310, -3,283186) = f (3,584428, -1,848126) = 0 and is calculated as: (3) 4) Levy function n. 13: Considered at a range from -4.5 to 4.5, it has a global minimum at f (0, 0) = 0 and is calculated as: (4) behaviour of fireflies, beetles from the family of Lampyridae. III. FIREFLY ALGORITHM Each of them emits a bioluminescent light from abdomen and uses it to attract the less bright fireflies. A. Fireflies’ behaviour / Genesis The firefly algorithm (FA) is an example of nature-inspired B. Method of operations heuristic algorithm, proposed by Xin-She Yand in [1] with To connect the FA algorithm with the optimization some interesting applications [2], [3]. It is inspired by the problem, the input of a cost function is interpreted as the co- ordinates of a firefly in a two-dimensional space. Then, for Copyright held by the author(s). 30 every point of the space the cost function value can be D. Details calculated for its co-ordinates. Also, it can be said that a firefly  The distance between two fireflies Ai and Aj is has a ‘f’ value, which means the value for the point the firefly obtained by using formula: is located at. The main objective of the algorithm is to find the best point – that with the smallest ‘f’. (5) Firstly, the population of fireflies needs to be generated randomly before the algorithm runs. Then, the algorithm should  The Aj attractiveness is determined by equation: be launched and repeated a certain number of times. During every iteration, each firefly is moved, one after the other, in the (6) direction of better ones in order to find the best ‘f’ value. There is always a random factor added to the movement. If a firefly is  The distance that Ai is moved in Aj direction is the best of all, the random step is the only factor responsible for calculated as: moving a firefly. (7) C. Pseudocode  The random move of Ai is defined by a vector which In our implementation, the FA algorithm works in co-ordinates are random real numbers from the range [- accordance with the pseudocode showed below: a, a]. Input: E. Observations  Attributes of the Ai fireflies colony: The consecutive algorithm iterations results can be split into two phases: a) Co-ordinates (xi, yi), 1) Grouping fireflies together: In this part each b) Value ‘fi’ of the cost function, calculated for (xi, yi), co- iteration of the algorithm results in the fireflies ordinates. getting closer and closer to each other and the  Population size ‘n’, a natural number, distance between the most distant pair of fireflies declines. The middle of the group moves randomly.  Maximum attractiveness ’β0’, a real number in the There is also a possibility of creating more than one range (0, 1], group, each at local minimums.  Absorption coefficient ‘γ’, a real number in the range 2) Movement of the group: Now the fireflies are (0, 1], moving randomly with the width of the group  Random step size ‘a’, a real positive number. staying approximately constant. The whole group can move consistently in the direction of the best Output: firefly when a better ‘f’ value is found.  The co-ordinates (xi, yi) and the ‘fi’ value of the best The phases are different for various algorithm coefficients firefly, values. Their adequate choice is essential in order to find the global minimum as precisely as possible.  Changes in every firefly’s attributes. Calculations: F. Analysis i=0 For different coefficients values the algorithm returns while i < n do different results. That can be analysed in order to find the j=0 coefficients values adequate to a function and a need. while j < n do The fireflies’ movement consists of two factors: attraction Counting the distance between Ai and Aj by the others and the random step. The former is very essential Assigning an attractiveness to Aj for the initial iterations when the distance between fireflies is if fi < fj then long. During the latter, fireflies are located so close to each Moving Ai in the direction of Aj other that the attraction impact is responsible only for keeping end if the group together and does not help with searching cost Moving Ai randomly. function global minima. Those statements can be justified by Calculating fi value for the new Ai co-ordinates mathematical calculations. end while end while By connecting the formula (6) with the formula (7) we get a Comparing ‘fi’ values for each fireflies function s(r) which describes the distance the fireflies cover end depending on the initial distance between them: (8) 31 Value of s(r) function (8) depends, for example, on ‘β0’ and in the neighbourhood. ABC is based on population of a swarm ‘γ’. Consequently, s(r) can be increased by increasing ‘β0’ and defined food sources. It is usually used for optimization value and decreasing ‘γ’ value and vice versa. problems. There are many articles reporting this method in various optimization aspects [5] – [8]. Bees are very Having calculated the first derivative of (8), we can analyse cooperative and thanks to it, the swarm is able to perform tasks monotonicity of s(r). With the initial distance declining, successfully. The whole population is divided into three starting from the zero value in the infinity, it appreciates on groups: employed bees, onlooker bees and scout bees. First of value, reaches a peak at the distance r0 shown below and them are looking for food sources. Meanwhile, they are also declines to 0 at the 0 distance. sharing information with other bees about the best ones they have found so far. The second group of bees observes them and (9) decides to follow them to the food sources with the best fitness. The better the source, the higher possibility of choosing it. So, the distance Ai firefly covers is the longest when Aj Employed bees can also change their food sources. They may firefly is located within r0 initial distance of Ai. That means that be encouraged to follow other bees to their food sources. by reducing absorption coefficient ‘γ’ value, we increase r0 However, if an employed bee decides to leave its current food value. The size of population ‘n’ has also impact on r0 because source and go to other randomly selected one, then it is named the more fireflies exist, the higher probability of one staying at a scout bee. Generally, a population of the swarm in ABC r0 is. On the other hand, a big amount of fireflies can slow algorithm is divided into half. Employed bees are the first half, down a computer because it would need to make many more whereas onlooking bees are in the other one. Over time, calculations. artificial bees discover better and better food sources to finally It needs to be mentioned that the s(r) value needs to be find the ones with the largest amount of nectar. Then the co- much more significant than the random step ‘a’ value. ordinates of its position represent the best solution for our Otherwise, the fireflies will not attract each other enough and optimization problem. they will split into two or more groups facing the local, not global minimums. I. Pseudocode During the second phase fireflies are located so close to In our implementation, the ABC algorithm works in each other that s(r) values are insignificant compared to ‘a’ and accordance with the pseudocode showed below: are responsible only for keeping the group together – when a Input: firefly moves too far, s(r) soars and brings the firefly back to the group.  Population of the colony ‘n’, a natural number, When a randomly moved firefly hits the ‘f’ value better  Number of iterations, a natural number than the found so far, it attracts all other fireflies. As a result,  Limit of chances for food source ‘t’, a natural number, the group is moving in its direction. The global minimum of the cost function is located approximately in the middle of the  Number of food sources ‘o’, a natural number. group and the determination of the minimum ‘f’ value with an acceptable accuracy depends mostly on luck. Output:  The co-ordinates (xi, yi) and value of the best food G. Conclusions source. 1) To minimise the time required for the first section, increase ‘n’ and ‘β0’ values, reduce ‘a’ value and set an appropriate value of ‘γ’. Phases of the algorithm: 2) To reduce a risk of fireflies splitting into many Initialization Phase groups, try increasing ‘γ’ and ‘β0’ values and Setting number of food sources, population, functions reducing ‘a’ value. parameters. 3) To reduce the time required for the second section, Repeat for every iteration increase ‘a’ value. Employed bees phase Onlooker bees phase 4) To determine the minimum value with the better Scouts bees phase accuracy, increase the size of population ‘n’ and Memorizing the best solution achieved so far reduce ‘a’ value, but not exactly to 0. After Writing the co-ordinates and value of the best ARTIFICIAL BEE COLONY ALGORITHM solution H. Bees’ behaviour / Genesis J. Initialization phase Artificial Bee Colony algorithm (ABC) was proposed and Firstly, variables for algorithm must be set, e.g. population implemented by Dervis Karaboga in [4]. He was inspired by a of a swarm, limit of chances for each food source. We can also bee swarm behaviour and their way to find the best food source change the number of food sources, which optimal value equals 32 the half of the population. Then, we must adjust parameters for N. Observations a function we want to optimize, e.g. upper and lower bound. The proper number of food sources equals a half of the During this phase all food sources are initialized by scout bees. swarm population. If we keep reducing the number of food Every food source represents possible solution for our sources, we will have worse and worse solutions. When we optimization problem. The following equation might be used increase bee population, it does not always go hand in hand for initialization: with getting a more accurate solution. To obtain optimal (10) chances we limit ‘o’ to 100. There is a slight difference, when we change this parameter. where ‘lb’ is lower and ‘ub’ is upper bound of our parameter ‘xi’. K. Employed bees phase Employed bees look for a new food source that might have a greater amount of nectar in a close neighbourhood of their last food source. The value of food source is set using the following equation: (11) where ‘i’ is a randomly chosen parameter index, ‘xi’ is a randomly selected food source and ‘σ’ represents a random number from range [-1,1]. Simultaneously, fitness of every food source is being computed. After these processes a bee makes a choice. The fitness value may be calculated using the following formula: (12) where f(xi) is a value of solution ‘xi’. L. Onlooker bees phase Onlooker bees wait in the swarm for information about food sources provided by employed bees. Then a probability is calculated. It is based on the fitness value, given them by employed bees. This probability means that onlooker bees are more willing to exploit food sources with higher fitness value. It can be calculated using a following formula: (13) where ‘fit(i)’ means fitness of food source with index ‘i’ and ‘s’ means a number of food sources. Afterwards a neighbouring source is calculated from (10) and fitness value from (12). The onlooker bee must choose one of two. The more bees are recruited to better food sources, the more positive feedback they have. M. Scout bees phase In this phase unemployed bees choose a new food source randomly. Scouts are bees, which abandoned their solutions due to chance limit set at the beginning of the algorithm. This means that their solutions could not be upgraded. What is more, they choose next food sources as well as share negative opinions on abandoned food sources, so that it will balance positive ones. 33 where: GENETIC ALGORITHM elite - number of individuals in elite group population - number of population A. Genesis  All chromosomes before crossover or mutation are Genetic algorithm (GA) was proposed by Alan Turing in translated into genes. In our case decimal numbers are 1950. He was inspired by Charles Darwin’s theory of natural translated into binary numbers. evolution. It was developed by John Holland and colleagues at the University of Michigan in [18]. Nowadays we can find its  We used 3 crossover variants: 1-Point Crossover, various improved versions reported in many articles [15]-[17]. Destructive Crossover and Constructive Crossover. In GA is based on population which uses natural selection. It is 1-Point Crossover offspring is created by exchanging used for optimization problems. Algorithm relies on biological the genes of parents. operations: selection, mutation and crossover, as in natural genetics. Firstly, whole population is selected by their fitness score (degree of adaptation). The higher the score, the higher chance of surviving to the next generation. The next generation is composed of parents, who survived and their children. Children are created by crossover or mutation. Fig. 1. Typical Crossover B. Pseudocode I our implementation, the GA works in accordance with the In Destructive Crossover only positive genes in both pseudocode shown below: chromosomes are reproduced. In Constructive Crossover if one of genes is positive, then Input: offspring’s gene is also positive.  Population of the generation, a natural number,  Number of iterations, a natural number,  Two chromosomes for each individual. Output: Fig. 2. Destructive and Constructive Crossover  Two chromosomes of the best individual and fitness value. Left side: parents Phases of the algorithm: Right side: up - destructive, down - constructive crossover. Initialization phase Setting number of populations, their chromosomes and function parameters In Crossover, it is also interesting how positive and negative value is inherited. Here , we applied the methodology Repeating for every generation: of inheritance Rh factor from blood group system. When two Selection positive chromosomes cross, the offspring is positive in 15 of Setting the best individual and elite individuals 16 cases. But, if one is positive and the other is negative, the Crossover positive individual appears 3 times per 4. If both parents are Mutation negative, the offspring is always negative. After Write the best fitness score and chromosomes Operation of mutation inverts random genes. It is used for mutating parents or children that have been created by C. Details crossover.  The leader of the population has the highest chance of reproduction. The elite of the population have lower D. Observations chance which is still high. A typical individual has the We can find two kinds of behaviour: lowest chance of reproduction. This algorithm is based  whole population does not evolve for the most of the on herd selection, where Alpha male, some group of time elite individuals and the rest of the population appear. The reproduction probability for the leader can be  rare but really efficient ‘jumps’, where the best calculated using a followed formula: individual evolves That is really interesting and the solution of this may be in combination of two algorithms: destructive crossover and (14) mutation. GA works the best with Rosenbrock function, but it did not look well until 70th generation. The ‘jump’ occurred 34 where chromosome evolved. In Baele function GA jumps are E. Conclusions only in the beginning and are not spectacular. Himmemblau 1) GA is very useful to find the surroundings of function is definitely the hardest to our GA. After the 10th solution, but after some upgrades, it could be more generation the algorithm slows down and starts again before the accurate end. In Levy’s function we can observe quick start and huge jump in the middle generation. 2) Our version of GA is looking for solution in whole range, not in closer environment 3) A lot of results after mutations and crossover are useless due to thoughtless randomizing algorithm BENCHMARK TESTS Plots present the smallest ‘f’ value found so far depending on the number of iterations done for each testing functions. FA algorithm’s results are indicated by green lines, ABC Algorithm’s by the blue ones and GA Algorithm’s by the yellow ones. [B’s sent.] Green line indicates the values of Firefly algorithm, while blue line represents Artificial Bee Colony. [K’s sent.] FA Algorithm data was taken for following coefficients’ values: ‘n’ = 100; ‘β0’ = 0,1; ‘γ’ = 0,1; ‘a’ = 0,01. ABC algorithm data was taken for following coefficients’ values: ‘n’ = 100, ‘t’ = 50, ‘o’ = 100. GA algorithm data was taken for following coefficients’ values: ‘n’ = 100, ‘o’ = 100, crossover probability = 0,5, mutation probability for not-crossover= 0,5, mutation probability for crossover = 0,1, probability of mutation single gene = 0,1, in crossover positive sign is for: two positive = 15/16, two different = ¾, two negative 0. Fig. 3. The best value found during consecutive iterations. (Rosenbrock function) 35 Fig. 4. The best value found during consecutive iterations. (Beale function) Fig. 5. The best value found during consecutive iterations. (Himmelblau function) 36 Fig. 6. The best value found during consecutive iterations. (Levy function n. 13) two decimal places, while the second algorithm reached five FINAL REMARKS times better result. Genetic algorithm reached an interesting The graphs show the smallest values found for each of precision, however, it was still less accurate than ABC the test functions depending on the number of iterations of algorithm. each algorithm. Population for our algorithms was set to 100 individuals. Other parameters are incomparable and POSSIBLE APPLICATION determined differently. Heuristic algorithms can be applied in many practical We tested Rosenbrock function first. As we can see FA situations when an optimization is needed. To use an generated higher value at the beginning and a value at 100s heuristic algorithm, first we need to find a cost function iteration exceeded a final value of ABC algorithm. It was formula. Also we must keep in mind that there is a risk that less accurate by almost two decimal places. ABC algorithm the algorithm will not find a local minimum. Then we line plummeted and at second iteration reached its lowest should try to apply another algorithm. value. Genetic algorithm performed the best in this function. It was more accurate by three decimal places than ABC. Today heuristic algorithms may be used for example in market analysis. It uses the fact that when a bee in ABC The second graph shows Beal’s function, in which FA algorithm moves to a better solution than the previous one. dominated over ABC algorithm and Genetic algorithm. Even That behaviour may be easily applied thanks to trend though it started with a slightly higher function value than the others, it started to decline very quickly and reached functions of specific stock chart. At the defined range, highly precise value of seven decimal places. This is an algorithm knows when it is hitting the lowest and the impressive result. highest value. Specially designed bot could sell or buy shares of a company we are following. Algorithms may be On the third graph we can see comparable results of FA also used in neuron networks that would learn to solve and ABC algorithms. The values declined at different issues faster than usually. Neurons would correspond with moments. ABC algorithm reached constant value at 60th each other and work with better quality so the data would be iteration, whereas FA fell finally at 95th iteration and had a interpreted more precisely. slightly more accurate function value. Genetic algorithm was not precise and its calculation was inaccurate, its precision Genetic algorithm is used in many processes which use a was by two decimal places, while the ABC and FA biological algorithm because of its natural solutions usage. algorithms reached values with 7 and 8 decimal places, For example, robots are able to learn human behaviour. As a respectively. result, now they can perform actions which were reserved FA did not perform well at Levy’s function. At 10 for humans only. It advances the moment when robots will iteration it reached a static value, which was highly replace physical works, which is called evolutionary inaccurate comparing to ABC algorithm. It had precision of robotics. 37 GA is also commonly used in training neural networks. [15] LAU, Richard R.; REDLAWSK, David P. Advantages and disadvantages of cognitive heuristics in political decision making. The main benefit of this method is the fact that American Journal of Political Science, 2001, 951-971. neuroevolution can find quicker ways of finding solutions. [16] REZAIE, Behrooz; GHASEMI, Hossein; RAHMANI, Zahra. Typical supervised learning algorithms require data of Terminal Sliding Mode Controller Tuned Using Evolutionary correct input-output pairs. In contrast, genetic algorithm Algorithms for Finite-Time Robust Tracking Control in a Class of requires only a measure of a network's performance at a Nonholonomic Systems. Information Technology And Control, 47.1: 26-44. task. For example, in games we do not provide strategies [17] BROCIEK, Rafal; SLOTA, Damian. Application of real ant colony (how to play), but only how to increase score. This optimization algorithm to solve space and time fractional heat mechanism makes GA easy to transfer from one program to conduction inverse problem. Information Technology And Control, the other one. 2017, 46.2: 171-182. [18] DEB, Kalyanmoy, et al. A fast elitist non-dominated sorting genetic Genetic algorithm is also used in music record algorithm for multi-objective optimization: NSGA-II. In: International production. Algorithm uses known songs to create new Conference on Parallel Problem Solving From Nature. Springer, ones. It is based on schemes that are most popular in the Berlin, Heidelberg, 2000. p. 849-858. songs, recombining them to the fresh chanson. [19] HORN, Jeffrey; NAFPLIOTIS, Nicholas; GOLDBERG, David E. A niched Pareto genetic algorithm for multiobjective optimization. In: Evolutionary Computation, 1994. IEEE World Congress on REFERENCES Computational Intelligence., Proceedings of the First IEEE Conference on. Ieee, 1994. p. 82-87. [1] YANG, Xin-She. Firefly algorithms for multimodal optimization. In: [20] MORRIS, Garrett M., et al. Automated docking using a Lamarckian International symposium on stochastic algorithms. Springer, Berlin, genetic algorithm and an empirical binding free energy function. Heidelberg, 2009. p. 169-178.J. Clerk Maxwell, A Treatise on Journal of computational chemistry, 1998, 19.14: 1639-1662. Electricity and Magnetism, 3rd ed., vol. 2. Oxford: Clarendon, 1892, pp.68–73. [21] GOLDBERG, David E.; HOLLAND, John H. Genetic algorithms and machine learning. Machine learning, 1988, 3.2: 95-99. [2] WOŹNIAK, Marcin; MARSZAŁEK, Zbigniew. An idea to apply firefly algorithm in 2d image key-points search. In: International Conference on Information and Software Technologies. Springer, Cham, 2014. p. 312-323. [3] NAPOLI, Christian, et al. Simplified firefly algorithm for 2d image key-points search. In: Computational Intelligence for Human-like Intelligence (CIHLI), 2014 IEEE Symposium on. IEEE, 2014. p. 1-8. [4] KARABOGA, Dervis; BASTURK, Bahriye. Artificial bee colony (ABC) optimization algorithm for solving constrained optimization problems. In: International fuzzy systems association world congress. Springer, Berlin, Heidelberg, 2007. p. 789-798.K. Elissa, “Title of paper if known,” unpublished. [5] KARABOGA, Dervis. Artificial bee colony algorithm. scholarpedia, 2010, 5.3: 6915. [6] Witanowski, Łukasz & Lampart, Piotr. (2015). Using of a bee algorithms for searching process of minimum of objective function. Mechanik. 570/971-570/978. 10.17814/mechanik.2015.7.318. [7] Behzad Nozohour-leilabady, Babak Fazelabdolabadi, On the application of artificial bee colony (ABC) algorithm for optimization of well placements in fractured reservoirs; efficiency comparison with the particle swarm optimization (PSO) methodology, Petroleum, Volume 2, Issue 1, 2016, Pages 79-89, ISSN 2405-6561. [8] NOZOHOUR-LEILABADY, Behzad; FAZELABDOLABADI, Babak. On the application of artificial bee colony (ABC) algorithm for optimization of well placements in fractured reservoirs; efficiency comparison with the particle swarm optimization (PSO) methodology. Petroleum, 2016, 2.1: 79-89. [9] WOŹNIAK, Marcin; POŁAP, Dawid. Adaptive neuro-heuristic hybrid model for fruit peel defects detection. Neural Networks, 2018, 98: 16-33. [10] Capizzi, G., Sciuto, G. L., Napoli, C., Shikler, R., & Woźniak, M. (2018). Optimizing the Organic Solar Cell Manufacturing Process by Means of AFM Measurements and Neural Networks. Energies, 11(5), 1-13. [11] Napoli, C., Pappalardo, G., Tina, G. M., & Tramontana, E. (2016). Cooperative strategy for optimal management of smart grids by wavelet rnns and cloud computing. IEEE transactions on neural networks and learning systems, 27(8), 1672-1685. [12] Bonanno, F., Capizzi, G., Coco, S., Napoli, C., Laudani, A., & Sciuto, G. L. (2014, June). Optimal thicknesses determination in a multilayer structure to improve the SPP efficiency for photovoltaic devices by an hybrid FEM—cascade neural network based approach. In International Symposium on Power Electronics, Electrical Drives, Automation and Motion (SPEEDAM), 2014 (pp. 355-362). IEEE. [13] WOŹNIAK, Marcin; POŁAP, Dawid. Bio-inspired methods modeled for respiratory disease detection from medical images. Swarm and Evolutionary Computation, 2018. [14] DESURVIRE, Heather; CAPLAN, Martin; TOTH, Jozsef A. Using heuristics to evaluate the playability of games. In: CHI'04 extended abstracts on Human factors in computing systems. ACM, 2004. p. 1509-1512. 38