Solving the TSP by the AALHNN algorithm

1.   Introduction

In a broad sense, combinatorial optimization problem involves finding the "best" object from a limited set of objects. "Best" is measured by a given evaluation function, which maps the object to a score or cost. The goal is to find the object with the highest evaluation score and the lowest cost. Combinatorial optimization often involves sorting, classification, screening and so on. In terms of discrete cop problem, the goal is to find a set, an arrangement or a graph from all feasible solutions.

The Traveling Salesman Problem (TSP) is a classical combinatorial optimization problem. There are highly similar problems in multiple disciplines. This problem is described as follows: a traveling salesman needs to visit a number of (n) cities; he returns to the starting point after visiting every city once; then the shortest path among all paths that meet this condition is the optimal solution to this problem. The TSP is a NP-hard problem in classical combinatorial optimization, which is characterized by a fact that there is no method with polynomial-time complexity that can accurately find the optimal solution at present. Therefore, the TSP is mostly solved by heuristic algorithms such as genetic algorithm (GA), neural network algorithm and ant colony optimization (ACO). Hence, it is of great significance and theoretical value to study this problem.

The study of artificial neural network had been in a silence period of for more than ten years since the late 1960s, but began to flourish again in the early 1980s. The research boom has continued till today. At that time, the concept of HNN was proposed in the two classic papers of Hopfield and Tank ^[1,2]. Y. Zhu ^[3] addresses the problems of synchronization and state estimation for a class of discrete-time hierarchical hybrid neural networks (NNs) with time-varying delays. Wilson and pawleyi ^[4] found that the energy functions of Hopfield and tank may not get effective solutions. And in ^[5] the state estimation problem for a class of discrete-time switched neural networks with modal persistent dwell time (MPDT) switching and mixed time delays is investigated.Hopfield neural network is a recursive neural network, which was invented by John Hopfield in 1982. Hopfield network is a neural network combining storage system and binary system. It guarantees the convergence to the local minimum, but it may also converge to the wrong local minimum rather than the global minimum. Hopfield network also provides a model to simulate human memory. The success Hopfield and Tank made in the solution to the TSP by HNN inspired researchers to get down to dig deep into solving the NP-hard problem by neural network. It is found that neural network has many advantages over other methods in solving the TSP. M. Waqas et al. ^[6] described a neural network optimizer/scheduler. A new initialization rule is proposed to improve the performance of the system and make the system converge to the optimal solution in a shorter time. Therefore, various methods to improve the convergence of HNN were proposed by researchers after various improvements and studies of solving combinatorial optimization problem by HNN.

L. García et al. ^[7] pointed out CHNN (Continuous Hopfield Neural Network) is used as the optimizer to make the neural network competitive in solving k-opt problem. I. Valova et al. ^[8] discussed The implementation of some new optimization algorithms and traditional deep learning (DL) optimization algorithms. S. Z. Li ^[9] transformed the relaxation labeling problem into a constrained optimization problem and solved it by Lagrange multiplier method. D. Kaznachey et al. ^[10] and Z. Wu et al. ^[11] solved the combinatorial optimization problem by using neural network and logarithmic descent algorithm respectively. A. Pvy et al. ^[12] proposed a hybrid artificial neural network and genetic algorithm to predict the hysteresis loop and magnetic properties of alloys. The research shows that artificial neural network, as a powerful calculation technology in nonlinear system modeling, can be reliably applied to the prediction of nonlinear systems. A. Rachmad et al. ^[13] and A. Mazeev et al. ^[14] improved simulated annealing algorithm to solve minimum distance and TSP problem respectively. S. Z. Li ^[15] proposed the relaxation labeling to improve HNN by Lagrangian multiplier method and hierarchical HNN. Honari-Latifpour et al. ^[16] proposed the application of three state plane Potts model in combinatorial optimization problem. S. Zhang et al. ^[17] analyzed in detail a type of neural network for general nonlinear programming, i.e., equality and inequality constraints, etc. This method is based on the optimization of Lagrangian multiplier theory and seeks to provide solutions that meet the necessary conditions for optimality. S. S. Kia ^[18] discusses how to use the idea of augmented Lagrange method to solve the convex optimization problem with affine constraints, and obtain the distributed solution with convergence guarantee in the network with convex local cost. Y. Hu et al. ^[19] proposed A bi-directional graph neural network to solve arbitrary symmetric neural networks. U. P. Wen et al. ^[20] by dividing the application direction of HNN into three categories: linear, nonlinear and mixed integer, that we can better understand the application direction of HNN.

