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

41-4

The Hybrid of Ant Colony Optimizationand Simulated Annealing
Naoto Hara

Yudai Shirasaki Sho Shimomura
Yoshifumi Nishio(Tokushima University)

Yoko Uwate

1. Introduction
Ant Colony Optimization (ACO) is an optimization algorithm imitating ant’s feeding action and is effective tosolve combinatorial optimization problems like the Traveling Salesman Problems (TSPs)[1]. It is well known that
TSP can be solved by using various kines of Algorithms
such as Genetic Algorithm (GA), Simulated Annealing(SA) and so on. However it is difficult to find the optimal solution by increasing the number of elements.
In this study, we propose the hybrid of Ant Colony Optimization and Simulated Annealing (ACOSA). ACOSA
has three important features. First, ACO and SA are
operated in parallel. Second, the information obtained
from SA is treated as a honey which is different with apheromone. Third, the honey affects the searching solutions of ACO. We apply ACOSA to two TSPs and confirm
its effectiveness.

2. ACOSAIn ACOSA algorithm, ACO and SA make tour, respectively. The tour made by SA is similarly estimated as apheromone and affects the search probability of ACO.
The evaluation value of the tour made by SA is calledhoney.
[ACOSA 1](Initialization): Let iteration number t = 0.
τij (t) is the amount of pheromone trail on the path (ij)between cities i and j at time t, and τij (t) is initially set
to τ0 . mij (t) is the amount of honey trail on the path (ij)between cities i and j at time t, and mij (t) is initially set
to m0 .
[ACOSA 2](Find tour):· Find tour of ACO: For the k-th ant (k = 1, 2, · · ·, M ),the visiting city is chosen by probability pkij (t). ACOSA
uses two kinds of pkij (t) according to conditions. The k-thant finds a tour according to the following equations;[τij ]α [ηij ]β [mij ],if LS ≥ LA
 P
αβh=Ω [τih ] [ηih ] [mih ](1)
pkij (t) =βγ[ηij ] [mij ] P,otherwise,βγh=Ω [ηih ] [mih ]where LA is the best tour length of ants at t, LS is thebest tour length of SA at t. Ω is a city set which ants are
not visiting yet. α, β, and γ are the control parametersof τ , η, and m, respectively.
· Find tour of SA:
1: City is set at random and tour is created. This tour
length is the present state s.
2: Two of the city turn of s are exchanged and tour iscreated. This is performed for the number of cities, andminimum length in its tours is the neighborhood state e.
3: Evaluation and updating are processed as follows.
Finds a tour according to the following equations;if sb ≥ s(t) sb = s(t),(2)s(t) ≥ e e,e,s(t) < e : f ollow the prob. ps (t) (3)s(t+1) = s(t), s(t) < e : f ollow the prob. p (t)sPowered by TCPDF (www.tcpdf.org)

where sb is the best state.

s(t) − e,(4)Twhere T is a temperature parameter.
[ACOSA 3](Pheromone update): Compute the tour
length Lk (t) and update the amount of the pheromone
trail τij byMXk
τij (t + 1) = (1 − ρ)τij (t) +∆τij(t),(5)k=1
1/Lk ,if tour made by antk(6)∆τij(t) =0,otherwise,
ps (t) = exp

where ρ ∈ [0, 1] is the pheromone trail decay coefficient.
[ACOSA 4](Honey update): Compute the tour lengthsb and update the amount of the honey by
mij (t + 1) = 1/sb
(7)
[ACOSA 5] Let t = t + 1 and T ∗ c. c ∈ [0, 1] is coolingcoefficient and makes T low gradually. Go to [ACOSA 2]
and repeat until the maximum time limit t = tmax .

3. Numerical Experiments
In order to confirm the effectiveness of ACOSA, we apply ACOSA to two TSPs, ulysses16 and att48. The total
number of the ants of ACO and ACOSA are set to thesame the number of cities. We carry out the simulation
2000 iterations for 10 times. The simulation results ofACO and ACOSA are shown in Table 1. In this table,
we can confirm that ACOSA obtains better result thanstandard ACO in both of TSPs. From this results, weconsider that honey has a good effect on search solutionof ACO. SA performs changing solution for the worse(adoption of a long tour) in an early stage. We consider
that this algorithm diversify search solution of ACO.
Table 1: Results of ACO and ACOSA for ulysses16 andatt48.
ulysses16
att48
AVG
0.89 %
2.52 %ACOMIN
0.15 %
2.30 %
AVG
0.10 %
2.19 %ACOSA MIN
0%0.80 %

AVG=(Avg.tour - Optimal tour)/Optimal tour ∗ 100
MIN=(M in.tour - Optimal tour)/Optimal tour ∗ 100

4. Conclusions
In this study, we have proposed the hybrid ofAnt Colony Optimization and Simulated Annealing(ACOSA). ACOSA obtained the better results than standard ACO. In particular, the minimum has been improved greatly because SA diversify search solution ofACO.
Reference[1] M. Dorigo and L. M. Gambardella, ”Ant Colonies
for the Traveling Salesman Problem,” BioSystems, vol.
43, pp. 73-81, 1997.