Particle S warm Simulation 159
x
i
, to renew its memory and forget the old one. If a food source c annot
be improved upon within a predetermined number of iterations, defined as
Limit, this food source is abandoned. The bee that was exploiting t his food
site b e c omes a scout and associates itself with a new food site that is chosen
via some principle. In canonical ABC [65], the scout looks for a new food site
by random initialization.
The details of the ABC algorithm are described below. The pseudocode of
the algorithm is shown in Algorithm 1.
Step 0: Preparation The total number of search points (N ), to tal number of
trips (T
max
), and a scout control par ameter (Limit) are initialized. The
numbers of employed bees and onlooker bees are set to be the same
as the total number of search points (N). The value of the objective
function f is taken to be non-neg ative, with larger values being better.
Step 1: Initialization 1 The trip counter k is set to 1, and the number of
search point updates s
i
is set to 0. The initial position vector for each
search point x
i
= (x
i1
, x
i2
, x
i3
, ··· , x
id
)
T
is assigned random values.
Here, the subscript i (i = 1, ··· , N) is the index of the search point,
and d is the number of dimensions in the sea rch spac e .
Step 2: Initialization 2 Determine the initial best solution best.
i
g
= a rgmax
i
f(x
i
) (6.10)
best = x
i
g
(6.11)
Step 3: Employed be e search The following equation is used to calculate
a new position vector v
ij
from the current position vector x
ij
.
v
ij
= x
ij
+ φ · (x
ij
− x
kj
) (6.12)
Here, j is a randomly chosen dimensional number, k is the index for
some randomly chosen search point other than i, and φ is a uniform
random number in the range [−1, 1]. The position vector x
i
and the
number of search point updates s
i
are determined according to the
following equation:
I = {i | f (x
i
) < f(v
i
)} (6.13)
x
i
=
v
i
i ∈ I
x
i
i /∈ I
(6.14)
s
i
=
0 i ∈ I
s
i
+ 1 i /∈ I
(6.15)
Step 4: Onlooker bee search The following two steps are performed.
160 Agent-Based Modeling and Simulation with Swarm
Algorithm 1 The ABC algorithm
Require: T
max
, #. of employed bees (=No. of onlooker bees),Limit
Initialize food sources
Evaluate food sources
i = 1
while i < T
max
do
Use employed bees to produce new solutions
Evaluate the new solutions and apply greedy selection process
Calculate the probability values us ing fitness values
Use onlooker bees to produce new solutions
Evaluate new solutions and apply greedy selection process
Determine abandoned s olutions and use scouts to generate new ones ran-
domly
Remember the best solution found s o far
i = i + 1
end while
Return b e st solution
1. Relative ranking o f s e arch points
The r e lative probability P
i
is calculated from the fitness f it
i
, which
is based on the evaluation score of each search p oint. Note that
fit
i
= f (x
i
). The onlooker bee search counter l is s e t to 1.
P
i
=
fit
i
P
N
j=1
fit
j
(6.16)
2. Roulette selection and search point updating
Search points are selected for updating based on the probability P
i
,
calculated above. After search p oints have been selected, perform a
procedure as in Step 3 to update the se arch point position vectors.
Then, let l = l + 1 and repeat until l = N.
Step 5: Scout bee search Given a se arch point for which s
i
≥Limit, ra n-
dom numbers are used to exchange generated search points.
Step 6: Update best solution Update the best solution best.
i
g
= a rgmax
i
f(x
i
) (6.17)
best = x
i
g
when f(x
i
g
) > f(best) (6.18)
(6.19)
Step 7: End determination End if k = T
max
. Otherwise, let k = k + 1 and
return to Step 3.
Particle S warm Simulation 161
FIGURE 6.22: ABC simulator with Swarm.
ABC has recently been improved in many aspects. For instance, we ana-
lyzed the mechanism of ABC to s how a po ssible drawback of using parame-
ter perturbation. To overcome this deficiency, we have proposed a new non-
separable operator and embedded it in the main framework of the cooperatio n
mechanism of bee foraging (see [47] for details).
A swarm-based ABC simulation has been provided (Fig. 6.22). In this im-
plementation of ABC, optimization is performed using CEC2005 benchmark
functions [110] a s the objective function set. Figure 6.23 s hows an example of
optimizing the F
8
Shifted Rotated Ackley’s function. When scout bees find a
local solution one can see them actively approaching an optimal solution. In
the window on the left, the movement o f employed bees will be in gre e n, that
of onlooker bees will be in yellow, and that of scouts will be drawn in red. The
window to the upper right shows the average and maximum fitness values by
generation. The window in the bottom right shows the number of scout bees
over time.
Control of ABC is as follows (Fig. 6.22).
• Start button
Starts the simulation.
• Stop button
Pauses the simulation.
• Next button
Advances the simulation one time step.
• Save button
Not used in this simulation.
• Quit button
Terminates the simulation.
162 Agent-Based Modeling and Simulation with Swarm
(a) (b)
(c)
FIGURE 6.23: ABC optimization with Swarm.
• ObserverSwarm parameter probe
– displayFrequency: Screen refresh frequency
– zoomFactor: Display zoom factor
• ModelSwarm parameter probe
– seed: Random number generator seed
– worldXSize,worldYSize: ABC screen w idth
– beeNum: Number of bees (= number o f search points)
– limit: Scout bee activation parameter
– tmax: Maximum number of generations. When tmax= 0, the simu-
lation will continue to run until “stop” is pressed.
– functype: Benchmark function settings
– dim: Dimensions in the simulation space
ModelSwarm parameters can be changed before the simulation starts (be-
fore pressing “Start” or “Next”). Note that changed parameters will not take
effect until the Enter key is pre ssed after input.
The objective functions implemented are F
1
–F
12
of the CEC2005 bench-
mark functions [110] (see also Fig. A.2; note that these functions are differ-
ently numbered). Setting the parameter functype to a value 1–1 2 will set the
associated function as the objective function.
Particle S warm Simulation 163
An arbitrary function can be defined as the objective function. For this
purpose, after setting the desired function, you should proceed as follows:
1. Change the following parts of ModelSwarm.java (the setFunc and func
functions) and ma ke appropria te definitions under case 0.
/* Define range */
void setFunc(){
....
case 0:
xMax= (define this here; range will be [-xMax,xMax])
break;
....
....
/* Define function */
double func(double po[]){
....
case 0:
result = (The function result;
point coordinates are stored in po[], dimensions
in dim)
break;
....
2. After recompiling, execute as functype:0.
It is also possible to change the dimensions and domain of the function.
Note that the display in the left Swarm window is for two dimensions.
6.6 BUGS: a bug-based search str ategy
This sec tion describes another new approach to strateg ic learning, based on
the concept of swarm intelligence. Simple GAs optimize functions by adaptive
combination (crossover) of coded solutions to problems (i.e., points in the
problem’s search spa c e ). In this approach, an analogy is made between the
value (at a given po int) of a function to be maximized and the dens ity of
bacteria at that point. More specifically, the adaptive learning used in this
system, called BUGS (a bug-based search strategy), is due to evolving choice of
directions, rather tha n positions (as with usual r e al-valued GA methods) [55].
The bug s evolved by the BUGS progra m learn to search for bacteria in the
highest density regions and are thus likely to move toward those points where
the function has a maximum value. This strategy combines a hill- c limbing
mechanism with the adaptive method of GA, and thus overcomes the usual
weakness of simple GAs (which do not include such local search mechanisms).
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.