Operational Research The 2-opt behavior of the Hopfield Network applied to the TSP --Manuscript Draft-- Manuscript Number: ORIJ-D-19-00400R2 Full Title: The 2-opt behavior of the Hopfield Network applied to the TSP Article Type: Original Paper Corresponding Author: Lucas García, Ph.D. Universidad Complutense de Madrid Madrid, SPAIN Corresponding Author Secondary Information: Corresponding Author's Institution: Universidad Complutense de Madrid Corresponding Author's Secondary Institution: First Author: Lucas García, Ph.D. First Author Secondary Information: Order of Authors: Lucas García, Ph.D. Pedro M. Talaván Javier Yáñez Order of Authors Secondary Information: Funding Information: Government of Spain (TIN2015-66471-P) Not applicable Government of Madrid, Spain (S2013/ICE-2845) Not applicable Abstract: The Continuous Hopfield Network (CHN) became one of the major breakthroughs in the come back of Neural Networks in the mid 80s, as it could be used to solve combinatorial optimization problems such as the Traveling Salesman Problem (TSP). Once researchers provided a mechanism, not based in trial-and-error, to guarantee the feasibility of the CHN, the quality of the solution was inferior to the ones provided by other heuristics.  The next natural step is to study the behavior of the CHN as an optimizer, in order to improve its performance. With this regard, this paper analyzes the attractor basins of the CHN and establishes the mathematical foundations that guarantee the behavior of the network as a 2-opt ; with the aim to open a new research line in which the CHN may be used, given the appropriate parameter setting, to solve a k-opt , which would make the network highly competitive. The analysis of the attraction basins of the CHN and its interpretation as a 2-opt is the subject of this article. Response to Reviewers: Again, we would like to deeply thank the reviewers for their interest in reviewing the submission, and their sound and valuable recommendations: Please find our comments to the suggested changes below: Reviewer #1 ======== We understand that despite being a theoretical paper on the attractor basins of the CHN, it is expected to provide some experimental results. We have added such results by comparing the CHN (exposing 2-opt behavior) detailed in the paper with with the state-of-the-art heuristic LKH-3 (see Table 2 and previous 3 paragraphs in section 5, which have been modified). Such benchmark may also be seen as a reference for future developments or aspirational goal for the CHN. Powered by Editorial Manager® and ProduXion Manager® from Aries Systems Corporation Additional simulations have been included to Table 1 for USA13509, given that such simulations were also carried out for Table 2. The run-on sentence in the last paragraph before section 6 has been simplified as suggested. Supplementary material has been included with tracked changes in red. Reviewer #2 ======== Empirical results have been included as suggested. Such results compare the CHN (exposing 2-opt behavior) detailed in the paper with with LKH-3 (see Table 2 in section 5). Such comparison includes, not only the performance of the heuristic, but also computational time of both heuristics for different TSPLIB instances. The 3 paragraphs preceding Table 2 have also been modified to incorporate such changes. The experimental results shown both in Table 1 and 2 can be used to see how quality of the solution in the CHN has been significantly improved and margin with respect to state-of-the-art heuristics reduced. Moreover, the benchmark with LKH-3 serves as an aspirational goal for future research. Additional simulations have been included to Table 1 for USA13509, given that such simulations were also carried out for Table 2. Supplementary material has been included with tracked changes in red. Powered by Editorial Manager® and ProduXion Manager® from Aries Systems Corporation The 2-opt behavior of the Hopfield Network applied to the TSP Lucas García * Universidad Complutense de Madrid Madrid, Spain lucasgarciarodriguez@ucm.es * Corresponding author Pedro M. Talaván Instituto Nacional de Estadístic a Madrid, Spain pedro.martinez.talavan@ine.es Javier Yáñez Universidad Complutense de Madrid Madrid, Spain jayage@ucm.es Title Page mailto:lucasgarciarodriguez@ucm.es mailto:pedro.martinez.talavan@ine.es mailto:jayage@ucm.es Noname manuscript No. (will be inserted by the editor) The 2-opt behavior of the Hopfield Network applied to the TSP Not available Received: 24-Aug-2019 / Accepted: date Abstract The Continuous Hopfield Network (CHN) became one of the major breakthroughs in the come back of Neural Networks in the mid 80s, as it could be used to solve combinatorial optimization problems such as the Traveling Salesman Problem (TSP). Once researchers provided a mechanism, not based in trial-and- error, to guarantee the feasibility of the CHN, the quality of the solution was inferior to the ones provided by other heuristics. The next natural step is to study the behavior of the CHN as an optimizer, in order to improve its performance. With this regard, this paper analyzes the attractor basins of the CHN and establishes the mathematical foundations that guarantee the behavior of the network as a 2-opt ; with the aim to open a new research line in which the CHN may be used, given the appropriate parameter setting, to solve a k-opt, which would make the network highly competitive. The analysis of the attraction basins of the CHN and its interpretation as a 2-opt is the subject of this article. Keywords Hopfield Network · 2-opt · Traveling Salesman Problem fNot available Not available for blind review Manuscript Click here to view linked References 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 https://www.editorialmanager.com/orij/viewRCResults.aspx?pdf=1&docID=3674&rev=2&fileID=70204&msid=fc102ebf-4a23-4285-9bd9-72055741689c https://www.editorialmanager.com/orij/viewRCResults.aspx?pdf=1&docID=3674&rev=2&fileID=70204&msid=fc102ebf-4a23-4285-9bd9-72055741689c 2 Not available 1 Introduction 1.1 The Continuous Hopfield Network The Continuous Hopfield Network (CHN) is a recurrent neural neural network designed by John Hopfield [12] in 1984. The CHN is a generalization of its discrete version [11], allowing to take all real values in the interval [0, 1], in contrast to the discrete model (which behaves as an associative memory with binary units). The recurrent neural network in the CHN has an associated differential equa- tion, whose states evolve from a starting to an equilibrium point by minimizing a Lyapunov function. If the Lyapunov function is to be associated with the objective function and constraints of an optimization problem (process known as mapping), then the stable or equilibrium point matches a local optimum of the optimization problem. The dynamics of the CHN is described by the differential equation (also de- picted in Figure 1): du dt = −u λ + Tv + ib (1) where, ∀i, j ∈ {1, . . . , n}: ui is the current state of neuron i vi is the output of neuron i Ti,j is the strength of the connection from neuron j to neuron i ibi is the offset bias of neuron i being the output function g(ui) a hyperbolic tangent: vi = g(ui) = 1 2 ( 1 + tanh ( ui u0 )) , u0 > 0 where the parameter u0 determines the slope of the sigmoid function. T ib1 + + − g−1 1 s 1/λ g du dt v(0) u v Fig. 1 Dynamical system of the Continuous Hopfield Network 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 The 2-opt behavior of the Hopfield Network applied to the TSP 3 Hopfield proved that if the weight matrix T is symmetric, then the following Lyapunov function exists: E(v) = −1 2 vtTv − (ib)tv + 1 λ n∑ i=1 ∫ vi 0 g−1(x)dx (2) guaranteeing the existence of an equilibrium point. The consequence of the inte- gral term 1 λ ∑n i=1 ∫ vi 0 g−1(x)dx in Equation 2 is the existence of stable equilibrium points in the interior of the hypercube of solutions. The proximity of such points to the minima in the quadratic term −1 2vtTv−(ib)tv is controlled by the parameter λ. If λ −→ 0, see Wasserman et al. [20], there is only one equilibrium point in the center of the hypercube [0, 1]n. On the contrary, when λ −→∞, the Lyapunov func- tion of the network can be associated with the objective function to be minimized by the combinatorial optimization problem. Thus, the CHN will solve the combi- natorial optimization problems that can be written as a constrained minimization of: E(v) = −1 2 vtTv − (ib)tv (3) which has its extremes at the corners of the n-dimensional hypercube [0, 1]n. Mov- ing forward, this modified energy function (proposed by Abe [1]) which does not include the integral term will be used. These aspects have been deeply studied by Joya et al. [14]. 1.1.1 The Continuous Hopfield Network applied to the Traveling Salesman Problem The Traveling Salesman Problem (TSP) is one of the most deeply studied problems in combinatorial optimization. Formulated in the XIX century by W. R. Hamilton and T. Kirkman, the problem is focused on a salesman who has to visit a finite set of cities. The TSP aims to find the shortest path through all the cities so that each city is visited only once and the salesman returns at the end of the journey to the city of departure. Let N be the number of cities and let dxy be the distance between cities x and y, x, y ∈ {1, 2, . . . , N}. Also, let V be the N ×N state variable matrix: vx,i = { 1 if the city x is visited in position i 0 otherwise x, i ∈ {1, . . . , N} (4) The TSP is one of the NP-hard optimization problems (see [16] and [21]), that is, it cannot be solved in polynomial time. As a consequence, heuristics are used to obtain good solutions for large instances of the TSP, although its optimality is not guaranteed. This paper analyzes the attractor basins of the CHN, with the aim of obtaining an adequate parameter setting that turns the CHN into a competitive heuristic. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 4 Not available Remark 1 Often, due to the nature of the energy function of the CHN (see Equa- tion 3), the N × N state variable matrix may be written in vector form (of size N2 × 1): v =  v·,1 v·,2 ... v·,N  N2×1 with v·i =  v1,i v2,i ... vN,i  N×1 The state variable v identifies a valid TSP tour if the following constraints are satisfied: – Each city is visited only once: Sx = N∑ i=1 vx,i = 1 ∀x ∈ {1, 2, . . . , N} (5) – Each tour position is associated with a single city: Si = N∑ x=1 vx,i = 1 ∀i ∈ {1, 2, . . . , N} (6) The objective function is min 1 2 N∑ x=1 ∑ y 6=x N∑ i=1 dxyvxi(vy(i+1) + vy(i−1))  (i+1 and i−1 subscripts are given modulo N) (7) In order to solve the TSP introduced in equations 4, 5, 6 and 7, Hopfield and Tank [13] proposed a CHN with N ×N neurons, corresponding to the pairs (x, i), which identify the city and the position in which the city is visited. For such network, the energy function (see Hopfield and Tank [13] for detailed explanation of the terms) for any state v ∈ H ≡ {v ∈ [0, 1]N×N} is: E(v) = A 2 N∑ x N∑ i N∑ j 6=i vx,ivx,j + B 2 N∑ i N∑ x N∑ y 6=x vx,ivy,i + C 2 ( N∑ x N∑ i vx,i −N ′ )2 + D 2 N∑ x N∑ y 6=x N∑ i dx,yvx,i(vy,i−1 + vy,i+1) (i+1 and i−1 subscripts are given modulo N) (8) Developing the terms in Equation 8 and comparing them with the general form of the energy function in Equation 3: E(v) = −1 2 ∑ x,i ∑ y,j vx,iTxi,yjvy,j − ∑ x,i ibx,ivx,i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 The 2-opt behavior of the Hopfield Network applied to the TSP 5 we obtain: Txi,yj = − (Aδx,y(1− δi,j) +B(1− δx,y)δi,j +C +D(δi,j−1 + δi,j+1)dx,y) ibx,i = CN ′ where δi,j = { 1 if i = j 0 if i 6= j is a Kronecker δ, x, y ∈ {1, . . . , N}, i, j ∈ {1, . . . , N}. Since the seminal paper by Hofield and Tank [13] many authors have studied the TSP as well as other optimization problems from a neuronal approach. How- ever, the energy function of the CHN requires giving values to certain parameters (A, B, C, D, N ′) which are being assigned experimentally. This process results in frequently obtaining non-feasible solutions. For several years, researchers have tried to find an adequate combination of parameters that guarantees the feasibility of the solutions of the TSP (see Hedge et al. [8], Platt and Barr [17], Cuykendall and Reese [3], etc.). However, it is not until the work of Talaván and Yáñez [19] that a complete parameter setting method, not based in trial-and-error, is pro- posed. This method guarantees that any stable point of the CHN corresponds with a valid tour of the TSP. Thus, the following parameter setting will be used: D = 1 dU N ′ = N + 3 C B = 3 + C A = B −DdL with C > 0 and dL ≤ dx,y ≤ dU ∀x, y ∈ {1, . . . N}. 1.2 The Divide-and-Conquer scheme for the CHN A Hopfield-based heuristic, consisting in a Divide-and-Conquer strategy, was pro- posed by Garćıa et al. [7] to improve the performance of the Hopfield model when applied to the TSP. In this section, we summarize the most relevant results from this paper, required for our analysis. The heuristic consists in solving the TSP in two phases, each of which is modeled using a CHN, where the feasibility of the solutions is guaranteed through different parameter settings. The goal is to con- nect together neighboring cities in the first phase to create a set of chains and, in a second phase, link the resulting chains of neighboring cities from the previous phase to obtain the final tour. Given a set of N cities, the first phase consists in connecting cities which are closer together. A new parameter τ ∈ {1, . . . , N} is introduced and the original distance is modified for each city which is not a τ -neighbor city of x. A city y is considered to be a τ -neighbor of a city x if y is one of the τ closest cities to x: dτxy =  dxy  if y is one of the τ -neighbor cities of x or if x is one of the τ -neighbor cities of y dU otherwise 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 6 Not available Note that a city can have τ neighbors but may be chosen as a neighbor by more than τ cities. This definition guarantees that the distance matrix is symmetric. Using this modified distance, a new TSP is solved using the traditional Hopfield model already detailed in Section 1.1. From the obtained solution, the arcs where the distance dτxy is equal to dU are removed, obtaining a set of K chains of cities and possibly isolated cities (not connected to any chain). This result feeds the second phase of the Divide-and-Conquer scheme. The second phase of the Divide-and-Conquer scheme, named TSPk 2 , consists in solving a new TSP, where some cities have already been fixed. The new TSP consists in n cities obtained by adding the endpoints of each chain and the isolated cities. An additional constraint must be added to the optimization problem to guarantee that the two endpoints of the same chain are connected, resulting from the contraction of each chain (see Garćıa et al. [7] for details). To formulate the problem, a new decision variable is proposed: vkx,i =  1 if x is the entrance city, visited at position i, and xc is the exit city 0 otherwise for x ∈ {z1, z2, . . . , zn} and i ∈ {1, 2, . . . , n−K}. where xc is introduced to refer to the endpoint of a chain, x being the other endpoint. If x is an isolated city, xc would be itself. Formally: Definition 1 Given a TSPk 2 with parameters (n,K, dk), for any city zh ∈ {1, 2, . . . , N}, with h ∈ {1, 2, . . . , n} its couple is defined as: zch =  z2k−1 if h = 2k for some k ∈ {1, 2, . . . ,K} z2k if h = 2k − 1 for some k ∈ {1, 2, . . . ,K} zh if h > 2K For any state Vk ∈ [0, 1]n×(n−K), its energy function is: E(vk) = A 2 n∑ x n−K∑ i n−K∑ j 6=i vkx,i(v k x,j + vkxc,j) + B 2 n−K∑ i n∑ x n∑ y 6=x vkx,iv k y,i + C 2 ( n∑ x n−K∑ i vkx,i − (n−K) )2 + D 2 n∑ x n−K∑ i vkx,i n∑ y 6=x (vky,i−1d k yc,x + vky,i+1d k xc,y) (i+ 1 and i− 1 subscripts are given modulo n−K) (9) where dkx,y = 0 if y = xc and dkx,y = dx,y otherwise. A mapping process for TSPk 2 is carried out by comparing the function in Equation 9 with the general form of the energy function of the CHN: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 The 2-opt behavior of the Hopfield Network applied to the TSP 7 E(vk) = −1 2 ∑ x,i ∑ y,j vkx,iTxi,yjv k y,j − ∑ x,i ibx,iv k x,i (10) obtaining: Txi,yj =− (Aδx,y(1 + δx,xc)(1− δi,j) +B(1− δx,y)δi,j + C +D(δi,j−1d k yc,x + δi,j+1d k xc,y)) ibx,i = C(n−K) (11) with x, y ∈ {1, 2, . . . , n} and i, j ∈ {1, 2, . . . , n−K}. A stability analysis is needed to guarantee the stability of valid solutions and instability of invalid ones. From such analysis, Equation 11 is modified: ibx,i = CN ′ ∀x ∈ {1, . . . , n}, ∀i ∈ {1, . . . , (n−K)} (12) and the following parameter setting is proposed (depending on C > 0): D = 1 dkU N ′ = n−K + 3 C A = 3 + C B = A+ dkL dkU (13) with dkL ≤ dkx,y ≤ dkU ∀x, y ∈ {1, . . . n}. Remark 2 For the sake of simplicity and considering that only TSPk 2 for the Divide-and-Conquer scheme will be used going forward, the superindex k will be dropped. 2 The saddle point of the second phase of Divide-and-Conquer In this section, an attractor basin analysis of the CHN applied to the TSP for the second phase of the Divide-and-Conquer scheme, TSPk 2 (introduced in Sec- tion 1.2), is carried out. The goal is being able to obtain the saddle point of the energy function for TSPk 2 , that is, when K chains of cities have been fixed. This will allow to deter- mine whether it is possible or not to move the saddle point (and by how much), so that an appropriate selection of the free parameter C in the parameter setting from Equation 13 favors to obtain better solutions. The following proposition al- lows to compute such saddle point. Notation: (A)p and (B)p×q denote p× p and p× q block matrices respectively. Proposition 1 Given a TSP with n cities where K chains have already been fixed, the saddle point v∗ of the energy function for the second phase (TSPk 2 ) of the Divide-and-Conquer scheme (defined by Equation 10 using the modified bias in Equation 12) is: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 8 Not available v∗x,i = C ( n−K + 3 C ) n∑ j=1 mx,j , ∀x ∈ {1, . . . , n},∀i ∈ {1, . . . , n−K} (14) where mx,j is a generic element of the square matrix M: M = [( (n−K+1)C+3 + dL dU ) 1+ (n−K−1) (C+3) IK − ( C + 3 + dL dU ) I + 1 dU ( DK+(DK) T )]−1 and where: 1 = (1)n ≡  1 · · · 1 ... . . . ... 1 · · · 1  n×n , I = (I)n ≡  1 0 · · · 0 0 . . . . . . ... ... . . . . . . 0 0 · · · 0 1  n×n JK = (JK)n ≡ (1)2 − (I)2 (0)2 (0)2 (0)2×(n−2K) (0)2 (0)2 (0)2 (0)2 (1)2 − (I)2 (0)2×(n−2K) (0)(n−2K)×2 (0)(n−2K)×2 (I)n−2K   n×n , IK = (IK)n ≡ δK · JK + I, where δK = { 0 if K = 0 1 if K > 0 and DK = (DK)n ≡ D · JK with D = (D)n ≡ (dx,y)x,y∈{1,...,n}. Proof See Appendix A (page 17). Remark 3 Note that by means of Proposition 1, the saddle point v∗ can be com- puted without having to invert the weight matrix T (see Equation 16), of size (n × (n − K)) × (n × (n − K)). Instead, it is sufficient to compute M, which consists of inverting a matrix of size n× n. Remark 4 Note that the matrix T (see Equation 17) has, in the proof of Proposi- tion 1, a slightly different structure for the extreme case n−K = 2: T = [ (B+C)1−BI C1+AIK+D(D2+(D2)T ) C1+AI2+D(D2+(D2)T ) (B+C)1−BI ] 3 The second phase of Divide-and-Conquer as a 2-opt swap In optimization, 2-opt consists of a local optimization heuristic introduced by Croes [2] in 1958 to solve the TSP. The main idea behind this local search al- gorithm is to iteratively improve an initial solution of the TSP by removing all possible crosses that are present in this solution. The 2-opt algorithm can be easily 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 The 2-opt behavior of the Hopfield Network applied to the TSP 9 visualized if cities are represented in the plane and the distance is the euclidean; the optimal trajectory cannot have crossing lines because, in this case, reconnecting the endpoints of these crosses improves the overall tour length. The process consists in consider every pair of non-consecutive arcs in the fol- lowing way: given a pair of arcs, if they are removed, there is only one way to reconnect them so that a new valid tour is obtained. Such movement is frequently known as 2-opt swap. If the length of the new obtained tour is lower than the original tour, then the original tour is replaced with the new tour. Otherwise, the original tour is maintained. Once the process has been repeated for each pair of non-adjacent arcs and the solution cannot be improved, the solution is said to be 2-optimal and the process ends. Figure 2 shows an example where, starting from an initial solution, crosses between pairs of arcs are removed to obtain a solution with lower objective func- tion, obtaining the optimum solution after two 2-opt swaps. The 2-opt is actually Fig. 2 Improving an initial solution using the 2-opt heuristic a particular case of the k-opt, a heuristic introduced by Lin and Kernighan [15]. In the k-opt, starting from an initial solution, k mutually disjointed edges are re- moved. The obtained subtours are combined in the best possible way, naming this move as the k-opt swap. The algorithm for the 2-opt heuristic is summarized in the following pseudo-code: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 10 Not available Algorithm 1 The 2-opt Heuristic procedure 2-opt(N, tour, D) improvement = 0 bestTourLength = computeTourLength(tour, D) do for i = 1 to N − 2 do for j = i+ 2 to N do a = tour[ i ] b = tour[ (i+ 1)modN ] c = tour[ j ] d = tour[ (j + 1)modN ] newImprovement = da,d + db,c − (da,c + db,d) if newImprovement > improvement then improvement = newImprovement best = [ c, d ] end if end for end for if improvement > 0 then bestTourLength = bestTourLength− improvement tour = swap2opt(tour, best[1], best[2]) end if while improvement 6= 0 return: tour end procedure Remark 5 Note that it is not necessary, if the distance matrix is symmetric, to compute the total tour with each 2-opt swap to determine if the swap favors to obtain a better solution or not. It is sufficient to compare the sum of each pair of distances, and thus the 2-opt swap is produced (see Figure 3) if da,c + db,d < da,d + db,c. a b c d Fig. 3 2-opt swap A new Hopfield model with n = 4 and K = 2 is proposed, i.e., solving a TSP with 2 chains and 4 cities (its extremes). The following theorem studies the behavior of such CHN as a 2-opt. Theorem 1 The Hopfield model with n = 4 cities and K = 2 chains behaves like a 2-opt when considering as the starting point the projection of the saddle point on one of the faces of the Hamming Hypercube, that is, fixing the position of the first city of one of the two chains. Proof See Appendix A (page 22). Remark 6 Note that the proof of theorem 1 shows how the Hopfield model with n = 4 and K = 2 will behave as a 2-opt swap irrespective of the parameter setting used, as long as it is a valid one (that is, it verifies the inequalities obtained from the mapping process in Garćıa et al. [7]). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 The 2-opt behavior of the Hopfield Network applied to the TSP 11 Remark 7 The result of the theorem 1 further indicates that chosen point always converges to the optimum solution regardless the value that C takes. However, as it will be shown in the next section, the attractor basin for the optimum solution grows as the free parameter decreases, as shown for the Generalized Quadratic Knapsack Problem (GQKP) by Garćıa et al. [6]. 4 Attractor basin analysis of the CHN behaving as a 2-opt swap Once proven that the Hopfield model with n = 4 cities and K = 2 chains behaves exactly like a 2-opt swap, the study is completed by analyzing the attractor basins of the CHN. The TSP with n = 4 cities located at the following coordinates is considered: a = (1, 1), b = (1, 8), c = (1, 2), d = (2, 8) (15) so that the (euclidean) distance matrix is: D =  0 7 1 5 √ 2 7 0 5 √ 2 1 1 5 √ 2 0 7 5 √ 2 1 7 0  The following K = 2 chains are fixed: [a, b]; [c, d], from the coordinates given in Equation 15 (see Figure 4), x y −1 1 2 3 4 5 6 7 8 9 −1 1 2 a b c d Fig. 4 TSP where two arcs or chains, [a, b] and [c, d], have been fixed turning the distance matrix into: Dk =  0 0 1 5 √ 2 0 0 5 √ 2 1 1 5 √ 2 0 0 5 √ 2 1 0 0  An associated Hopfield model (N = 4, K = 2) is created and solved with the help of a CHN simulator developed in MATLAB (The MathWorks Inc., Natick, MA, USA), using different starting points. The starting points have been selected by sampling the face on which the saddle point is projected with a 400 × 400 array. That is, having fixed the first city visited (in this case the city a is chosen), values are given to v3,2 and v4,2 so that: V0 =  1 0 0 0 0 v3,2 0 v4,2  , with v3,2, v4,2 ∈ (0, 1) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 12 Not available Figure 4 shows that the optimum solution is reached when v3,2 = 0 and v4,2 = 1. Showing a similar analysis as the one done by Garćıa et al. [6] for a simple GQKP problem, Figure 5 depicts the energy function and attractor basin (overlaid with the phase diagram of the dynamic system) for the proposed TSP, given different values of the free parameter. Note that a projection of the energy function onto one of its faces and not the original energy function is being considered. Again, the starting points are colored according to the color of the solution to which they converge. It can be shown that, as studied by Garćıa et al. [6] for the GQKP, that the attractor basin for the best solution grows as the free parameter decreases, but with an important difference with respect to the GQKP example: choosing the starting point as the projection of the saddle point (represented by a red point in Figure 5) on one of its faces, it is guaranteed to always obtain the optimum solution, which leads to the CHN with N = 4 and K = 2 to behave as a 2-opt swap. C = 104 C = 10 C = 1 C = 10−2 1-2.5 -2 1 -1.5 10 4 -1 0.5 -0.5 0.5 00 1-30 -25 1 -20 -15 -10 0.5 -5 0.5 00 1-8 -7 1 -6 -5 0.5 -4 0.5 00 1-6 -5.5 1 -5 -4.5 -4 0.5 -3.5 -3 0.5 00 Fig. 5 Projection of the energy function of the CHN for the example defined by the cities of Equation 15 (fixing chains [a, b] and [c, d], and city a as the first visited city), together with its attractor basins for different values of the free parameter C In the previous example, there does not seem to be a high competition between the neurons v3,2 and v4,2, partly due to the sufficient margin between the sum of distances of the two possible solutions 2 = da,c + db,d < da,d + db,c = 10 √ 2. For this reason, the worst case scenario is now considered: the chains [a, c]; [b, d] are fixed (see Figure 6). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 The 2-opt behavior of the Hopfield Network applied to the TSP 13 x y −1 1 2 3 4 5 6 7 8 9 −1 1 2 a b c d Fig. 6 TSP with two fixed chains [a, c] and [b, d] For this new example, as the order used in the rows of the matrix V as well as Dk corresponds to the canonical order ({a, b, c, d}), the distance matrix of the problem is: Dk =  0 0 7 5 √ 2 0 0 5 √ 2 7 7 5 √ 2 0 0 5 √ 2 7 0 0  C = 104 C = 1 C = 10−2 C = 10−8 1 -2.2 -2 1 -1.8 -1.6 -1.4 -1.2 -1 10 4 -0.8 -0.6 -0.4 0.50.5 00 1 -7 -6 1 -5 -4 -3 -2 -1 0.50.5 00 1 -4.5 -4 1 -3.5 -3 -2.5 -2 -1.5 -1 0.50.5 00 1 -4.5 -4 1 -3.5 -3 -2.5 -2 -1.5 -1 0.50.5 00 Fig. 7 Projection of the energy function of the CHN for the example defined by the cities of Equation 15 (fixing chains [a, c] and [b, d], and city a as the first visited city), together with its attractor basins for different values of the free parameter C Conducting again multiple simulations of the CHN with different starting points, it is shown in Figure 7 how the now greater competition between neurons v3,2 and v4,2 (due to the greater similarity between the distances of the problem) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 14 Not available is practically imperceptible when decreasing the value of the free parameter C, being necessary to get closer to the saddle point to see how the attractor basin increases. Moreover, it is noted how the trajectory of the point that starts in the projection of the saddle point (represented by a red point in Figure 7) is modified as the free parameter decreases. 5 Computational experiences In order to further validate the 2-opt behavior of the CHN and to confirm that the quality of the solution of the CHN drastically improves by successively applying 2- opt swaps (each of them being a CHN, particular case of TSPk 2 ), several computa- tional experiences have been carried out. For such simulations and supporting this research, a library named Hopfield Network Toolbox was developed using MATLAB and is freely and openly available in GitHub: URLnotavailableforblindreview The quality of the solutions was measured by computing the performance ratio ρ of the network: ρ = tour length optimum tour length Table 1 compares the computational experiences of using the standard Hop- field model and the same model after which we have applied a 2-opt algorithm using the Hopfield model, that is, successively applying 2-opt swaps consisting of Table 1 Computational experiences for TSPLIB instances using the Standard CHN and CHN with 2-opt behavior, that is, Standard CHN + 2-opt (multiple TSPk 2 ) models, with C = 10−5 TSP Instance N #Trials Standard CHN model CHN (2-opt behavior) ρ ρ Minimum Mean Mode Minimum Mean Mode GR24 24 1000 1.04 1.40 1.44 1 1.03 1.01 FRI26 26 1000 1.19 1.46 1.43 1 1.04 1.02 BAYG29 29 1000 1.13 1.47 1.42 1 1.03 1.02 BAYS29 29 1000 1.10 1.52 1.56 1 1.03 1.02 ATT48 48 1000 1.36 1.80 1.74 1 1.04 1.04 GR48 48 1000 1.36 1.78 1.74 1 1.04 1.03 EIL51 51 1000 1.15 1.48 1.46 1 1.06 1.06 EIL76 76 1000 1.24 1.61 1.65 1.02 1.08 1.07 PR76 76 1000 1.72 2.15 2.03 1 1.05 1.04 GR96 96 1000 1.86 2.33 2.29 1.01 1.07 1.06 KROA100 100 1000 2.06 2.60 2.60 1 1.08 1.07 KROC100 100 1000 2.22 2.74 2.64 1 1.08 1.08 KROD100 100 1000 1.98 2.47 2.41 1.01 1.07 1.06 RD100 100 1000 1.47 1.99 1.89 1.01 1.09 1.08 EIL101 101 1000 1.40 1.74 1.68 1.02 1.08 1.08 LIN105 105 1000 1.94 2.65 2.62 1 1.07 1.08 GR120 120 1000 1.88 2.34 2.28 1.02 1.08 1.08 CH130 130 1000 1.70 2.20 2.10 1.02 1.08 1.07 CH150 150 1000 1.83 2.19 2.15 1.03 1.10 1.08 GR202 202 500 1.71 1.98 1.99 1.03 1.08 1.07 A280 280 500 2.75 3.21 3.13 1.06 1.12 1.12 PCB442 442 500 2.48 2.85 2.88 1.06 1.11 1.11 PA561 561 250 2.53 2.91 2.90 1.08 1.12 1.12 GR666 666 250 3.10 3.43 3.46 1.08 1.11 1.10 PR1002 1002 125 4.23 4.60 4.61 1.07 1.10 1.10 PR2392 2392 25 5.44 5.70 5.63 1.11 1.13 1.13 PLA7397 7397 5 14.50 14.77 14.50 1.10 1.11 1.11 USA13509 13509 5 12.91 13.26 12.91 1.10 1.12 1.10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 URLnotavailableforblindreview The 2-opt behavior of the Hopfield Network applied to the TSP 15 CHNs with 4 cities and 2 fixed chains (subproblem); using as starting point the projection of the saddle point of the subproblem onto one of the faces of the Ham- ming Hypercube. Each row in the table begins with the problem identification (TSPLIB [18]), the number of cities of the problem (N), followed by the number of trials considered for each problem. The remaining columns include performance ratio measurements (minimum, mean and mode) for each of the CHN models con- sidered. The value of the free parameter C has been set at a low value of 10−5, given that it has been proven that small values of the free parameter favor to obtain better solutions (see Garćıa et al. [6] and Garćıa [5]). The starting point for both CHN methods compared Table 1 is a randomly chosen point in the neighborhood of the saddle point. It is worth noting that the quality of the solutions drastically improves by leveraging the intrinsic behavior of the CHN as a 2-opt (see Table 1). Although state-of-the-art heuristics specialized in solving constrained TSP and vehicle routing problems, such as LKH3 (see Helsgaun [9] and [10]), consistently produce better results for solving the TSP (see Table 21), the goal of this paper is not to compete with such heuristics, but to set the mathematical foundations in the CHN by analyzing its attractor basins. Nevertheless, the comparison given in Table 2 provides an aspirational goal for the CHN. Thus, the results addressed in this paper show an extraordinary improvement in the quality of the solutions of the CHN (see Table 1) and open a new research line that could lead to the CHN exposing a k-opt behavior, making it then extremely competitive against other heuristics. Table 2 Computational experiences for TSPLIB instances using the CHN with 2-opt behavior, with C = 10−5 and LKH-3 (using default values) TSP Instance N #Trials CHN (2-opt behavior) LKH-3 ρ ρ Min Mean Time (s) Min Mean Time (s) BAYS29 29 1000 1 1.03 0.04 1 1 0.00 PR76 76 1000 1 1.05 0.23 1 1 0.01 LIN105 105 1000 1 1.07 0.41 1 1 0.00 A280 280 500 1.06 1.12 4.47 1 1 0.01 PCB442 442 500 1.06 1.11 6.78 1 1 0.13 PA561 561 250 1.08 1.12 9.59 1 1 0.52 GR666 666 250 1.08 1.11 16.95 1 1.0003 2.95 PR1002 1002 125 1.07 1.10 19.24 1 1 0.51 PR2392 2392 25 1.11 1.13 149.00 1 1 4.51 PLA7397 7397 5 1.10 1.11 3675.00 1 1 292.00 USA13509 13509 5 1.10 1.12 33185.00 1.0000008 1.00002 3479.00 6 Summary and conclusions Despite bringing back a lot of interest to the field of Neural Networks in the mid 80s, the CHN received later heavy criticism for its inability to guarantee 1 Note this benchmark does not provide a full and fair comparison between the heuristics, CHN –detailed in this paper– and LKH-3 [10], as they have been implemented in different programming languages, MATLAB and C, respectively. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 16 Not available feasible solutions. Once this obstacle was tackled by Talaván and Yáñez [19], through a parameter setting that guaranteed the feasibility of the solutions, the main objection was that quality of the solutions obtained by the network was not competitive when compared to other heuristics. This paper addresses this concern by analyzing core aspects of the CHN, study- ing the saddle point of the second phase of the Divide-and-Conquer scheme pro- posed by Garćıa et al. [7] and proving that a CHN with 4 cities and 2 fixed chains (particular case of the second phase of the Divide-and-Conquer scheme) behaves exactly as a 2-opt swap, given that the starting point is appropriately chosen. A thorough analysis is carried out to choose such starting point, finding a relation between the free parameter in the parameter setting and the saddle point of the energy function of the second phase of the Divide-and-Conquer scheme applied to the TSP (as had been proven by Garćıa et al. [6] for the case of the CHN applied to the GQKP). Moreover, this result generalizes the computation of the saddle point of the energy function of the CHN applied to the TSP (that is, when no chains are fixed). The intrinsic behavior in the CHN as a 2-opt swap exposed in this paper allows to drastically improve the quality of the solutions of the CHN when applied to the TSP, entirely using the CHN throughout the process and matching the effect of applying a 2-opt heuristic to a solution of the CHN. This paper opens new research lines that should be continued. Building a CHN that simultaneously solves all the 2-opt swaps at once could make the CHN competitive with the traditional 2-opt heuristic, strictly from the computational point of view. Also, the extension of the CHN to solve 3-opt swaps, or more generally, k-opt swaps, becomes a promising research line that could further improve the quality of the solution of the CHN. Acknowledgements Not available for blind review. A Some technical results Lemma 1 Given a block-circulant matrix (each row-block is rotated one block to the right relative to the preceding row-block vector) of size N (N even, N = 2m), its inverse has the following structure: Q1 Q2 Q3 · · · QN 2 −1 QN 2 QN 2 +1 QN 2 QN 2 −1 · · · Q3 Q2 Q2 Q3 Q3 ... ... QN 2 −1 QN 2 −1 QN 2 QN 2 QN 2 +1 QN 2 +1 QN 2 QN 2 QN 2 −1 QN 2 −1 ... ... Q3 Q3 Q2 Q2 Q3 · · · QN 2 −1 QN 2 QN 2 +1 QN 2 QN 2 −1 · · · Q3 Q2 Q1   Proof Let T be an invertible block-circulant matrix. Then, using the result by De Mazancourt et al. [4] regarding block-circulant matrices (BCM), the inverse of a BCM matrix is also BCM. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 The 2-opt behavior of the Hopfield Network applied to the TSP 17 Thus, since T−1 is BCM, it can be written as follows (if N = 2m): T−1 = Q1 Q2 QN−2 QN−1 QN QN Q1 Q2 QN−1 QN−1 QN Q1 Q2 QN−2 Q3 Q2 Q2 Q3 QN−1 QN Q1   Since T−1 is symmetric (as T is symmetric), it is deduced that: Qk = QN−(k−2) ∀k ∈ { 2, . . . , N 2 + 1 } An equivalent result is obtained if N is odd. ut Proof (Proof of Proposition 1 (See page 7 for formulation)) The saddle point of the energy function for the second phase (TSPk 2 ) of the Divide-and-Conquer scheme, defined by Equa- tion 10, is obtained by computing the partial derivatives of E (v) with respect to v and make them equal to zero, −Tv − ib = 0. Thus, the saddle point v∗ is: v∗ = −T−1ib (16) The matrix T can be written as a (n× (n−K))× (n× (n−K)) matrix ((n−K)× (n−K) block-matrix of square matrices of size n× n): T = − (B+C)1−BI C1+AIK+D(DK)T C1+AIK · · · C1+AIK C1+AIK+DDK C1+AIK+DDK C1+AIK C1+AIK . . . . . . C1+AIK C1+AIK C1+AIK+D(DK)T C1+AI+(DDK)T C1+AIK · · · C1+AIK C1+AIK+DDK (B+C)1−BI   (17) where the matrices 1, I, IK and DK follow the definitions of the proposition. In order to be able to consider the trivial case K = 0 in which there are no fixed chains and all isolated cities are couples to themselves, the term δK was introduced in the definition of the matrix IK. Moreover, the bias vector ib has the structure: ib = CN ′ ... CN ′  (n×(n−K))×1 T is a block-circulant matrix (see De Mazancourt et al. [4]). If T is invertible, using Lemma 1, T−1 is also block-circulant and has the following structure (depending on whether n −K is even or odd): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 18 Not available If n−K = 2m: T−1 = Q1 Q2 Qn−K 2 Qn−K 2 +1 Qn−K 2 Q3 Q2 Q2 Q3 Qn−K 2 Qn−K 2 Qn−K 2 +1 Qn−K 2 +1 Qn−K 2 Qn−K 2 Q3 Q2 Q2 Q3 Qn−K 2 Qn−K 2 +1 Qn−K 2 Q2 Q1   where Qs are n× n matrices ∀s ∈ {1, . . . , n−K 2 + 1}. If n−K = 2m+ 1: T−1 = Q1 Q2 Qn−K−1 2 Qn−K+1 2 Qn−K+1 2 Qn−K−1 2 Q3 Q2 Q2 Q3 Qn−K−1 2 Qn−K−1 2 Qn−K+1 2 Qn−K+1 2 Qn−K+1 2 Qn−K+1 2 Qn−K−1 2 Qn−K−1 2 Q3 Q2 Q2 Q3 Qn−K−1 2 Qn−K+1 2 Qn−K+1 2 Qn−K−1 2 Q2 Q1   where Qs are (n−K)× (n−K) matrices ∀s ∈ {1, . . . , n−K+1 2 }. Considering equation 16 and the structure for T−1, v∗ may be obtained2 in the following way: v∗ = −T−1ib =  v∗·1 v∗·2 .. . v∗·(n−K)  (n×(n−K))×1 2 As noted in Remark 1 (see section 1.1.1), the state matrix V = (vx,i)x∈{1,...,n},i∈{1,...,n−K} can be expressed as a vector: v =  v·1 v·2 ... v·(n−K)  (n×(n−K))×1 with v·i =  v1,i v2,i ... vn,i  n×1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 The 2-opt behavior of the Hopfield Network applied to the TSP 19 with v∗·i =  − ( Q1 + 2 n−K 2∑ s=2 Qs + Qn−K 2 +1 ) CN ′ 1 if n−K = 2m − ( Q1 + 2 n−K+1 2∑ s=2 Qs ) CN ′ 1 if n−K = 2m+1 where 1 =  1 1 ... 1  n×1 . Let Qrow ≡  Q1 + 2 n−K 2∑ s=2 Qs + Qn−K 2 +1 if n−K = 2m Q1 + 2 n−K+1 2∑ s=2 Qs if n−K = 2m+ 1 then, considering that Tv∗ = ib and defining qrow ≡ Qrow1: Tv∗ = T  v∗·1 v∗·2 ... v∗·(n−K)  (n×(n−K))×1 = T  −QrowCN ′1 −QrowCN ′1 ... −QrowCN ′1  (n×(n−K))×1 = −CN ′T  qrow qrow ... qrow  (n×(n−K))×1 o =  CN ′ CN ′ ... CN ′  (n×(n−K))×1 Since all the components are equal, it is sufficient to develop just one of them: −CN ′ ( − [ (B+C) 1− BI + (n−K−3) (C1+AIK) + 2 (C1+AIK) +D ( DK+(DK) T )]) q row = CN ′ 1 obtaining: qrow = [ (B + C)1−BI + (n−K − 3) (C1 +AIK) + 2 (C1 +AIK) +D ( DK+(DK)T )]−1 1 = [ (B + (n−K)C)1 + (n−K−1)AIK −BI +D ( DK+(DK)T )]−1 1 The saddle point v∗ of the energy function E(v) given by Equation 9 in terms of the parameters A,B,C,D and N ′ is: v∗ =  v∗·1 v∗·2 ... v∗·(n−K)  (n×(n−K))×1 where ∀i ∈ {1, . . . , n−K} v∗·iCN ′qrow = CN ′ [ (B + (n−K)C)1 + (n−K−1)AIK −BI +D ( DK+(DK)T )]−1 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 20 Not available which may be written equivalently as: v∗x,i = CN ′ n∑ j=1 mx,j , ∀x ∈ {1, . . . , n}, ∀i ∈ {1, . . . , n−K}, with M = [ (B + (n−K)C)1 + (n−K−1)AIK −BI +D ( DK+(DK)T )]−1 (18) Considering the parameter setting in Equation 13 for A,B,C,D and N ′: v∗x,i = C ( n−K + 3 C ) n∑ j=1 mx,j , ∀x ∈ {1, . . . , n},∀i ∈ {1, . . . , n−K}, M = [( (n−K+1)C+3 + dL dU ) 1+ (n−K−1) (C+3) IK − ( C + 3 + dL dU ) I + 1 dU ( DK+(DK) T )]−1 ut Lemma 2 Given a positive definite matrix X of size 4× 4 with the following structure: X =  x1 x2 x3 x4x2 x1 x4 x3 x3 x4 x1 x2 x4 x3 x2 x1  4×4 then its inverse matrix M satisfies 4∑ j=1 mi,j = 1 x1 + x2 + x3 + x4 , ∀i = 1, 2, 3, 4. Proof Being X positive definite, its inverse matrix exists. Thus, let M be the inverse matrix of X. Being its inverse, it satisfies that mi,·x·,j = { 1 if i = j 0 otherwise with mi,· = [ mi,1 mi,2 mi,3 mi,4 ] , ∀i = 1, 2, 3, 4. and x·,j =  x1,jx2,j x3,j x4,j  , ∀j = 1, 2, 3, 4. obtaining: 4∑ j=1 mi,·x·,j = mi,· 4∑ j=1 x·,j = 1, ∀i = 1, 2, 3, 4. According to the definition for X of the lemma: 4∑ j=1 x·,j =  x1 + x2 + x3 + x4 x1 + x2 + x3 + x4 x1 + x2 + x3 + x4 x1 + x2 + x3 + x4  which is not the vector 0 as X is invertible. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 The 2-opt behavior of the Hopfield Network applied to the TSP 21 Thus, mi,· 4∑ j=1 x·,j = 4∑ j=1 mi,j(x1 + x2 + x3 + x4) = 1, ∀i = 1, 2, 3, 4. and therefore 4∑ j=1 mi,j = 1 x1 + x2 + x3 + x4 , ∀i = 1, 2, 3, 4. ut Lemma 3 As a consequence of Proposition 1, the saddle point for the case with four cities and two chains (n = 4, K = 2) is: v∗x,i = (2C + 3) dU (13C + 15)dU + 3dL + d1,3 + d1,4 + d2,3 + d2,4 , ∀x ∈ {1, 2, 3, 4}, ∀i ∈ {1, 2}. Proof If n = 4 and K = 2, and considering the definitions for the matrices in Proposition 1: 1 = (1)4 ≡  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  4×4 , I = (I)4 ≡  1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1  4×4 , J2 = (J2)4 ≡ [ (1)2 − (I)2 (0)2 (0)2 (1)2 − (I)2 ] 4×4 =  0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0  4×4 , I2 = (I2)4 ≡ (J2)4 + (I)4 =  1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1  4×4 (19) and D2 = (D2)4 ≡ D · J2 =  0 0 d1,3 d1,4 0 0 d2,3 d2,4 d1,3 d2,3 0 0 d1,4 d2,4 0 0  4×4 ·  0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0  4×4 =  0 0 d1,4 d1,3 0 0 d2,4 d2,3 d2,3 d1,3 0 0 d2,4 d1,4 0 0  4×4 (20) the matrix M required to obtain the saddle point (see Equation 18 and Remark 4) can be computed as: M = [ (B + 2C)1 +AI2 −BI +D ( D2+(D2)T )]−1 =  2C+A A+B+2C B+2C+D(d1,4+d2,3) B+2C+D(d1,3+d2,4) A+B+2C 2C+A B+2C+D(d1,3+d2,4) B+2C+D(d1,4+d2,3) B+2C+D(d1,4+d2,3) B+2C+D(d1,3+d2,4) 2C+A A+B+2C B+2C+D(d1,3+d2,4) B+2C+D(d1,4+d2,3) A+B+2C 2C+A  −1 4×4 Taking into account the results of Proposition 1, Lemma 2 and the parameter setting in Equation 13: v∗x,i = (2C + 3) 4∑ j=1 mx,j = (2C + 3)dU (13C + 15)dU + 3dL + d1,3 + d1,4 + d2,3 + d2,4 , ∀x ∈ {1, 2, 3, 4}, ∀i ∈ {1, 2}. ut 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 22 Not available Remark 8 From the obtained saddle point in Lemma 3, it can be concluded that: lim C→ ∞ v∗x,i = 2 13 , ∀x ∈ {1, 2, 3, 4}, ∀i ∈ {1, 2} and lim C→ 0 v∗x,i = 3dU 15dU + 3dL + d1,3 + d1,4 + d2,3 + d2,4 , ∀x ∈ {1, 2, 3, 4}, ∀i ∈ {1, 2}. Proof (Proof of Theorem 1 (See page 10 for formulation)) Let {1, 2, 3, 4} be the set of n = 4 cities and let [1, 2], [3, 4] be the K = 2 fixed chains. From the saddle point v∗ obtained in Lemma 3, we can fix, without loss of generality, any of the 4 cities as the first visited city. Thus, city 1 is considered to be the first visited city in the tour, which allows to obtain the following starting point: V(0) =  1 0 0 0 0 v∗3,2 0 v∗4,2  , where v∗3,2 = v∗4,2 = (2C + 3)dU (13C + 15)dU + 3dL + d1,3 + d1,4 + d2,3 + d2,4 With this projection, all symmetries of the problem are eliminated. That is, there are only two possible solutions: the tour 1 − 2 − 3 − 4 or the tour 1 − 2 − 4 − 3, whose solutions are respectively: V1 =  1 0 0 0 0 1 0 0  , V2 =  1 0 0 0 0 0 0 1  The Hopfield model with n = 4 and K = 2 will behave like a 2-opt if the starting point V(0) converges3 to the optimal solution, that is, between the solutions V1 and V2, converges to the one that has less value in the objective function. To find out to which solution the point V(0) converges to, it suffices to compute V(∆t), ∆t > 0 (following the differential Equation 1 with λ −→∞) and verify if the point is closer4 to the solution V1 or V2. du(0) dt = T · v(0) + ib (21) where the vector v(0) corresponds to the matrix V(0) written in vector form. In order to simplify calculations, the matrix V will be written as: V = [ v·,1 v·,2 ] being arranged in vector form as: v = [ v·,1 v·,2 ] As seen in the proof of Proposition 1, the weight matrix T and the bias vector ib are: T = − [ (B+C)1−BI C1+AI2+D(D2+(D2)T ) C1+AI2+D(D2+(D2)T ) (B+C)1−BI ] 3 Note that V(0) is not an equilibrium point of the dynamic system, since the projection of the saddle point is a different point than the saddle point of the projected energy function. 4 In case of continuing at the same distance, that is, v3,2(∆t) = v4,2(∆t), V(∆t) is projected again onto the same face, and the process is repeated. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 The 2-opt behavior of the Hopfield Network applied to the TSP 23 ib = CN ′ [ (1)4×1 (1)4×1 ] = CN ′ [ 1 1 ] By breaking down Equation 21, we obtain: du(0) dt = T · v(0) + ib = − [ (B+C)1−BI C1+AI2+D(D2+(D2)T ) C1+AI2+D(D2+(D2)T ) (B+C)1−BI ] · [ v·,1(0) v·,2(0) ] + CN ′ [ 1 1 ] = − [ ((B+C)1−BI)v·,1(0) + ( C1+AI2+D(D2+(D2)T ) ) v·,2(0) + CN ′1( C1+AI2+D(D2+(D2)T ) ) v·,1(0) + ((B+C)1−BI)v·,2(0) + CN ′1 ] The value of the potential in t = 0 can be obtained by applying the inverse of the activation function to the vector v(0): u(0) = g−1(v(0)) Using the piecewise-linear activation function proposed by Abe [1]: vi = g(ui) =  0 si ui ≤ −u0 1 2 ( 1 + ui u0 ) si −u0 < ui < u0 1 si ui ≥ u0 , ∀i ∈ {1, . . . , n} (22) its inverse function is: ui = g−1(vi) =  −u0 if vi ≤ 0 u0(2vi − 1) if 0 < vi < 1 u0 if vi ≥ 1 , ∀i ∈ {1, . . . , n}. Thus: u(0) = g−1(v(0)) = g−1 ([ v·,1(0) v·,2(0) ]) = [ u·,1(0) u·,2(0) ] where u·,1(0) =  u0 −u0 −u0 −u0  and u·,2(0) =  −u0 −u0 g−1(v∗3,2) g−1(v∗4,2)  with g−1(v∗3,2) = g−1(v∗4,2) = u0 ( 2(2C + 3)dU (13C + 15)dU + 3dL + d1,3 + d1,4 + d2,3 + d2,4 − 1 ) . Then, the potential in t = ∆t is computed: u(∆t) = u(0) + du(0) dt · ∆t being ∆t the integration step. Finally, the output of the dynamic system is computed at t = ∆t (using again Abe’s piecewise-linear activation function, see Equation 22): v(∆t) = g(u(∆t)) = g ( u(0) + du(0) dt · ∆t ) = [ g ( u·,1(0) − ( ((B+C)1−BI)v·,1(0) + ( C1+AI2+D(D2+(D2) T ) ) v·,2(0) + CN ′1 ) ∆t ) g ( u·,2(0) − ( ( C1+AI2+D(D2+(D2) T ) ) v·,1(0) + ((B+C)1−BI)v·,2(0) + CN ′1 ) ∆t ) ] Each of the two vectors (by blocks) obtained for v(∆t) is then computed: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 24 Not available v·,1(∆t) = g ( u·,1(0) − ( ((B+C)1−BI)v·,1(0) + ( C1+AI2+D(D2+(D2) T ) ) v·,2(0) + CN ′ 1 ) ∆t ) = 1 2 ( 1 + 1 u0 ( u·,1(0) − ( ((B+C)1−BI)v·,1(0) + ( C1+AI2+D(D2+(D2) T ) ) v·,2(0) + CN ′ 1 ) ∆t )) = 1 2 ( 1 1 1 1 + 1 u0 ( u0 −u0 −u0 −u0 − ( C B+C B+C B+C B+C C B+C B+C B+C B+C C B+C B+C B+C B+C C  ·  1 0 0 0  +  A+C A+C C+D(d1,4+d2,3) C+D(d1,3+d2,4) A+C A+C C+D(d1,3+d2,4) C+D(d1,4+d2,3) C+D(d1,4+d2,3) C+D(d1,3+d2,4) A+C A+C C+D(d1,3+d2,4) C+D(d1,4+d2,3) A+C A+C  ·  0 0 v∗3,2 v∗3,2  +  CN ′ CN ′ CN ′ CN ′  ) ∆t )) = − 1 2u0  ( (2v∗3,2 +N ′ + 1)C + v∗3,2(d1,3 + d1,4 + d2,3 + d2,4)D ) ∆t− 2u0( B + (2v∗3,2 +N ′ + 1)C + v∗3,2(d1,3 + d1,4 + d2,3 + d2,4)D ) ∆t( 2v∗3,2A+ B + (2v∗3,2 +N ′ + 1)C ) ∆t( 2v∗3,2A+ B + (2v∗3,2 +N ′ + 1)C ) ∆t  v·,2(∆t) = g ( u·,2(0) − ( ( C1+AI2+D(D2+(D2) T ) ) v·,1(0) + ((B+C)1−BI)v·,2(0) + CN ′ 1 ) ∆t ) = 1 2 ( 1 + 1 u0 ( u·,2(0) − ( ( C1+AI2+D(D2+(D2) T ) ) v·,1(0) + ((B+C)1−BI)v·,2(0) + CN ′ 1 ) ∆t )) = 1 2 ( 1 1 1 1 + 1 u0 ( −u0 −u0 g−1(v∗3,2) g−1(v∗3,2)  − ( A+C A+C C+D(d1,4+d2,3) C+D(d1,3+d2,4) A+C A+C C+D(d1,3+d2,4) C+D(d1,4+d2,3) C+D(d1,4+d2,3) C+D(d1,3+d2,4) A+C A+C C+D(d1,3+d2,4) C+D(d1,4+d2,3) A+C A+C  ·  1 0 0 0  +  C B+C B+C B+C B+C C B+C B+C B+C B+C C B+C B+C B+C B+C C  ·  0 0 v∗3,2 v∗3,2 +  CN ′ CN ′ CN ′ CN ′  ) ∆t )) = − 1 2u0  (A+ 2v∗3,2B + (2v∗3,2 +N ′ + 1)C)∆t (A+ 2v∗3,2B + (2v∗3,2 +N ′ + 1)C)∆t (v∗3,2B + (2v∗3,2 +N ′ + 1)C + (d1,4 + d2,3)D)∆t− u0 − g−1(v∗3,2) (v∗3,2B + (2v∗3,2 +N ′ + 1)C + (d1,3 + d2,4)D)∆t− u0 − g−1(v∗3,2)  The saddle point leaves all valid solutions at the same distance (see Lemma 3). Having projected the saddle point v∗ on one of its faces to obtain v(0), this point will not be an equilibrium point. However, the distance from v(0) to the two problem solutions will remain the same. In order to find out to which solution, starting from v(0), the dynamic system converges to, it will be enough to know to which solution v(∆t) is closer to. The dynamic system will converge to such solution. Let’s assume that v(∆t) is closer to the first solution. The case in which v(∆t) is closer to the second solution is equivalent. Considering that the solutions are written in vector form, we obtain: dist(v(∆t),v1) < dist(v(∆t),v2) Considering the squares of the distances to simplify the analysis: dist(v(∆t),v1)2 < dist(v(∆t),v2)2 and taking into account that all the terms except the last two are canceled: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 The 2-opt behavior of the Hopfield Network applied to the TSP 25 ( − 1 2u0 ( (v∗3,2B + (2v∗3,2 +N ′ + 1)C + (d1,4 + d2,3)D)∆t− u0 − g−1(v∗3,2) ) − 1 )2 + ( − 1 2u0 ( (v∗3,2B + (2v∗3,2 +N ′ + 1)C + (d1,3 + d2,4)D)∆t− u0 − g−1(v∗3,2) ))2 <( − 1 2u0 ( (v∗3,2B + (2v∗3,2 +N ′ + 1)C + (d1,4 + d2,3)D)∆t− u0 − g−1(v∗3,2) ))2 + ( − 1 2u0 ( (v∗3,2B + (2v∗3,2 +N ′ + 1)C + (d1,3 + d2,4)D)∆t− u0 − g−1(v∗3,2)− 1 ))2 The inequality (α− 1)2 + β2 < α2 + (β − 1)2 is satisfied if and only if β < α. This result leads to conclude that the previous inequality is satisfied if and only if: d1,3 + d2,4 < d1,4 + d2,3 that matches with the inequality satisfied in a 2-opt swap when the tour that produces v1 is shorter than the one produced by v2 (see Remark 5 and Figure 3, taking a = 1, b = 2, c = 3, d = 4). Therefore, using as the starting point in the Hopfield model the projection of the saddle point on one of its faces (to fix the first city to be visited), the Hopfield model behaves exactly as a 2-opt swap. References 1. Abe, S.: Global convergence and suppression of spurious states of the Hopfield neural networks. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Appli- cations 40(4), 246–257 (1993) 2. Croes, G.A.: A method for solving traveling-salesman problems. Operations research 6(6), 791–812 (1958) 3. Cuykendall, R., Reese, R.: Scaling the neural TSP algorithm. Biological Cybernetics 60(5), 365–371 (1989) 4. De Mazancourt, T., Gerlic, D.: The inverse of a block-circulant matrix. IEEE transactions on antennas and propagation 31(5), 808–810 (1983) 5. Garćıa, L.: Algunas cuestiones notables sobre el modelo de Hopfield en optimización. Ph.D. thesis, Universidad Complutense de Madrid (2017). URL https://eprints.ucm. es/46536/ 6. Garćıa, L., Talaván, P.M., Yáñez, J.: Attractor basin analysis of the Hopfield model: The Generalized Quadratic Knapsack Problem. In: International Work-Conference on Artificial Neural Networks, pp. 420–431. Springer (2017) 7. Garćıa, L., Talaván, P.M., Yáñez, J.: Improving the Hopfield model performance when applied to the traveling salesman problem. Soft Computing 21(14), 3891–3905 (2017). DOI 10.1007/s00500-016-2039-8 8. Hedge, S.U., Sweet, J.L., Levy, W.B.: Determination of parameters in a Hopfield/Tank computational network. In: Neural Networks, 1988., IEEE International Conference on, pp. 291–298. IEEE (1988) 9. Helsgaun, K.: An effective implementation of the lin–kernighan traveling salesman heuris- tic. European Journal of Operational Research 126(1), 106–130 (2000) 10. Helsgaun, K.: An extension of the lin-kernighan-helsgaun tsp solver for constrained trav- eling salesman and vehicle routing problems. Roskilde: Roskilde University (2017) 11. Hopfield, J.J.: Neural networks and physical systems with emergent collective computa- tional abilities. Proceedings of the national academy of sciences 79(8), 2554–2558 (1982) 12. Hopfield, J.J.: Neurons with graded response have collective computational properties like those of two-state neurons. Proceedings of the national academy of sciences 81(10), 3088– 3092 (1984) 13. Hopfield, J.J., Tank, D.W.: “Neural” computation of decisions in optimization problems. Biological cybernetics 52(3), 141–152 (1985) 14. Joya, G., Atencia, M., Sandoval, F.: Hopfield neural networks for optimization: study of the different dynamics. Neurocomputing 43(1-4), 219–237 (2002) 15. Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling-salesman prob- lem. Operations research 21(2), 498–516 (1973) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 https://eprints.ucm.es/46536/ https://eprints.ucm.es/46536/ 26 Not available 16. Papadimitriou, C.H.: The Euclidean travelling salesman problem is NP-complete. Theo- retical Computer Science 4(3), 237–244 (1977) 17. Platt, J.C., Barr, A.H.: Constrained differential optimization for neural networks (1988) 18. Reinelt, G.: TSPLIB. A traveling salesman problem library. ORSA journal on computing 3(4), 376–384 (1991) 19. Talaván, P.M., Yáñez, J.: Parameter setting of the Hopfield network applied to TSP. Neural Networks 15(3), 363–373 (2002) 20. Wasserman, P.D., Meyer-Arendt, J.R.: Neural computing, theory and practice. Applied Optics 29, 2503 (1990) 21. Woeginger, G.J.: Exact algorithms for NP-hard problems: A survey. In: Combinatorial Optimization—Eureka, You Shrink!, pp. 185–207. Springer (2003) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 Manuscript with tracked changes Click here to access/download Supplementary Material lucasgarcia_manuscript_trackedChanges_rev2.pdf https://www.editorialmanager.com/orij/download.aspx?id=70205&guid=afda4487-f4f6-4587-99bc-657297741aed&scheme=1