2009 IEEE Workshop on
Nonlinear Circuit Networks, Tokushima, Dec 11-12, 2009

Behavior of Ant Colony Optimization
with Intelligent and Dull Ants
Sho Shimomura, Masaki Sugimoto, Taku Haraguchi, Haruna Matsushita and Yoshifumi Nishio
Dept. Electrical and Electronic Eng,Tokushima University
Email: {s-sho, sugimoto, taku, haruna, nishio} @ee.tokushima-u.ac.jp

Abstract— In this study, we investigate Ant Colony Optimization (ACO) containing two kinds of ants: intelligent ants and dull
ants. Algorithm of the proposed method is more near to the real
ant colony than algorithm of the conventional ACO. We apply
the proposed method to Traveling Salesman Problem (TSP), andconfirm that the proposed method obtains the effective results
than the conventional ACO in solving optimization problem.

I. I NTRODUCTION
Ant Colony Optimization (ACO) [1] is an evaluational
optimization algorithm inspired by pheromone effect of ants
and is effective to solve difficult combinatorial optimization
problems, such as graph coloring problem, routing in communications networks, Quadratic Assignment Problem (QAP)and so on [2]-[4]. It has also been used to produce nearoptimal solutions to the traveling salesman problem (TSP) [5].
TSP is a problem in combinatorial optimization studied inoperations research and theoretical computer science. Given alist of cities and their pairwise distances, the task is to find ashortest possible tour that each city exactly once. In algorithmof ACO, the ants drop pheromones on the path connecting
cities. The pheromones are updated depending on behaviorof the ants to find a food source through path having strong
pheromone deposits. Referring to the pheromone strength andcommunication among ants, the algorithm tries to find theoptimal solution. However, ACO has the problem which is
to fall into local solution. It means that the balance of thedecentralization and the centralization is bad. Therefore, it isimportant to enhance the algorithm performances for flexible
and adaptive.
Meanwhile, it is believed that God does not create an
unnecessary thing even if it seems to useless. This story wasbacked by a report about the ant’s world [6]. This report has
confirmed that about 20 percent of the ants are unnecessary
ants. The unnecessary ants keep still or stay around theircolony whereas the other ants in a colony perform feeding
behavior. We consider that the ants are seemingly unnecessary,
however, the researchers consider the unnecessary ants havecertain roles. Because, the idea was backed by a computational
experiment of feeding behavior in trailing the pheromone. In
the experiment, the researchers performed the feeding behavior
by using the intelligent ants, which can trail the pheromone
exactly, and the dull ants which can not trail the pheromone
exactly. From the results, the ants group including a certain
amount of the dull ants, can obtain more foods than the group- 52 -containing only the intelligent ants. The intelligent ants caneffectively carry the discovered foods to the colony, however,it may be difficult to discover new foods just because they
consider the efficiency. On the other hand, the researchersconsider that the dull ants work as the searcher of the new
foods or have the effect to discover the shortest route. Inorder words, the coexistence of the intelligent and the dull
ants improves the effectiveness of the feeding behavior.
In this study, we investigate ACO containing two kinds ofants, which are intelligent ants and dull ants. The intelligent
ants can trail the pheromone exactly and the dull ants cannot trail the pheromone exactly. Their features are essentiallysimilar to the real ant’s world. Therefore, the proposed method
is more near to the real ant colony than the conventional ACO.
We apply the proposed method to TSP problem and confirm
the effectiveness.
II. A NT C OLONY O PTIMIZATIONWITH I NTELLIGENT AND D ULL A NTS

We explain the proposed method in detail. The importantfeature of the proposed method is that two kinds of ants exist;
intelligent ants can exactly trail pheromone, and dull ants cannot trail the pheromone. S denotes the input space of N city
positions asS ≡ {P1 , · · · , PN }, Pi ≡ (xi , yi ),(1)where the input area is normalized as the unit square and Pi
is the i-th city position. M ants are deposited on each city atrandom. d × M ants are classified into a set of the dull ants
Sdull . d is rate of the dull ants on all the ants.
[Step1](Initialization): Let iteration number t = 0. τij (t) isthe amount of pheromone trail on the path (i, j) between cityi and city j at time t, and τij (t) is initially set to τ0 .
[Step2](Find tour): For the Intelligent ants and the Dull ants,
the visiting city is chosen by probability pij,I (t) and pij,D (t)as shown in Fig. 1. The probability with which k-th ant (k =1, · · · , M ) chooses to go from city i to city j is as followingequations;ηij, if k ∈ Sdull
pkij ,D (t) =Σl∈Nk ηil(2)pkij ,I (t) =[τij (t)]α [ηij ]β, otherwise,Σl∈Nk [τil (t)]α [ηil ]β(3)where 1/ηij is the distance of path (i, j). The adjustableparameters α and β control the weight of pheromone intensity
and city information, respectively. Therefore, Searching ability
goes up and down by changing α and β. Dull ants can nottrail the pheromone. Because, the equation of the dull ants does
not include the amount of pheromone trail τij (t). Therefore,
intelligent ants judge next city by the pheromone and thedistance from the present location, however, dull ants judge
next city by only the distance from the present location. Nk isa set of cities that k-th ant has not yet visited. The ants repeatchoosing next city until all the cities are visited.

