2015 International Symposium on Nonlinear Theory and its Applications
NOLTA2015, Kowloon, Hong Kong, China, December 1-4, 2015

Hopfield Neural Networkwith Synaptic Pruning for TSP
Ryota Oshima† , Yoko Uwate† and Yoshifumi Nishio††Departmaent of Electrical and Electronic Enginnering, Tokushima University
2-1 Minamijosanjima, Tokushima, 770-8506, Japan
Email: {ryota, uwate, nishio}@ee.tokushima-u.ac.jp
Abstract—In this study, we propose two methods thatincorporate the concept of synaptic pruning for an artificial
neural network. The synaptic pruning is that the excess
couplings between the neurons are disconnected. The performance of the two methods are investigated when thesemethods are applied to the Hopfield neural network for
Traveling Salesman Problem (TSP).
1. Introduction
In recent years, the brain science has been widely studiedin various fields. It is important to study brain science for
future various kinds of applications in our society. Amongthese, we focus on the neural network. The neural network
is calculation model which can replicate some functions ofhuman brain. In particular, it has been researched extensively that Hopfield neural network is applied to solvingmethod for the combinatorial problems [1]-[3]. The Hopfield neural network is applied to various fields such as associative memory [4]-[5], optimization problem [6] and soon. However, Hopfield neural network has several problems. For instance, the number of couplings between neurons is too large because Hopfield neural network is fullcoupling. It makes diﬃcult to optimize the problem.
We focus on the synaptic pruning, the phenomenon
which causes actually in the brain. Excess synapses areformed in the brain of the newborn creatures. Unnecessary synapses in the process of growth are cut, and normal
neural circuit is completed. This process is called synaptic pruning, it has been demanded for the functional neuralcircuit. It follows that, the synaptic pruning is the process
to increase the eﬃciency of the neural network [7]-[8].
In this study, we propose two methods as condition tocutting the couplings between the neurons. In order to confirm the performance of two proposed methods, we apply
the proposed methods to Hopfield neural network. The first
method is that all couplings of the selected neurons are disconnected. The second one is that certain couplings selected by random are cut with the disconnecting rate. Inaddition, we investigate Hopfield neural network with theproposed methods for Traveling Salesman Problem (TSP),
which is known as representative applications of the Hopfield neural network. Furthermore, we discuss the comparison of the performance by the two proposed methods.

2. Solving for TSP by Hopfield neural network
Hopfield neural network is defined as the energy function the objective function and constraints condition tosolve this problem. The objective function represents thatfind the shortest route, and constraints condition represents
that visit each city exactly once. The state of neurons xi j arerenewed to decrease the energy function E. Hopfield neural network is used for solving the optimization problem.
Solutions are obtained by using Hopfield neural network tominimize the energy function. For solving N-element traveling salesman problem by Hopfield neural network, N×N
neurons are required.
The energy function E for the TSP is described as follows:A∑∑B∑∑(xi j − 1)2 +(xi j − 1)22 i
2 j ijNE=NND ∑∑∑dik xi j (xk, j+1 + xk, j−1 ).
2 i k jN+NNN(1)where dik is the distance from city i to city k, and the scaling
parameters A, B and D are positive constants.
The first term of the above formula represents that eachcity is only visited once. The second term indicates that it
is not possible to visit more than one city at the same time.
The third term represents the energy function to find theshortest of the route.
Furthermore, the Hopfield neural network has the couplings strengths and external input given as:
W= −Aδim (1 − δ jn ) − Bδ jn (1 − δim )
 i j,mn− Ddim (δn, j+1 + δn, j−1 ).
 h = A + B.

(2)

ij

