平成 29 年度電気関係学会四国支部連合大会 講演論文集 (2017 愛媛大学)
2017 SHIKOKU-SECTION JOINT CONVENTION RECORD OF THE INSTITUTES OF ELECTRICAL AND RELATED ENGINEERS (EHIME)

15-4
Ant Colony Optimization Changing Reaction to Pheromone
Ken KAMIYOTSUMOTO,

Masaki TAKEUCHI, Yoko UWATE and Yoshifumi NISHIO( Tokushima University)

1. Introduction

rate of the solution is improved by gradually increasing α.
We compare the solutions of 4 kinds of h (h = 0.5, 1.0, 1.5,2.0).

Recently, nature-inspired metaheuristic optimization algorithms such as Ant Colony Optimization (ACO) is developed. ACO is based the feeding behavior of ant herds.
We suggest the new ACO for Traveling Selesman Problem(TSP).
In this study, we propose ACO in which the pheromone’s
response improves by increasing at the number of repetition. We compare the accuracy of the solution with ACO
and the proposed method.

4. Simulation result
We compare the result of Traveling Salesman Problem(TSP). TSP sets the coordinate of all cities. The purpose of this problem is to find the shortest route which isvisited once to all cities. We performed an experiment using
TSP benchmark eil51 (optimal solution is 426). Averagesof 10 solutions of IACO of each h are obtained and are compared it afterwards. We express the constant value to use
for similation in Eqs. (5), (6).

2. Ant Colony Optimization
Ant Colony Optimization (ACO) was developed by
Marco Dorigo in 1992. We use the following two idealized
rules:• All ants leave volatile pheromone on the route from anest to place of the bait;• All ants choose the strong pheromone route.

k = 51, β = 2.0, ρ = 0.02, tmax = 2000(5)

α = 1.0 (ACO), α0 = 0.001 (IACO)(6)

Table 1 tells the length of the route by the diﬀerence in h.

Table 1: Solution according to the change of h

Implementation steps of the algorithm are summarized
below:
Step1. Initialize the total number of ants k , reaction ofpheromone α, responding to heuristic information βand evaporation rate of pheromone ρ.
Step2. Calculate the evaluation value Eq. (1) when eachant moves from city i to city j. Then, select a routeaccording to the probability based on it.

[τij ]α [ηij ]β,[τij ]α [ηij ]βl∈Nτij (t + 1)=(1 − ρ)τij (t) +∆τi kj (t)=1/Lk (t)(if i, j ∈ Lk ) ,∆τi kj (t) ,

539
434
435
435

604
456
451
454

568
442
438.1
439.1

bestworst

average

435
435

463
451

444.5
438.1

5. Conclusion
This study introduced the improved Ant Colony Optimization. We tried improvement of ACO, where reaction
to pheromone is reinforced according to the number of repetitions. We compared the average values of IACO and thestandard ACO. As a result, IACO performed better thanACO. In the future work, we will make the cause of thisresult clear.

(2)

k=1

(3)

where, Lk expresses the length of the route that each ant
visited.

3. Proposed method

Reference

We propose a improved ACO (IACO). The reaction ofpheromone is constant value in the standard ACO. IACO
is that the pheromone’s response improves by increasing at
the number of repetition. Therefore, IACO changes α byEq. (4)α + = h/tmax

0.5
1.0
1.5
2.0

From the Table 2, it is clear that the average of IACO isbetter than the average of ACO.

(1)km∑average

ACO
IACO

Pheromone values τ and evaluations value a are given byfollowing equations:∑worstTable 2: Simulation results

Step4. Repeat steps 2 to 3 and output the solution.

=best

Table 1 shows that the average of h = 1.5 is best. The
results of IACO and the standard ACO are compared inTable 2.

Step3. Add pheromone to the route that the ant visited.
The value of pheromone can be obtained by Eqs. (2)and (3).

akij (t)h[1] K. Yosuke and K. Hitoshi, “Solution to Traveling Saleman Problem by Ant Colony Optimization Applying Local
Optimum Solutions to Initiazation,” MPS, vol. 19, pp. 109112, 2007.
[2] M. Dorigo and L. M. Gambardella, “Ant Colonies for
the Traveling Salesman Problem,” BioSystem, vol. 43, pp.
73-81, 1997.

(4)

We continue adding it until α becomes 1 and calculate all
α as 1 at time beyond 1. We expect that the convergence167