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

151-15Ant Colony Optimization Changing the Rate of Dull Ants for QAP
Sho SHIMOMURA1 , Haruna MATSUSHITA2 and Yoshifumi NISHIO1(Tokushima University1 , Kagawa University2 ){10/Lk , if (i, j) ∈ T k (t)1. Introductionk∆τij (t) =(3)0,otherwise,
Ant Colony Optimization (ACO) is a biologicallyinspired optimization algorithm with pheromone efwhere Tk (t) is obtained permutation by k-th ant andfects of ants and is eﬀective to solve diﬃcult comLk (t) is its total cost. ρ ∈ [0, 1] is the pheromone trail
binatorial optimization problems like the Quadratic
decay coeﬃcient. Update τij (t) of each coupling (i, j)
Assignment Problem (QAP). QAP is one of the NPk
depending on its ∆τij;
hard combinatorial optimization problems.
M∑kIn our previous study, we have proposed a new
τij (t + 1) = ρτij (t) +∆τij(t).
(4)
ACO algorithm; ACO with Intelligent and Dull ants
k=1(IDACO) [1]. In IDACO, two kinds of ants coexist; in[Step4] The rate of dull ants d is changed if the systelligent ant and dull ant. The intelligent ant can trail
tem is trapped into the local optima. If the best sothe pheromone, however the dull ants cannot trail thelution is not updated within 2000 times, IDACO-CRpheromone. We have conﬁrmed that IDACO obtained
is judged trapped into local solution. The rate of dull
eﬀective result for the Traveling Salesman Problems.
ants d is{changed according toIn this study, we propose an improved IDACO;.
d + dup if trapped local solution
ACO Changing the Rate of Dull Ants (IDACO-CR).
d=(5)0,otherwise,
In addition to the existence of the dull ants, the rate
where the adjustable parameter dup controls the adof dull ants in IDACO-CR are ﬂexibly changes in thedition of the rate of dull ants. Thus, the rate of dull
optimization. We apply IDACO-CR to QAPs.
ants d is ﬂexibly varied from 0 to 1.0. If the best so2. IDACO-CR
lution is updated, d is reset to the initial value d = 0.
Given two matrices, a distance matrix D and a ﬂow[Step5] Let t = t + 1. Go back to [Step2] and repeat
matrix F , ﬁnd a permutation Π which corresponds tountil the maximum time limit t = tmax .
the minimum value of the total assignment cost L in
3. Numerical Experimentsn ∑nEq. (1).
∑We apply IDACO-CR to three QAPs and compare
L=Dij Fπ(i)π(j) ,(1)IDACO-CR with the standard ACO and the conveni=1 j=1tional IDACO. The rate of dull ants d in the conwhere Dij and Fij are the (i, j)-th elements of D andventional IDACO is ﬁxed. In the experiments, theF , respectively, π(i) is the i-th element of the vector
number of ants M is set to the same as the number ofΠ, and n is the size of the problem. The number oflocations. We repeat the simulation 20 times for all
ants is denoted by M . d × M ants are classiﬁed into
the problems. The parameters are set to the follows;a set of the dull ants Sdull . d is a rate of dull ants inρ = 0.9, α = 1, β = βD = 1, tmax = 15000, dup = 0.2.
all the ants.
[Step1] Let t = 0. τij (t) is the amount of pheromone
The simulation results are shown in Table 1. We canconﬁrm that IDACO-CR obtains better results thantrail on a coupling (i, j) to assign the activity j to thethe other methods. We can see that changing thelocation i, and τij (0) = 10.
rate of dull ants in the simulation is more eﬀective[Step2] From the two vectors D and F , one may obthan using the ﬁxed rate of dull ants.
tain a matrix A. The element aij of A is given by
the product di · fj . IDACO-CR uses the two kinds
Table 1: Results of IDACO-CR, the standard ACO andof choice probabilities. The probability that k-th ant
the conventional IDACO with d = 0.5.
(k = 1, · · · , M ) assigns activity j to location i is deNug12
Scr12
Had20
cided by βD[η]ijThe standard ACO
4.76%
7.95%
3.83%
,if k ∈ Sdull
Σl∈N k [ηil ]βDIDACOwithd=
0.5
5.88%
8.16%
3.91%
pk,ij (t) =(2)[τij (t)]α [ηij ]βIDACO-CR
4.57%
7.83%
3.62%
, otherwise,Σl∈N k [τil (t)]α [ηil ]β
4. Conclusionswhere 1/ηij is the element aij . The adjustable paramIn this study, we have applied IDACO-CR to QAPs.
eters α, β and βD control the weight of pheromone
We have conﬁrmed that IDACO-CR obtained better
kintensity and of the element, respectively. N is a set
results than the standard ACO and the conventionalof activities such that k-th ant has not yet assigned
IDACO because IDACO-CR can change the rate ofany activity in the set.
dull ants depending on the problems.
[Step3] After all the ants have completed assignment,
Referencescompute the total cost Lk (t) and update the amountof the pheromone τij (t). Note that dull ants can de[1] S. Shimomura, M. Sugimoto, T. Haraguchi,
posit the pheromone, though, they cannot trail theH. Matsushita and Y. Nishio, “Ant Colony Optimizaktion with Intelligent and Dull Ants”, Proceeding of Inpheromone. The amount of the pheromone ∆τij
deternational Symposium on Nonlinear Theory and its
posited by k-th ant on the coupling (i, j) is decided
Applications (NOLTA’10), pp. 504-507, Sep. 2010.
asPowered by TCPDF (www.tcpdf.org)