As it is difficult for HNN to converge to an efficient solution when solving the TSP, an AALHNN was designed in this paper. Firstly, the TSP was converted into a neural network model to solve a constrained optimization problem. For the convenience of solving the TSP by AALHNN, some changes were made to the corresponding constraints and objective functions in this paper. Secondly, AALHNN made some amendments to the defect that HNN could not get an efficient solution when solving the TSP. That is, the stability of neural network was improved by adding a quadratic term to AALHNN and the effectiveness and convergence of the algorithm were theoretically proved. Finally, the effectiveness of the algorithm was verified by some experiments of solving the TSP by simulation.

The rest of parts in this paper are included as follows. Part 2 is the model of the TSP to be solved. That is, the description of the problem model is illustrated herein. Part 3 refers to the dynamic iterative process of augmented Lagrangian neural network energy function and proves the convergence of the algorithm. A method based on nesterov technique is proposed to update the Lagrange factor which does not affect the convergence and robustness of ALHNN algorithm. Experimental process and data analysis and summary are provided in Part 4. Part 5 is the summary of this paper.

2.   Model of the TSP

2.1.   Problem description

The TSP, i.e., the traveling salesman problem, is a classical combinatorial optimization problem. This problem is described as follows. Suppose a traveling salesman has to visit a number of cities, he needs to choose a travel path, the constraints on which are that every city must be traversed once and only once and final arrival city must be the departure one so as to guarantee the salesman's profit. The ultimate goal of path selection is to obtain an efficient one, the total length of which should be the minimum among the all. For the salesman, the route length usually varies according to the sequence he chooses to traverse all the cities. For instance, the traversal length is different according to the two paths, i.e., A-H-G-F-E-D-C-I-B-A and A-H-G-F-E-D-C-B-I-A in Figure 1(a), (b), but both of them satisfy the constraints of the problem, which means they are both efficient solutions. When the number of cities is not great, the optimal path may be obtained by the method of exhaustion. Yet, when cities are considerable enough in number, the TSP is a typical NP-hard combinatorial optimization problem with the characteristic that it is always easy to describe but extremely difficult to solve to the extent that the optimal solution often cannot be obtained. In such cases, an approximate optimal solution can be obtained only by heuristic algorithm. Among various intelligent methods for solving the TSP, there is no universal optimal solver for all problem instances. This fact greatly facilitates the selection of solution algorithm. Neural networks generate solutions by fully representing a graph with a set of coordinates followed by capturing graphic information from the coordinates. It is more convenient to apply the TSP model on any symmetric graph here in reality ^[21]. Therefore, solving the TSP by neural networks has been proved to have great potential ^[22]. Meanwhile, under appropriate parameter settings, the network can be made more competitive by using continuous HNN ^[23]. Therefore, in this paper, in addition to referring to the previous experimental parameters, some parameters were also set in a reasonable and independent way, thus making the augmented Lagrangian neural network algorithm designed herein for solving the TSP more stable and effective.

2.2.   Mathematical model of the TSP

When solving the TSP by neural networks, this problem can be regarded as a label assignment problem. Let $S = \left\{ {1, \cdots, m} \right\}$ represent the set of $m$ element, and $\ell = \left\{ {1, \cdots, M} \right\}$ represent the set of $M$ cities, in which$m = M$. An $M$-dimensional vector ${p_i} = [{p_i}(I)|I \in \ell]$ is used to represent the assignment status of $i \in S$. The actual value ${p_i}(I) \in [0, 1]$ reflects the status in which $i$ is assigned to label $I$. The matrix $p = [{p_i}(I)|i \in S, I \in \ell]$ is the results of assignment.The Generative Adversarial Network (GAN) is composed of a generator and a discriminator.

Initially, Hopfield and Tank ^[2] proposed the following energy function for the TSP of $m$ citie

