平成21年度電気関係学会四国支部連合大会

334

18-10
Ant Colony Optimization with Intelligent and Dull Ants
Sho SHIMOMURA Masaki SUGIMOTO
Taku HARAGUCHI Haruna MATSUSHITA Yoshifumi NISHIO(Tokushima University){1/Lk , if (i, j) ∈ T k (t)1. Introductionk∆τij(t) =(4)0,otherwise,
Ant colony optimization (ACO) is an evaluational
optimization algorithm inspired by pheromone eﬀect
where Tk (t) is obtained tour by the k-th ant and Lk (t)of ants and is eﬀective to solve diﬃcult combinatois its length. ρ ∈ [0, 1] is the pheromone trail decay
rial optimization problems like the traveling salescoeﬃcient.
man problems (TSPs)[1]. Meanwhile, there is a sim[IDACO4] Let t = t+1. Go to [IDACO2] and repeat
ulation result of ant’s feeding action that the ants
until the maximum time limit t = tmax .
group, which contains the certain dull ants, can collect more foods than the group which contains only
3. Numerical Experiments
intelligent ants [2]. Because the intelligent ants colIn order to conﬁrm the eﬀectiveness of IDACO, welect the foods and the dull ants are searchers of new
apply IDACO to two problems, ulysses16 and att48.
foods. Therefore, the dull ants increase the eﬀectiveThe total number of the ants of ACO and IDACO areness of the feeding action. In this study, we propose
10, respectively. All the ants of ACO are the intelAnt Colony Optimization with Intelligent and Dullligent ants, and 10 % of all the ants of IDACO areAnts (IDACO), which is a new ACO algorithm. Thethe dull ants and other ants are the inteligent ants.
important feature of IDACO is that two kinds of antsWe carry out the simulation 2000 times. The simulaexist. We apply IDACO to two TSPs and conﬁrm thetion results of ACO and IDACO are shown in Tableeﬀectiveness.
1. In this table, we can conﬁrm that IDACO obtains
2. ACO with Intelligent and Dull Ants
better result than ACO for diﬃcult TSP. In the realworld, there is a simulation result of ant’s feeding acIn IDACO algorithm, the important feature oftion that the intelligent ants collect the foods and theIDACO is that two kinds of ants exist; intelligent ants
dull ants are searchers of new foods. From these, wewhich exactly trail pheromone, and dull ants which do
think that the dull ants are ineﬃcient, however, thenot trail the pheromone. S denotes the input space
dull ants increase the eﬀectiveness of the feeding acof N city positions as
S ≡ {P1 , · · · , PN }, Pi ≡ (xi , yi ),(1)tion. Therefore, we can see that IDACO has a goodwhere the input area is normalized as the unit squareeﬀect to escape local minima and achieves a good perand Pi is the i-th city position. M ants are depositedformance to ﬁnd near optimal solutions.
on each city at random. d × M ants are classiﬁed into
a set of the dull ants Sdull . d is rate of the dull ants
Table 1: Results of ACO and IDACO for ulysses16
on all the ants.
and att48.
[IDACO1](Initialization): Let iteration number t =0. τij (t) is the amount of pheromone trail on the pathulysses16
att48(i, j) between cities i and j at time t, and τij (t) is iniACO
AVG
80.956192
tially set to τ0 .
Min
76.8
47276.3[IDACO2](Find tour): For the k-th ant (k =Max
91.5
56499.4
1, · · · , M ), the visiting city is chosen by probability
LACOAVG
90.2
48635.3
pkij (t) and the k-th ant ﬁnds a tour according to thefollowing equations;Min
80.4
44088.8

ηij
Max
90.5
48953.9
,if k ∈ Sdull Σl∈N k ηilk
Optimalsolution
72.9
33523.9pij (t) =(2)[τij (t)]α [ηij ]β, otherwise,Σl∈N k [τil (t)]α [ηil ]β

4. Conclusions

where 1/ηij is the distance of path (i, j). The adjustable parameters α and β control the weight ofpheromone intensity and city information, respectively. As the dull ants do not trail the pheromone, setto (α, β) = (0, 1). Therefore, the equation of the dull
ants does not include the amount of the pheromone
trail τij (t). N k is a set of cities such that k-th ant has
not yet visited any city in the set.
[IDACO3](Pheromone update): Compute the tour
length Lk (t) and update the number of the pheromone
trail τij (t) byτij (t + 1) = (1 − ρ)τij (t) +M∑
k=1k∆τij(t),(3)In this study, we have proposed Ant Colony Optimization with Intelligent and Dull Ants. We have conﬁrmed that IDACO obtains better result than ACO
for diﬃcult TSP.
Reference[1] M. Dorigo and L.M. Gambardella, “Ant Colonies
for the Traveling Salesman Problem,” BioSystems,
vol. 43, pp. 73–81, 1997.
[2] H. Hasegawa, “Optimization of GROUP Behavior,” Japan Ethological Society Newsletter, no. 43,
pp. 22–23, 2004.