第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
An idea based on honey bee swarm for numerical optimization.pdf
I. 介绍
II. 蜂群的行为
III. 建议和方法
IV. 仿真结果
AN IDEA BASED ON HONEY BEE SWARM FOR NUMERICAL OPTIMIZATION
(TECHNICAL REPORT-TR06, OCTOBER, 2005)
Dervis KARABOGA
karaboga@erciyes.edu.tr
Erciyes University, Engineering Faculty
Computer Engineering Department
Kayseri/Türkiye
I. INTRODUCTION
Swarm intelligence has become a research interest to many research scientists of related fields
in recent years. Bonabeau has defined the swarm intelligence as “any attempt to design
algorithms or distributed problem-solving devices inspired by the collective behaviour of
social insect colonies and other animal societies” [1]. Bonabeau et al. focused their viewpoint
on social insects alone such as termites, bees, wasps as well as other different ant species.
However, the term swarm is used in a general manner to refer to any restrained collection of
interacting agents or individuals. The classical example of a swarm is bees swarming around
their hive; nevertheless the metaphor can easily be extended to other systems with a similar
architecture. An ant colony can be thought of as a swarm whose individual agents are ants.
Similarly a flock of birds is a swarm of birds. An immune system [2] is a swarm of cells and
molecules as well as a crowd is a swarm of people [3]. Particle Swarm Optimization (PSO)
Algorithm models the social behaviour of bird flocking or fish schooling [4].
Two fundamental concepts, self-organization and division of labour, are necessary and
sufficient properties to obtain swarm intelligent behaviour such as distributed problem-
solving systems that self-organize and adapt to the given environment:
a) Self-organization can be defined as a set of dynamical mechanisms, which result in
structures at the global level of a system by means of interactions among its low-level
components. These mechanisms establish basic rules for the interactions between the
components of the system. The rules ensure that the interactions are executed on the basis of
purely local information without any relation to the global pattern. Bonabeau et al. have
characterized four basic properties on which self organization relies: Positive feedback,
negative feedback, fluctuations and multiple interactions [1]:
i) Positive feedback is a simple behavioural “rules of thumb” that promotes the
creation of convenient structures. Recruitment and reinforcement such as trail laying and
following in some ant species or dances in bees can be shown as the examples of positive
feedback.
ii) Negative feedback counterbalances positive feedback and helps to stabilize the
collective pattern. In order to avoid the saturation which might occur in terms of available
foragers, food source exhaustion, crowding or competition at the food sources, a negative
feedback mechanism is needed.
iii) Fluctuations such as random walks, errors, random task switching among swarm
individuals are vital for creativity and innovation. Randomness is often crucial for emergent
structures since it enables the discovery of new solutions.
iv) In general, self organization requires a minimal density of mutually tolerant
individuals, enabling them to make use of the results from their own activities as well as
others.
b) Inside a swarm, there are different tasks, which are performed simultaneously by
specialized individuals. This kind of phenomenon is called division of labour. Simultaneous
task performance by cooperating specialized individuals is believed to be more efficient than
the sequential task performance by unspecialized individuals [2,5-7]. Division of labour also
enables the swarm to respond to changed conditions in the search space. Two fundamental
concepts for the collective performance of a swarm presented above, self-organization and
division of labour are necessary and sufficient properties to obtain swarm intelligent
behaviour such as distributed problem-solving systems that self-organize and -adapt to the
given environment.
II. BEHAVIOUR OF HONEY BEE SWARM
The minimal model of forage selection that leads to the emergence of collective intelligence
of honey bee swarms consists of three essential components: food sources, employed foragers
and unemployed foragers and the model defines two leading modes of the behaviour: the
recruitment to a nectar source and the abandonment of a source.
i) Food Sources: The value of a food source depends on many
factors such as its proximity to the nest, its richness or concentration
of its energy, and the ease of extracting this energy. For the sake of
simplicity, the “profitability” of a food source can be represented with
a single quantity [8].
ii) Employed
foragers: They are
associated with a particular food source which they are currently
exploiting or are “employed” at. They carry with them information
about this particular source, its distance and direction from the nest,
the profitability of the source and share this information with a
certain probability.
iii) Unemployed foragers: They are continually at look out
for a food source to exploit. There are two types of unemployed
foragers: scouts, searching the environment surrounding the
nest for new food sources and onlookers waiting in the nest and
establishing a food source through the information shared by employed foragers. The mean
number of scouts averaged over conditions is about 5-10% [8].
The exchange of information among bees is the most important occurrence in the formation of
the collective knowledge. While examining the entire hive it is possible to distinguish
between some parts that commonly exist in all hives. The most important part of the hive with
respect to exchanging information is the dancing area. Communication among bees related to
the quality of food sources takes place in the dancing area. This dance is called a waggle
dance.
Since information about all the current rich sources is available to an onlooker on the dance
floor, probably she can watch numerous dances and decides to employ herself at the most
profitable source. There is a greater probability of onlookers choosing more profitable sources
since more information is circulated about the more profitable sources. Employed foragers
share their information with a probability proportional to the profitability of the food source,
and the sharing of this information through waggle dancing is longer in duration. Hence, the
recruitment is proportional to the profitability of the food source [9].
In order to understand the basic behaviour characteristics of foragers better, let us examine
Figure 1. Assume that there are two discovered food sources: A and B. At the very beginning,
a potential forager will start as unemployed forager. That bee will have no knowledge about
the food sources around the nest. There are two possible options for such a bee:
some internal motivation or possible external clue (S on Figure 1).
source (R on Figure 1).
After locating the food source, the bee utilizes its own capability to memorize the location and
then immediately starts exploiting it. Hence, the bee will become an “employed forager”. The
i) It can be a scout and starts searching around the nest spontaneously for a food due to
ii) It can be a recruit after watching the waggle dances and starts searching for a food
i) It becomes an uncommitted follower after abandoning the food source (UF).
ii) It dances and then recruits nest mates before returning to the same food source (EF1)
iii) It continues to forage at the food source without recruiting other bees (EF2).
foraging bee takes a load of nectar from the source and returns to the hive and unloads the
nectar to a food store. After unloading the food, the bee has the following three options:
It is important to note that not all bees start foraging simultaneously. The experiments
confirmed that new bees begin foraging at a rate proportional to the difference between the
eventual total number of bees and the number of present foraging.
Figure 1. The behaviour of honey bee foraging for nectar
i)
ii)
In the case of honey bees, the basic properties on which self organization relies are as follows:
Positive feedback: As the nectar amount of food sources increases, the number of
onlookers visiting them increases, too.
Negative feedback: The exploration process of a food source abandoned by bees
is stopped.
Fluctuations: The scouts carry out a random search process for discovering new
food sources.
iii)
iv) Multiple interactions: Bees share their information about food source positions
with their nest mates on the dance area.
III. PROPOSED APPROACH
In this work, a particular intelligent behaviour of a honey bee swarm, foraging behaviour, is
considered and a new artificial bee colony (ABC) algorithm simulating this behaviour of real
honey bees is described for solving multidimensional and multimodal optimisation problems.
In the model, the colony of artificial bees consists of three groups of bees: employed bees,
onlookers and scouts. The first half of the colony consists of the employed artificial bees and
the second half includes the onlookers. For every food source, there is only one employed
bee. In other words, the number of employed bees is equal to the number of food sources
around the hive. The employed bee whose food source has been exhausted by the bees
becomes a scout. The main steps of the algorithm are given below:
Send the scouts onto the initial food sources
REPEAT
Send the employed bees onto the food sources and determine their nectar amounts
Calculate the probability value of the sources with which they are preferred by the
onlooker bees
Stop the exploitation process of the sources abandoned by the bees
Send the scouts into the search area for discovering new food sources, randomly
Memorize the best food source found so far
UNTIL (requirements are met)
Each cycle of the search consists of three steps: moving the employed and onlooker bees onto
the food sources and calculating their nectar amounts; and determining the scout bees and
directing them onto possible food sources. A food source position represents a possible
solution to the problem to be optimized. The amount of nectar of a food source corresponds to
the quality of the solution represented by that food source. Onlookers are placed on the food
sources by using a probability based selection process. As the nectar amount of a food source
increases, the probability value with which the food source is preferred by onlookers
increases, too. Every bee colony has scouts that are the colony’s explorers [10]. The explorers
do not have any guidance while looking for food. They are primarily concerned with finding
any kind of food source. As a result of such behaviour, the scouts are characterized by low
search costs and a low average in food source quality. Occasionally, the scouts can
accidentally discover rich, entirely unknown food sources. In the case of artificial bees, the
artificial scouts could have the fast discovery of the group of feasible solutions as a task. In
this work, one of the employed bees is selected and classified as the scout bee. The selection
is controlled by a control parameter called "limit". If a solution representing a food source is
not improved by a predetermined number of trials, then that food source is abandoned by its
employed bee and the employed bee is converted to a scout. The number of trials for releasing
a food source is equal to the value of "limit" which is an important control parameter of ABC.
In a robust search process exploration and exploitation processes must be carried out together.
In the ABC algorithm, while onlookers and employed bees carry out the exploitation process
in the search space, the scouts control the exploration process.
In the case of real honey bees, the recruitment rate represents a “measure” of how quickly the
bee swarm locates and exploits the newly discovered food source. Artificial recruiting process
could similarly represent the “measurement” of the speed with which the feasible solutions or
the optimal solutions of the difficult optimization problems can be discovered. The survival
and progress of the real bee swarm depended upon the rapid discovery and efficient utilization
of the best food resources. Similarly the optimal solution of difficult engineering problems is
connected to the relatively fast discovery of “good solutions” especially for the problems that
need to be solved in real time.
IV. SIMULATION RESULTS
In the simulation studies, Artificial Bee Colony (ABC) Algorithm was applied for finding the
global minimum of the well-known three test functions. One of the functions is Sphere
function that is continuous, convex and unimodal function. xr is in the interval [-100, 100].
Global minimum value
is
r
xopt
. The second function is a well known classic optimization
problem: Rosenbrock valley. The global optimum is inside a long, narrow, parabolic shaped
flat valley. Therefore, it is very difficult to converge the global optimum. Variables of the
function are strongly dependent, and the gradients generally do not point towards the
optimum. xr is in the interval [-2.048, 2.048], the global minimum value is 0; and the
optimum solution is
. The global optimum of the function is the only
the optimum solution
for
)0,...,0,0(
is 0 and
function
,...,
x
(
xx
,
1
2
this
=
=
)1,1(
)
5
=
r
xopt
=
(
xx
,
1
2
)
optimum and the function is unimodal. The third function is Rastrigin function which is based
on Sphere function with the addition of cosine modulation to produce many local minima. xr
is in the interval [-600, 600] and the minimum value is 0. The optimum solution for this
function is
)0,...,0,0(
,...,
=
=
r
xopt
(
xx
,
1
2
x
10
)
Table 1: Benchmark functions tested by the ABC Algorithm
Functions
Ranges
−
≤
5
100
r
xf
)(
1
=
f
2
=r
x
)(
∑
ix
2
i
1
=
100(x
−
2
)x
2
1
+
(x
1
2
2
−
1
)
Minimum Value
≤
100
=r
0)0(f
1
ix
−
−
048.2
≤
ix
≤
048.2
r
(f
0)
=12
600
≤
x
i ≤
600
=r
0)0(f
2
r
)x(f
3
10
= ∑
1i
=
(x
2
i
−
10cos(2
)x
π
i
+
10)
In the ABC algorithm, the maximum number of cycles was taken as 2000. The percentages of
onlooker bees and employed bees were %50 of the colony and the number of scout bees was
selected to be one. The increase in the number of scouts encourages the exploration process
while the increase of onlookers on a food source encourages the exploitation process.
Parameters adopted for the ABC algorithm are given in Table 2.
Table 2: Control parameters adopted for the ABC algorithm
Control parameters of ABC Algorithm
20
Number of onlooker bees *Dim.
50% of the swarm
50% of the swarm
1
swarmsize
limit
number of onlookers
number of employed bees
number of scouts
Each of the experiments was repeated 30 times with different random seeds and the average
function values of the best solutions were recorded. The mean and the standard deviations of
the function values obtained by ABC algorithm for the same conditions are given in Table 3.
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
