IEEE Workshop on Nonlinear Circuit Networks
December 9-10, 2011

Growing Ant Colony Optimization
with Intelligent and Dull Antsand its Application to TSP
Sho Shimomura

Haruna Matsushita

Dept. Electrical and Electronic Eng.,
Tokushima University
Email: s-sho@ee.tokushima-u.ac.jp

Dept. Reliability-based Information Systems Eng.,
Kagawa University
Email: haruna@eng.kagawa-u.ac.jp

Yoko Uwate

Yoshifumi Nishio

Dept. Electrical and Electronic Eng.,
Tokushima University
Email: uwate@ee.tokushima-u.ac.jp

Dept. Electrical and Electronic Eng.,
Tokushima University
Email: nishio@ee.tokushima-u.ac.jp

Abstract— This study proposes an Growing Ant Colony Optimization with Intelligent and Dull Ants (GIDACO). In theGIDACO algorithm, two kinds of ants coexist: intelligent ants
and dull ants. In addition, the number of ants in the colony isincreased with the passage of time. The new ant is added basedon the best ant which has the best tour. Also, the added ant isdecided whether the dull ant or intelligent ant by the probability.
By growing the colony, the structure of GIDACO is changed
flexibly and automatically depending on the problem. Moreover,the growing can also reduce the simulation time because thesimulation time depends on the number of ants. We apply
GIDACO to Traveling Salesman Problems (TSPs) and confirm
that GIDACO obtains more effective results than the standard
ACO which consists of only the intelligent ants.

a computational experiment, the researchers performed thefeeding behavior by using intelligent ants, which can trail
the pheromone exactly, and dull ants which cannot trail thepheromone. From these results, the ants group including thedull ants can obtain more foods than the group containing only
the intelligent ants. The dull ants are regarded as having task
which find the new food sources by dawdle. It means thatthe coexistence of the intelligent and dull ant improves theeffectiveness of the feeding behavior.
In this study, we propose a new type of the ACO algorithm
called Growing Ant Colony Optimization with Intelligent andDull Ants (GIDACO). The first important feature is thattwo kinds 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. The
second important feature of GIDACO is that the number ofants in the colony is increased with the passage of time. In
other words, there are a few ants in the initial colony, however,the colony grows depending on ants’ conditions. The newants are added based on the ant which obtained the best tour.
Also, the added ant is decided whether dull ant or intelligent
ant by the probability. By growing the colony, the structureof GIDACO is changed flexibly and automatically dependingon the problem. Moreover, the growing can also reduce thesimulation time because the simulation time depends on thenumber of ants. Because their features are essentially similar
to the real ant’s world, we can say that GIDACO algorithm isnearer to the real ant colony than the standard ACO algorithm.
This paper is organized as follows. The basic method ofACO is introduced in the Section II. We explain the GIDACO
algorithm in detail in the Section III. In the Section IV, weapply GIDACO to four kinds of TSPs whose number of cities
are different. Furthermore, we investigate the behavior of GIDACO in detail. Performances are evaluated quantitatively incomparison with the standard ACO. We confirm that GIDACO

I. I NTRODUCTION
Ant Colony Optimization (ACO) [1][2] is proposed to solve
difficult combinatorial optimization problems, such as Traveling Salesman Problem (TSP), graph coloring problem, routing
in communications networks, Quadratic Assignment Problem(QAP) [3]-[7] and so on. TSP is a problem in combinatorial
optimization studied in an operations research and a theoreticalcomputer science. In TSP, given a list of cities and theirpairwise distances, the task is to find the shortest possible
tour that each city exactly visited once. In the ACO algorithm,multiple solutions called “ants” coexist, and the ants drop a
substance called the pheromone. Pheromone trails are updated
depending on the behavior of the ants. By communicatingwith other ants according to the pheromone strength, thealgorithm tries to find the optimal solution. However, ACO
has a problem which is to trap at local solutions. Therefore,
it is important to enhance the algorithm performances byimproving its flexibility.
Meanwhile, it has been reported that about 20 percent ofthe ants are unnecessary ants called “dull ant” in the real
ant’s world [8]. The dull ant keeps dawdle its colony whereas
the other ants in the colony perform feeding behavior. In- 44 -Start

