Bees algorithm
Encyclopedia
In computer science
and operations research
, the bees algorithm is a population-based search algorithm
first developed in 2005. It mimics the food foraging behaviour of swarms of honey bees. In its basic version, the algorithm performs a kind of neighbourhood search combined with random search and can be used for both combinatorial optimization
and functional optimisation.
The foraging process begins in a colony by scout bees being sent to search for promising flower patches. Scout bees move randomly from one patch to another. During the harvesting season, a colony continues its exploration, keeping a percentage of the population as scout bees.
When they return to the hive, those scout bees that found a patch which is rated above a certain quality threshold (measured as a combination of some constituents, such as sugar content) deposit their nectar or pollen and go to the “dance floor” to perform a dance known as the waggle dance
.
This dance is essential for colony communication, and contains three pieces of information regarding a flower patch: the direction in which it will be found, its distance from the hive and its quality rating (or fitness). This information helps the colony to send its bees to flower patches precisely, without using guides or maps. Each individual’s knowledge of the outside environment is gleaned solely from the waggle dance. This dance enables the colony to evaluate the relative merit of different patches according to both the quality of the food they provide and the amount of energy needed to harvest it. After waggle dancing inside the hive, the dancer (i.e. the scout bee) goes back to the flower patch with follower bees that were waiting inside the hive. More follower bees are sent to more promising patches. This allows the colony to gather food quickly and efficiently.
While harvesting from a patch, the bees monitor its food level. This is necessary to decide upon the next waggle dance when they return to the hive. If the patch is still good enough as a food source, then it will be advertised in the waggle dance and more bees will be recruited to that source.
The pseudo code for the bees algorithm in its simplest form:
1. Initialise population with random solutions.
2. Evaluate fitness of the population.
3. While (stopping criterion not met) //Forming new population.
4. Select sites for neighbourhood search.
5. Recruit bees for selected sites (more bees for best e sites) and evaluate fitnesses.
6. Select the fittest bee from each patch.
7. Assign remaining bees to search randomly and evaluate their fitnesses.
8. End While.
In first step, the bees algorithm starts with the scout bees (n) being placed randomly in the search space. In step 2, the fitnesses of the sites visited by the scout bees are evaluated.
In step 4, bees that have the highest fitnesses are
chosen as “selected bees” and sites visited by them
are chosen for neighbourhood search. Then, in steps
5 and 6, the algorithm conducts searches in the
neighbourhood of the selected sites, assigning more
bees to search near to the best e sites. The bees can
be chosen directly according to the fitnesses
associated with the sites they are visiting.
Alternatively, the fitness values are used to
determine the probability of the bees being selected.
Searches in the neighbourhood of the best e sites
which represent more promising solutions are made
more detailed by recruiting more bees to follow them
than the other selected bees. Together with scouting,
this differential recruitment is a key operation of the
Bees Algorithm. However, in step 6, for each patch only the bee
with the highest fitness will be selected to form the
next bee population. In nature, there is no such a
restriction. This restriction is introduced here to
reduce the number of points to be explored. In step 7,
the remaining bees in the population are assigned
randomly around the search space scouting for new
potential solutions. These steps are repeated until a
stopping criterion is met. At the end of each iteration,
the colony will have two parts to its new population –
those that were the fittest representatives from a patch
and those that have been sent out randomly.
The honey bees' effective foraging strategy can be applied to job shop scheduling problems.
A feasible solution in a job shop scheduling problem is a complete schedule of operations specified in the problem. Each solution can be thought of as a path from the hive to the food source. The figure on the right illustrates such an analogy
The makespan of the solution is analogous to the profitability of the food source in terms of distance and sweetness of the nectar. Hence, the shorter the makespan, the higher the profitability of the solution path.
We can thus maintain a colony of bees, where each bee will traverse a potential solution path. Once a feasible solution is found, each bee will return to the hive to perform a waggle dance
. The waggle dance will be represented by a list of "elite solutions", from which other bees can choose to follow another bee's path. Bees with a better makespan will have a higher probability of adding its path to the list of "elite solutions", promoting a convergence to an optimal solution.
Using the above scheme, the natural honey bee's self organizing foraging strategy can be applied to the job shop scheduling problem.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
and operations research
Operations research
Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...
, the bees algorithm is a population-based search algorithm
Search algorithm
In computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots...
first developed in 2005. It mimics the food foraging behaviour of swarms of honey bees. In its basic version, the algorithm performs a kind of neighbourhood search combined with random search and can be used for both combinatorial optimization
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
and functional optimisation.
The foraging process in nature
A colony of honey bees can extend itself over long distances (up to 14 km) and in multiple directions simultaneously to exploit a large number of food sources. A colony prospers by deploying its foragers to good fields. In principle, flower patches with plentiful amounts of nectar or pollen that can be collected with less effort should be visited by more bees, whereas patches with less nectar or pollen should receive fewer bees.The foraging process begins in a colony by scout bees being sent to search for promising flower patches. Scout bees move randomly from one patch to another. During the harvesting season, a colony continues its exploration, keeping a percentage of the population as scout bees.
When they return to the hive, those scout bees that found a patch which is rated above a certain quality threshold (measured as a combination of some constituents, such as sugar content) deposit their nectar or pollen and go to the “dance floor” to perform a dance known as the waggle dance
Waggle dance
Waggle dance is a term used in beekeeping and ethology for a particular figure-eight dance of the honey bee. By performing this dance, successful foragers can share with their hive mates information about the direction and distance to patches of flowers yielding nectar and pollen, to water...
.
This dance is essential for colony communication, and contains three pieces of information regarding a flower patch: the direction in which it will be found, its distance from the hive and its quality rating (or fitness). This information helps the colony to send its bees to flower patches precisely, without using guides or maps. Each individual’s knowledge of the outside environment is gleaned solely from the waggle dance. This dance enables the colony to evaluate the relative merit of different patches according to both the quality of the food they provide and the amount of energy needed to harvest it. After waggle dancing inside the hive, the dancer (i.e. the scout bee) goes back to the flower patch with follower bees that were waiting inside the hive. More follower bees are sent to more promising patches. This allows the colony to gather food quickly and efficiently.
While harvesting from a patch, the bees monitor its food level. This is necessary to decide upon the next waggle dance when they return to the hive. If the patch is still good enough as a food source, then it will be advertised in the waggle dance and more bees will be recruited to that source.
The Bees Algorithm
The Bees Algorithm is an optimisation algorithm inspired by the natural foraging behaviour of honey bees to find the optimal solution. The algorithm requires a number of parameters to be set, namely: number of scout bees (n), number of sites selected out of n visited sites (m), number of best sites out of m selected sites (e), number of bees recruited for best e sites (nep), number of bees recruited for the other (m-e) selected sites (nsp), initial size of patches (ngh) which includes site and its neighbourhood and stopping criterion.The pseudo code for the bees algorithm in its simplest form:
1. Initialise population with random solutions.
2. Evaluate fitness of the population.
3. While (stopping criterion not met) //Forming new population.
4. Select sites for neighbourhood search.
5. Recruit bees for selected sites (more bees for best e sites) and evaluate fitnesses.
6. Select the fittest bee from each patch.
7. Assign remaining bees to search randomly and evaluate their fitnesses.
8. End While.
In first step, the bees algorithm starts with the scout bees (n) being placed randomly in the search space. In step 2, the fitnesses of the sites visited by the scout bees are evaluated.
In step 4, bees that have the highest fitnesses are
chosen as “selected bees” and sites visited by them
are chosen for neighbourhood search. Then, in steps
5 and 6, the algorithm conducts searches in the
neighbourhood of the selected sites, assigning more
bees to search near to the best e sites. The bees can
be chosen directly according to the fitnesses
associated with the sites they are visiting.
Alternatively, the fitness values are used to
determine the probability of the bees being selected.
Searches in the neighbourhood of the best e sites
which represent more promising solutions are made
more detailed by recruiting more bees to follow them
than the other selected bees. Together with scouting,
this differential recruitment is a key operation of the
Bees Algorithm. However, in step 6, for each patch only the bee
with the highest fitness will be selected to form the
next bee population. In nature, there is no such a
restriction. This restriction is introduced here to
reduce the number of points to be explored. In step 7,
the remaining bees in the population are assigned
randomly around the search space scouting for new
potential solutions. These steps are repeated until a
stopping criterion is met. At the end of each iteration,
the colony will have two parts to its new population –
those that were the fittest representatives from a patch
and those that have been sent out randomly.
Applications
The Bees Algorithm has found many applications in engineering, such as:- Training neural networks for pattern recognition.
- Forming manufacturing cells.
- Scheduling jobs for a production machine.
- Solving continuous problems and engineering optimization.
- Finding multiple feasible solutions to a preliminary design problems.
- Data clustering
- Optimising the design of mechanical components.
- Multi-Objective Optimisation.
- Tuning a fuzzy logic controller for a robot gymnast.
- Computer Vision and Image Analysis.
In Job Shop Scheduling
A feasible solution in a job shop scheduling problem is a complete schedule of operations specified in the problem. Each solution can be thought of as a path from the hive to the food source. The figure on the right illustrates such an analogy
The makespan of the solution is analogous to the profitability of the food source in terms of distance and sweetness of the nectar. Hence, the shorter the makespan, the higher the profitability of the solution path.
We can thus maintain a colony of bees, where each bee will traverse a potential solution path. Once a feasible solution is found, each bee will return to the hive to perform a waggle dance
Waggle dance
Waggle dance is a term used in beekeeping and ethology for a particular figure-eight dance of the honey bee. By performing this dance, successful foragers can share with their hive mates information about the direction and distance to patches of flowers yielding nectar and pollen, to water...
. The waggle dance will be represented by a list of "elite solutions", from which other bees can choose to follow another bee's path. Bees with a better makespan will have a higher probability of adding its path to the list of "elite solutions", promoting a convergence to an optimal solution.
Using the above scheme, the natural honey bee's self organizing foraging strategy can be applied to the job shop scheduling problem.
See also
- Evolutionary computationEvolutionary computationIn computer science, evolutionary computation is a subfield of artificial intelligence that involves combinatorial optimization problems....
- Swarm intelligenceSwarm intelligenceSwarm intelligence is the collective behaviour of decentralized, self-organized systems, natural or artificial. The concept is employed in work on artificial intelligence...
- Manufacturing Engineering CentreManufacturing Engineering CentreThe Manufacturing Engineering Centre is an international R&D Centre of Excellence for Advanced Manufacturing and Information Technology. The Centre forms part of Cardiff University, which dates back to 1883 and is one of Britain's major civic universities.The MEC was founded in 1996 by Professor,...
- Particle swarm optimizationParticle swarm optimizationIn computer science, particle swarm optimization is a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality...
- Ant colony optimization algorithms
- Invasive weed optimization algorithm
- Intelligent Water Drops