where ${d_{IJ}}$ is the distance between city $I$ and city $J$, while A, B, C and D are some constants. Variable ${p_i}(I) \in (0, 1)$ represents the neural output of city $I$ at position $i$ (position $m + 1$ is the same as 1). The relation between them and the internal variable ${u_i}(I)$ is${p_i}(I) = 1/(1 + {e^{ - {u_i}(I)/T}})$, where $T$ is a parameter for temperature. When $T \to 0$, all ${p_i}(I)$ are forced to take an extreme value. That is, the value of every ${p_i}(I)$ is 1 or 0. The first three terms on the right side of the equation are the constraints that generate effective travel paths and the last term determines the path length. The variable parameter is the solution to the TSP. HNN is the main neural network to solve combinatorial optimization problems. The structure of HNN uses three common methods i.e., penalty function, Lagrange multiplier, original method and dual method to construct the energy function. When the energy function converges to a steady state, the approximate optimal solution ${p^*} = \arg {\min _p}E(p)$ to this problem is obtained.

When studying the equation above, Wilson and PawleyI ^[4] found that there is a probability that this energy function cannot get an efficient solution. The reason for this is that the equation above may obtain a local minimum, which corresponds to an invalid travel path. In order to solve this problem, Brandt et al. proposed a corrected energy function as follows:

Although this made it converge better to travel paths than the equation proposed by Hopfield and Tank does, the quality of these paths is inferior to that of the original paths. In terms of theoretical analysis, it is reasonable because HNN is a classic use of penalty method. In order to make the penalty method converge to a feasible solution, the weighting factor of the penalty term should be big enough. However, as the penalty term becomes stronger and the constraints on the original problem become relatively weaker, the quality of the solution is also deteriorating. Even worse is that as they become ever-greater, the problem itself becomes pathological accordingly. This is a dilemma in penalty method. Therefore, neither of the above-mentioned methods can ensure that the solution obtained is an efficient and the optimal solution. The potential of HNN for solving combinatorial optimization problems is limited to some extent due to some of its own problems ^[24]. The AALHNN method designed herein helps the TSP converge to high-quality solutions by improving HNN by the augmented Lagrangian method. The TSP model in this paper is given in Eqs (3) to (5).

In this paper, the TSP is established as HNN dynamic system model by the same steps as HNN:

Step1: Each effective path of the TSP is extracted as a m*m-dimensional 0-1 digital matrix (commutation matrix). There is only one single 1 on each row and each column of the matrix while the others are 0. The length of each corresponding path should be calculated.

Step2: The commutation matrix in Step1 is associated with a neuron network composed of N neurons, and each element in the matrix corresponding to each path is associated with the corresponding neuronal steady-state output.

Step3: An energy function E should be found to solve the constrained optimization of the TSP.

Step4: The moment the minimum value of energy function E is calculated, record the connection weight matrix of the neural network and the bias parameter of the neural network.

The neural network designed by the steps above can solve the TSP. Then, the steady-state output of the network is the regional optimal solution to the TSP, and also the minimal point of the energy function ^[25]. Therefore, the extremum of the energy function can be obtained through the steady-state output obtained. At this moment, the search time for the neural network to reach the steady state is that for solving the TSP, and the calculating process is the iterative process of the dynamic equation of the neural network. Therefore, the objective function of an optimization problem needs to be at first converted into the energy function of the neural network, and the variables of the initial problem should correspond to the state of the network. In such cases, the combinatorial optimization problem TSP can be solved by HNN.

2.3.   Constrained minimization problem of the TSP

Firstly, the original combinatorial optimization problem is modified to the following constrained minimization problem:

where $E(p)$ is the objective function of the total length of the travel path, $K$ is an integer, ${C_k}$ is some real functions and the constraint is that the value should be 0. The final solution ${p_k}$ will be subject to additional constraints:

${C_k}(p)$ in Eq (4) is the following equality constraint:

Therefore, there is a total of a number of ($K$) equality constraints. They can be classified into three categories: the first category includes terms ${C_1}$ and ${C_2}$, the second does terms ${C_3}$ and ${C_4}$, and the third does term ${C_5}$. In this paper, when solving the objective function Eq (3) by the AALHNN method, the function $C$ was not simply added to the path length function as a penalty term. Instead, an augmented constraint optimization term was combined to form an augmented Lagrangian function.

3.   Solving the TSP by the ALHNN algorithm

