Proceedings of International Joint Conference on Neural Networks, San Jose, California, USA, July 31 – August 5, 2011

Ant Colony Optimization Changing the Rate of Dull Antsand its Application to QAP
Sho Shimomura, Haruna Matsushita and Yoshifumi Nishio

Abstract— In our previous study, we have proposed an Ant
Colony Optimization with Intelligent and Dull Ants (IDACO)
which contains two kinds of ants. We have applied IDACO tovarious Traveling Salesman Problems (TSPs) and conﬁrmed its
effectiveness. This study proposes an Ant Colony Optimization
Changing the Rate of Dull Ants (IDACO-CR) and its Application to Quadratic Assignment Problems (QAPs). In addition to
the existence of the dull ants which cannot trail the pheromone,the rate of dull ants in IDACO-CR is changed ﬂexibly andautomatically in the simulation, depending on the problem. We
investigate the behavior of IDACO-CR in detail and the effectof changing the rate of dull ants. Simulation results show thatIDACO-CR gets out from the local optima by changing therate of dull ants, and we conﬁrm that IDACO-CR obtains theeffective results in solving complex optimization problems.

I. I NTRODUCTION
NT COLONY OPTIMIZATION (ACO) [1] is an evaluational optimization algorithm inspired by a pheromone
effect of ants and is effective to solve difﬁcult combinatorial
optimization problems, such as graph coloring problem,
routing in communications networks, Traveling Salesman
Problem (TSP) and so on [2]-[4]. It has also been used to
produce near-optimal solutions to the Quadratic Assignment
Problem (QAP) [5]. QAP is a generalization of the TSP, and
it is also an NP-hard combinatorial optimization problem.
Given two matrices corresponding to a distance and a ﬂow
between activities, the task is to assign all activities todifferent locations with the minimum cost among all of thepossible combinations. In ACO algorithm, multiple solutions
called “ants” coexist, and the ants drop pheromone about
an assignment of activity. Pheromone trails are updated
depending on the behavior of the ants. The ants ﬁnd afood source through paths having strong pheromone. Bycommunicating with other ants according to the pheromone
strength, the algorithm tries to ﬁnd the optimal solution.
However, ACO has a problem which is to fall into local
solutions. Therefore, it is important to enhance algorithm
performances by improving its ﬂexibility.
Meanwhile, it has been reported that about 20 percent of
the ants are unnecessary ants called “dull ant” in the real ant’s
world [6]. The dull ant keeps still around its colony whereas
the other ants in the colony perform feeding behavior. In
a computational experiment, the researchers performed thefeeding behavior by using intelligent ants, which can exactlyA

Sho Shimomura and Yoshifumi Nishio are with the Department
of Electrical and Electronic Engineering, Tokushima University, Japan.
Haruna Matsushita is with the Reliability-based Information Systems Engineering, Kagawa University, Japan. (email: s-sho@ee.tokushima-u.ac.jp,
haruna@eng.kagawa-u.ac.jp and nishio@ee.tokushima-u.ac.jp).

978-1-4244-9636-5/11/$26.00 ©2011 IEEE

trail the pheromone, and dull ants which cannot trail thepheromone. In the results, the ants group including the dull
ants was able to obtain more foods than the group containing
only the intelligent ants. It means that the coexistence of thedull ant improves the effectiveness of the feeding behavior.
In our previous study [7], we have proposed a new typeof ACO algorithm, which is called Ant Colony Optimization
with Intelligent and Dull ants (IDACO). The importantfeature of IDACO is that two kinds of ants coexist. The one is
an intelligent ant and the another is a dull ant. The intelligent
ant can trail the pheromone exactly, however the dull ant
cannot trail the pheromone exactly. Because their features
are essentially similar to the real ant’s world, we can say thatIDACO algorithm is nearer to the real ant colony than theconventional ACO algorithm. We have applied the IDACO
to various TSPs and have conﬁrmed an interesting result thatIDACO including the dull ants obtained better results than thestandard ACO consisted of only the intelligent ants. However,since the difﬁculty of getting out from the local optima varies
from problem to problem, we have to consider changing therate of dull ants ﬂexibly depending on the problem.
In this study, we propose an improved IDACO; ACO
Changing the Rate of Dull Ants (IDACO-CR). In addition to
the existence of the dull ants, the rate of dull ants in IDACOCR ﬂexibly changes in the optimization. In other words, therate of dull ants is automatically determined depending on the
problem. Furthermore, we propose an application of IDACOCR to QAP. By applying the proposed method to various
QAPs, we conﬁrm the behavior of IDACO-CR, its efﬁciency
and an importance of the dull ants.
This paper is organized as follows. In the Section II, theQAP is introduced. The basic method of ACO for QAP isintroduced in the Section III. We explain about the proposed
algorithm of IDACO-CR for QAP in detail in the Section IV.
In the Section V, we apply IDACO-CR to ﬁve QAPs whose
number of locations and facilities are different. Furthermore,
we investigate the behavior of IDACO-CR in detail. We, in
addition to IDACO-CR, consider the conventional IDACO
for QAP whose algorithm does not change the rate of thedull ants in the simulation. Performances are evaluated bothvisually and quantitatively in comparison with the conventional ACO and the conventional IDACO. Finally, the Section
VI concludes this paper.
II. Q UADRATIC A SSIGNMENT P ROBLEM
The QAP of order 𝑛 is a problem which looking for thebest allocation of 𝑛 activities in 𝑛 locations. The QAP has
been recognized as a model of many different real situations;2830

