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

325

18-26
ACO with Intelligent and Dull Ants for QAP
Sho SHIMOMURA1 , Masaki SUGIMOTO1 ,Haruna MATSUSHITA2 and Yoshifumi NISHIO1(Tokushima University1 , Hosei University2 )½
10/Lk , if (i, j) ∈ T k (t)1. Introductionk∆τij(t) =(3)0,otherwise,
Ant Colony Optimization (ACO) [1] is a biologically inspired optimization algorithm with pheromone
where Tk (t) is obtained permutation by k-th ant andeffects of ants and is effective to solve difficult comLk (t) is its total cost. ρ ∈ [0, 1] is the pheromone trail
binatorial optimization problems like the Quadratic
decaycoefficient. 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.
In our previous study, we have proposed a newMX
ACO algorithm; ACO with Intelligent and Dull antskτ
(t+1)
=
ρτ
(t)+
∆τij(t).
(4)ijij(IDACO) [2]. In IDACO, two kinds of ants coexist; ink=1
telligent ant and dull ant. The intelligent ant can trail
the pheromone, however the dull ants cannot trail the[Step4] Let t = t + 1. Go back to [Step2] and repeatpheromone. We have confirmed that IDACO obtained
until the maximum time limit t = tmax .
effective result for the Traveling Salesman Problem.
In this study, we apply IDACO to various QAPs.
3. Numerical Experiments

2. IDACO

Given two matrices, a distance matrix D and a flow
matrix F , one sums the elements of each line to obtain two vectors D and F , find a permutation Πwhich corresponds to the minimum value of the total
assignment cost L in Eq. (1).
n XnX
L=Dij Fπ(i)π(j) ,(1)i=1 j=1

where Dij and Fij are the (i, j)-th elements of D andF , respectively, π(i) is the i-th element of the vector
Π, and n is the size of the problem. The number ofants is denoted by M . d × M ants are classified into
a set of the dull ants Sdull . d is a rate of dull ants inall the ants.
[Step1] Let t = 0. τij (t) is the amount of pheromone
trail on a coupling (i, j) to assign the activity j to thelocation i, and τij (0) = τ0 .
[Step2] From the two vectors D and F, one may
obtain a matrix A. The element aij of A is givenby the product di・fj . The probability that k-th ant(k = 1, · · · , M ) assigns activity j to location i is decided by[ηij ]βD,if k ∈ Sdull
Σl∈N k [ηil ]βD
pk,ij (t) =(2)[τij (t)]α [ηij ]β,otherwise,Σl∈N k [τil (t)]α [ηil ]β
where 1/ηij is the element aij . The adjustable parameters α and β, βD control the weight of pheromone
intensity and of the element, respectively. N k is a setof activities such that k-th ant has not yet assigned
any activity in the set.
[Step3] After all the ants have completed assignment,
compute the total cost Lk (t) and update the amountof the pheromone τij (t). Note that dull ants can deposit the pheromone, though, they cannot trail thekpheromone. The amount of the pheromone ∆τij
deposited by k-th ant on the coupling (i, j) is decidedasWe apply IDACO to three QAPs and compare
IDACO with different rates of dull ants with the standard ACO.
In the experiments, the number of ants M is set tothe same as the number of locations. The rate of dull
ants d is set to 0.2 and 0.5 in each simulation. We
repeat the simulation 20 times for all the problems.
The parameters are set as follows;τ0 = 10, ρ = 0.9, α = 1, β = βD = 1, tmax = 15000.
The simulation results are shown in Table 1. We canconfirm that IDACO obtains better results than thestandard ACO. Especially, IDACO with d = 0.5 obtains the best results. We can confirm that IDACO
including more dull ants obtains the effective results.
Table 1: Results of the standard ACO and IDACO.
Scr12

Tai12

Nug12

The standard ACO
IDACO with 0.2
IDACO with 0.534067.7
338488.5
33846.5

2472283.1
245435.8247031

613.2
615
611.9

Optimal solution

31410

224416578

4. Conclusions
This study has applied IDACO to quadratic assignment problems. We have confirmed that IDACO obtained better results than the standard ACO becausethe dull ants help in getting out of the local optima.

References[1] M. Dorigo and T. Stutzle, Ant Colony Optimization, Bradford Books, 2004.
[2] S. Shimomura, M. Sugimoto, T. Haraguchi,H. Matsushita, and Y. Nishio, “Behavior of Ant
Colony Optimization with Intelligent and Dull
Ants”, Technical Report on Nonlinear Problems, no.
NLP2010-20 & NC2010-20, pp. 157-160, Jun. 2010.