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 vonpfeil cae wisc edu 1 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 2 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 dui wij s j I i dt j i si f ui 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 3 completely described by a Lyapunov function E which is also referred to the Hopfield energy function E 1 si s j wij 2 i j i s I i i i One can easily verify that this is a Lyapunov function 7 One notices that dui E dt dsi 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 4 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 A B C D 1 2 3 4 0 0 0 1 1 0 0 0 0 0 1 0 0 1 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 E A B s xi s xj 2 x i j i 2 2 s i x y x xi s yi C D s xi N d xy s x i s y i 1 s y i 1 2 x i 2 x y x i 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 5 allowed to be visited only one The second term is only zero if and only if each column has not …
View Full Document
Unlocking...