2011 International Symposium on Nonlinear Theory and its Applications
NOLTA2011, Kobe, Japan, September 4-7, 2011

Ant Colony Optimization using Genetic Information for TSP
Sho Shimomura† , Haruna Matsushita‡ and Yoshifumi Nishio††Department of Electrical and Electronic Engineering, Tokushima University
2-1 Minami-Josanjima, Tokushima 770–8506, Japan‡Department of Reliability-based Information Systems Engineering, Kagawa University
2217-20 Hayashi-cho, Takamatsu, Kagawa 761–0396, Japan
Email: †{s-sho, nishio}@ee.tokushima-u.ac.jp, ‡haruna@eng.kagawa-u.ac.jp
Abstract—This study proposes an Ant Colony Optimization using Genetic Information (GIACO). The GIACO
algorithm combines Ant Colony Optimization (ACO) with
Genetic Algorithm (GA). GIACO searches solutions by using the pheromone of ACO and the genetic information ofGA. In addition, two kinds of ants coexist: intelligent ant
and dull ant. The dull ant is caused by the mutation andcannot trail the pheromone. We apply GIACO to Traveling
Salesman Problems (TSPs) and confirm that GIACO obtains more eﬀective results than the conventional ACO andthe conventional GA.
1. Introduction
Ant Colony Optimization (ACO) [1] is a biologicallyinspired optimization algorithm with pheromone eﬀect ofants and is eﬀective to solve diﬃcult combinatorial optimization problems, such as the Traveling Salesman Problem (TSP) [2], the graph coloring problem, the Quadratic
Assignment Problem (QAP) and so on. TSP is a problem
in combinatorial optimization studied in an operations research and a theoretical computer science. In TSP, given alist of cities and their pairwise distances, the task is to findthe shortest possible tour that each city exactly visited once.
In the ACO algorithm, multiple solutions called “ants” coexist, and the ants drop pheromone on the path connecting
the cities. Pheromone trails are updated depending on thebehavior of the ants. The ants find a food source throughpaths having strong pheromone. By communicating withother ants according to the pheromone strength, the algorithm tries to find the optimal solution. However, ACO hasa problem which is to fall into local solutions. Therefore,
it is important to enhance the algorithm performances byimproving its flexibility.
Genetic Algorithm (GA) [3] is a learning algorithm thatmimic the process of biological evolution and is eﬀective
to solve problems which solution space is unknown. InGA, the solutions are expressed as the genetic code, and anindividual has a genetic code. GA is a collection of individuals and can produce better solution by using crossover,mutation and selection strategies. Several researchers havedeveloped a lot of techniques to improve GA. Those advanced methods are diﬀerent in the chromosome representation and the genetic operators. GA is also combined withlocal search algorithms to find better solution [4].
In our previous study [5], we have proposed anAnt Colony Optimization with Intelligent and Dull Ants(IDACO). IDACO is composed of not only the standard
ants but also ants called “dull ant” which cannot trail thepheromone. We have confirmed an interesting result thatIDACO including the dull ants obtained better results thanthe conventional ACO which containing only the intelligent
ants.
In this study, we propose an Ant Colony Optimization
using Genetic Information (GIACO). GIACO is a combination of IDACO and GA. Some ants pass on genetic information to the next generation by “crossover” and “mutation”. Therefore, GIACO search solutions using thepheromone and the genetic information. The most important feature of GIACO is that two kinds of ants coexist asIDACO. The one is an intelligent ant, and the another is adull ant. The intelligent ant can trail the pheromone andcan use the genetic information. In contrast, the dull ant
cannot trail the pheromone and cannot use the genetic information. Because we consider that dull ant is similar tothe mutation of GA, the dull ant is caused by the mutationin GIACO algorithm.
2. Ant Colony Optimization using Genetic Information
We explain the proposed GIACO algorithm in detail.
A flowchart of the GIACO algorithm is shown in Fig. 1.
GIACO is a combination of IDACO and GA. Some ants ofGIACO pass on genetic information to the next generationby the crossover and the mutation. The most important feature of GIACO is that two kinds of ants coexist; intelligent
ant and dull ant. The intelligent ant can trail the pheromone
and can use the genetic information. In constant, the dull
ant cannot trail the pheromone and cannot use the genetic
information for making the tour. Because we consider thatthe dull ant is similar to the mutation of GA, the dull ant
in GIACO is caused by the mutation. N-city of TSP is denoted as
S ≡ {P1 , P2 , · · · , PN }, Pi ≡ (xi , yi ),(1)where the data area is normalized from 0 to 1, and Pi denotes the i-th city position (i = 1, 2, · · · , N). Each ant (total- 48 -Start

Initialize deposited pheromone τ 0Dull ant

Intelligent
antCity it=1

pi1, I (t )M ants are set to city at random. k = 1

pi1, D (t )k ∈ S dull

Choice probability is pij , D

Figure 2: Probability pi j (t) of Intelligent and Dull ants.The
visiting city of intelligent ant is chosen by the probability pi j,I (t). The visiting city of dull ant is chosen by theprobability pi j,D (t) which does not include the amount ofpheromone and does not include the genetic information.

Choose the next city jNo
Ant ｋ visited all cities

Yes
NoCity 2

City 1

Yes

Choice probability is pij , I

t=t+1

pi 2, D (t )pi 2, I (t )

No

k=k+1

pi 3, D (t )City 3pi 3, I (t )All ants visited all cities

Yes
Update the pheromone

Tour
2→1→5→3→4

Evaluation of all ants

represent

Chromosome
2 1 5 3 4

Selection of high fitness ants

Figure 3: Example of the representation. The tour obtainedby respective ant is represented as a chromosome.

Crossover
Mutation
Update the genetic informationYes

t < t max
NoEnd

Figure 1: Flowchart of the GIACO.

M) is deposited on a city selected at random. (1 − Pm ) × M
ants and Pm × M ants are classified into a set of the intelligent ants S Intel and of the dull ants S dull , respectively.
[GIACO1](Initialization): Let the iteration number t = 0.
τi j (t) is the amount of pheromone deposited on the path(i, j) between the city i and j at time t, and τi j (t) is initially
set to τ0 . The genetic information gi j (t) is initially set to g0 .
[GIACO2](Find tour): The visiting city of each ant is chosen by the probability pi j,I (t) and pi j,D (t) as shown in Fig. 2.
The probability of k-th ant moving from the city i to j is decided by
pki j ,D (t) =[ηi j ]βD, if k ∈ S dull ,Σl∈Nk [ηil ]βD[τi j (t)]α [ηi j ]βI [gi j (t)]γ. otherwise.
pki j ,I (t) =Σl∈Nk [τil (t)]α [ηil ]βI [gi j (t)]γant, respectively. As Eq. (2) does not include the amountof deposited pheromone τi j (t) and τil (t), and the genetic
information gi j (t) and gil (t), the dull ants cannot trail thepheromone and cannot use the genetic information. Thedull ants judge next city depending on only the distancefrom the present location. In contrast, the intelligent ants
which judge next city by the pheromone, the distance andthe genetic information from the present location.
[GIACO3](Pheromone update): After all ants have completed their tours, the amount of deposited pheromone oneach path is updated. We should note that the dull ants
can deposit the pheromone on the path, though they cannot
trail the pheromone. Then, the tour length Lk (t) is computed for both the intelligent and dull ants, and the amountof pheromone ∆τki j (t) deposited by k-th ant on the path (i, j)
is decided as{10/Lk , if (i, j) ∈ T k (t)∆τki j (t) =(4)0,otherwise,
where T k (t) is the tour obtained by k-th ant, and Lk (t) is its
length. Total amount of pheromone τi j (t) of each path (i, j)
is updated depending on ∆τki j (t);(2)
τi j (t + 1) = (1 − ρ)τi j (t) +(3)The adjustable parameters α, βI and βD control the weightof the city information of the intelligent ant and of the dullM∑∆τki j (t),(5)k=1where ρ ∈ [0, 1] is the rate of pheromone evaporation.
[GIACO4](Evaluation): The solutions obtained by ants arerepresented as the chromosomes, and it is shown in Fig. 3.

- 49 -f4 : 8

Child1

Parent2

Child2

Choice probability

f 3 : 12f 2 : 20

Parent1pGA, 1pGA, 2pGA, 3pGA, 4

f1 : 60

60/10020/10012/1008/100

Figure 5: Partially-mapped crossover operator (PMX).

Figure 4: 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 highfitness to be selected when the roulette spins.

BeforeAfter

Figure 6: The inverse mutation.
The evaluation ek of k-th ant is decided as
ek =N,
Lk(6)where ek shows the quality of obtained tour.
[GIACO5](Selection): The GIACO algorithm bequeaths
the ants with high fitness to next generation, to obtain better
solution. We perform scaling and leading of the fitness fk
from the evaluation. The scaling is decided asfk =[χ(ek − eave ) + (emax − ek )]eave,emax − eave

(7)

where χ is the scaling parameter, eave is the average of theant evaluation and emax is the best evaluation in the population. The individuals, whose genetic information is bequeathed to the next generation, are chosen by according
to the probability pGA as shown in Fig. 4, and this rule iscalled roulette selection.
The choice probability of k-th ant is decided byfkpGA,k = ∑ M

k=1 fk.

(8)

It should be noted that it is possible for the dull ant to bechosen as the ant whose genetic information is bequeathedto the next generation, although the dull ant cannot use thegenetic information to choose the next visit city as [GIACO2].
[GIACO6](Crossover): Parents are chosen from the population, and these parents produce their children. This operation is repeated until the number of children is same as
the population. However, the number of parents participating in the crossover is decided by a crossover rate Pc .
There are various ways of the crossover, in this paper, weuse Partially-mapped crossover operator (PMX). PMX istwo-point crossover and is shown in Fig. 5. PMX selects

two cut points along the strings, which represent the parent
tours, at random. The substrings between the cut points areexchanged for genes of the other parents.
[GIACO7](Mutation): After a crossover is performed, themutation is taken place. The probability of the mutation isdecided by the mutation rate Pm . In this paper, we use theinverse mutation, and it is shown in Fig. 6. This mutation
selects two cut points along the strings, which represent thetours, at random. The substrings between the cut points areinversed.
[GIACO8](Update the genetic information): After the genetic operators, the obtained tour length Gk (t) is calculated. The genetic information ∆gki j (t) bequeathed to thenext generation by k-th ant is decided as{
10/Gk , if (i, j) ∈ T k (t)∆gki j (t) =(9)0,otherwise,
where T k (t) is the tour obtained by k-th ant, and Gk (t) is its
length. gi j (t) of each path (i, j) is updated depending on its∆gki j (t);M∑∆gki j (t),(10)gi j (t + 1) = g0 +k=1

where the genetic informations are initialized to g0 at every
iteration t.
[GIACO9] Let t = t + 1. Go back to [GIACO2] and repeat
until t = tmax .
3. Numerical Experiments
In order to evaluate a performance of GIACO and to investigate its behavior, we apply GIACO to various TSPs.
In addition, in order to confirm the eﬀectiveness of the dull- 50 -Table 1: Results of the conventional ACO and GA, GAACO and GIACO.
eil51
kroC100
Average
7.43% 10.21%
ACO
Minimum
6.09%
9.79%
Average
7.52% 13.92%
GAMinimum
4.16%
4.08%
GAAverage
6.32%
9.86%
ACO
Minimum
4.91%
9.55%
Average
5.15%
9.48%
GIACO
Minimum
3.34%
8.38%
Improved rate of GIACO
30.7%
7.15%
from ACOThe TSPs are conducted on eil51 (composed of 51cities), kroC100 (composed of 100 cities).
The simulation results of the conventional ACO, the conventional GA, GA-ACO and GIACO are shown in Table 1. We can see that GA-ACO, which is the combination
method of ACO and GA but does not include the dull ants,obtained better results than the conventional ACO and GA,
for most problems. This result means that the combination
method of ACO and GA is more eﬀective than using only
ACO or GA. In addition, in comparison with GA-ACO, GIACO containing the dull ants obtained better results than
GIACO including no dull ant, in all the problems. This result means that the dull ants help in getting out of the local
optima.
4. Conclusions

ants, we consider GA-ACO whose algorithm is same as GIACO containing no dull ants. We compare GIACO with theconventional ACO, the conventional GA and GA-ACO.
In the experiments, the number of ants M in the conventional ACO, GIACO and GA-ACO are set to the same as
the number of cities, namely M = N. The number of individuals U in the conventional GA is fixed as U = 1024.
The conventional ACO contains the ants whose choiceprobability is decided bypki j (t) =[τi j (t)]α [ηi j ]β.
Σl∈Nk [τil (t)]α [ηil ]β(11)GIACO contains Pm × M dull ants and (1 − Pm ) × M intelligent ants. We repeat the simulation 10 times for all
the problems. The parameters of three methods are set asfollows;τ0 = 10, g0 = 1, ρ = 0.3, α = 1, β = βI = βD = 5,
γ = 5, χ = 100, Pc = 0.8, Pm = 0.05, tmax = 2000,
where the evaporation rate ρ, the weight of pheromone α,
the weight of distance β, βI and βD , the weight of genetic
information γ, the scaling parameter χ, the crossover rate
Pc , the mutation rate Pm and the search limit t = tmax arefixed values.
In order to compare obtained solutions with the optimal
solution, we use an error rate as follow;
Error rate[%]=(obtained solution) − (optimal solution)
× 100.
(optimal solution)(12)
This equation shows how close to the optimal solution theACOs obtain the tour length. Thus, the error rate nearer 0 is
more desirable. Furthermore, in order to evaluate how well
the solution of GIACO are improved from that of ACO, we
use an improved rate as follow;
Improved rate[%] =(Avg. of Error of ACO)−(Avg. of Error of GIACO)
× 100.
(Avg. of Error of ACO)

(13)

In this study, we have proposed Ant Colony Optimization using Genetic Information (GIACO). GIACO optimizes the tour of TSP by using not only pheromone but
also the genetic information as GA. GIACO is composedof the intelligent ants and the dull ants, and the dull ants
are caused by the mutation of GA. We have investigatedthe performances of GIACO by applying it to two TSPs.
We have confirmed that GIACO including the dull ants obtained better results than GIACO which containing only theintelligent ants because the dull ants help in getting out ofthe local optima.
Acknowledgment
This work was partly supported by JSPS Grant-in-Aidfor Scientific Research 22500203.
References[1] M. Dorigo and T. Stutzle, Ant Colony Optimization,Bradford Books, 2004.
[2] M. Dorigo and L. M. Gambardella, “Ant Colonies for
the Traveling Salesman Problem,” BioSystems, vol. 43,
pp. 73–81, 1997.
[3] L. Homaifar, C. Guan, and G. Liepins, “A New Approach to the Traveling Salesman Problem by Genetic
Algorithms,” Proc. 5th Int. Conf. On Genetic Algorithms, Morgan Kaufmann, pp.460-466, 1993.
[4] B. Freisleben and P. Merz, “A Genetic Local Search
Algorithm for Solving Symmetric and Asymmetric
Traveling Salesman Problems,” Proceedings of the1996 IEEE International Conference on EvolutionComputation , pp. 616-621, 1996.
[5] S. Shimomura, M. Sugimoto, T. Haraguchi, H. Matsushita and Y. Nishio ”Ant Colony Optimization withIntelligent and Dull Ants” Proceedings of International Symposium on Nonlinear Theory and its Applications (NOLTA’10), pp. 504-507, Sep. 2010

- 51 -