The approximate optimal solution of the TSP was obtained by the ALHNN algorithm. The basic structure of neural network is to multiply the output of each neuron by some weights and then send it to the input end of other neurons, thus forming a total feedback structure ^[26]. The way how algorithm works is as follows. The objective function and constraints of the TSP are mapped to energy functions (e.g., Eqs (3) to (5) in Section 2.3) of a Hopfield model, Iterative updating of neural network by AALHNN. When the iterative convergence of the network reaches a certain stable solution, the energy function reaches some local minimum value. After these local minima were determined to meet the conditions for the approximate optimal solution, a solution that meets the conditions was obtained, i.e., the approximate optimal TSP path.

The algorithm flow chart is as follows:

3.1.   Solving the minimum constraint by the Lagrangian neural network

Like the method proposed by Hopfield, the internal variable ${u_i}(I) \in (- \infty, + \infty)(\forall i, I)$ was introduced and associated with ${p_i}(I)$ through Eqs (13) and (14).

${\psi _T}(x)$ is a Sigmoid Function controlled by the temperature parameter $T > 0$.

Because of the internal variable introduced $u$, the energy function $E(u)$ could be regarded as $E(p(u))$. This method made the value of ${p_i}(I)$ within the range of (0, 1), which satisfies the condition of Inequality Constraint Eq (5). Equality constraint Eq (4) was added to the Lagrangian function by the Lagrangian multiplier method. When $T \to {0^ + }$, the value of ${p_i}(I)$ will be 0 or 1 (depending on the positivity or negativity of ${u_i}(I)$), which meets the condition of constraint Eq (6). Finally, the following Lagrangian function was defined:

where, ${\gamma _k}$is a Lagrangian multiplier. The complete Lagrangian function of equality constraints Eqs (7) to (11) for solving the travelling salesman problem (TSP) is:

This function is composed of ${m^2}$ $p$ variables and number of $K$ $\gamma$ variables. Since ${p^*}$ is the local minimum solution, $({p^*}, {\gamma ^*})$ must be the stable point of the Lagrangian function, and therefore,

Now $({p^*}, {\gamma ^*})$ satisfies

The gradient (first derivative) value of the objective function at this point is 0, but one direction starting from the change point is the maximum point of the function, and the other direction is the minimum point of the function. This point is defined as the saddle point.

It can be seen from Eq (18) that when $p$ is constant, $L(p, \gamma)$ takes the maximum value when $\gamma$ = ${\gamma ^*}$, and when $\gamma$ is constant, $L(p, \gamma)$ takes the minimum value when $p$ = ${p^*}$.That is, $({p^*}, {\gamma ^*})$is a saddle point.

Therefore, when we know the value of ${\gamma ^*}$, we find ${p^*}$, and when we find ${p^*}$, the value of ${\gamma ^*}$ can also be obtained. This means that robustness of Lagrange algorithm is very strong. Augmented Lagrange has better robustness and convergence. It is more suitable for equality constraints. For inequality constraints, we need to deform the problem to obtain the intermediate variables, and then discuss and solve the intermediate variables.

According to Eq (18), if $({p^*}, {\gamma ^*})$ is a saddle point of $E(p)$, it can be seen from Eq (17) that $({p^*}, {\gamma ^*})$ meets the condition of being the minimum constraint of the Lagrangian function, and thus $({p^*}, {\gamma ^*})$ is a local minimum point of Lagrangian Function Eq (16) ^[27].

Such a saddle point can be found by solving the following kinetic equation by a basic differential multiplier:

Such an equation causes energy to fall as $p$ goes up and rise as $\gamma$ goes up. This process will be analyzed in detail in Section 3.2.

3.2.   Proof of convergence of the augmented Lagrangian neural network algorithm

Lagrangian function Eq (16) could be augmented into the following augmented Lagrangian function by adding a penalty term ${[{C_k}(p)]^2}$:

where, ${\beta _k} > 0$ is a penalty factor.

The kinetic equation used to find the saddle point was changed to:

This dynamic equations corresponds to the improved differential multiplier. ${p_i}(I)$ and ${\gamma _k}$ represent the state variables of corresponding neurons. The neurons in the neural network model were classified, according to the different functions of the variables in the neural network model, into two categories, i.e., Lagrangian neuron ${\gamma _k}$ and variable neuron${p_i}(I)$. It can be seen from the state equation of neural network model (22) that ${\gamma _k}$ made the trajectory of the network fall into the feasible region; and ${p_i}(I)$ reduced the Lagrangian function and made it always decrease with ${p_i}(I)$ and increase with ${\gamma _k}$ along the trajectory of the neural network model. Finally, when the neural network model iterated to the steady state, the stable point $({p^*}, {\gamma ^*})$ satisfies Eq (23),

