2010 International Workshop on Nonlinear Circuits,Communication and Signal Processing
NCSP'10, Waikiki, Hawaii, March 3-5, 2010

Investigation of Ant Colony Optimization
with Intelligent and Dull Ants
Sho Shimomura, Masaki Sugimoto, Taku Haraguchi, Haruna Matsushita and Yoshifumi Nishio
Department of Electrical and Electronic Engineering
Tokushima University
2–1 Minami–Josanjima, Tokushima, Japan
Phone:+81–88–656–7470, Fax:+81–88–656–7471
Email: {s-sho, sugimoto, taku, haruna, nishio}@ee.tokushima-u.ac.jp

Abstract
In the previous study, we have proposed Ant Colony Optimization with Intelligent and Dull Ants (IDACO), which two
kinds of ants coexist. We have applied IDACO to various TSP
problems and confirmed the eﬀectiveness. However, the association between the rate of dull ants and its behaviors was
not completely clear. In this study, we investigate the eﬀectof the rate of dull ants in IDACO and of the parameter whichis related to the distance between the cities.
1. Introduction
The Ant Colony Optimization (ACO) [1] is an evaluational optimization algorithm inspired by the pheromone effect of ants and is eﬀective to solve diﬃcult combinatorial
optimization problems, such as Traveling Salesman Problems(TSP) [2], graph coloring problems, Quadratic Assignment
Problems (QAP) and so on. TSP is a problem in combinatorial optimization studied in operations research and theoretical computer science. In TSP, given a list of cities andtheir pairwise distances, the task is to find the shortest possible tour that each city exactly once. In ACO algorithm,
the ants drop the pheromones on the path connecting cities.
The pheromones are updated depending on the behavior ofthe ants to find a food source through paths having strong
pheromone deposits. By communicating with other ants according to the pheromone strength, the algorithm tries to findthe optimal solution. However, ACO has a problem whichis to fall into local solutions. Therefore, it is important toenhance the algorithm performances by improving its flexibility.
An interesting report about the real ant world [3] was proposed. This report has confirmed that about 20 percent of
the ants are unnecessary ants called “dull ant”. The dull ant
keeps still or stay around their colony whereas the other ants
in a colony perform feeding behavior. In a computational ex-periment, the researchers performed the feeding behavior byusing intelligent ants, which can trail the pheromone exactly,
and the dull ant which can not trail the pheromone exactly.
From the results, the ants group including the dull ant can obtain more foods than the group containing only the intelligent
ant. It means that the coexistence of the intelligent and thedull ant improves the eﬀectiveness of the feeding behavior.
In our previous study, we have proposed a new ACO algorithm; Ant Colony Optimization with Intelligent and Dullants (IDACO) [4]. The important feature of IDACO is thattwo kinds of ants coexist. The one is the intelligent ant
and the other one is the dull ant. The intelligent ant cantrail the pheromone exactly and the dull ant can not trail thepheromone. These features are essentially similar to the real
ant world. Therefore, IDACO algorithm is closer to the real
ant colony than the standard ACO algorithm. We have applied
IDACO to various TSP problems and confirmed the eﬀectiveness. However, the association between the rate of dull antsand its behavior was not completely clear. In this study, weinvestigate eﬀect of the rate of dull ants on IDACO.
2. Ant Colony Optimization with Intelligent and Dull
AntsWe explain IDACO algorithm in detail. The important feature of IDACO is that two kinds of ants coexist; the intelligent
ant and the dull ant. The intelligent ant is the same as the antof the standard ACO, and it can exactly trail the pheromone.
In constant, the dull ant can not trail the pheromone. Theinput space of N-city positions is denoted asS ≡ {P1 , P2 , · · · , PN }, Pi ≡ (xi , yi ),(1)

where the input area is normalized from 0 to 1, and Pi is thei-th city position. M ants are deposited on each city at random. d × M ants are classified into a set of the dull ants S dull .
d is the rate of dull ants on all the ants.