where δim is the Kronecker’s delta, which is defined as:- 105 -{
δim =10(i = m),(i , m).

(3)

The update equation for the state of neurons is given as:ui j =∑

Wi j,mn xmn + hi j .

(4)

mn

where xi j is a sigmoid function such as:
xi j =( u ))1(ij
1 − tanh.
20.5

(5)

In next section, we discuss two proposed methods as condition to cutting couplings between the neurons.

Figure 1: Disposition with 22 cities.

3. Proposed Method
In this study, we investigate the influences of Hopfieldneural network with synaptic pruning for TSP. In order torealize synaptic pruning, we define two methods as condition to cutting couplings between the neurons. The first
method is defined neuronal death method. This neuronal
death method’s cutting conditions are described as follows:• Selecting the neurons at a constant rate at random.

Figure 2: Disposition with 48 cities.

• Cutting all couplings of the neurons which we select.
• The internal states are retained till next cutting.

4.1. 22 cities
The second method is defined random cutting method. Thisrandom cutting method’s cutting conditions are describedas follows:• Selecting the couplings between the neurons at a constant rate at random.
• Cutting the couplings which we select.
• The internal states are retained till next cutting.
The diﬀerence of two methods is to cut all couplings ofthe neurons which we select, or couplings are cut selectedat random from among all of the couplings.
Here, the couplings are cut at a regular interval. The
length of regular interval (update of network) is set from
1 to 20. The unnecessary neurons and couplings are decided completely random. In addition to this, we discuss
the comparison of the performance by the two methods.

The simulation results of neuronal death and random cutting methods when the results comparison of the shortest
distance are shown in Table 1, Fig. 3 and Table 2, Fig. 4.
The parameters of Hopfield neural network are fixed as A
= 1, B = 1 and D = 41. The cutting rate is r, the regularinterval is I. These results shows that the comparison of performance of the conventional method and that of the proposed networks with 22 cities. As these simulation results,
the proposed networks are improved performance than theconventional network. However, comparing the two methods, neuronal death method has a higher performance thanrandom cutting method.
On the other hand, Tables 3 and 4 represent the results by
two proposed methods when the results comparison of theaverage distance. By comparison with the two proposed
methods, neuronal death method has a higher performance
than random cutting method.
Table 1: The neuronal death method (shortest distance).

4. Simulation results
In this simulation, we discuss the optimization in thecase of the disposition with 22 and 48 cities as shown inFigs. 1 and 2. The number of iteration is 5000 times perone trial. In addition, the cutting rate r is changed from 1 to25 %. We compare the shortest and the average distances.
We simulated ten times of trials with diﬀerent initial values. The optimal solutions of the problems are known as
75.7 and 33523.7.

r=1r=5r = 10r = 15r = 20r = 25- 106 -Conv.
99.8
99.8
99.8
99.8
99.8
99.8

Proposed network (neuronal death)I = 1 I = 5 I = 10 I = 15 I = 20
88.5
81.8
84.2
82.7
83.9
83.8
79.5
80.6
79.9
80.6
83.3
79.3
78.4
79.7
79.4
79.7
79.2
79.1
79.1
80.4
80.1
79.6
79.6
79.8
79.3
80.1
80.8
80.4
81.0
81.7

Table 2: The random cutting method (shortest distance).

r=1r=5r = 10r = 15r = 20r = 25

Conv.
108.5
108.5
108.5
108.5108.5
108.5

Proposed network (random cutting)I = 1 I = 5 I = 10 I = 15 I = 20
83.2
92.9
100.0
98.5
100.1
81.8
80.2
84.3
83.3
85.9
85.8
79.9
79.8
80.4
80.6
90.0
81.7
81.4
81.2
81.7
92.4
82.5
81.7
82.4
82.8
96.4
85.7
82.9
84.2
84.6

Table 3: The neuronal death method (average distance).

r=1r=5r = 10r = 15r = 20r = 25

Conv.
105.1
105.1
105.1
105.1
105.1
105.1

Proposed network (neuronal death)
I=1I=5I = 10 I = 15 I = 20
95.1
91.295.2
91.1
94.0
92.0
89.7
93.0
92.1
92.1
93.0
94.5
93.8
95.1
94.9
101.8
98.8
99.4
99.6
99.7
112.9 105.6 106.9
106.9
106.1
113.9 114.7 112.7
112.5
113.5

Table 4: The random cutting method (average distance).

r=1
r=5r = 10r = 15r = 20r = 25

Figure 3: Comparison of performance between the neuronal

Conv.
112.8
112.8
112.8
112.8
112.8
112.8

Proposed network (random cutting)
I=1
I=5I = 10 I = 15 I = 20
95.6
103.4 108.2
109.1
112.3
110.2
95.8
98.6
99.6
103.2123.9 104.0 100.7
100.3
100.2
132.9 113.3 110.0
106.3
107.6
141.3 121.7 116.2
113.7
111.6
148.9 127.5 120.7
118.3
117.3

Table 5: The neuronal death method (shortest distance).

death and the conventional methods.
r=1
r=5r = 10r = 15r = 20r = 25

Conv.
46006.2
46006.2
46006.2
46006.2
46006.2
46006.2

Proposed network (neuronal death)
I=1
I=5I = 10I = 15I = 2045357.3 43012.7 42806.0 42895.0 42464.4
44887.8 40519.0 40445.9 40200.7 41385.9
44083.7 40090.9 40210.4 40518.1 40719.2
45217.0 40844.6 40727.4 40821.3 40146.2
44850.5 41440.4 41267.0 41007.6 40552.7
45456.6 41961.0 41938.2 41156.6 41604.6

Table 6: The random cutting method (shortest distance).

Figure 4: Comparison of performance between the random cutting and the conventional methods.

r=1r=5r = 10r = 15r = 20r = 25

Conv.
50060.750060.750060.750060.750060.750060.7

Proposed network (random cutting)
I=1I=5I = 10I = 15I = 2040718.4 44712.5 43932.3 45450.0 45413.451761.2 43082.1 44004.5 43235.3 43420.359129.9 46349.9 45832.5 45694.6 46001.263547.2 49307.5 47719.9 47637.4 48272.471495.7 51175.3 47608.1 47530.9 47942.977058.8 53384.5 47773.5 46852.9 47580.6

4.2. 48 cities
Next, we explain the results of 48 cities. The simulation results of neuronal death method and random cutting
method with shortest distance are shown in Table 5, Fig. 5
and Table 6, Fig. 6. The parameters of Hopfield neural network are fixed as A = 1, B = 1 and D = 100. These resultsshows that the comparison of performance of the conventional method and that of the proposed networks. As theresults of neuronal death method, the performance of network is improved although away from the optimal solution.

However, the results of random cutting method does not
improve performance. In consequence, the performanceof neuronal death method is better than random cutting
method.
On the other hand, each of the Tables 7 and 8 represents
the results by two proposed methods when the results comparison of the average distance. The performance of resultsof 48 cities, the both neuronal death and random cutting
methods are not high performance when we compare with- 107 -the results of 22 cities. However, comparing the two methods, neuronal death method has a higher performance thanrandom cutting method.
5. Conclusion

Figure 5: Comparison of performance between the neuronal
death and the conventional methods.

We have studied the solution abilities of the Hopfieldneural network with two methods as condition to cutting
couplings between the neurons for TSP. As the simulation
results, the neuronal death method shows very good performance. In addition, the random cutting method also better
performance than conventional network. However, compared to neuronal death and random cutting methods theperformance of the random cutting method is inferior.
In future works, we would like to devise various algorithms to cut the couplings. Furthermore, we would like tosimulate Hopfield neural network for large-scale model.
References[1] S. V. B. Aiyer, M. Niranjan, and F. Fallside, “A theoretical investigation into the performance of the Hopfield model”, IEEE Trans. Neural Netw., vol. 1, no. 2,pp.204 -215 1990.

Figure 6: Comparison of performance between the random cutting and the conventional methods.

Table 7: The neuronal death method.

r=1
r=5r = 10r = 15
r = 20r = 25

Conv.
48608.4
48608.4
48608.4
48608.4
48608.4
48608.4

Proposed network (neuronal death)
I=1
I=5I = 10
I = 15I = 2047904.9 46638.1 48806.2 48250.0 48981.249685.4 48048.4 48418.0 48983.0 49179.0
51733.6 50589.1 49940.1 49394.6 50630.4
57304.1 52281.7 51898.9 51940.6 51884.860390.3 54721.0 53622.4 53125.0 52473.363055.6 56758.4 55509.9 54817.8 54392.9[2] S. Abe, “Global convergence and suppression of spurious states of the Hopfield neural networks”, IEEE
Trans. Circuits Syst. I, vol. 40, no. 4, pp.246 -257
1993.
[3] M. Peng, K. Narendra, and A. Gupta, “An investigation into the improvement of local minimum of theHopfield network”, Neural Netw., vol. 9, pp.1241 1253 1996.
[4] Received 25 January 1989, Accepted 22 February
1989, Available online 19 March 2003.
[5] J. Hopfield Neural networks and physical systems
with emergent collective computational abilities Proc.
Natl. Acad. Sci. USA, 79 (1982), pp. 25542558[6] Biological Cybernetics July 1985, Volume 52, Issue
3, pp 141-152.

Table 8: The random cutting method.

r=1
r=5r = 10r = 15r = 20r = 25

Conv.
53136.6
53136.6
53136.6
53136.6
53136.6
53136.6

Proposed network (random cutting)
I=1
I=5I = 10I = 15I = 2050066.0 52071.1 50224.3 50425.8 50531.474404.2 55519.7 54164.4 53769.8 52854.7
83887.2 65999.3 62390.1 61185.8 60568.192893.1 74874.1 69606.6 67991.7 66060.0
103076.8 81607.4 74152.1 71511.5 70255.7
113611.1 87703.2 78493.8 74529.0 72741.6[7] Encyclopedia of Child Behavior and Development,
2011, pp 1464-1465[8] A Mechanism for Synaptic Pruning During Brain
Maturation,November 15, 1999, Vol. 11, No. 8, Pages
2061-2080 Posted Online March 13, 2006.

- 108 -