problem. The TSP problem is conducted on bayg29 (composedof 29 cities).
In the experiments, the number of ants M in the proposed
methods and the conventional ACO are the same as the numberof cities, respectively. The conventional ACO contains only
the intelligent ants. The proposed method 1 contains the dull
ants, which are 10 percent of all the ants and the intelligent
ants which are the others. The proposed method 2 contains
the dull ants, which are 20 percent of all the ants and theintelligent ants which are the others. We repeat the simulation
5 times. The parameters of the two proposed methods and theconventional ACO were set to the following;ρ = 0.3, α = 1, β = 5, tmax = 2000,(6)where evaporation rate ρ, weight of pheromone α, weight of
distance β and search limit t = tmax are fixed value. In order
to compare the obtained solution with the optimal solution,
we use the error rate as follow;
error rate =(obtained solution) − (optimal solution),(optimal solution)(7)

where this equation shows how near to the optimal solution
the conventional ACO obtains the tour length. Furthermore,in order to investigate how well the solution of the proposed
method are improved from the solution of the conventional
ACO, we use the improved rate of AVG of the proposed
method from AVG of the conventional ACO as follow;
Fig. 1.

Probability pij (t) of Intelligent and Dull ants

Improved rate =[Step3](Pheromone update): After all ants have completed
their tour, pheromone is updated by all ants. Dull ants can nottrail pheromone, however, can deposit pheromone on the path.
Then, compute the tour length Lk (t), how k-th ant deposits
pheromone ∆τkij (t) between city i and city j at iteration t is
as following equations;½
1/Lk , if (i, j) ∈ Tk (t)∆τkij (t) =(4)0,otherwise,
where Tk (t) is obtained tour by the k-th ant and Lk (t) is its
length. All ants finished the tour, updated the τij (t) of eachpath (i,j) depending on its ∆τkij (t);τij (t + 1) = (1 − ρ)τij (t) +MX∆τkij (t),(5)k=1ρ ∈ [0, 1] is the pheromone trail decay coefficient.
[Step4] Let t = t + 1. Go back to [Step2] and repeat untilt = tmax .
III. N UMERICAL E XPERIMENTS
In order to investigate feasibility and effectiveness of theproposed method, we apply the proposed method to TSP- 53 -(AVG of ACO) − (AVG of Proposed method).
(AVG of Proposed method)(8)

Table I shows the simulation results of the conventional ACO
and the two proposed methods. In this table, Min shows
the shortest value of the whole simulation, namely 10 times.
AVG shows the average value of Min for each simulation.
We can confirm that the two proposed methods obtain better
results than the conventional ACO for AVG and Min, andthe proposed method has a good performance to find near
optimal solutions. Furthermore, in the improved rate, the two
proposed methods have greatly improved than the conventional
ACO. As the results, we can say that the proposed method nearto the real ant colony are effective in solving TSP problem.
Figures 2 show the best tour of bayg29 obtained by theconventional ACO and the proposed method, respectively.
From these results, we can visually confirm that the crossover
path of the proposed method is less than the crossover path ofthe conventional ACO. Therefore, we can say that the proposed
method is more effective than the conventional ACO.
IV. C ONCLUSIONSIn this study, we have investigated Ant Colony Optimization(ACO) containing the intelligent ants and the dull ants, andapplied to the TSP problem. We have confirmed that theproposed method obtains better results than the conventionalACO for various performances. From these results, we can saythat the proposed method is more near to the real ant colony

TABLE I
R ESULTS OF CONVENTIONAL ACO AND PROPOSED METHODS FORBAYG 29.

TSP problem
The total number of ants
The number of dull ants of Proposed method1
The number of dull ants of Proposed method2
ACO
AVG
Min
ADAGE1AVG
Min
ADAGE2
AVG
Min
Improved rate of Proposed method1 from ACO
Improved rate of Proposed method2 from ACO

2400

2400

2200

2200

2000

2000

1800

1800

1600

1600

1400

1400

1200

1200

1000

1000

800

800

600

bayg2929252.76%
1.82%2.35%
1.54%
2.00%
1.15%
17%
38%

600

400

4000200400600

800

1000

1200

1400

1600

1800

2000

0200(a)400600

800

1000

1200

1400

1600

1800

2000(b)Fig. 2. The best tour of bayg29. (a) Conventional ACO. (b) Proposed methodthan the conventional ACO and obtains the effective results insolving TSP problem.
R EFERENCES[1] M.Dorigo and T.Stutzle, Ant Colony Optimization, Bradford Books, 2004.
[2] Blum and Merkel (eds.), Swarm Intelligence, Springer, 2008
[3] Inspiration for optimization from social insect behaviour. E. Bonabeau1,2,M. Dorigo3 and G. Theraulaz4[4] Stutzle, Thomas and Dorigo, Marco (1999) ACO Algorithms for the
Quadratic Assignment Problem. New Ideas in Optimization.
[5] M. Dorigo and L.M. Gambardella, “Ant Colonies for the Traveling
Salesman Problem,” BioSystems, vol. 43, pp. 73–81, 1997.
[6]

H. Hasegawa, “Optimization of GROUP Behavior,” Japan EthologicalSociety Newsletter, no. 43, pp. 22–23, 2004.

[7] M.Dorigo and T.Stutzle, Ant Colony Optimization, Bradford Books, 2004.

- 54 -