arrangement of departments in the hospitals, minimizationof the total wire length in electronic circuits and so on.
Mathematically the problem is deﬁned by two matrices ofthe dimension 𝑛 × 𝑛;
𝑫 =[𝑙𝑖ℎ ] = matrix of the distances (between location 𝑖 andlocation ℎ).
𝑭 = [𝑓𝑗𝑘 ] = matrix of the ﬂows (between activity 𝑗 andactivity 𝑘).

III. A NT C OLONY O PTIMIZATION FOR QAP
We explain the conventional ACO algorithm for QAP indetail. A ﬂowchart of ACO algorithm for QAP is shown in
Fig. 1. The number of ants is denoted by 𝑀 . Total assignment
cost 𝐿 is same as Eq. (1).

In order to solve the QAP, we ﬁnd a permutation Π whichcorresponds to the minimum value of the total assignment
cost 𝐿 in Eq. (1).
𝐿=

𝑛
𝑛 ∑
∑

𝑑𝑖𝑗 𝑓𝜋(𝑖)𝜋(𝑗) ,(1)𝑖=1 𝑗=1

where 𝑙𝑖𝑗 and 𝑓𝑖𝑗 are the (𝑖, 𝑗)-th elements of 𝑫 and 𝑭 ,respectively, 𝜋(𝑖) is the 𝑖-th element of the vector Π, and 𝑛 is
the size of the problem. From the two matrices 𝑫 and 𝑭 , one
sums the elements of each line to obtain two vectors 𝒟 andℱ called distance potentials and ﬂow potentials, respectively.
Furthermore, from the two vectors 𝒟 and ℱ , one may obtaina matrix 𝑨 called the coupling matrix. The element 𝑎𝑖𝑗 of
𝑨 is given by the product 𝒟𝑖 ⋅ℱ𝑗 . We show an exampleof calculate by using Nugment’s problem of order 5. Twomatrices 𝑫 and 𝑭 is shown as⎡⎤
0 1 1 2 3
⎢1 0 2 1 2⎥
⎢
⎥
⎥
𝑫=⎢
⎢1 2 0 1 2⎥ ,⎣2 1 1 0 1⎦
3 2 2 1 0⎡⎤
0 5 2 4 1
⎢ 5 0 3 0 2⎥
⎢
⎥
⎥
𝑭 =⎢
⎢ 2 3 0 0 0⎥ .
⎣ 4 0 0 0 5⎦
1 2 0 5 0

Fig. 1.

Flowchart of the conventional ACO algorithm for QAP

We obtain the vectors of the potentials 𝒟 and ℱ ;
⎡ ⎤
⎡ ⎤
7
12
⎢6⎥
⎢10⎥
⎢ ⎥
⎢ ⎥
⎥
⎢ ⎥
𝒟=⎢
⎢6⎥ , ℱ = ⎢ 5 ⎥ .
⎣5⎦
⎣9⎦
8
8
𝑨 is given from the two vectors 𝒟 and ℱ. In Nugent’s
example, this corresponds to the following values;⎤⎡
84 70 35 63 56⎢72 60 30 54 48⎥
⎥
⎢
⎥
𝑨=⎢
⎢72 60 30 54 48⎥ .
⎣60 50 25 45 40⎦
96 80 40 72 64
𝑨 shows potential cost of assignment. Thus, 𝑎𝑖𝑗 nearer 0 is
more desirable.

