2010 International Symposium on Nonlinear Theory and its Applications
NOLTA2010, Krakow, Poland, September 5-8, 2010

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 770-8506, Japan‡Department of Electrical and Electronics Engineering, Hosei University
3-7-2 Kajino-cho, Koganei-city, Tokyo 184-8584, Japan
Email: †{s-sho, sugimoto, nishio}@ee.tokushima-u.ac.jp, ‡haruna.matsushita.pd@k.hosei.ac.jp
Abstract—This study proposes a new Ant Colony Optimization (method; ACO) with Intelligent and Dull Ants(IDACO). In IDACO algorithm, two kinds of ants coexist:
intelligent ants and dull ants. IDACO algorithm is nearer
to the real ant colony than the standard ACO algorithm. We
apply IDACO to Traveling Salesman Problems (TSPs) andconfirm that IDACO obtains more effective results than thestandard ACO which consists of only the intelligent ants.

called Ant Colony Optimization with Intelligent and DullAnts (IDACO). The important feature of IDACO is that twokinds of ants coexist. The one is an intelligent ant andthe another is a dull ant. The intelligent ant can trail thepheromone and the dull ants cannot trail the pheromone.
Because their features are essentially similar to the real
ant’s world, we can say that IDACO algorithm is nearer
to the real ant colony than the standard ACO algorithm.

1. Introduction

2. Ant Colony Optimization
with Intelligent and Dull Ants (IDACO)Ant Colony Optimization (ACO) [1] is a biologicallyinspired optimization algorithm with pheromone effect ofants and is effective to solve difficult combinatorial optimization problems, such as Traveling Salesman Problem(TSP) [2], graph coloring problem [3], Quadratic Assignment Problem (QAP) [4] and so on. TSP is a problem
in combinatorial optimization studied in an operations research and a theoretical computer science. In TSP, given alist of cities and their pairwise distances, the task is to findthe shortest possible tour that each city exactly visited once.
In ACO algorithm, multiple solutions called “ants” coexist, and the ants drop pheromone on the path connecting
the cities. Pheromone trails are updated depending on thebehavior of the ants. The ants find a food source throughpaths having strong pheromone. By communicating withother ants according to the pheromone strength, the algorithm tries to find the optimal solution. However, ACO has
a problem which is to fall into local solutions. Therefore,
it is important to enhance the algorithm performances byimproving its flexibility.
Meanwhile, it has been reported that about 20 percent of
the ants are unnecessary ants called “dull ant” in the real
ant’s world [5]. The dull ant keeps still around its colony
whereas the other ants in the colony perform feeding behavior. In a computational experiment, the researchers
performed the feeding behavior by using intelligent ants,
which can trail the pheromone exactly, and dull ants whichcannot trail the pheromone. From results, the ants group including the dull ants can obtain more foods than the groupcontaining only the intelligent ants. It means that the coexistence of the intelligent and dull ant improves the effectiveness of the feeding behavior.
In this study, we propose a new type of ACO algorithm

We explain the proposed IDACO algorithm in detail.
In the IDACO algorithm, the most important feature ofIDACO is that two kinds of ants coexist; the intelligent
ants and the dull ants. The intelligent ant is the sameas the ant of the standard ACO, and it can exactly trail
the pheromone. In constant, the dull ant cannot trail thepheromone.
N-city of TSP is denoted as
S ≡ {P1 , P2 , · · · , PN }, Pi ≡ (xi , yi ),(1)

where a data area is normalized from 0 to 1, and Pi is an
i-th city position (i = 1, 2, · · · , N). Each ant (total M) isdeposited on a city selected at random. (1 − d) × M ants andd × M ants are classified into a set of the intelligent ants
S Intel and of the dull ants S dull , respectively. d is a rate ofdull ants in all the ants.
[Step1](Initialization): Let an iteration number t = 0. τi j (t)is an amount of pheromone deposited on a path (i, j) between the city i and the city j at time t, and τi j (t) is initially
set to τ0 .
[Step2](Find tour): For the intelligent ants and the dull
ants, the visiting city is chosen by the probability pi j,I (t)and pi j,D (t), respectively, as shown in Fig. 4. The probability of k-th ant moving from the city i to the city j is decidedby[ηi j ]βD
, if k ∈ S dull
pki j ,D (t) =(2)Σl∈Nk [ηil ]βD- 504 -