- 17 -

[Step1](Initialization): Let the iteration number t = 0. τi j (t) where T k (t) is the tour obtained by k-th ant, and Lk (t) is its
is the amount of pheromone deposited on the path (i, j) be- length. Updated τi j (t) of each path (i, j) depending on its
tween the city i and the city j at time t, and τi j (t) is initially ∆τki j (t);set to τ0 .
M∑
τi j (t + 1) = (1 − ρ)τi j (t) +∆τki j (t),(5)[Step2](Find tour): For the intelligent ants and the Dull
k=1
ants, the visiting city is chosen by the probability pi j,I (t) andwhere ρ ∈ [0, 1] is the rate of pheromone evaporation.
pi j,D (t), respectively, as shown in Fig. 1. The probability ofk-th ant moving from the city i to the city j is decided as;[Step4] Let t = t + 1. Go back to [Step2] and repeat until
ηi jt = tmax .
pki j ,D (t) =, if k ∈ S dullΣl∈Nk ηil(2)[τi j (t)]α [ηi j ]β
pki j ,I (t) =,Σl∈Nk [τil (t)]α [ηil ]β

3. Numerical Experiments
otherwise,(3)

In order to investigate the association between the rate ofdull ants and its behavior, we apply IDACO to two TSP probwhere k = 1, 2, · · · , M, and 1/ηi j is the distance of the path lems and compare IDACO with the diﬀerent rate of dull ants
(i, j). The adjustable parameters α and β control the weight with the standard ACO. The TSP problems is conducted onof the pheromone intensity and of the city information, re- bayg29 (composed of 29 cities) shown in Fig. 2(a) and att48
spectively. Therefore, the searching ability goes up and down (composed of 48 cities) shown in Fig. 2(b).
by changing α and β. As Eq. (2) does not include the amountof deposited pheromone τi j (t), the dull ants can not trail thepheromone. Therefore, while the intelligent ants judge nextcity by both the pheromone and the distance from the present
location, the dull ants judge next city depending on only thedistance from the present location. Nk is a set of cities thatk-th ant has never visited. The ants repeat choosing next city
until all the cities are visited.
11

0.9

0.9

0.8

0.8

0.7

0.7

0.6

0.6

0.5

0.5

0.4

0.4

0.3

0.3

0.2

0.2

0.1

00

0.1

0.2

0.4

0.6

(a)

Dull ant

Intelligentant

pi1, I (t )City i

pi1, D (t )pi 3, D (t )City 3pi 3, I (t )pi 2, D (t )pi 2, I (t )City 2City 1

0.8

100

0.2

0.4

0.6

0.8

1

(b)

Figure 2: Two benchmark problems and their optimal tours.
(a) bayg29. (b) att48.
In the experiments, the number of ants M in the standard
ACO and IDACO are set to the same as the number of cities.
The standard ACO contains only the intelligent ants. IDACO
includes the dull ants, which are d × 100 percent of all theants, and the intelligent ants which are the others. We repeat
the simulation 10 times for all the problems. The parametersof the standard ACO and IDACO were set to the follows;ρ = 0.3, α = 1, tmax = 2000,

Figure 1: Probability pi j (t) of intelligent and dull ants

(6)

