ECE/CS/ME 539: Final course project report
Development of a program to solve the Traveling Salesman Problem with a Hopfield net
December 20, 2001
Karl von Pfeil
UW ID: 901 803 6807 0
Abstract
A program is developed to solve the Traveling Salesman Problem with a Hopfield net and is provided with a graphical user interface (GUI). With this program any user can investigate the usefulness of Hopfield nets for solving combinatorial optimization problems, specifically for the TSP, in an appealing way. The performance of the Hopfield net is examined in a simulation study.
1. Introduction
The Traveling Salesman Problem (TSP) is one of the most famous combinatorial optimization problems. It can be stated as following: given a finite number of cities and their pair-wise distances, find the shortest tour which connects all cities once and only once and returns to its starting point [1].
The mathematician Karl Menger first studied the TSP in its general form in Vienna in the 1920’s [2].In 1954 a computer program by G. Dantzig et al. solved a nontrivial TSP with 49 cities. The number of cites for which the TSP has been solved has increased with more sophisticated computer codes and ever faster computers. In 2001, for example, a TSP using 15,112 German cites was solved [2]. Even though the work on the TSP is often not directly applicable, it does provide a platform to investigate general methods to solve discrete optimization problems.
Nevertheless, the TSP arises naturally in the field of transportation and logistics. Examples in which modules of TSP computer programs were applied include the planning of postal truck routes, the scheduling of service calls at companies, and the scheduling of stacker cranes. Another classical application is the scheduling of a drilling machine for which the order in which the holes are drilled is optimized with respect to the manufacturing time [2].
Hopfield and Tank showed how a dynamic system, represented by an analog network, could be used to solve the TSP [3]. This dynamic system is referred as a Hopfield net. Since their approach is known to produce many invalid solutions, many researchers tried to improve the performance of the Hopfield net based on linear stability analyses [4,5,6,7].
The outline of this report is the following. In Chapter 2 the theory for solving the TSP with a Hopfield net is reviewed. In Chapter 3 the developed program is described including a detailed scheme of the algorithm and the introduction of the GUI of the program. In Chapter 4 the performance of the program is investigated with a brief simulation study and in Chapter 5 conclusions about the usefulness of Hopfield nets to solve the TSP are drawn.
2. Review of the theory
2.1 The Hopfield net
The Hopfield network is a dynamic system. It can be written in its continuous form as:
where ui denotes the net function of neuron i, si represents the nonlinear output of neuron i, wij is the weight and Ii denotes an external input [7]. The activation function f is usually either a hardlimiter or a sigmoid. One notices that the output of each neuron is fed back to the input of all the other neurons except for its own input. The Hopfield net can be completely described by a Lyapunov function E which is also referred to the Hopfield energy function:
One can easily verify that this is a Lyapunov function [7]. One notices that Hence, the energy function completely describes the Hopfield net. Since a Lyapunov function exists, we know that the Hopfield net is stable. Assuming that the weight matrix is symmetric (wij=wji) and that the neurons are asynchronously updated, the Lyapunov function converges to a local minimum without oscillating between different states [1]. That is, the state of the Hopfield net converges and the state corresponds to a local minimum of the Lyapunov function.
In general, a Hopfield net can either be utilized as an associate memory to store and retrieve information or to solve combinatorial optimization problems. In this report only the latter is addressed.
2.2 Mapping the TSP onto a Hopfield net
The basic approach of solving the TSP with a Hopfield net is described as follows: the output of all neurons represents the current tour. The weights wij of the Hopfield net are chosen such that a Hopfield energy function can be defined with the properties that it measures the length of a tour and that the lowest energy state corresponds to the optimal tour. Letting the Hopfield net evolve in time the energy function decreases monotonically until a stable steady state is reached. This steady state should correspond to the optimal tour. In the following paragraphs it is described how a tour can be represented by the state of a set of neurons and how the weights of the network are determined.
First a representation scheme for the tour needs to be found, or, more specifically, the tour has to be encoded by the states of a set of neurons. Hopfield and Tank used a scheme in which N2 neurons are needed for a N-city problem [3]. The tour can be conveniently represented by a N´N matrix. If the ij-element is equal to one, then city i has the jth position in the tour. An example for the matrix representation of the TSP for a 4-city tour can be seen below:
1 / 2 / 3 / 4A / 0 / 1 / 0 / 0
B / 0 / 0 / 0 / 1
C / 0 / 0 / 1 / 0
D / 1 / 0 / 0 / 0
The matrix indicates that city D is the first visited city. The total tour is D-A-C-B.
Secondly an appropriate Hopfield energy function and the corresponding weights have to be determined. Hopfield and Tank proposed the following energy function [3]:
where A,B,C and D are positive coefficients. All indices are defined in modulo N. For convenience double-indices are used were sxi denotes the output of the neuron corresponding to the city x and tour position i. The distance between the cities x and y is indicated by dxy. The first three terms of the energy function correspond to the constraints of the TSP meaning the solution is a valid path. Let us assume that the Hopfield net reached a steady state with outputs only either ‘0’ ore ‘1’. The first term is only zero if and only if each row has not more than one ‘1’, which is the constraint that each city is allowed to be visited only one. The second term is only zero if and only if each column has not more than one ‘1’, which corresponds to the constraint that each position of the tour can only be occupied by one city. One notices that the first two terms are also zero if all outputs are zero meaning that no city is visited. Hence, the third term is needed to meet the constraint that N cities are visited on the tour. The forth term penalizes tours with a long distance. The energy function is direct proportional to the length of the tour. Hence, the state with the lowest energy should correspond to the optimal tour.
Defining
with the Kronecker-delta d, the Hopfield energy function can be rewritten as
It can be shown that this is a Lyapunov equation. One notices that this energy function is similar to that described in Section 1.1.
When implementing a Hopfield net based on this energy function it turns out that many solutions are invalid [4]. Ansari and Hou [7] performed a linear stability analysis of the Hopfield net. Based on their eigenvalue analysis, they proposed the following expression for the weighs:
where A1 is a new, positive parameter and B is replaced by A. Since this expression is reported to produce a relative high percentage of valid solutions, it is used for the implementation of the program.
3. Program description
I implemented the program in MATLAB, which provides the possibility of developing a GUI in an easy way. Even though MATLAB is rather slow in comparison to other computer languages, the developed code can be accelerated by compiling it to C or C++[1].
In the following section only the subroutine calculating the solution to the TSP is described. The subroutines involving the GUI are not addressed in this report. For more details please refer to the documentation of the program code.
3.1 Description of the algorithm
The algorithm for computing the solution of the TSP is implemented in the function ‘fctMainAlgorithm.m’. It is summarized in the following scheme:
1. Calculate the distance d(x,y) between all cities.
2. Calculate the fixed weight matrix (the weight is stored in a four-dimensional array):
3. Initiate the net functions of all neuron to a random value with zero mean (corresponds to an mean output of the neurons of 0.5)
4. Repeat the following steps until stop-criterion is satisfied:
a) Randomly determine the order in which the neurons are going to be updated
b) Update each neuron in the order determined in 4a):
5. Check if stop-criterion is satisfied
6. Check if current solution is a valid tour
Implementation details like synchronous updating of the neurons are neglected in this scheme in favor for clarity. The implementation is straightforward and does not need to be explained. For example, the code uses four-dimensional arrays in order to avoid for-loops in MATLAB and therefore accelerates the program. I feel that the language specific details do not contribute to the overall understanding.
Note: in Step 4 of the algorithm the activation function is chosen to be a sigmoid. I also tested a hardlimiter but the obtained solutions were not satisfying. The stop-criterion in Step 5 consists of different conditions. The algorithm terminates if the maximum number of iterations is reached or if the output of each neuron is either between 0 and b1 or b2 and 1, where b1 < b2 are user specified parameters. One notices that the algorithm can terminate even though the solution is not a valid tour.
3.2 Running the program
The program can be executed in MATLAB with the command ‘Traveling_salesman’. The main-window appears on which the user can undertake the most important steps like starting and stopping the simulation or changing the number of cities. Furthermore, the current tour and other information about the tour can be viewed. Figure 3.1 shows a screen shot of the main window for a random 10-city TSP.
Figure 3.1 Screen shot of the main-window
Figure 3.2 Screen shot of the parameter-window
By pressing the parameter-button the user can change all relevant parameters like the coefficients of the energy function, parameters of the Hopfield net, or simulation parameters. Additionally, the user can choose to use a city configuration that is specified in a curtain file. A screen shot of the parameter-window is depicted in Figure 3.2.
After the optimization is finished or being stopped, one can view the output of the neurons by pressing the ‘view output-button’. A screen shot of this window can be seen in Figure 3.3.
Figure 3.3 Screen shot of the output window
Furthermore, one can plot the cost function (=energy function) over the time steps. Figure 3.4 shows how the cost function monotonically decreases in time until a steady state is reached.
Figure 3.4 Plot of the Lyapunov energy function over the time steps
4. Performance of the Hopfield net
In order to get an idea how useful a Hopfield net is to solve the TSP, I tested my program with one specific configuration of ten cities. I used a random configuration of the cities stored in the file ‘randomCity10.m’. The shortest tour length for this problem is 2.6299. I chose the parameters of the Hopfield energy function as suggested for a 10-city TSP by Aiyer et al. [6] to A=8; A1=7.75; C=0.8. The parameter D, penalizing the total length of the tour, was varied between 1.0 and 3.0. All other parameters were held constant and can be looked up in the file ‘InitParameter.m’.
D / Convergence rate [%] / Found best tour [%]1.0 / 100 / 3
1.5 / 96 / 8
2.0 / 88 / 11
3.0 / 41 / 10
Table 4.1 The statistics for solving a 10-city TSP with different weightings D
For each value of D 100 simulations were performed. The results of the simulation study can be seen in Table 4.1. With D=1.0 (as suggested by Aiyer et al. [6]) all solutions converged, meaning that all tours were valid (but not necessarily the shortest tour) and that the output of each neuron was either between 0 and 0.2 or 0.8 and 1. However, the Hopfield net converged only three times to the optimal solution. When increasing the penalty for the tour length to D=2.0 the solution converged eleven times to the optimum; the convergence rate decreased to 88%. For D=3.0 the number of optimal tours did not increase. However, it should be mentioned that the obtained results probably have a high variance due to the relatively low number of experiments performed.
5. Conclusions
In this project a program is developed to solve the TSP with a Hopfield net. It is provided with a GUI, such that anyone is able to use it without any explanations. Thus every user can investigate the performance of the Hopfield net in an appealing way.
I think Hopfield’s idea to solve the TSP with a dynamic system as reviewed in Chapter 2 is very elegant. However, according to the experiences gained by this project, I conclude that the Hopfield net is not applicable for solving combinatorial optimization problems, such as the TSP. First, as can be seen in Chapter 4, the Hopfield net produces only a very low percentage of optimal solutions. The problem is that a constrained optimization problem is transformed into an unconstrained one. Furthermore, the optimal choice of the coefficients of the energy function is unknown. A second disadvantage of the Hopfield net is that N2 neurons are needed to solve a N-city TSP. Hence, the computation time increases exponentially with the number of cities. The calculation time of my program for a 10-city TSP and 1000 time steps, for example, was about 8.5s on a PC with a clock rate of 1.4 GHz. Therefore, even when using a faster programming language, it is completely impossible to use a Hopfield net to solve TSPs with hundreds or thousands of cities.