平成 26 年度電気関係学会四国支部連合大会 講演論文集 （2014 徳島大学）
2014 SHIKOKU-SECTION JOINT CONVENTION RECORD OF THE INSTITUTES OF ELECTRICAL AND RELATED ENGINEERS (TOKUSHIMA)

1-20
Hopfield Neural Network with Random Cutting
for Traveling Salesman Problem
Ryota OSHIMA

Yuki SHOJI Yoko UWATE( Tokushima University)

Yoshifumi NISHIO

1. Introduction
Hopfield neural network is applied to various fields suchas associative memory, optimization problem and so on.
However, the Hopfield neural network often leads to thelocal minimum. It makes diﬃcult to optimize the problem
because of stopping the solutions at local minimum. On
the other hand, some synapses are pruned in the process of
growing a brain of baby in order to inhibit the noises. We
expect that precision of the solution is increased by introducing this phenomenon to the Hopfield neural network
for solving TSP. In this study, we propose the Hopfieldneural network with random cutting of the connections.
Moreover, we carry out the simulation and discuss influence of the Hopfield neural network with random cuttingfor TSP.

Figure 1: Disposition with 22 cities.

Table 1: Average distance (A = 1, B = 1, D = 41).
Con.
I=5I = 10 I = 15 I = 20
r = 1 105.12 91.19
95.16
91.12
93.95
r = 5 105.12 89.69
92.98
92.08
92.13
r = 10 105.12 94.52
93.79
95.08
94.90
r = 15 105.12 98.80
99.41
99.56
99.73
r = 20 105.12 105.55 106.90 106.88 106.12

2. Proposed method
In this study, we focus on influences of the Hopfieldneural network with random cutting for TSP. In particular, we cut some connections between the neurons. The
cutting conditions are described below.
• Cutting ratio sets constantly.
• We carry out the cutting at a regular interval.
• The internal states are retained till next cutting.
• We cut the connections between the neurons after
resetting the connections at each interval.
We fix the length of regular interval as 5, 10, 15 and20. The unneccessary connections are decided completelyrandom. In addition to this, we discuss the simulation
results by the average distance in next section.

3. Simulation results
In this simulation, we discuss the optimization in thecase of the disposition with 22 cities as shown in Fig. 1.
We simulated 5000 times per one trial. In addtion, thecutting ratio r is defined from 1 to 20 %. We compare
the average distance, and we simulated ten times of trials
with diﬀerent initial values. The shortest distance to goaround all cities is about 75.67.
The simulation results are shown in Table 1. It is expressed the comparsion between average distances of proposed and the conventional methods. The cutting ratioshows r. In addition, the regular interval shows I. The
diﬀerences of each average distance with the low cutting
rate is smaller than the one with the high cutting rate.
In other simulation results, the precision of the solution
decreases when the cutting ratio is raised. This cause includes that we may cutting necessary connections between
the neurons by random cutting.

Figure 2: Comparsion between the proposed and the conventional methods.

4. Conclusions
We studied the solution abilities of the Hopfield neural network with the random cutting for the Traveling
Salesman Problem. As the simulation results, the proposed method shows smaller average distances than theconventional method. However, the precision of the proposed method decreases if the cutting ratio is defined as
the large value. In future work, we would like to devise
various algorithms to cut the connections. Furthermore,
we increase city numbers and simulate it.

20