Abstract: The Bees Algorithm (BA) is a new population-based optimization algorithm inspired by the foraging nature of bees. In the basic version of the Bees Algorithm, the algorithm performed a combination of neighborhood search and global search. However, the current BA has the disadvantage of not fully imitate all physical and social aspect of bees’ nature. In this study, enhancements to the BA will be introduced as Memory-based Bees Algorithm (MBA) by adding memory (local and global) to two types of bees to make the algorithm more natural. The results of comparing the proposed Local-MBA, global-MBA and MBA (combination of Local-MBA and global-MBA) are tested using several benchmark functions. They had obtained approximately 59.34, 73.02, 74.9 and 75.44% improvement on mean number of evaluations over the basic BA, respectively. Novel fitness values of two engineering design problems are obtained by applying MBA. The proposed algorithms have great potential to be used in many optimization problems.
INTRODUCTION
The BA algorithm is one of many biologically inspired algorithms. It is a new population-based algorithm that has been proposed to overcome the local optima problem and is applicable to both combinatorial and functional optimization problems (Pham et al., 2006). The BA follows the behavior of honey bees in food foraging. It uses neighborhood search with random search to find best food sources. The BA depends on exchange of information among a large number of scout and follower bees, where these bees’ based on the information received from each to search and find new plentiful sources. The BA has proved to be the most powerful fair optimization method for sampling a large solution space because of its fair random sampling. Some other nature-based algorithms are the Ant Colony Optimization (ACO), the Particle Swarm Optimization (PSO), the Artificial Bee Colony algorithm (ABC) and the Honey Bee Mating Optimization (HBMO) algorithm (Pham et al., 2007).
The BA is used to solve many problems such as control chart pattern recognition, job scheduling, data clustering and function optimization. Popov et al. (2006), performed experiments on the basic BA using eight benchmark functions and their results showed that the basic BA could reliably handle complex multi-model optimization problems without being trapped at local optima. This study also revealed that the basic BA generally outperformed other techniques in terms of speed and accuracy of the results. However, the basic BA has two disadvantages: (1) A small No. of trials are needed to set the parameter values and (2) A No. of tunable parameters are used (Pham et al., 2007). The enhanced BA will be used to solve these problems by adding memory to store the social information of bees in nature that they use to choose the patches to visit. These were not included in the basic BA. By adding this natural behavior of bees to the algorithm, the performance is improved.
The objective of the study is to enhance basic BA algorithm by adding two types of memory including: private and social information, which meant for individual bee and the colony, respectively. This enhancement intended to copy the decision making capability of bees.
Bees in nature: Bees live in colonies that can span more than 10 km in different directions with many food sources (Pham et al., 2006). In a colony, the scout bees search for food in the following ways (Gruter and Farina, 2009): (1) Using private information which is “the information acquired via direct interaction with the environment” (Gruter and Farina, 2009). For example, many plants offer nectar during some periods of the day and bees can learn these times of food existence after a few days (Lloyd, 1983; Rowe, 1999; Biesmeijer and de Vries, 2001); (2) Using social information which is “any information acquired through the actions (e.g., waggle dance), body structures (e.g., shapes or colors) or products (e.g., pheromones) of other individuals” (Pham et al., 2007) or (3) Using innate search behaviors to find the best patch (patches with a plentiful amount of nectar or patches that need less effort to collect the nectar).
Based on the information exchanged by the scout bees using the waggle dance on the dance floor, the following information can be obtained (Gil and Farina, 2002): (1) The direction of the patch (based on the sun) (2) The distance (based on the duration of the dance) and (3) The quality (fitness, the amount of nectar). The waggle dance sends different signals with different objectives. The objective of each signal can be one of the following (Pham et al., 2007): (1) Gives different types of information to the surrounding bees, (2) Informs the follower bees about good food sources, (3) Activates private navigational information (if present) and (4) Identifies the location of the food source.
Another type of bees, called follower bees use the scout bees’ information or private information (if it is reliable and present) and social information to go to the best patches. More bees go to the best patches and fewer bees go to the poor patches. A follower bee in a patch collects nectar and monitors the nectar amount. Based on the amount, the bee decides if the patch is still good or not in the next waggle dance. The follower bee based on (Beekman et al., 2007) can (1) be an uncommitted follower, (2) continue the collection of nectar from the patch only, or (3) dance and tell more bees to go to the patch.
Basic BA: The BA is an optimization algorithm based on the nature of bees foraging for food, which was described in the previous section. The steps of the algorithm are (Pham et al., 2006):
The BA requires seven control parameters: the number of scout bees n, the number of sites selected out of n visited sites m, the number of best sites out of m selected sites e, the number of bees recruited for the best e sites nep, the number of bees recruited for the other (m-e) selected sites nsp, the initial size of patches around each scout bee ngh and the maximum iteration number.
Enhancements of the BA: Many enhancements have been added to the BA. Although these enhancements are logical, they do not necessarily describe what happens in nature. The BA enhancements are as follows:
| • | Pheromones by Packianather et al. (2009). They employ bee pheromones to find good food patches. Their work depends on the fact that there are two types of pheromones, releaser pheromones (short term effects) and premier pheromones (long term effects). The releaser pheromones change the behavior of the recipient bee, whereas the primer pheromones change the physiology. They use the pheromones to recruit bees to specific regions, where the amount of pheromones besides the fitness of each patch is used |
| • | Neighborhood shrinking by Ghanbarzadeh (2007). In this study, the authors decrease the ngh parameter value when the algorithm reaches a state where there is little to no improvement in its best candidate solution, thus increasing the solution density around each site |
| • | Site abandoning by Ghanbarzadeh (2007). The site is replaced with a new site when there is no improvement seen even if the new one has a lower fitness. The replaced site will be stored temporarily so that it can be retrieved if necessary |
| • | Fuzzy greedy selection-based BA by Pham and Darwish (2008). The basic BA uses greedy selection to choose the m best patches and the e elite patches out of the patches explored by the scout bees |
MEMORY-BASED BA (MBA)
As mentioned before, many enhancements have been made to the BA, but these algorithms do not mimic all of the natural behaviors of honey bees for food foraging. Based on the experiments described by Bergen et al. (2004), Partan and Marler (2005) and Leadbeater and Chittka (2007), there are foraging behaviors used by honey bees that not taken into account in basic BA. The bees that do not follow the dancers find food patches using their memories (Rowe, 1999), “93% of all foragers with private information about the location of a good food source ignored the dance language” (Grutere et al., 2008). The bees also use social information. In addition, the honey bees have photographic memories (Gil and Farina, 2002).
Based on these observations, basic BA will be enhanced by adding two types of memory: local memory (for private information) and global memory (for social information). These memories will be added to the scout bees along with the follower bees where these bees could (Gruter and Farina, 2009) (1) Use private information about previously visited patches (2) Use social information and (3) Use innate search behaviors. Before adding the local and global memories, the basic BA will be recoded making it object-oriented. The Object-Oriented BA (OOBA) is as follows:
End in OOBA the following structs used to save and handle the memory of each bee:
The following variables are used: imax is the maximum number of iterations, iter is the iteration count, mem-fit and mem bee-pos are arrays used to store the fitness and position of each bee in their memories, id is the identity of the bee being processed, status tracks if this bee will go randomly or if it is one of the best scout bees and type indicates if this bee is a scout bee or a follower bee. Set methods are used to store information and get methods are used to retrieve information. The next two subsections contain an explanation of local and global memory.
Local memory (private information): Local memory or private information is the information acquired from direct interaction with the environment. This information affects the way forager bees (both scout and follower bees) choose the patch to visit and whether it will be based on a waggle dance or not (i.e., choosing a familiar food source). Foragers depend on their own memories to find particular locations when visiting food patches repeatedly (Gruter and Farina, 2009). Private information is important, especially when food patches offer food for several days. The following pseudo code shows the main methods that added for the local memory. The first code is for the near method which determines if the new position of any bee is near its previous one stored in its memory. The naming of this method for follower bees is included in the search neighbor ( ) method and for scout bees in the rest-rand ( ) method.
The radius value for scout bees depends on the solution space size in different dimensions and on the neighborhood size ngh for follower bees, which means that the value of radius will be more than ngh for scout bees and less than ngh for follower bees. The values of x1 and x2 are set by trial and error. Figure 1 shows how various x2 values affect the mean number of evaluations. Another method used to compare private memory (compare fitness) is to see if the bee was in better place before. If it was, then go back to that place. This method is used for both the scout and follower bees and it is called in the iterations ( ) method.
Global memory (social information): In a colony, the scout bees search using private information or social information. Social information is used as a back-up if the private information has proven to be unreliable (Bergen et al., 2004; Laland, 2004; Leadbeater and Chittka, 2007) or outdated or if individuals evaluate this option as unbeneficial.
| Fig. 1: | Effect of choosing x2 variable value on the mean number of evaluations |
Given the fact that experiments on waggle dances are normally performed after the end of the flowering season or in places with few food sources, one would expect private information to be outdated or not available and that foragers would rely more on social information (Gruter and Farina, 2009). Based on the previous observation the importance of social information was shown. Therefore, method to compare the global memory of different scout bees (except the best bees: (m) was added to determine if the present position for any bee is near to any previous position. To do this first store all the information (the position in different dimensions and the fitness of each position) in different iterations for all the bees is needed. See the pseudo code below:
In compare global memory method the distance between two bees compared with (3* ngh) value because of wanting to give more options for the scout bees to find new places that are not stuck on local optima. The call of this method is included in the rest-random method. The next section includes the experimental results.
EXPERIMENTS AND RESULTS
To evaluate the effectiveness of the enhancements (adding local and global memory) to the basic BA, the basic BA, Local-MBA, global-MBA and MBA (combination of Local-MBA and global-MBA) were applied to nine benchmark functions: De Jong, Goldstein and Price, Branin, Martin and Gaddy, Rosenbrock (a and b), Rosenbrock, Hyper Sphere and Griewangk and to two engineering optimization problems: Welded Beam and Spring Design (Yang and Deb, 2010). In these experiments visual C++ 2005 used. The next table shows the values for the BA parameters when applied to the nine benchmark functions and the two engineering optimization problems: welded beam and spring design.
The parameters include the initial population n, the number of selected sites m, the number of elite sites e, the number of bees recruited for best e sites nep, the number of bees recruited for the other (m-e) selected sites nsp and the size of the patches ngh. The dimension denotes the number of dimensions used for each benchmark function and optimization problem. The basic BA and MBA are applied to different problems with different numbers of dimensions and the problems become more difficult with an increasing number of dimensions. The following table shows the results of applying the basic BA, local memory-based BA, global memory-based BA and local and global memory-based BA using the values in Table 1.
In Table 2, the mean number of evaluation results that are obtained when applying the basic BA, local memory-based BA, global memory-based BA and local and global memory-based BA to nine benchmark functions shown. The results show the superiority of the memory-based BA algorithm and how the addition of local memory and global memory affects the results. The best results are for the Branin benchmark function in 2 dimensions when applying local memory, global memory and both local and global memories. The second best result is for the Goldstien and Price benchmark function in 2 dimensions. The third best result is for the Rosenbrock benchmark function in 10 dimensions. The average improvement percentage for local memory is 59.34 and 73.02% for global memory and the best s 74.9% when applying local and global memory together for scout and follower bees.
Tables 3 and 4 show the results when applying the basic BA and memory-based BA (local and global) to the welded beam and spring design problems. It is clear that applying the basic BA gives better results compared with Cagnina et al. (2008) and Yang and Deb (2010) when applying evolutionary and Cuckoo Search on those two problems, respectively. The memory-based BA is superior in fitness values and all other variables. Novel fitness values of two engineering design problems are obtained by applying Memory-based BA algorithm (MBA).
| Table 1: | Parameters values used in basic BA, Local-MBA, global-MBA and MBA algorithm for benchmark functions and the two engineering optimization problems |
| Table 2: | Mean number of evaluations results of basic BA, Local-MBA, Global-MBA and MBA, along with the improvement percentage of each comparing with basic BA when applied to nine benchmark functions |
| Table 3: | Welded beam results of Cagnina et al. (2008), Yang and Deb (2010), basic BA and MBA |
| Table 4: | Spring design results of Cagnina et al. (2008), Yang and Deb (2010), basic BA and MBA |
CONCLUSION
The BA is one of the meta-heuristic algorithms that is used to solve combinatorial and functional problems. It was proposed based on the honey bees’ nature to solve local optima problems and many enhancements have been made to this algorithm. Some of these enhancements are based on natural behaviors; others are not.
In this study, a new enhancement to the basic BA by adding private information (local memory) and social information (global memory) were presented. These types of memory are part of the honey bees’ nature but were not included in basic BA. These two types of memory added for both the follower and the scout bees. The results of applying the BA before and after the enhancements on nine benchmark functions show that the memory-based BA outperforms the basic BA and the improvement percentage exceeds all previous enhancements results (Pham et al., 2006; Packianather et al. 2009; Zaidi et al., 2011). Additionally, the results of applying the memory-based BA on the welded beam and spring design engineering problems are novel results exceed the previous results of Yang and Deb (2010).