2011 International Workshop on Nonlinear Maps and their Applications
NOMA'11, Evora, Portugal, September 15-16, 2011

Investigation of Behavior of Bee Colony
Optimization with Role and Responsibility
Yudai Shirasaki, Sho Shimomura, Yoko Uwate and Yoshifumi Nishio
Dept. Electrical and Electronic Eng.,
Tokushima University
Email: {shirasaki, s-sho, uwate, nishio}@ee.tokushima-u.ac.jp

Abstract—In previous study, we proposed Bee Colony Optimization with Role and Responsibility (BCOR&R) as new Bee
Colony Optimization (BCO). BCOR&R has two kind of searchmethods like an actual honeybee. One is the global search to doa wide area search, another is the local search to do a small areasearch. In this study, we investigate the behavior of BCOR&R bychanging the range of local search and the formation time of local
search (after a period of time, initialization and re-formation) for
solving Traveling Salesman Problem (TSP).

PL are updated. After a fixed period of time (t < tlimit ), recruitbees Mi do local search using GL. The number of search cities
is reduced (Nl = N ∗ LS range ) using the GL of global search.
As shown in a Fig. 1, the starting point and a terminal point
are fixed, and a local search is performed in two points. N-cityof TSP denoted as follows.
S ≡ P1 , P2 , ..., PN , Pi ≡ (xi , yi )(1)

City coordinates are normalized from 0 to 1, and Pi is the city
coordinate of i-th (i = 1, 2, ..., N)DI. Introduction
Traveling Salesman Problem (TSP) is known as one of the
combinatorial optimization problems, the task is to find theshortest possible tour that each city exactly once. Althoughsmall number of cities is easy to solve the problem, many
number of cities become more diﬃcult to solve. By swarm
intelligence, Ant Colony Optimization (ACO) [1] [2] andParticle Swarm Optimization (PSO) [3] are often generally
used for solution of TSP. In this time, we use Bee Colony
Optimization (BCO) [4]- [6]for solve TSP. BCO has two kindof lists, Personal tour List (PL) and Global tour List (GL).
PL is the optimal tour list of each bee. When better tour isdiscovered, PL is updated. And, GL is the optimal tour list ofall bees. In the all PL, the best evaluation PL become GL.
In our previous study, we have proposed Bee Colony
Optimization with Role and Responsibility (BCOR&R) as new
Bee Colony Optimization algorithm for TSP. The feature ofBCOR&R is to have two kind of search methods, global searchand local search. Global search is the same as the standard
BCO’s. Local search is new search method in BCOR&R. In
local search, the cities of all are divided into a small group. The
optimal tour of the group is searched. When the optimal tourof the group is updated, the tour information of local searchis exported to global search. BCOR&R can be to explore toall the corners of large area by combining the two types ofsearch.
In this study, we investigate the influence of the local searchby changing the range of local area.
II. Bee Coloy Optimization with Role and Responsibility(BCOR&R)
For comparison with the standard BCO, the importantfeature of BCOR&R has two kind of search methods, global
search and local search. At initial phase, search-bees Mi (i =1, 2, ..., mi ) do global search. And, the evaluated tour in GL and- 59 -Step. 1 (Initialization): BCOR&R lets a generation step t =0 and the initialization count of local search tR = 0.
Step. 2 (Find tour): The global tour of M bees is created.
A local search is started after (t > tlocal ).
pi j,n (t) = ∑[ρi j,n ]α · [ d1i j ]βj∈Ai,n [ρi j,n ]α · [ 1 ]βdi j(2)Where ρi j,n is the arc fitness from city i to city jafter n transitions and di j represents the distance
between city i and city j. Note that the di j is inversely
proportional to the city distance. In other words, theshorter the distance, the higher is the likelihood ofthat city to be selected. Where α and β are controlparameters.
Arc fitness ρi j,n is defined as blow. (0 ≤ λ ≤ 1)
λ, j ∈ Fi,n , |Ai,n | > 1 






 1−λ|Ai,n ∩Fi,n |,j<F,|A|>
1
ρi j,n = (3)i,ni,n|A−F|
i,ni,n 1, |Ai,n | = 1
Step. 3 (Evaluation): Evaluate tours, and the probability offollowing a waggle dance is calculated.
1P fi = , Li = tour length
(4)
LiM
1 ∑i
P fi
P fcolony =(5)P fi , GL(t) =Nbee i=1
P fcolony
Where P fi is the profitability score of bee i andP fcolony is the bee colony’s average profitability andis updated after each bee completes its tour.
The following Table I shows the probability which
each bee M use GL(t) or PLi (t), at the time of (t +1).

TABLE I
Probability of following Waggle DanceProfitability Scores
P fi < 0.95P fcolony
0.95P fcolony ≤ P fi < 0.975P fcolony
0.975P fcolony ≤ P fi < 0.99P fcolony
0.99P fcolony ≤ P fi ≤ P fiP f ollow
0.80
0.20
0.02
0and re-formation new local search group.
Step. 5 BCOR&R let t = t + 1 and tR (t + 1) = tR (t) + 1.
BCOR&R goes back to [Step. 2], and repeats until
T = t.
III. SIMULATION
In order to investigate the behavior of BCOR&R, we apply
BCOR&R to att48 (N = 48) and kroA100 (N = 100) of twoTSPs. In this study, we carry out the simulation 100 times with
2000 generations. The number of bee M is same as the numberof city N. The parameter of standard BCO and BCOR&R isshown below.