City 2

Initialize deposited pheromoneτ 0City 3
pi 2 (t )City 1

M ants are set to city at random. k = 1

pi1 (t )Choose the next city j according to the choice probability pij

City iNo

k=k+1

Ant ｋ visited all cities

Fig. 2. Probability pij (t) of ants. The visiting city is chosen by probabilitypij (t).

YesNoAll ants visited all citiesboth the pheromone and the distance from the present location.
Nk is a set of the cities that k-th ant has never visited. Theants repeat choosing next city until all the cities are visited.

Yes
Update pheromone

Yest < t max[ACO3](Pheromone update): After all ants have completed
their tours, the amount of pheromone deposited on each pathis updated. The tour length Lk (t) is computed, and the amountof pheromone ∆τkij (t) deposited on the path (i, j) by k-th ant
is decided as{10/Lk , if (i, j) ∈ Tk (t)∆τkij (t) =(3)0,otherwise,NoEndFig. 1.

pi3 (t )Flowchart of the ACO algorithm.

can obtain a more effective results than the standard ACO.
Finally, the Section V concludes this paper.
II. T HE BASIC ALGORITHM OF ACO
ACO is popular search algorithms and applied to variousapplications. In this section, we introduce the basic algorithmof ACO.
A flowchart of the ACO algorithm is shown in Fig. 1. N city of TSP is denoted asS ≡ {P1 , P2 , · · · , PN }, Pi ≡ (xi , yi ),(1)where the data area is normalized from 0 to 1, and Pi denotes
the i-th city position (i = 1, 2, · · · , N ). Each ant k (total M )is deposited on a city selected at random.
[ACO1](Initialization): Let the iteration number t = 0. τij (t)is the amount of pheromone deposited on the path (i, j)between the city i and j at time t, and τij (t) is initially set toτ0 .
[ACO2](Find tour): The visiting city is chosen by according
to the probability pij (t) as shown in Fig. 2. The probabilityof k-th ant moving from the city i to j is decided bypkij (t) =[τij (t)]α [ηij ]β,Σl∈Nk [τil (t)]α [ηil ]β(2)where k = 1, 2, · · · , M , and 1/ηij is the distance of thepath (i, j). The adjustable parameters α and β control theweight of the pheromone intensity and of the city information,respectively. Therefore, the searching ability goes up and down
by changing α and β. As Eq. (2), the ants judge next city by

where Tk (t) is the tour obtained by k-th ant, and Lk (t) is its
length. Total amount of pheromone τij (t) of each path (i, j)
is updated depending on ∆τkij (t);τij (t + 1) = (1 − ρ)τij (t) +M∑∆τkij (t),(4)k=1where ρ ∈ [0, 1] is the rate of pheromone evaporation.
[ACO4] Let t = t + 1. Go back to [ACO2] and repeat untilt = tmax .
III. G ROWING A NT C OLONY O PTIMIZATIONWITH I NTELLIGENT AND D ULL A NTS
We explain the proposed GIDACO algorithm in detail. Aflowchart of the GIDACO algorithm is shown in Fig. 3. Thefirst important feature of GIDACO is that two kinds of ants
coexist; intelligent ant which can exactly trail the pheromone
and dull ant which cannot trail the pheromone for making
the tour. The second important feature of GIDACO is that thenumber of ants is increased with the passage of time. In otherwords, the colony grows depending on the problem. N -city
positions of TSP is set to according to Eq. (1). First, each ant
k (total MG ) is deposited on a city selected at random. Ants
are classified into a set of the intelligent ants SIntel , namely,the initial colony consists of only the intelligent ants.
[GIDACO1](Initialization): Let iteration number t = 0 andinitialize the pheromone τij (t) according to [ACO1].
[GIDACO2](Find tour): For the intelligent ants and the dull
ants, the visiting city is chosen by the probability pij,I (t) and- 45 -StartCity 2
Initialize deposited pheromone τ0

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

pi 3, D (t )pi1, D (t )pi1, I (t )MG ants are set to city at random. k = 1

City 3City iK∈SIntel
Yes

Intelligent ant

No

Choice probability is pij, I

Choice probability is pij, DDull ant

Fig. 4. Probability pij (t) of Intelligent and Dull ants.The visiting city ofintelligent ant is chosen by the probability pij,I (t). The visiting city of dull
ant is chosen by the probability pij,D (t) which does not include the amountof pheromone.

Chose the next city jNo
Ant ｋ visited all cities

k =k+1

Yes
Compute the tour length Lk(t)t =t +1

Lk(t-1) ≦ Lk(t)Yes

C =C+1

NoNoAll ants visited all cities

Yes
Update the pheromone

CGrow≦ CNo
Yes

Yes

MG = MG + 1t < tmax

where C is a counter which counts the number of times
which obtained results are worse than that of last iteration.
The number of ants is decided by{MG + 1 and C = 0, if C ≥ CGrow
MG =(8)MG .
otherwise,NoEnd

Fig. 3.

Flowchart of the GIDACO algorithm.

pij,D (t) as shown in Fig. 4. The probability of k-th ant movingfrom the city i to j is decided bypkij ,D (t) =pkij ,I (t) =[ηij ]βD, if k ∈ Sdull
Σl∈Nk [ηil ]βD[τij (t)]α [ηij ]βI. otherwise,Σl∈Nk [τil (t)]α [ηil ]βI

the pheromone. Then, the tour length Lk (t) is computedfor both the intelligent and dull ants, and the amount ofpheromone ∆τkij (t) deposited by k-th ant on the path (i, j) isdecided according to Eq. (3), Update τij (t) of each path (i, j)according to Eq. (4)[GIDACO4](Growing): After the their tour length Lk (t) iscomputed, we evaluate the tour length Lk (t) and considerwhether the colony should be grown. A growing rule is asfollows;{C + 1, if Lk (t − 1) ≤ Lk (t)C=(7)
C,otherwise,(5)(6)

The adjustable parameters βI and βD control the weight ofthe city information of the intelligent ant and of the dullant, respectively. As Eq. (5) does not include the amount ofdeposited pheromone τij (t) and τil (t), the dull ants cannot
trail the pheromone. The dull ants judge next city depending
on only the distance from the present location, in contrast tothe intelligent ants which judge next city by the pheromone
and the distance from the present location.
[GIDACO3](Pheromone update): After all ants have completed their tours, the amount of deposited pheromone oneach path is updated. We should note that the dull ants candeposit the pheromone on the path, though, they cannot trail

The adjustable parameter CGrow controls the rate of ants increase. The added ant is decided whether dull ant or intelligent
ant by the probability. The dull ant is added by according tothe probability Pm , in contrast the intelligent ant is added by
the probability (1 − Pm ). In addition, the added ant is affectedby the best ant. Namely, the new ant is deposited in the samecity of ant which obtained best tour.
[GIDACO5] Let t = t+1. Go back to [GIDACO2] and repeat
until t = tmax .
IV. N UMERICAL E XPERIMENTS OF TSP
In order to evaluate a performance of GIDACO and toinvestigate its behavior, we apply GIDACO to various TSPs.
We compare GIDACO with the standard ACO.
In the experiments, the number of ants M in the standard
ACO is set to the same as the number of cities, namelyM = N . However, the initial number of ants MG in theGIDACO is set to the one-tenth of the number of cities, namely
MG = N/10. Therefore, the number of ants MG in GIDACO
is changed from N/10 to N . The standard ACO contains
ants whose choice probability is decided by Eq. (2). GIDACO
includes dull ants and intelligent ants whose choice probability- 46 -

TABLE I60

kroC100

gr120

Average of ACO

2.87%

7.43%

10.59%

7.05%

Average of GIDACO

1.65%

3.74%

9.78%

5.22%

42.5%

49.66%

7.65%

25.96%

from ACO

is decided by Eq. (6). We repeat the simulation 20 times for
all the problems. The parameters of two methods are set asfollows;

40550

20500

Tour lengtheil51

The number of ants

att48

Improved rate of GIDACO

600
The total number of ants
The number of intelligent ants
The number of dull ants
Minimum

R ESULTS OF THE STANDARD ACO AND GIDACO.

0050

100

150

200

250300Iteration

350

400

450

450500Fig. 5. Relationship between the performance and the number of ants in thesimulation of eil51.

τ0 = 10, ρ = 0.3, α = 1, β = βI = βD = 5,Pm = 0.2, CGrow = 30, tmax = 2000,
where the evaporation rate ρ, the weight of pheromone α, theweight of distance β, βI and βD , probability of dull ant Pm ,the rate of ants increase CGrow and the search limit t = tmax
are fixed values. In order to compare obtained solutions withthe optimal solution, we use an error rate as follow;
Error rate[%]=(obtained solution) − (optimal solution)
× 100.
(optimal solution)(9)This equation shows how close to the optimal solution theACOs obtain the tour length. Thus, the error rate nearer 0 is
more desirable. Furthermore, in order to evaluate how well thesolution of GIDACO are improved from that of ACO, we use
an improved rate as follow;
Improved rate[%] =(Avg. of Error of ACO)−(Avg. of Error of GIDACO)
× 100.
(Avg. of Error of ACO)

(10)The TSPs are conducted on att48 (composed of 48 cities),
eil51 (composed of 51 cities), kroC100 (composed of 100cities) and gr120 (composed of 120 cities). These problems
are quoted from TSPLIB [9]. The simulation results of thestandard ACO and GIDACO are shown in Table I.
In this table, the average values nearer 0 are more desirable.
We can confirm that the proposed GIDACO obtained the best
results than the standard ACO for all the problems. Furthermore, we investigate the relationship between the performanceand the number of ants of GIDACO for eil51. Figure 5 shows
the simulated result for 1 trial. We can see that obtained
solutions are improved by increasing the number of ants.
Also, GIDACO can reduce the simulation time because thesimulation time depends on the number of ants. From theseresults, we can say that GIDACO is more effective algorithm
than the standard ACO in solving TSPs.

V. C ONCLUSION
In this study, we have proposed Growing Ant Colony
Optimization with Intelligent and Dull Ants (GIDACO). We
have investigated the performances of GIDACO by applying
it to four TSPs. We have confirmed that GIDACO including
the dull ants obtained better results than the standard ACO
which containing only the intelligent ants. We consideredthat the structure of GIDACO which changed flexibly andautomatically depending on the problem is effective. Fromthese results, we can say that GIDACO is more effective
algorithm than the standard ACO in solving TSPs.
R EFERENCES[1] M. Dorigo and T. Stutzle, Ant Colony Optimization, Bradford Books,2004.
[2] M. Dorigo, V. Maniezzo and A. Colorni, “Ant System: Optimization
by a Colony of Cooperating Agents,” IEEE Trans. Systems, Man, andCybernetics, Part B: Cybernetic, vol.26 no. 1, pp. 29-41, 1996.
[3] M. Dorigo and L. M. Gambardella, “Ant Colonies for the Traveling
Salesman Problem,” BioSystems, vol. 43, pp. 73–81, 1997.
[4] M. Dorigo, G. D. Caro and L. M. Gambardella, “Ant Algorithms forDiscrete Optimization,” Artificial Life vol. 5 no. 2, pp. 137-172, 1999.
[5] Blum and Merkel (eds.), Swarm Intelligence, Springer, 2008.
[6] Inspiration for optimization from social insect behavior. E. Bonabeau, M.
Dorigo and G. Theraulaz.
[7] V. Maniezzo and A.Colorni, “The ant system applied to the quadratic
assignment problem,” IEEE Transactions on Knowledge and Data Engineering vol. 11 no. 5, pp. 769-778, 1999.
[8] H. Hasegawa, “Optimization of GROUP Behavior,” Japan EthologicalSociety Newsletter, no. 43, pp. 22-23, 2004 (in Japanese).
[9] G. Reinelt, “TSPLIB-A traveling salesman problem library, ” ORSA J.
Comput. Vol. 3: pp.376-384, 1991.

- 47 -