2012 International Workshop on Nonlinear Circuits,
Communications and Signal Processing
NCSP'12, Honolulu, Hawaii, USA. March 4-6, 2012

Application of Ant Colony Optimization Using Genetic Information to QAP
Sho Shimomura† , Haruna Matsushita‡ , Yoko Uwate† and Yoshifumi Nishio††Tokushima University
2-1 Minami-Josanjima, Tokushima, Japan
Phone:+81-88-656-7470
FAX:+81-88-656-7471
Email: {s-sho, uwate, nishio}@ee.tokushima-u.ac.jp

Abstract
This study proposes an Ant Colony Optimization using Genetic Information (GIACO). The GIACO algorithm combines
the Ant Colony Optimization (ACO) with the Genetic Algorithm (GA). GIACO searches solutions using the pheromoneof ACO and the genetic information of GA. In addition, twokinds of ants coexist: intelligent ant and dull ant. The dull ant
is caused by the mutation and cannot trail the pheromone. GIACO algorithm is more similar to the real ant colony than theconventional ACO algorithm. We apply GIACO to Quadratic
Assignment Problems (QAPs) and confirm that GIACO obtains more effective results than the conventional ACO andthe conventional GA.
1. Introduction
The Ant Colony Optimization (ACO) [1] was proposed tosolve difficult combinatorial optimization problems [2], suchas a Quadratic Assignment Problem (QAP) [3], a Traveling
Salesman Problem (TSP) [4], a graph coloring problem [5]and so on. 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 flow between activities, the task is to assign all activities to different locations
with the minimum cost among all of the possible combinations. In the ACO algorithm, multiple solutions called “ants”
coexist, and the ants drop a substance called the pheromone.
Pheromone trails are updated depending on the behavior of
the ants. By communicating with other ants according to thepheromone strength, the algorithm tries to find the optimal
solution. However, ACO has a problem which is to fall into
local solutions. Therefore, it is important to enhance the algorithm performances by improving its flexibility.
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 dawdle 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 trail‡Kagawa University
2217-20 Hayashi-cho, Takamatsu, Kagawa, Japan
Phone:+81-87-864-2237
FAX:+81-87-864-2262
Email: haruna@eng.kagawa-u.ac.jp

the pheromone exactly, and dull ants which cannot trail thepheromone. From results, the ants group including the dull
ants can obtain more foods than the group cosisting of only
the intelligent ants. The dull ants are regarded as having task
which find the new food sources by dawdle. It means thatthe coexistence of the intelligent and dull ant improves theeffectiveness of the feeding behavior.
Genetic Algorithm (GA) [7] [8] is a learning algorithm thatmimics the process of biological evolution and is effective tosolve problems which solution space is unknown. In GA, thesolutions are expressed as the genetic code, and an individual
has a genetic code. GA is a collection of individuals and can
produce better solution by using crossover, mutation and selection strategies. Several researchers have developed a lot oftechniques to improve GA. Those advanced methods are different in the chromosome representation and the genetic operations. GA is also combined with local search algorithms
to find better solution.
In this study, we propose a novel ACO algorithm called
an Ant Colony Optimization using Genetic Information (GIACO). GIACO is a combination of ACO and GA. Someants pass on genetic information to the next generation by“crossover” and “mutation”. Therefore, GIACO search solutions using both the pheromone and the genetic information.
The most important feature of GIACO is that two kinds ofants coexist. The one is an intelligent ant and the another is adull ant. The intelligent ant can trail the pheromone and canuse the genetic information. In contrast, the dull ant cannot
trail the pheromone and does not use the genetic information.
Because the dull ants are similar to the mutation of GA, we
consider that the dull ants are caused by the mutation in GIACO algorithm.
2. Ant Colony Optimization Using Genetic Information(GIACO)We explain the proposed GIACO algorithm in detail. A
flowchart of the GIACO algorithm is shown in Fig. 1. GIACO
is a combination of ACO and GA. Some ants of GIACO- 481 -StartActivity 3

Location i

Initialize deposited pheromone τ0