(a) Global search.

λ = 0.95, α = 1, β = 10, R = 0.65
In order to compare the obtained solution with the optimalsolution, we use the error rate as follows;(obtainedsolution) − (optimalsolution)
Errorrate[%] =× 100 (6)(optimalsolution)
where this equation shows how close to the optimal solution
the standard BCO obtains the tour length. Thus, the error ratenearer 0 is more desirable.
(b) Local search.

A. Investigation of the initialization count tlimit
First, we investigate the value of tlimit that is updated ateach range of local search LS range . Where tlimit is initialization
count of local search, LS range is search range of local search.
At this time, determined by the random location of the localsearch.
TABLE II
The result of tlimit

att48

tlimitkroA100

tlimitLS range =Number of updates[time]
min[]
max[]
Number of updates[time]
min[]
max[]

0.2
192
107
533
179

0.322313142390.541001370-0.700-(c) Exportation of global search from local search.
Fig. 1.

Search methods of BCOR&R.

Step. 4 (Local search): After (t > tlocal ), carry out the following tasks. Thereafter, a local search is performed instead of a global search. A local search is performed
in a small number of city Ml (Ml = M ∗ LS range )using the GL of global search. After tR (t) > tlimit ,initialize current local search group and tR (t) = 0,

As shown in a Table II, LS range = 0.3 is the most number ofupdates at N = 48. The number of updates shows 150 or lesstimes at the longest in the time of every LS range . However, theupdate could not confirm LS range = 0.7. Thus, the local search
can consider that LS range = 0.3 is a peak, and is decreasing
gradually from there. In N = 100, LS range = 0.2 is the mostnumber of updates. As in common with N = 48,- 60 -N = 48 : N × LS range = 48 × 0.3 = 14.4
N = 100 : 100 × 0.2 = 20(7)(8)In a local search, it can be guessed that about 15-20 cities are
the optimal number of cities.
N = 48 : 48 × 0.7 = 33.6
N = 100 : 100 × 0.2 = 50

(9)
(10)

In an above case, there was no updating. Local search is not
influential at the time of at least 33 or more cities. The numberof updates is same maximum 150 times as N = 48 except
LS range = 0.1.
The value of tlimit which considers these results and is usedby the following simulations is shown in table III.
TABLE III
determination of tlimit

att48
kroA100

LS range =tlimit

0.2150200

0.3150150

0.5150-References[1] M. Dorigo and T. Stutzle, “Ant Colony Optimization,” Bradford Books,2004.
[2] H. Koshmizu, T. Saito, “Parallel Ant Colony Optimizers with Local andGlobal Ants,” Proceedings of International Joint Conference on NeuralNetworks, 2009.
[3] J. Kennedy and R. Eberhart, “Particle swarm optimization,” Proc. IEEE
Int. Conf. on Neural Networks, vol. 4, pp. 1942–1948, 1995.
[4] D.T. Pham, A. Ghanbarzaden, E. Koc, S. Otri, S. Rahim and M.
Zaidi, “The Bees Algorithm - A Novel Tool for Complex Optimization
Problems,” Intelligent Production Machines and Systems, pp. 454-459,
Cardiﬀ University, UK, 2006.
[5] K. Guney and M. Onay, “Bees algorithm for interference suppression oflinear antenna arrays by controlling the phase-only and both the amplitude
and phase,” Faculty of Engineering, Erciyes University, 2007.
[6] L. Wong, M.Y.H. Low, C.S. Chong, “An Eﬃcient Bee Colony Optimization Algorithm for Traveling Salesman Problem using Frequency-basedPruning,” 7th IEEE International Conference on Industrial Informatics(INDIN2009), pp. 775-782, Nanyang Technol University, 2009.

0.7-B. Investigation of the local search range LS range
Next, we investigate behavior when the local search range
LS range is changed. Optimal LS range of every N is determinedusing tlimit optimized above section.
TABLE IV
The result of LS range

att48

kroA100

LS range =avg[]
Error ratemin[]deviation[]
avg[]
Error ratemin[]deviation[]

0.2
2.28
1.37
0.67
11.38
7.42
2.21

0.3
1.89
1.17
0.47
13.27
11.83
0.91

0.5
2.35
1.56
0.46
13.68
11.79
1.3

0.7
2.56
1.37
0.8312.51
10.75
1.37

As shown in a Table IV, for N = 48, the best result is obtainedwith LS range = 0.3, and for N = 100, the best result is obtainedwith LS range = 0.2. From these results, it turned out that thenumber of updates by local search is greatly related to a result.
In order to increase the number of updates of a local search, itturned out that a suitable range setup is required. This positionof the local search was also determined randomly, there isa possibility of better results by improving the methods ofpositioning
IV. CONCLUSIONSIn this study, we investigated about behavior of the local
search of BCOR&R. The local search was very eﬀective asa method of improving TSP. However, local search has muchinfluence on the results by changing range. We have discovered
the optimal parameter of the local search this time. In thefuture work, we want to discover new positioning method oflocal search.

- 61 -