pki j ,I (t) =[τi j (t)]α [ηi j ]βI,Σl∈Nk [τil (t)]α [ηil ]βI

otherwise,(3)

3. Numerical Experiments

Dull ant

Intelligent
ant

pi1, I (t )City ipi1, D (t )In order to evaluate a performance of IDACO and to investigate its behavior, we apply IDACO to two TSPs andcompare IDACO with different rates of dull ants with thestandard ACO.
In the experiments, the number of ants M in the standard ACO and IDACO are set to the same as the number ofcities. The standard ACO contains only the intelligent ants
whose choice probability is decided by Eq. (3). IDACO includes d × M dull ants, and (1 − d) × M intelligent ants ineach simulation. The rate of dull ants d is set to 0.2 and 0.5
in each simulation. We repeat the simulation 10 times for
all the problems. The parameters of the standard ACO andIDACO were set as follows;

pi 3, D (t )City 3pi 3, I (t )pi 2, D (t )pi 2, I (t )City 2City 1Figure 1: Probability pi j (t) of Intelligent and Dull ants.The
visiting city of intelligent ant is chosen by the probability pi j,I (t). The visiting city of dull ant is chosen by theprobability pi j,D (t) which does not include the amount ofpheromone τi j (t) and τil (t).

where k = 1, 2, · · · , M, and 1/ηi j is a distance of the path(i, j). The adjustable parameters βI and βD control theweight of the city information of the intelligent ant and of
the dull ant, respectively. Therefore, the searching ability
goes up and down by changing α and β. As Eq. (2) does notinclude the amount of deposited pheromone τi j (t) and τil (t),the dull ants cannot trail the pheromone. In contrast to theintelligent ants which judge next city by the pheromone andthe distance from a present location, the dull ants judge
next city depending on only the distance from a present location. Nk is a set of cities that k-th ant has never visited.
The ants repeat choosing next city until all the cities arevisited.
[Step3](Pheromone update): After all ants have completed
their tours, the amount of deposited pheromone on eachpath is updated. We should note that the dull ants can deposit the pheromone on the path, though, they cannot trail
the pheromone. Then, the tour length Lk (t) is computedfor both the intelligent and dull ants, and the amount ofpheromone ∆τki j (t) deposited by k-th ant on the path (i, j)
is decided as(1/Lk , if (i, j) ∈ T k (t)∆τki j (t) =(4)0,otherwise,

τ0 = 10, ρ = 0.3, α = 1, β = βI = βD = 5, tmax = 2000,
where the evaporation rate ρ, the weight of pheromone α,
the weight of distance β, βI and βD and the search limitt = tmax are fixed values.
In order to compare obtained solutions with the optimal
solution, we use an error rate as follow;
Error rate[%]=MX∆τki j (t),(5)(6)

This equation shows how close to the optimal solution theACOs obtain the tour length. Thus, the error rate nearer 0 ismore desirable. Furthermore, in order to evaluate how well
the solution of IDACO are improved from that of ACO, we
use an improved rate as follow;
Improved rate[%] =(Avg. of Error of ACO)−(Avg. of Error of IDACO)
× 100.
(Avg. of Error of ACO)

(7)

3.1. Simulation 1: att48
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3

where T k (t) is a tour obtained by k-th ant, and Lk (t) is its
length. Update τi j (t) of each path (i, j) depending on its∆τki j (t);τi j (t + 1) = (1 − ρ)τi j (t) +(obtained solution) − (optimal solution)
× 100.
(optimal solution)

0.2
0.1
00

0.2

0.4

0.6

0.8

1

Figure 2: Benchmark problem att48 and its optimal tour.

k=1where ρ ∈ [0, 1] is the rate of pheromone evaporation.
[Step4] Let t = t + 1. Go back to [Step2] and repeat untilt = tmax .

The TSP conducted on att48 (composed of 48 cities)
shown in Fig. 2. The simulation results of the standard
ACO and IDACO are shown in Table 1. Figure 3 shows- 505 -

1

1

1

0.9

0.9

0.9

0.8

0.8

0.8

0.7

0.7

0.7

0.6

0.6

0.6

0.5

0.5

0.5

0.4

0.4

0.4

0.3

0.3

0.3

0.2

0.2

0.2

0.1

0.1

00

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0.1

00

0.1

0.2

0.3

0.4

(a)

0.5

0.6

0.7

0.8

0.9

1(b)

00

0.1

0.2

0.3

0.4

0.5

0.60.70.80.91(c)Figure 3: The best tours of the three ACOs for att48. (a) The standard ACO. (b) IDACO with d = 0.2. (c) IDACO withd = 0.5.

Table 1: Results of the standard ACO and IDACO for att48.
ACO
IDACO
d = 0 d = 0.2 d = 0.5
Error
Average
2.87% 2.62%
3.84%
rate
Minimum 2.43% 1.46%
2.09%
Improved rate
8.7%
−33.8%
from ACOIn Table 2, IDACO obtained better results than the standard ACO. Furthermore, as the result of att48, IDACO withd = 0.2 obtained better results than IDACO with d = 0.5.
From the results of the Simulation 1 and 2, we can confirm
that IDACO obtains the effective results when the rate ofdull ants is same as that in the real ant world. Especiallyin case of TSP containing many cities, IDACO greatly improves the result of the standard ACO.

the best tours of att48 obtained by the standard ACO andIDACO.
In Table 1, IDACO with d = 0.2 obtained better result
than the standard ACO. We should note that the result ofIDACO with d = 0.5 was worse than the standard ACO.
This result suggest that too many dull ants make the result
bad.

Table 2: Results of the standard ACO and IDACO forkroA100.
ACOIDACO
d = 0 d = 0.2 d = 0.5
Error
Average
1.27% 1.12%
1.13%
rate
Minimum 1.22% 1.12%
1.12%
Improved rate
11.81% 11.02%
from ACO

3.2. Simulation 2: kroA100
4. Conclusions

10.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
00

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1Figure 4: Benchmark problem kroA100 and its optimal
tour.

Furthermore, we considered the TSP conducted onkroA100 (composed of 100 cities) shown in Fig. 4. Thesimulation results of the standard ACO and IDACO areshown in Table 2. Figure 5 shows the best tours of kroA100
obtained by the standard ACO and IDACO.

In this study, we have proposed Ant Colony Optimization with Intelligent and Dull Ants (IDACO). We have investigated the performances by applying it to two TSPs.
We have confirmed that IDACO including the dull ants obtained better results than ACO which containing only theintelligent ants because the dull ants help in getting outof the local optima. Furthermore, we have confirmed thatIDACO with d = 0.2 obtained better results than the standard ACO for all the cases. From these results, we can saythat IDACO is nearer to the real ant colony than the standard ACO and is effective algorithm in solving TSP.
References[1] M. Dorigo and T. Stutzle, Ant Colony Optimization,
Bradford Books, 2004.
[2] M. Dorigo and L. M. Gambardella, “Ant Colonies for- 506 -111

0.9

0.9

0.9

0.8

0.8

0.8

0.7

0.7

0.7

0.6

0.6

0.60.5

0.5

0.5

0.4

0.4

0.4

0.3

0.3

0.3

0.2

0.2

0.2

0.1

0.1

00

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

000.1
0.1

0.2

0.3

0.4

(a)

0.5

0.6

(b)

0.7

0.8

0.9

1

00

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1(c)

Figure 5: The best tours of the three ACOs for kroA100. (a) The standard ACO. (b) IDACO with d = 0.2. (c) IDACO
with d = 0.5.

the Traveling Salesman Problem,” BioSystems, vol. 43,
pp. 73–81, 1997.
[3] M. Dorigo, G. D. Caro and L. M. Gambardella, “Ant
Algorithms for Discrete Optimization”, Artificial Life
vol. 5 no. 2, pp. 137-172, 1999.
[4] V. Maniezzo and A.Colorni, “The ant system applied tothe quadratic assignment problem”, IEEE Transactions
on Knowledge and Data Engineering vol. 11 no. 5,
pp. 769-778, 1999.
[5] H. Hasegawa, “Optimization of GROUP Behavior,”
Japan Ethological Society Newsletter, no. 43, pp. 22–23, 2004 (in Japanese).

- 507 -