pki3, I (t)pki3,D(t)M ants are set to location. k = 1

pki1,D(t) p
ki1, I (t)Population size M

Activity 1

K∈Sdull
Evaluation of individuals

No

Yes

Probability pij, I

Probability pij, D

pki2,I (t)pki2,D(t)Dull ant

Activity 2Intelligent
ant

Selection of high fitness individuals

k =k+1

Assign activity j to location iNo

Ant k assigned all activities

Figure 2: Choice probability pkij (t) of Intelligent and Dull
ants. The assigning activity of intelligent ant is chosen by
the probability pkij,I (t). The assigning activity of dull ant ischosen by the probability pkij,D (t) which does not include
the amount of pheromone and does not include the genetic
information.

CrossoverYes
Mutation

Compute the total cost Lk(t)No

Compute the total cost Gk(t)All ants assigned all activities

Yes
Update the genetic information

Update the pheromone

t =t +1

Yes

assign activity depending on the probability pkij,I (t) andpkij,D (t), respectively, as shown in Fig. 2. GIACO uses
the two kinds of choice probabilities. The choice probability Pkij (t), that k-th ant (k = 1, · · · , M ) assigns activity j tothe location i, is decided byt < tmaxNo
End

Figure 1: Flowchart of the GIACO.

pkij ,D (t) =pass on the genetic information to the next generation by thecrossover and the mutation. The most important feature of
GIACO is that two kinds of ants coexist; intelligent ant anddull ant. The intelligent ant can trail the pheromone and canuse the genetic information. In constant, the dull ant cannot
trail the pheromone and does not use the genetic information
for making the tour. Because the dull ant is similar to themutation of GA, we consider that the dull ant in GIACO iscaused by the mutation.
In QAP, given two matrices, a distance matrix D and aflow matrix F , find a permutation Π which corresponds tothe minimum value of the total assignment cost L in Eq. (1).
n ∑
n
∑
L=
Dij Fπ(i)π(j) ,(1)[ηij ]βD, if k ∈ Sdull ,Σl∈Nk [ηil ]βD(2)[τij (t)]α [ηij ]βI [gij (t)]γ. otherwise.
Σl∈Nk [τil (t)]α [ηil ]βI [gij (t)]γ(3)
where ηij is defined as the inverse of the coupling matrix element aij . The adjustable parameters α and γ control theweight of the pheromone intensity and of the genetic information of the intelligent ant, respectively. The adjustable parameters βI and βD control the weight of the coupling matrix
element of the intelligent ant and of the dull ant, respectively.
Eq. (2) does not include the amount of deposited pheromone
τij (t) and τil (t), and the genetic information gij (t) and gil (t).
i=1 j=1
It means that the dull ants cannot trail the pheromone andwhere Dij and Fij are the (i, j)-th elements of D and F , re- does not use the genetic information. Therefore, although
spectively. π(i) is the i-th element of the vector Π, and n is the intelligent ants judge the next assigning activity by thethe size of the problem. The number of ants is denoted by pheromone, the coupling matrix element and the genetic inM . (1 − Pm ) × M ants and Pm × M ants are classified into formation, the dull ants judge the next assigning activity bya set of the intelligent ants SIntel and of the dull ants Sdull , only the coupling matrix element. The ants repeat the assignrespectively.
ment until all the activities are assigned to locations.
[GIACO1](Initialization): Let the iteration number t = 0. [GIACO3](Pheromone update): After all the ants have comτij (t) is an amount of pheromone trail on a coupling (i, j) to pleted assignment, the total cost Lk (t) are calculated and theassign an activity j to the location i, and τij (0) = τ0 . The amount of the pheromone τij (t) are updated. We should note
genetic information gij (t) is initially set to g0 .
that the dull ants can deposit the pheromone although they
[GIACO2](Assign activity): The intelligent and dull ants cannot trail the pheromone. The amount of the pheromone
pkij ,I (t) =- 482 -

f4 : 8

Parent1f 3 : 12Child11 2 3 4 5

Choice probability
Parent2

pGA,60/100
A
1 60/100