In the above Eq (23), $\frac{{dL}}{{dt}}{|_{({p^*}, {\gamma ^*})}}$means the sum of the results after partial derivation of $p$ and $\gamma$ respectively^[28], In other words, the stable point of neural network model (22) is the stable point of the Lagrangian function we constructed. Equation (23) represents the sum of two partial derivatives are equal to zero. Because dynamic equations corresponds to the improved differential multiplier, So the differential of L over t is equal to the partial derivative of L at point P Plus the partial derivative of L at point R.

Lemma 3.2.1. If the following equation is satisfied, $({p^*}, {\gamma ^*})$ is an equilibrium point of neural network model (22).

Theorem 3.2.1. If and only if $({p^*}, {\gamma ^*})$ is an equilibrium point of neural network model (22), $({p^*}, {\gamma ^*})$is a saddle point of the Lagrangian function Eq (21).

Proof: If $({p^*}, {\gamma ^*})$ is a saddle point of the Lagrangian function Eq (21), Then according to Lemma 3.1.1, ${p^*}$ is a local minimum point of nonlinear programming problem Eq (21). Therefore, when $({p^*}, {\gamma ^*})$ is a saddle point of the Lagrangian function Eq (21), $({p^*}, {\gamma ^*})$is an equilibrium point of neural network model (22). If $({p^*}, {\gamma ^*})$ is an equilibrium point of neural network model (22), according to the analysis of the state equation of neural network model (22), the equilibrium point $({p^*}, {\gamma ^*})$ is a saddle point of the Lagrangian function. The theorem is thus proved.

Theorem 3.2.2. If $({p^*}, {\gamma ^*})$ is an equilibrium point of neural network model (22), the neural network model (22) is stable at point $({p^*}, {\gamma ^*})$.

Proof: The energy function that constructs neural network model (22) is

The differential of the energy function with respect to time $t$ is

The following conclusion can be drawn from the stability theory of Lyapunov:

1) If ${\nabla ^2}_{pp}L(p, \gamma)$ is positive definite, the differential of the energy function with respect to $t$ is $\frac{{dE}}{{dt}} < 0$. Therefore, the neural network model is asymptotically stable at point $({p^*}, {\gamma ^*})$.

2) If ${\nabla ^2}_{pp}L(p, \gamma)$ is positive semi-definite, the differential of the energy function with respect to $t$ is $\frac{{dE}}{{dt}} \leqslant 0$. Therefore, the neural network model is stable at point $({p^*}, {\gamma ^*})$.

Since $({p^*}, {\gamma ^*})$ is an equilibrium point of neural network model (22) and satisfies ${\nabla _p}L(p, \gamma) = 0$, the differential of the energy function with respect to $t$ at point $({p^*}, {\gamma ^*})$ is $\frac{{dE}}{{dt}} = 0$. Therefore, the conclusion above shows that the neural network is stable at point $({p^*}, {\gamma ^*})$. That is, the algorithm converges at this point.

The quadratic term introduced ${\sum\limits_k {{\beta _k}[{C_k}(p)]} ^2}$ does not affect the position of the saddle point because of $[{C_k}(p)] = 0$, and the quadratic term plays a role in stabilizing the system ^[29]. The penalty term is necessary for resisting the oscillations of the standard Lagrangian method and can improve the convergence performance of numerical calculation.

3.3.   Process of accelerate augmenting the Lagrangian neural network algorithm

In the augmented Lagrangian multiplier method, the label assignment object changed from $p$ to $u$; and neural network model (22) was replaced with

It is noticed that

Hence $u$ was updated with

In the TSP, the energy gradient in neural network model (22) is:

There are (n = ) $K$ Lagrangian multipliers $\gamma$ in the second term of neural network model (22); and the value of $K$ is given in Eq (12). There are three different types of constant ${\beta _k}$, which adapt to constraints Eqs (7) to (11) ^[30]. The neurons corresponding to travel paths are composed of ${m^2}$ ${p_i}(I)$ neurons. These neurons are associated with internal variable $u$ through Sigmiod Function. Meanwhile, an additional number of $5{m^2} + m$ $\gamma$ neurons for the Lagrange multipliers.