Fig. 2. Choice probability 𝑝𝑖𝑗 (𝑡) of ants. The assigning activity is chosen
by probability 𝑝𝑖𝑗 (𝑡)[ACO1](Initialization): Let an iteration number 𝑡 = 0. 𝜏𝑖𝑗 (𝑡)is an amount of pheromone trail on a coupling (𝑖, 𝑗) to assign
an activity 𝑗 to the location 𝑖, and 𝜏𝑖𝑗 (0) = 𝜏0 .
[ACO2](Assign activity): The assigning activity is chosen byaccording to the probability 𝑝𝑖𝑗 (𝑡) as shown in Fig. 2. The
probability that 𝑘-th ant (𝑘 = 1, ⋅ ⋅ ⋅ , 𝑀 ) assigns activity 𝑗to the location 𝑖 is decided by𝑝𝑘𝑖𝑗 (𝑡) =[𝜏𝑖𝑗 (𝑡)]𝛼 [𝜂𝑖𝑗 ]𝛽,Σ𝑙∈𝑁𝑘 [𝜏𝑖𝑙 (𝑡)]𝛼 [𝜂𝑖𝑙 ]𝛽

(2)

2831

Fig. 3.

Flowchart of IDACO-CR algorithm for QAP

where 𝜂𝑖𝑗 is deﬁned as the inverse of the coupling matrix
element 𝑎𝑖𝑗 . The adjustable parameters 𝛼 and 𝛽 control theweight of pheromone intensity and of the coupling matrix
element, respectively. Therefore, a searching ability goes up
and down by changing 𝛼 and 𝛽. 𝑁 𝑘 is a set of activities
such that 𝑘-th ant has not yet assigned any activity in theset. The ants repeat assigning activity until all the activities
are assigned to the locations.
[ACO3](Pheromone update): After all the ants have completed assignment, the total cost 𝐿𝑘 (𝑡) is computed, and theamount of the pheromone 𝜏𝑖𝑗 (𝑡) is updated. The amount of𝑘deposited by 𝑘-th ant on the coupling
the pheromone Δ𝜏𝑖𝑗
(𝑖, 𝑗) is decided as{
10/𝐿𝑘 , if (𝑖, 𝑗) ∈ 𝑇 𝑘 (𝑡)
𝑘
(𝑡) =
(3)
Δ𝜏𝑖𝑗
0,
otherwise,
where 𝑇𝑘 (𝑡) is obtained permutation by 𝑘-th ant and 𝐿𝑘 (𝑡)is its total cost. 𝜌 ∈ [0, 1] is the pheromone trail decay
coefﬁcient. Update 𝜏𝑖𝑗 (𝑡) of each coupling (𝑖, 𝑗) depending𝑘;on its Δ𝜏𝑖𝑗
𝜏𝑖𝑗 (𝑡 + 1) = 𝜌𝜏𝑖𝑗 (𝑡) +

𝑀
∑
𝑘=1

𝑘
Δ𝜏𝑖𝑗
(𝑡).

(4)

[ACO4] Let 𝑡 = 𝑡 + 1. Go back to [ACO2] and repeat until𝑡 = 𝑡max .
IV. ACO C HANGING THE R ATE OF DULL ANTS
(IDACO-CR) FOR QAP
We propose ACO Changing the Rate of Dull Ants
(IDACO-CR) and explain its optimization algorithm for QAP
in detail. A ﬂowchart of the proposed IDACO-CR algorithm
for QAP is shown in Fig. 3. Important features of IDACOCR for QAP are follows;(1) Two kinds of ants coexist; intelligent ants which canexactly trail pheromone, and dull ants which cannot trail
the pheromone.
(2) The rate of dull ants are ﬂexibly changed if the system
is trapped into the local optima.
The number of ants is denoted by 𝑀 . Total assignment cost
𝐿 is same as Eq. (1).
[IDACO-CR1](Initialization): Let the iteration number 𝑡 =0. 𝜏𝑖𝑗 (0) = 𝜏0 .
[IDACO-CR2](Classiﬁcation): (1 − 𝑑) × 𝑀 ants and 𝑑 × 𝑀
ants are classiﬁed into a set of the intelligent ants 𝑆intelligent
and of the dull ants 𝑆dull , respectively. 𝑑 is the rate of dull

2832

The update 𝜏𝑖𝑗 (𝑡) of each coupling (𝑖, 𝑗) depending on its𝑘is same as Eq. (4).
Δ𝜏𝑖𝑗
[IDACO-CR5](Change the rate of dull ants): The rate ofdull ants 𝑑 is changed if the system is trapped into the
local optima. Whether IDACO-CR is trapped into the local
solution or not, is judged by following equation;
𝑐𝑢𝑝𝑑𝑎𝑡𝑒 + 𝑐𝑙𝑜𝑐𝑎𝑙 ≤ 𝑡,

Fig. 4. Choice probability 𝑝𝑖𝑗 (𝑡) of Intelligent and Dull ants. The assigning
activity of intelligent ant is chosen by the probability 𝑝𝑖𝑗,𝐼 (𝑡). The assigning
activity of dull ant is chosen by the probability 𝑝𝑖𝑗,𝐷 (𝑡) which does notinclude the amount of pheromone.

ants in all the ants.
[IDACO-CR3](Assign activity): For the intelligent ants andthe dull ants, the assigning activity is chosen by the probability 𝑝𝑖𝑗,𝐼 (𝑡) and 𝑝𝑖𝑗,𝐷 (𝑡) as shown in Fig. 4. IDACO-CR uses
the two kinds of choice probabilities. The probability, that𝑘-th ant (𝑘 = 1, ⋅ ⋅ ⋅ , 𝑀 ) assigns activity 𝑗 to the location 𝑖,is decided by𝑝𝑘𝑖𝑗 ,𝐷 (𝑡) =𝑝𝑘𝑖𝑗 ,𝐼 (𝑡) =[𝜂𝑖𝑗 ]𝛽𝐷,Σ𝑙∈𝑁𝑘 [𝜂𝑖𝑙 ]𝛽𝐷

if 𝑘 ∈ 𝑆dull[𝜏𝑖𝑗 (𝑡)]𝛼 [𝜂𝑖𝑗 ]𝛽𝐼, 𝑘 ∈ 𝑆intelligent ,Σ𝑙∈𝑁𝑘 [𝜏𝑖𝑙 (𝑡)]𝛼 [𝜂𝑖𝑙 ]𝛽𝐼

(5)
(6)

where 𝜂𝑖𝑗 is deﬁned as the inverse of the coupling matrix
element 𝑎𝑖𝑗 . The adjustable parameters 𝛽𝐼 and 𝛽𝐷 control
the weight of the coupling matrix element of the intelligent
ants and dull ants, respectively. Therefore, a searching ability
goes up and down by changing 𝛼, 𝛽𝐼 and 𝛽𝐷 . The equationof intelligent ants is same as that of the conventional ACO.
Since the dull ants cannot trail the pheromone, the equationof the dull ants does not include the amount of pheromone
trail 𝜏𝑖𝑗 (𝑡). Therefore, the intelligent ants judge the next
assigning activity by the pheromone and the coupling matrix
element, however, the dull ants judge the next assigning
activity by only the coupling matrix element. The ants
repeat the assignment until all the activities are assigned tolocations.
[IDACO-CR4](Pheromone update): After all the ants havecompleted assignment, the total cost 𝐿𝑘 (𝑡) are computed andthe amount of the pheromone 𝜏𝑖𝑗 (𝑡) are updated. Note thatdull ants can deposit the pheromone, although they cannot𝑘trail the pheromone. The amount of the pheromone Δ𝜏𝑖𝑗
deposited by 𝑘-th ant on the coupling (𝑖, 𝑗) is same as Eq. (3).

(7)

where 𝑐𝑙𝑜𝑐𝑎𝑙 is the ﬁxed parameter corresponding to the
maximum steps in case IDACO uses the same parameter 𝑑,𝑐𝑢𝑝𝑑𝑎𝑡𝑒 is the iteration number which ﬁnds the best solution.
The rate of dull ants 𝑑 is changed according to{𝑑 + 𝑑𝑢𝑝 and 𝑐𝑢𝑝𝑑𝑎𝑡𝑒 = 𝑡, if Eq. (7) is satisﬁed.
𝑑=otherwise,𝑑0 ,(8)
where the adjustable parameter 𝑑𝑢𝑝 controls the addition of
the rate of dull ants. Thus, the rate of dull ants 𝑑 is ﬂexibly
varied from 𝑑0 to 1.0 and 𝑐𝑢𝑝𝑑𝑎𝑡𝑒𝑑 is reset to 𝑡, if the bestsolution is not updated within a ﬁxed time 𝑐𝑙𝑜𝑐𝑎𝑙 . If the bestsolution is updated, 𝑑 is reset to the initial value 𝑑0 .
[IDACO-CR6] Let 𝑡 = 𝑡 + 1. Go back to [IDACO-CR2] andrepeat until 𝑡 = 𝑡max .
V. S IMULATION R ESULTS
In order to investigate a feasibility and an effectiveness ofthe proposed IDACO-CR, we apply the proposed IDACOCR to ﬁve QAPs. In addition, to conﬁrm the effectiveness ofchanging the rate of dull ants, we consider the conventional
IDACO for QAP whose algorithm does not change the rateof dull ants in the simulation. The rate of dull ants 𝑑 ofthe conventional IDACO is set to 20%, 50% and 100%.
The conventional IDACO with 𝑑 = 100% contains only thedull ants, and the conventional ACO consisted of only theintelligent ants. The QAPs are conducted on Nug12, Scr12(composed of 12 locations and activities), Nug20, Had20 andlipa20a (composed of 20 locations and activities).
In the experiments, the total number of ants 𝑀 in IDACOCR, the conventional IDACO and the conventional ACO are
the same as the number of locations. IDACO-CR and theconventional IDACO include 𝑑×𝑀 dull ants and (1−𝑑)×𝑀
intelligent ants in each simulation. Although the rate of dull
ants 𝑑 in the conventional IDACO is ﬁxed, the rate of dull
ants in IDACO-CR is changed according to Eq. (8) to get
out from the local solution if IDACO-CR is trapped into
the local solution. We repeat the simulation 20 times. The
parameters of IDACO-CR, the conventional IDACO and theconventional ACO were set to the follows;𝜏0 = 10, 𝜌 = 0.9, 𝛼 = 1, 𝛽 = 𝛽𝐼 = 𝛽𝐷 = 1,
𝑡𝑚𝑎𝑥 = 15000, 𝑐𝑙𝑜𝑐𝑎𝑙 = 2000, 𝑑0 = 0, 𝑑𝑢𝑝 = 0.2,

(9)where the evaporation rate 𝜌, the weight of pheromone 𝛼, theweight of coupling matrix element 𝛽, 𝛽𝐼 and 𝛽𝐷 , the search
limit 𝑡𝑚𝑎𝑥 and 𝑐𝑙𝑜𝑐𝑎𝑙 are ﬁxed value. The initial value of therate of dull ants 𝑑0 of IDACO-CR is set to 0. However, the2833

TABLE I
R ESULTS OF THE CONVENTIONAL ACO, IDACO AND IDACO-CR FOR N UG 12, S CR 12, N UG 20, H AD 20 AND LIPA 20 A

Nug12

Scr12

Nug20

Had20

lipa20a

The conventional ACO

4.76%

7.95%

11.84%

3.83%

4.02%

IDACO-CR

4.57%

7.83%

11.66%

3.62%

3.96%

𝑑 = 20%

5.26%

9.47%

12.47%

3.9%

3.99%

𝑑 = 50%

5.88%

8.16%

12.25%

3.91%

3.99%

𝑑 = 100%

6.18%

9.01%

12.47%

3.9%

4.02%

4%

1.5%

1.5%

5.5%

1.5%

I
D
A
C
O

Improved rate of IDACO-CR from ACO

800

1

7500

Total costd1
Total cost
d
0.8

0.6
7300

d

0.5

Total cost

700

dTotal cost

7400

0.4

7200
0.2

600
0

1000

2000

3000

4000

5000 6000
Iteration

7000

8000

0
9000 10000(a)Fig. 5.

7100
0

1000

2000

3000

4000

5000 6000
Iteration

7000

8000

9000 10000(b)

Relationship between the performance and the change of the dull ants rate 𝑑 in the simulation of (a) Nug12, (b) Had20.

rate of dull ants 𝑑 increases every 𝑑𝑢𝑝 when it is judged thatthe system falls into the local solution. In order to compare
the obtained result with the optimal solution, we use the error
rate as follow;(obtained solution) − (optimal solution),(optimal solution)(10)
where this equation shows how close to the optimal solution
the conventional ACO obtains the total cost. Thus, the error
rate nearer 0 is more desirable. Furthermore, in order toinvestigate how well the solution of IDACO-CR are improved
from the solution of the conventional ACO, we use following
improved rate;
Error rate =(AVG of ACO) − (AVG of IDACO-CR).
(AVG of ACO)
(11)
where AVG is the average result in 20 simulations. The
simulation results of the conventional ACO, the conventional
Improved rate =IDACO and the proposed IDACO-CR are shown in Table I.
In this table, the average values nearer 0 are more desirable.
We can conﬁrm that the proposed IDACO-CR obtained better
results than the conventional ACO and the conventional
IDACO for all cases. However, we should note that theconventional IDACO was worse than the conventional ACO
in the cases of Nug12, Scr12, Nug20 and Had20. This resultmeans that the dull ants have a bad effect on the colony
regardless of the number of the dull ants. However, IDACOCR changing the rate of dull ants in the simulation wasable to obtain the best results for all the problems because
it ﬂexibly changed the rate of dull ants depending on the
problem. We can conﬁrm that changing the rate of dull antsin the simulation is more effective than using the ﬁxed rateof dull ants.
Furthermore, we investigate the behavior of IDACO-CR.
Relation of the iteration 𝑡 to the rate of dull ants 𝑑 of IDACOCR for Nug12 and Had20 in 1 simulation is shown in Fig. 5.
We can see that IDACO-CR got out from the local optima
when the iteration time was 𝑡 = 1900, 𝑡 = 3100 and 𝑡 =2834

TABLE IIR ESULTS OF CHANGING THE 𝑑𝑢𝑝 OF IDACO-CR FOR N UG 12, S CR 12,
N UG 20, H AD 20 AND LIPA 20 A
IDACO-CR

Nug12

Scr12

Nug20

Had20

lipa20a

𝑑𝑢𝑝 = 0.2

4.57%

7.83%

11.66%

3.62%

3.96%

𝑑𝑢𝑝 = 0.1

4.13%

7.19%

11.93%

3.75%

3.96%

𝑑𝑢𝑝 = 0.4

5%

8.49%

12.01%

3.86%

3.96%

[8] R. E. Burkard, S.E. Karisch, and F.Rendl, “QAPLIB-A Quadratic
Assignment Problem Library, ” Technical Report No. 287, Technical
Univ. of Graz, Austria, 1994.
[9] 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.

9500 for Had20. At 𝑡 = 1000 and 𝑡 = 2500, IDACO-CR
with 𝑑 = 0.2 fell into local optima, however, the total cost
improved after the rate of dull ants was changed from 𝑑 = 0.2
to 𝑑 = 0.4. This ﬁgure means that increasing the rate of dull
ants 𝑑 has an effect to get out from the local optima. We cansay that the dull ants help getting out from the local optima
because the behavior of the dull ants is different from thatof the intelligent ants. Furthermore, in order to investigate
the effect of varying the rate of dull ants 𝑑𝑢𝑝 , we carriedout the simulations by changing 𝑑𝑢𝑝 . The simulation resultsof IDACO-CRs are shown in Table II. We can conﬁrm thatIDACO-CR with 𝑑𝑢𝑝 = 0.1 obtained the best results for
Nug12 and Scr12. However, by increasing the order of QAP,IDACO-CR with 𝑑𝑢𝑝 obtained the best results for Nug20 and
Had20. We consider that we need to set high 𝑑𝑢𝑝 because itis easy for the QAP of large order to fall into local optima.
VI. C ONCLUSION
This study has proposed novel ACO which contains theintelligent and dull ants and varies the rate of dull ants.
We have conﬁrmed that IDACO-CR changing the rate ofdull ants in the simulation obtained better results than theconventional ACO consisted of only the intelligent ants andthe conventional IDACO which does not change the rate ofdull ants. We have investigated behavior of IDACO-CR andconﬁrmed that changing the rate of dull ants ﬂexibly has theeffect to get out from the local optima because the behaviorof the dull ants is different from that of the intelligent ants.
From these results, we can say that we have to change therate of dull ants depending on the problem and IDACO-CR
is the effective algorithm in solving QAPs.
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 behavior. E. Bonabeau,
M. Dorigo and G. Theraulaz.
[4] M. Dorigo and L. M. Gambardella, “Ant Colonies for the Traveling
Salesman Problem,” BioSystems, vol. 43, pp. 73–81, 1997.
[5] 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.
[6] H. Hasegawa, “Optimization of GROUP Behavior,” Japan EthologicalSociety Newsletter, no. 43, pp. 22–23, 2004 (in Japanese).
[7] S. Shimomura, M. Sugimoto, T. Haraguchi, H. Matsushita, andY. Nishio, “Ant Colony Optimization with Intelligent and Dull Ants”.
Proceedings of International Symposium on Nonlinear Theory and its
Applications (NOLTA’10), pp. 504-507, Sep. 2010.

2835