where the evaporation rate ρ, the weight of pheromone α, the[Step3](Pheromone update): After all ants have completed weight of distance β and the search limit tmax are fixed values.
their tour, the amount of deposited pheromone on each path In order to compare the obtained solution with the optimalis updated. We should note that the dull ants can not trail the solution, we use the error rate as follow;
pheromone, however, they can deposit the pheromone on the(obtained solution) − (optimal solution)
path. Then, compute the tour length Lk (t), and the amount of
× 100. (7)Error rate[%] =(optimal solution)
pheromone deposited by k-th ant on the path (i, j) is decided
This equation shows how close to the optimal solution theas;{
standard ACO obtains the tour length. Thus, the error rate
1/Lk , if (i, j) ∈ T k (t)∆τki j (t) =(4) nearer 0 is more desirable.
0,otherwise,- 18 -Table 1: Results of ACO and IDACO with varying parameter Table 2: Results of ACO and IDACO with varying parameter
β for bayg29.
β for att48.
βACO
(d=0)
3.74%
2.87%
2.49%
2.66%

234
5

d=0.1
2.62%
2.08%
2.47%
2.6%

IDACO
d=0.2 d=0.3
1.72% 1.72%
1.73% 1.7%
2.18% 1.74%
2.27% 2.02%

β
d=0.4
1.54%
1.38%
1.7%
1.83%

2345ACO
(d=0)
4.06%
3.61%
2.78%
2.85%

d=0.1
3.04%
3.43%
2.65%
2.46%

IDACO
d=0.2 d=0.3
2.55% 2.93%
2.21% 2.59%
2.72% 3.1%
2.36% 2.81%

d=0.4
3.19%
3.92%
3.07%
3.06%

4.5

44

3.5

3.5
3

Error rate[%]Error rate[%]

32.5
β=22

β=3
β=4

1.5

β=5

2.5

β=2
β=32

β=4
1.5

β=5

1

1
0.5

0.5
000
0

0.1

0.2

0.3

0.1

0.2

0.3

0.4

Rate of dull ants d0.4

Rate of dull ants dFigure 4: Results of ACO as d=0 and IDACO with varyingFigure 3: Results of ACO as d=0 and IDACO with varying parameter β for att48.
parameter β for bayg29.
4. Conclusions
Tables 1 and 2 show the average values of the shortest tour
for bayg29 and att48 in the standard ACO and IDACO withthe diﬀerence rate of dull ants, respectively. The parameter β,which is related to the distance between the cities, is changed
from 2 to 5. Figures 3 and 4 show the results obtained from
Tables 1 and 2, respectively. The vertical axis shows the error rate and the horizontal axis shows the rate of dull ants d.
IDACO with d = 0 is exactly the same as the standard ACO.

In this study, we have investigated the eﬀect of the rateof dull ants on Ant Colony Optimization with Intelligent andDull Ants (IDACO) and of the parameter β for various problems. We have confirmed that the obtained results depend on
the rate of dull ants and the number of cities. Furthermore,even if the parameter β is changed, IDACO including about
20 percent of dull ants obtain better values than the standardACO. In consequence, we can say that IDACO obtains theIn Fig. 3, we can confirm that all IDACO obtain better val- eﬀective results, when the rate of dull ants is the same as theues than the standard ACO, and IDACO including more dull rate of dull ants in the real ant world.
ants obtains the better results. Furthermore, even if the parameter β is changed, IDACO consistently obtains better valReferences
ues than the standard ACO. As the results, we can say thatIDACO including more dull ants obtains the eﬀective result [1] M. Dorigo and T. Stutzle, Ant Colony Optimization,
Bradford Books, 2004.
when the number of cities is small.
In Fig. 4, we can say that IDACO including about 20 per- [2] M. Dorigo and L. M. Gambardella, “Ant Colonies forcent of dull ants obtains the best value. Furthermore, even if
the Traveling Salesman Problem,” BioSystems, vol. 43,
the parameter β is changed, IDACO including about 20 perpp. 73–81, 1997.
cent of dull ants almost obtains better value than the standard
ACO. As the results, when the rate of dull ants is the same as [3] H. Hasegawa, “Optimization of GROUP Behavior,”
Japan Ethological Society Newsletter, no. 43, pp. 22–23,
the rate of dull ants in the real ant world, IDACO obtains the2004 (in Japanese).
eﬀective results.

- 19 -

[4] S. Shimomura, M. Sugimoto, T. Haraguchi, H. Matsushita, and Y. Nishio, “Behavior of Ant Colony Optimization with Intelligent and Dull Ants” (being submitted).

- 20 -