The tradition ALHNN algorithm realizes the kinetic processes described in Eqs (14), (22) and (30) in the following order as a whole:

Where, $\mu$ is the step length factor. During the update, $T$ may decrease and ${\beta _k}$ may increase to increase the convergence rate. All $i$ and $I$ were synchronously updated. The ALHNN algorithm is better than the genetic algorithm (GA) because it does not need the normalized operation required by the GA, which is more convenient for conducting a simulation experiment ^[29]. The convergence rate of ALHNN is $O(1/k)$.

In the experiment, we found that the iterative speed of ALHNN is too slow. This is because although ALHNN is globally convergent. Therefore, Using nesterov acceleration technique, we can obtain the following AALM (acceleration of augmented Lagrangian method) iterations.

Among them,

The convergence rate of AALHNN by nesterov acceleration technique is $O(1/{k^2})$^[31], Compared with the traditional ALHNN, it improves ALHNN's convergence speed.

Remarks: In the above proof process, the dynamic model is required to be a convex function ^[31], which has some good properties:

1) The feasible solution set is a convex set;

2) Any local optimal value of the objective function in the definition domain must be the global optimal solution;

3) The set of optimal solutions is convex (when the optimal solution exists);

if the programming problem to be solved is a nonconvex function, AALHNN probably not suitable.

The model in this paper is Minimized Energy Function $E(p)$. If Maximized Function $F(p)$ needs to be solved in some cases, simply $E(p) = - F(p)$, then the same renewal equation is used.

With the output to TSP written below, and constraints Eqs (7) to (11) as the constraints on the problem, the following augmented Lagrangian algorithm process could be obtained:

In Eqs (37) to (39) above, $\mu$ is the step length constant; $D$ is the weighting constant; $T$is the temperature constant; $\lambda$ is a non-decreasing factor of penalty term; and the two partial derivatives in neural network model (22) are

Equation (40) is the partial derivative of Lagrangian multipliers; and Eq (41) is the partial derivative of penalty terms. Here constant ${\beta _k}$ is uncorrelated to $i$ or $I$.

The system of dynamic equation with respect to variable $u$ in ^[4] is

The $p - u$ relation is

$u_i^{(t + 1)}(I)$ in Eq (43) shifted by 0.5. In this algorithm, $i$ and $j$ were synchronously updated.

4.   Simulation experiment

4.1.   Setting the experimental process

Experimental parameters were set as follows:

Since paths were closed, the city visited first was set as $I = 1$. Updated the algorithm parameters when $i, I = 2, \cdots, m$. During each operation, the initial value of variable $p$ was that recommended by Brandt as below.

$\delta$ was a value randomly taken from the uniform distribution$[-{10^6}, {10^6}]$; and variable ${u^{(0)}}$ was determined by the respective $u - p$ relation ^[31]. Finally, in the augmented Lagrangian multiplier, the Lagrangian multiplier $\gamma _k^{(0)}$ was set to 0.

If the following three conditions are met, the iterative process is deemed convergent. Here it was set to solve the termination condition.

Equation (46) ensures that the final state is stable, Eq (47) ensures the feasibility of the process; and Eq (48) indicates that the process is definite and that the value of $p$ is 0 or 1. The experiments that cannot meet these conditions during the experiment iteration are deemed invalid.

4.2.   Solving the TSP by the simulation experiment

In order to verify the actual application effect of the proposed AALHNN, the effect of the AALHNN was compared with that of the traditional Hopfield neural network (HNN) on the same TSP by pathfinding simulation, with a group of random paths set as a reference for the two algorithms. The number of cities was set to 8, 10, 12 and 15, respectively. The coordinates for solving the TSP for 15 cities are listed in Table 1 and the TSP of the number of other cities takes the coordinates of the previous corresponding number in the Table 1. Such data can be easily modified in the running code when solving practical problems.

The experimental environment is Intel(R) Core(TM) i7-7500U CPU, 8 GB memory, Geforce 940 MX, Windows 10 operating system, The simulation code of the AALHNN in this paper was solved by matlab 2016 b, while the codes of the HNN and random paths were compiled and solved by Phthon 3.7. Since there is a difference in the solving efficiency between the two languages, the solving time was not added as a performance comparison indicator for the two algorithms. The final pathfinding compare results are listed in Table 2. The experimental data settings are provided in Section 4.1.

