1. Introduction
In computer science and operations research, the bee’s algorithm is a population-based search algorithm which was developed by Pham, Ghanbarzadeh et al. in 2005. It mimics the food foraging behaviour of honey bee colonies. In its basic version the algorithm performs a kind of neighborhood search combined with global search, and can be used for both combinatorial optimization and continuous optimization [1]. The only condition for the application of the bee’s algorithm is that some measure of distance between the solutions is defined. The effectiveness and specific abilities of the bee’s algorithm have been proven in a number of studies. During the last decade nature inspired approaches, like Particle Swarm Optimization, Ant Colony Optimization, bees inspired algorithms have become increasingly popular. The bees inspired algorithms are divided, mainly, in two categories according to their behavior in the nature, the foraging behavior and the mating behavior. A colony of honey bees can extend itself over long distances (over 14 km) and in multiple directions simultaneously to harvest nectar or pollen from multiple food sources (flower patches) [2]. A small fraction of the colony constantly searches the environment looking for new flower patches. These scout bees move randomly in the area surrounding the hive, evaluating the profitability (net energy yield) of the food sources encountered. When they return to the hive, the scouts deposit the food harvested. Those individuals that found a highly profitable food source go to an area in the hive called the “dance floor”, and perform a ritual known as the waggle dance. Through the waggle dance a scout bee communicates the location of its discovery to idle onlookers, which join in the exploitation of the flower patch. Since the length of the dance is proportional to the scout’s rating of the food source, more foragers get recruited to harvest the best rated flower patches. After dancing, the scout returns to the food source it discovered to collect more food. As long as they are evaluated as profitable, rich food sources will be advertised by the scouts when they return to the hive. Recruited foragers may waggle dance as well, increasing the recruitment for highly rewarding flower patches. Thanks to this autocatalytic process, the bee colony is able to quickly switch the focus of the foraging effort on the most profitable flower patches [3].
2. Life Cycle of BBMO
Bumblebee colonies have a yearly cycle, except for some tropical bumblebees where the year-round availability of flowers allows colonies to survive for more than one year, and some nests in New Zealand. Queens that have mated in late summer the previous year hibernate, usually in the soil, and emerge in spring [4]. It is usually the first species to emerge in northern Europe. In the north east of Scotland the first queens are usually sighted in late March or early April depending on weather conditions.
These queens haven’t eaten anything since the previous summer, so they are hungry. This is why it is vitally important that they find early flowers to feed [5]. Newly emerged queens eat both nectar and pollen, and it is the pollen that helps her ovaries develops. A bumblebee cannot fly unless her flight muscles are at 30oC, so she has to brave the cold weather to feed or else she will sink into torpor and never wake up. She continues feeding and sheltering at night near the food plants in nooks and crannies for a few weeks until her body signals her that it is time to find a nest site [6].
3. Bumble Bee Mating Optimization (BBMO)
Bumble bees are social insects that form colonies consisting of the queen, many workers (females) and the drones (males). Queens are the only members of the nest to survive from one season to the next, as they spend the winter months hibernating in a protected underground overwintering chamber. Upon emerging from hibernation, a queen collects pollen and nectar from flowers and searches for a suitable nest site and when she finds such a place, she prepares wax pots to store food and wax cells into which eggs are laid. The bumble bee queen can lay fertilized or unfertilized eggs [7]. The fertilized eggs have chromosomes from the queen and a male or males she mated with the develop into workers while the unfertilized eggs contain chromosomes from the queen alone and they develop into males. After the emergence of the first workers, the queen no longer forages as the workers take over the responsibilities of collecting food (foragers) and the queen remains in the nest laying eggs and tending to her young. Some workers, also remain in the nest and help raise the brood (household workers). Males do not contribute in collecting food or helping rear young as the sole purpose of the males are to mate with the queens. Bumble bee workers are able to lay haploid eggs when the queen’s ability to suppress the workers’ reproduction diminishes. These eggs are developed into viable male bumble bees. A few days after the males leave the nest, new queens will emerge. After new queens and males have gone, the colony begins to deteriorate. The founder queen stops laying eggs and grows weak from old age while the remaining workers continue to forage for food but only for themselves. Away from the colony, the new queens and males live off nectar and pollen and spend the night on flowers or in holes. The queens are eventually mated (often more than once), the sperm from the mating is stored in sperm and she searches for a suitable location for diapauses. Three different mating behaviors exist in bumble bees. The first mating behavior is where a male perches on a tall structure and waits for queens to fly by and he will pursue them for mating once one queen is spotted. The second mating behavior is when males create a scent trail, marking their flight path with pheromones and, thus, queens of the same species will be attracted to the pheromones and follow the scent trail. The third mating behavior is where males wait at the entrance of a bumble bee nest for queens to leave [8].
3.1. Steps for Bumble Bee Mating Optimization
- Representation and Evaluation method
- Initial population
- Crossover operators
- Worker phase
- Multiple-descendant BBMO algorithm
3.1.1. Representation and Evaluation method
The solutions are encoded as permutation of n trips without any trip delimiters. These permutations could be interpreted as the order in which a vehicle must visit all the trip nodes, if a unique vehicle were to perform all trips one by one [9]. This function based on a permutation builds an auxiliary graph where each node represents a trip in the solution plus a dummy node. Each arc in this graph represents a feasible extractable route from the permutation.
3.1.2. Initial population
The initial population is an array of n bees, each of which has two fields: the sequence of the permutation of the trip and the cost of the bee (quality), which is computed by the split function. The initial drones are initialized randomly. Each drone bee receives a randomly generated permutation of trips. However, a high-quality permutation can be obtained by merging all the generated routes [10].
3.1.3. Crossover operators
A combined crossover operator is used in the proposed HBMO algorithm. If necessary, the algorithm makes a selection from eight different crossover operators, which are adapted for the permutation problem to generate new broods. These crossovers are one-point crossovers type one and two, two-point crossovers type one and two, three-point crossovers type one and two, the cycle crossover (CX), and the partially matched crossover (PMX), which are adapted for permutation problems [11].
One-point crossover: A random cut point is selected for the two bees. The entire section before the cutting point is copied from the queen bee to the new brood. The missing trips are copied from the selected drone in their order of appearance [12]. This is the first type of one-point crossover. In the second type, the trips after the cutting point are copied from the queen to the brood. The other missing trips are copied from the drone to the brood in their order of appearance [13].
Two-point crossover: Two cutting points are made randomly in the two bees, which obtain three sub-sequences for each bee. This type of crossover copies the second sequence from the queen to the brood and the other two missing sequences are trips that are copied from the drone in their order of appearance. In the second type of this crossover, the trips between the two cutting points are copied from the drone to the brood and the remaining trips are taken from the queen.
Three-point crossover: This crossover produced three cutting points in the two selected bees in order to obtain four different sub-sequences of trips. The first and third sequences are copied from the queen to the new brood and the other missing parts are copied in their order of appearance from the drone [14]. This is the first type of three-point crossover. The second type of this crossover copies the trips from the second and fourth sequences from the drone to the generated brood and the other missing trips are completed from the queen.
3.1.4. Worker phase
In order to enhance the quality of the solutions in the BBMO algorithm, a worker phase is introduced. In bees hive, workers’ job consists mainly in brood care. Thus the worker phase is regarded as a specific heuristic that aims to improve the set of broods. Generally, the worker phase consists of a local search phase in the BBMO algorithm. However, the BBMO algorithm introduces a strict parallelism of the local search phase in the worker phase. By doing so, the BBMO algorithm simulates what really happens in real life. In fact, each worker bee takes care of specific brood by feeding him in order to make him fittest. If the new fittest brood is better than the queen, then here place her. Therefore, the BBMO algorithm combines the mating process and the foraging process of honeybees [15].
3.1.5. Multiple-descendant BBMO algorithm
An extension of the basic BBMO algorithm is also proposed in the present study, which integrates a different crossover scheme. The BBMO mating process aims to mate the queen bee with one of theselected drones, thus the multiple-descendant crossover scheme wasintegrated into the proposed BBMO algorithm. The multiple-descendant crossover scheme is based on the principle that a largersearch space can be explored as the number of descendants isincreased. The proposed BBMO algorithm simultaneously appliesdifferent crossover operators to obtain different new broods from thesame queen and drone [16]. This algorithm simultaneously applies the eightcrossover operators used in the simple version of the BBMO to obtaineight different broods. Next, only the best brood is selected to enter theworker bee phase.
3.2. Flow Chart of BBMO Algorithm
4. Numerical methods of BBMO Algorithm
The basic equations and for more explanation about the equations please see [17]:
5. Applications of BBMO Algorithm
- Function Optimization
- Training classifiers like MLP, LVQ, RBF and SNNs
- Electronic Designs[18]
- Mechanical Designs
- Digital Filter Optimization
- Data Clustering[19]
- Robot control
6. Advantages of BBMO Algorithm
- Very efficient in finding optimal solutions
- Overcoming the problem of local optima
- Bumble Bees Mating Optimization algorithm is a new population-based swarm intelligence algorithm that simulates the mating behavior that a swarm of bumble bees perform [20].
- Bumble Bees Mating Optimization algorithm for the solution of the feature selection problem and a GRASP algorithm for the solution of the clustering problem.
- The performance of this algorithm is tested using various benchmark data sets from the UCI machine learning repository [21].
- One of the most common used ways to solve the problem is the trial and error procedure.
Reference
[1] Marinakis, Y. and Marinaki, M. (2014). A Bumble Bees Mating Optimization algorithm for the Open Vehicle Routing Problem. Swarm and Evolutionary Computation, 15, pp.80-94.
[2] Lenin, K. and Reddy, B. (2014). Bumble Bees Mating Optimization (BBMO) Algorithm for Solving Optimal Reactive Power Dispatch Problem. International Journal of Electronics and Electrical Engineering, 3(4).
[3] Gómez, J. and Romero, M. (1998). Global convergence of a multidirectional algorithm for unconstrained optimal control problems. Numerical Functional Analysis and Optimization, 19(9), pp.995-1023.
[4] Marinaki, M. and Marinakis, Y. (2014). A bumble bees mating optimization algorithm for the feature selection problem. International Journal of Machine Learning and Cybernetics, 7(4), pp.519-538.
[5] Marinakis, Y. and Marinaki, M. (2014). Combinatorial neighborhood topology bumble bees mating optimization for the vehicle routing problem with stochastic demands. Soft Computing, 19(2), pp.353-373.
[6] Zhang, S. and Liu, S. (2019). A Discrete Improved Artificial Bee Colony Algorithm for 0–1 Knapsack Problem. IEEE Access, 7, pp.104982-104991.
[7] Diwold, K., Aderhold, A., Scheidler, A. and Middendorf, M. (2011). Performance evaluation of artificial bee colony optimization and new selection schemes. Memetic Computing, 3(3), pp.149-162.
[8] Storage battery separators and battery electrolytes. (1933). Electrical Engineering, 52(2), pp.130-131.
[9] Harder, L. and Wilson, W. (1994). Floral evolution and male reproductive success: Optimal dispensing schedules for pollen dispersal by animal-pollinated plants. Evolutionary Ecology, 8(5), pp.542-559.
[10] Yilmaz, Z. and Basciftci, F. (2018). Binary Artificial Bee Colony Algorithm to Solve Single Objective Resource Allocation Problem. International Journal of Future Computer and Communication, 7(1), pp.21-25.
[11] Marinakis, Y., Marinaki, M. and Migdalas, A. (2017). An Adaptive Bumble Bees Mating Optimization algorithm. Applied Soft Computing, 55, pp.13-30.
[12] Iqbal, S., Kaykobad, M. and Rahman, M. (2015). Solving the multi-objective Vehicle Routing Problem with Soft Time Windows with the help of bees. Swarm and Evolutionary Computation, 24, pp.50-64.
[13] PourkamaliAnaraki, M. and Sadeghi, M. (2015). Honey bee-inspired algorithms for SNP haplotype reconstruction problem. Journal of Experimental & Theoretical Artificial Intelligence, 28(1-2), pp.201-214.
[14] RASHEED, S. and HARDER, L. (1997). Foraging currencies for non-energetic resources: pollen collection by bumblebees. Animal Behaviour, 54(4), pp.911-926.
[15] Kraus, F., Szentgyörgyi, H., Rożej, E., Rhode, M., Moroń, D., Woyciechowski, M. and Moritz, R. (2010). Greenhouse bumblebees (Bombus terrestris) spread their genes into the wild. Conservation Genetics, 12(1), pp.187-192.
[16] Dorchin, A., Filin, I., Izhaki, I. and Dafni, A. (2012). Movement patterns of solitary bees in a threatened fragmented habitat. Apidologie, 44(1), pp.90-99.
[17] Rajasekhar, A., Lynn, N., Das, S. and Suganthan, P. (2017). Computing with the collective intelligence of honey bees – A survey. Swarm and Evolutionary Computation, 32, pp.25-48.
[18] Erler, S. and Lattorff, H. (2010). The degree of parasitism of the bumblebee (Bombus terrestris) by cuckoo bumblebees (Bombus (Psithyrus) vestalis). Insectes Sociaux, 57(4), pp.371-377.
[19] Nayak, J. and Naik, B. (2018). A Novel Honey-Bees Mating Optimization Approach with Higher order Neural Network for Classification. Journal of Classification, 35(3), pp.511-548.
[20] Ramírez, S., Nieh, J., Quental, T., Roubik, D., Imperatriz-Fonseca, V. and Pierce, N. (2010). A molecular phylogeny of the stingless bee genus Melipona (Hymenoptera: Apidae). Molecular Phylogenetics and Evolution, 56(2), pp.519-525.
[21] Susanto, F., Gillard, T., De Souza, P., Vincent, B., Budi, S., Almeida, A., Pessin, G., Arruda, H., Williams, R., Engelke, U., Marendy, P., Hirsch, P. and He, J. (2018). Addressing RFID Misreadings to Better Infer Bee Hive Activity. IEEE Access, 6, pp.31935-31949.