3 2 5 4 1Child23 4 5 2 1

1 4 3 2 5

BpGA,
20/1002 20/100

f 2 : 20

f1 : 60

CpGA,
12/1003 12/100

Figure 4: Cycle crossover (CX).

pGA,8/100
D
4 8/100

BeforeFigure 3: Example of the roulette selection. Individuals,
whose genetic information is bequeathed to the next generation, are chosen by the choice probability pGA,k . For example, evaluation of 1st individual f1 is 60, of 2nd individual f2
is 20, of 3rd individual f3 is 12 and of 4th individual f4 is 8.
It shows that it is easy for the individual with high fitness tobe selected when the roulette spins.

After

Figure 5: Order changing.

is repeated until the number of children is same as the population size. However, the number of parents participating in
the crossover is decided by a crossover rate Pc . There areas{
10/Lk , if (i, j) ∈ Tk (t)various ways of the crossover, in this paper, we use the Cycle∆τkij (t) =(4)0,otherwise,crossover (CX) shown in Fig. 4. CX exchanges the first locus
of Parent 1 with the first locus of Parent 2. Next, CX searches
where Tk (t) is obtained permutation by k-th ant, and Lk (t) issame value as Parent 2 from Parent 1 and exchanges the locus
its total cost. Update τij (t) of each coupling (i, j) dependingof Parent 1 with the locus of Parent 2 which is the same as thekon its ∆τij;
locus of Parent 1. Repeat same operation until CX searches alocus which has been exchanged once.
M∑τij (t + 1) = (1 − ρ)τij (t) +∆τkij (t),(5) [GIACO7](Mutation): After a crossover is performed, thek=1
mutation is carried out. The probability of the mutation is decided by the mutation rate Pm . In this paper, we use the orderwhere ρ ∈ [0, 1] is the rate of pheromone evaporation.
[GIACO4](Evaluation): GA is performed in parallel with changing shown in Fig. 5. This mutation selects two numbers
ACO. The solutions of GA are represented as the chromo- and exchanges them. The number of dull ants is same as thesomes and are performed genetic operation like the evalua- number of mutated individuals.
tion, the crossover and the mutation. The population size U [GIACO8](Update the genetic information): After the geis same as the number of ants, namely U = M . The evalua- netic operation, the obtained tour length Gk (t) is calculated.
The genetic information ∆gkij (t) bequeathed to the next gention ek of k-th individual is decided as
eration by k-th individual is decided as
1
ek =
,
(6)
{
Lk
10/Gk , if (i, j) ∈ Tk (t)∆gkij (t) =(8)0,otherwise,
where ek shows the quality of obtained tour.
[GIACO5](Selection): The GIACO algorithm bequeaths the where Tk (t) is the tour obtained by k-th inidividual, andindividuals with high fitness to next generation to obtain bet- Gk (t) is its cost. gij (t) of each coupling (i, j) is updated
ter solution. The individuals, whose genetic information is depending on its ∆gkij (t);bequeathed to the next generation, are chosen by according toM
the probability pGA as shown in Fig. 3, and this rule is called∑
roulette selection. The choice probability of k-th individualgij (t + 1) = g0 +∆gkij (t),(9)
is decided by
k=1
ek
pGA,k = ∑M.
(7)where the genetic information are initialized to g0 at every
k=1 ekiteration t.
[GIACO6](Crossover): Parents are chosen from the popula- [GIACO9] Let t = t + 1. Go back to [GIACO2] and repeattion, and these parents produce their children. This operation until t = tmax .
k∆τij
deposited by k-th ant on the coupling (i, j) is decided- 483 -

Table 1: Results of the conventional ACO, IDACO and IDACO-CR for Nug12, Scr12, Nug20, Had20 and lipa20a.
Nug12 Tai 12
Scr12
Nug20 Had20 lipa20a
The conventional ACO 3.17% 5.54% 5.36% 11.39% 3.44% 3.92%
The conventional GA
1.82% 5.13% 3.13% 7.46% 3.45% 4.14%
GA-ACO
1.97% 4.87% 3.69%
7.51%
3.37%
4.1%
GIACO
1.73% 4.97% 2.84% 7.46% 3.16% 3.04%

3. Simulation Results
In order to evaluate a performance of GIACO and to investigate its behavior, we apply GIACO to various QAPs.
In addition, in order to confirm the effectiveness of the dull
ants, we consider GA-ACO whose algorithm is same as GIACO but containing no dull ants. We compare GIACO withthe conventional ACO, the conventional GA and GA-ACO.
In the experiments, GIACO include P m × M dull ants and(1 − P m) × M intelligent ants in each simulation. The QAPs
are conducted on Nug12, Tai12 and Scr12 (composed of 12
locations and activities), Nug20, Had20 and lipa20a (composed of 20 locations and activities).
We repeat the simulation 20 times. The parameters of GIACO, the conventional ACO, the conventional GA and GAACO were set to the follows;

the colony even if they look like unnecessary. From these results, we can say that the algorithm which similar to the real
ant colony obtained effective results.
4. Conclusions
In this study, we have proposed Ant Colony Optimization
using Genetic Information (GIACO). GIACO optimizes thecost of QAP by using not only pheromone but also the genetic
information as GA. GIACO is composed of the intelligent
ants and the dull ants, and the dull ants are caused by themutation of GA. We have investigated the performances of
GIACO by applying it to six QAPs. We have confirmed that
GIACO including the dull ants obtained better results than
GIACO which containing only the intelligent ants. Therefore,
we can say that the algorithm which similar to the real ant
colony obtained effective results.

τ0 = 10, ρ = 0.9, α = 1, βI = βD = 1, γ = 1,
M = U = 100, tmax = 4000, Pc = 0.4, Pm = 0.05
References(10)
where the evaporation rate ρ, the weight of pheromone α, the [1] M. Dorigo and T. Stutzle, Ant Colony Optimization, Bradford
Books, 2004.
weight of coupling matrix element βI and βD , the weight ofgenetic information γ, the search limit tmax , the crossover [2] E. Bonabeau, M. Dorigo, and G. Theraulaz. From Natural to
Artificial Swarm Intelligence, Oxford University Press, 1999.
rate Pc and the mutation rate Pm are fixed value. In order tocompare the obtained result with the optimal solution, we use [3] V. Maniezzo and A.Colorni, “The ant system applied to thethe error rate as follow;
quadratic assignment problem,” IEEE Transactions on Knowledge and Data Engineering, vol. 11, no. 5, pp. 769-778, 1999.

(obtained solution) − (optimal solution),(optimal solution)(11)
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. The simulation results of theconventional ACO, the conventional GA, GA-ACO and the
proposed GIACO are shown in Table I.
We can see that GIACO, which is the combination methodof ACO and GA including the dull ants, obtained better results than the conventional ACO and GA, for most the problems. This result means that the combination method of ACO
and GA is more effective than using only ACO or GA. In addition, in comparison with GA-ACO, GIACO including thedull ants obtained better results than GIACO including no dullant, in most problems. This result means that the dull ants affect the colony in a positive way. In fact, the dull ants help
Error rate =[4] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy-Kan, and D. B.
Shmoys, The Travelling Salesman Problem, Wiley, 1985.
[5] M. Dorigo, G. D. Caro and L. M. Gambardella, “Ant Algorithms
for Discrete Optimization,” Artificial Life, vol. 5 no. 2, pp. 137172, 1999.
[6]

H. Hasegawa, “Optimization of GROUP Behavior,” Japan
Ethological Society Newsletter, no. 43, pp. 22–23, 2004 (inJapanese).

[7] D.E. Brown, C.L. Huntley, and A.R. Spillane, “A parallel genetic heuristic for the quadratic assignment problem,” Proc. ofInt. Conf. on Genetic Algorithms, pp. 406-415, 1989.
[8] P. Merz and B. Freisleben, “A genetic local search approach tothe quadratic assignment problem,” Proc. of Int. Conf. on Genetic Algorithms, pp. 465-472, 1997.

- 484 -