Figure 3 shows that the HNN may generate a trivial solution due to its limitations; and according to the statistics by multiple experiments, the solution success rate is about 80% when the city number of TSP is 10 and will decreases to about 71% when the city number of TSP is 15. And under the same circumstances AALHNN can always solve TSP as long as the number of cities of TSP is reasonable. Therefore, experiments show that the AALHNN can jump out of the local optimal solution for the same problem and get a better solution result.

Figures 4 to 7 show the solution path diagrams of the three algorithms when the city number of TSP is 8, 10, 12 and 15, respectively. It can be seen from these figures that when the number of TSP cities is certain, the AALHNN solution result is better than HNN, and the two algorithms have great path length optimization compared with random paths, which means that AALHNN has certain application effectiveness and novelty.

It can be seen from Table 2 that the results obtained by AALHNN change little when the number of TSP cities increases. However, the results obtained by HNN begin to deform when the number of cities increases to 12, and the TSP path length increases greatly at this time. This reflects the robustness of AALHNN. Of course, from Figures 3 to 7, it can be seen that the results of the two neural networks are more optimized than the random path.

From Figure 8(a) it shows the comparison of the effective solution path length obtained by the three methods for TSP with different number of cities. It can be seen from the figure that the result obtained by AALHNN is better than that obtained by HNN, and from the simulation experiment, the success rate of AALHNN is 100%, which is greatly optimized compared with HNN. It is worth noting that the path length obtained by AALHNN is not optimized compared with ALHNN This is because the acceleration technique in this paper only improves the convergence rate of ALHNN, which can be seen from Table 3.

Figure 8(b) shows that the method of updating Lagrange factor by using the acceleration technique of Eq (39) can greatly improve the convergence speed (repeat the experiment 50 times for each coordinate and take the average value) of ALHNN. Table 3 shows that AALHNN improves the convergence rate compared with ALHNN, while AALHNN and ALHNN greatly improve the probability of obtaining feasible solutions compared with HNN.

4.3.   Result analysis

Tables 2 and 3 show that the length of random TSP paths was greatly optimized by the HNN. However, according to Figure 3, the HNN has a probability of not finding the efficient solution. Moreover, the AALHNN and ALHNN ensures better results when solving the TSP than the HNN, and greatly improves the solution success rate. It can be noticed that the solution success rate by the HNN decreases as the number of cities increases. The reason is that with the increase in the number of cities in the TSP, there's more probability of obtaining a trivial solution as the corresponding HNN equation gets stuck in the local minimum. It can also be noted that AALHNN greatly improves the convergence rate of ALHNN.The following conclusion is made based on the above simulation experiment and its analysis: the proposed AALHNN has better solution lengths and success rates than the HNN, and also has better solution convergence rate than ALHNN.

5.   Conclusions

Based on the basic HNN, an accelerated augmented Lagrangian method was proposed in this paper to solve the TSP. The innovation of this paper is from the existing literature, the paper found that the HNN may not always generate an efficient solution when solving the TSP (i.e., the shortcoming of the penalty method), but the AALHNN can overcome the shortcoming. The AALHNN introduces Lagrangian multipliers to solve the function and introduces quadratic terms to augment the Lagrangian function, providing greater convergence stability, And an iterative method based on nesterov acceleration technique is proposed to update the Lagrange factor. In this paper, the convergence of the AALHNN was theoretically proved. Besides, the performances and success rates in solving the TSP were compared between the HNN and AALHNN by a simulated program. It is concluded that the final solution length is shorter than HNN, and the solution success rate is greatly improved. It was found in experiments that the efficiency of solving the TSP by the AALHNN decreases with the increase in the number of cities. The reason is that when the number of cities increases, the equations with Lagrangian multipliers become more complex; the algorithm iteration becomes more difficult; and the amount of calculation also soars. As a result, the efficiency of obtaining efficient solutions decreases. Therefore, the next research direction should be expanding the application scope of the AALHNN by simplifying the equations.

Acknowledgments

This work is supported by the national key research and development program (2019YFB1705702).

Conflict of interest

The authors declared that they have no conflicts of interest to this work.