The problem under review is improving the efficiency of the solution search for the Traveling Salesman Problem. We propose a shortest path neural network training method that executes a calibration of winner neuron weights and his neighbours based on the calculation of the centre of gravity, which allows paralleling the learning process and also utilizes the effective dynamic width of the topological neighbourhood (based on simulated annealing) for the calculation of topological neighbourhood function. A proposed modification to the single solution humanbased metaheuristic allows for potential integer solutions and utilizes a 2-opt permutation in local search neighbourhood creation and a 4-opt permutation in the case of global search. This will increase efficiency in the search for the optimal path by decreasing the computational complexity and increasing the accuracy of solutions.
The subject of inquiry. Methods for finding a quasi-optimal solution based on metaheuristics and artificial neural networks.
The paper aims to increase the efficiency of a quasi-optimal solution search to the travelling salesman problem using neural networks and metaheuristic methods.
Create an optimization method based on single-solution human-based metaheuristics.
The problem of increasing the efficiency of solution search to the travelling salesman problem based on single-solution human-based metaheuristics is presented as the problem of finding local and global search operators Alocal and Aglobal respectively, its application provides a search for such a solution, under which F(x* ) min and T min .
The problem of increasing the efficiency of searching for a solution to the travelling salesman problem based on a neural network is reduced to the problem of finding such a vector of parameters W that satisfies the criterion for the adequacy of the quasi-optimal solution search model 1 P F ( f (x ,W ) d )2 min i.e. they result in the minimum mean square error (the difference
P 1 W between the model output and the desired output), where is the power of the test set .– -th training input value, d .– -th - training output value.
The advantage of single-solution human-based metaheuristics is the ease of implementation, low computational complexity (no need to calculate a population of potential solutions), a small number of adjustable parameters and operators, and no requirement to model the behaviour of objects of different nature [1-3].
Existing metaheuristics suffer from one or more of the following disadvantages: there is only an abstract description of the method, or the description of the method is focused on solving only a specific problem [4-5]; the convergence of the method is not guaranteed [7-6]; the influence of the iteration number on the process of finding a solution is not taken into account [8-9]; the procedure for determining the values of parameters is not automated; [11-10] there is no possibility of using non-binary potential solutions [13-12]; insufficient accuracy of the method [14-15] ; there is no possibility of solving problems of conditional optimization [16-17]; This raises the problem of constructing efficient metaheuristic optimization methods. Existing neural networks suffer from one or more of the following disadvantages: high probability of the learning and adaptation method hitting the local extremum[18-19]; difficulty in determining the structure of the network since there are no algorithms for calculating the number of layers and neurons in each layer for specific applications [20-21]; inaccessibility for human understanding of the knowledge accumulated by the network (it is impossible to represent the relationship between output and output in the form of rules) since they are distributed among all elements of the neural network and are presented in the form of its weight coefficients [22]; the difficulty of forming a representative sample [23];
In this regard, the problem arises of constructing effective neural network optimization methods.
A one-dimensional self-organizing feature map (SOFM) [24-25] is a single-layer non-recurrent network. The neurons of the input layer correspond to the coordinates of the vertices. Before running the network, the neurons of the output layer correspond to the points of the multidimensional sphere (if the vertices are given on the plane, then these neurons correspond to the points of the ring), and after running the network, they correspond to the points in the obtained suboptimal path. In contrast to the classical learning method, in this paper, the weights of the winning neuron and its neighbours are adjusted not based on the Kohonen rule but based on calculation of the centre of gravity, which makes it possible to parallelize the learning process. [26-27]. In addition, unlike the classical learning method, this paper uses the effective dynamic width of the topological neighbourhood (based on simulated annealing) to calculate the topological neighbourhood function, which allows to explore the entire search space at the initial iterations and make the search directed at the final iterations, which ensures high search accuracy of this neural network.
Training iteration number = 1, initialization of all network weights ( ), ∈ 1, , ∈ 1, ℎ so that the point with coordinates ( 1( ), . . . , an M -dimensional sphere of radius ∈ (0,1], where ( )) is located on the is on the surface of – the number of input layer neurons (or the length of the vertex coordinate vector), ℎ -the number of neurons in the output layer, usually ≤ A set of vertex coordinates is specified { | ∈ }, ∈ 1, , where – - vertex coordinate ℎ ≤ 3 . vector.
2. 3. = example, Initial shortest distance ( ) =0.
The distance from the vertex to each j neuron is determined by the formula: = ∑ =1( and the winning neuron is selected ∗ for which the distance is the shortest.
Setting the weights of the winning neuron ∗ and its neighbours based on the calculation of the centre of mass of the j cluster.
( + 1) =
∑ =1 ℎ , ∗ ( )
∑ =1 ℎ , ∗ ( )
, ∈ 1, , ∈ 1, ℎ, where ℎ , ∗( ) - is the topological neighbourhood function, which is equal to 1 for = ∗and decreases as the distance between the and ∗ neurons in the topological space increase. For ℎ , ∗( ) = { (− 2( , ∗) 2 2( ) ) , ( , ∗) < ( ) ( , ∗) ≥ ( ) ( , ∗) =
{| − ∗|, (1) − | − ∗|}, ( ) – the effective width of the topological neighbourhood (the "diameter" of the topological neighbourhood function) decreases with time. In this paper, it is calculated based on simulated annealing ( ) = 0 ( ) = (0), (−
1 ( )
), 0 – initial effective width of the topological neighbourhood, 5. 6. 7.
The result is a vector of top-rank pairs ((1, 1∗), . . . , ( , ∗ ))
Iterated local search was proposed by Stutzle [28]. The algorithm consists of two phases perturbation and local search. The use of a perturbation action makes it possible to avoid local optima in a local search. Too little perturbation makes the algorithm greedy. In this paper, the perturbation consists of the formation of a new solution by a permutation called "4-opt" (the current solution is randomly divided into 4 parts, which become in order 1,4,3,2), and the local search consists of the formation of a new solution by permutation called "2-opt" (the elements of the new solution, located between two randomly selected vertices, are rearranged in reverse order).
1.
Initialization 1.1. Setting the maximum number of iterations 1; the maximum number of local search iterations 2, where no new best solution is found; vertex vector lengths . 1.2. An ordered set of vertices is specified = {1, . . . , } and the edge weight matrix [ ], , ∈ and the selection of these 1.3. Specifying the Cost Function (Goal Function) – vertex vector. 1.4. Set by randomly ordering the set , the best vertex vector ∗.
1.5.1.
vertices continues until the condition 1 < 2 − 1 < − 1 is satisfied.
The vector is created 1.5.3. Based on the vector ∗ = ( 1∗, . . . , ∗1−1, ∗1, . . . , ∗2, ∗2+1, . . . , ∗ ) = ( 1∗, . . . , ∗1−1, ∗2, . . . , ∗1, ∗2+1, . . . , ∗ ), 1.5.4. If ( ) < ( ∗), then ∗ = , i.e. vertexes ∗1, . . . , ∗2 are transmitted in reverse order. 2. 1.5.5. If
< 2, then go to step 1.5.2.
where (0,1) – a function that returns a uniformly distributed random number in a range [0,1]
x∗ = (x1∗, . . . , xc∗1−1, xc∗1, . . . , xc∗2−1, xc∗2, . . . , xc∗3−1, xc∗3, . . . , xM∗) x̑ = (x1∗, . . . , xc∗1−1, xc∗3, . . . , xc∗M, xc∗2, . . . , xc∗3−1, xc∗1, . . . , xc∗2−1)
vertices continues until the condition 1 < c2 − c1 < M − 1 is satisfied.
x̑ = (x̑ 1, . . . , x̑ c1−1, ̑ 1, . . . , ̑ 2, ̑ 2+1, . . . , ̑ ) ̆ = ( ̑1, . . . , ̑ 1−1, ̑ 2, . . . , ̑ 1, ̑ 2+1, . . . , ̑ ) i.e. the vertices ̑ 1, . . . , ̑ 2 are rearranged in reverse order. 4.4. If ( ̆) < ( ̑ ), then ̑ = ̆, = 0, otherwise = + 1 4.5. If
If ( ̑ ) < ( ∗), then ∗ = ̑
< 2, then go to step 4.2.
If is a local minimum for one neighbourhood, possibly not a local minimum for another the global minimum is a local minimum for all possible neighbourhoods; local minima are relatively close to global minima.
In this paper, the creation of a neighbourhood and a local search consists of the formation of a new
search in an growing neighbourhood.
neighbourhood; solution by a permutation called "2-opt".
1, . 1.3. 1.4. 2. 3. 4.
Variable neighbourhood search was proposed by Mladenović and Hansen [28] and used a local
Setting the maximum number of iterations 1; the maximum number of local search iterations 2, where no new best solution is found; maximum neighbourhood size 3; vertex vector lengths An ordered set of vertices is specified = {1, . . . , } and the edge weight matrix [ ], , ∈ Specifying the Cost Function (Goal Function)
Iteration number = 0.
Create a neighbourhood ∗ solutions ∗ based on 2-opt 4.1. = 1 4.2. Two vertices 1 и 2, are randomly selected from the vector ∗ vertices continues until the condition 1 < 2 − 1 < − 1 is satisfied. and the selection of these 4.3. Based on the vector the vector is created ∗ = ( 1∗, . . . , ∗1−1, ∗1, . . . , ∗2, ∗2+1, . . . , ∗ ) i.e. the vertices ∗1, . . . , ∗2 4.4. If ∉ ∗, то ∗ = ∗ ∪ { }, = + 1 = ( 1∗, . . . , ∗1−1, ∗2, . . . , ∗1, ∗2+1, . . . , ∗ )
are rearranged in reverse order. 4.5. If ≤ , then go to step 4.2. 5. 6. 6.1.
= 0
Vector ̑ is randomly selected from the neighbourhood ∗ 6.2. Two vertices 1 и 2, are randomly selected from the vector ̑ and the selection of these vertices continues until the condition 1 < 2 − 1 < − 1 is satisfied. 6.3. Based on the vector ̆ = ( ̑1, . . . , ̑ 1−1, ̑ 2, . . . , ̑ 1, ̑ 2+1, . . . , ̑ ) i.e. the vertices ̑ 1, . . . , ̑ 2 are rearranged in reverse order. 6.4. If ( ̆) < ( ̑ ), then ̑ = ̆, 7. 8.
If ( ̑ ) < ( ∗), then ∗ = ̑ , = 0, go to step 3, otherwise = + 1 If If < 3, then < 1, then go to step 3
= + 1, go to step 4
Greedy randomized adaptive search was proposed by Feo and Resende [29]. The algorithm consists of two phases - a greedy randomized procedure and a local search. The goal of the algorithm is to repeatedly generate random greedy solutions and then use a local search to bring these solutions closer to local optima. In this paper, local search consists of the formation of a new solution by a permutation called "2-opt".
1.
Initialization 1.1. Setting the greediness parameter or a greedy randomized procedure, where ∈ [0,1] (where
= 0 maximum greed) 1.2. Setting the maximum number of iterations 1; the maximum number of local search iterations 2, where no new best solution is found; vertex vector lengths . 1.3. An ordered set of vertices is specified = {1, . . . , } and the edge weight matrix [ ], , ∈
1.5. ( ) = , 1 + ∑ =−11 , +1 → ,
is randomly selected from the plurality of vertices.
From a set of vertices V, a vertex is randomly selected vcurThe initialization of the set of forbidden 3.2. Creating a set of allowed vertices ̃ = \ vertices is Vtabu = {vcur}, number of forbidden vertices l = 1, x̑ 1 = vcur , initialization of the set of restricted candidates
3.3. 3.4. If ∈1,|̃| ,̃ , , ̃ ≤ = ∅, vertex number = 1 ∈1,|̃| , then = ∪ { ̃ } 3.5. If < | ̃|, then = + 1, go to step 3.3 3.6. From a set a vertex is randomly selected , ∪ { }, ̑ +1 = 4.2. Two vertices 1 и 2, are randomly selected from the vector ̑ and the selection of these vertices continues until the condition 1 < 2 − 1 < − 1 is satisfied. 4.3. Based on the vector x̑ = (x̑ 1, . . . , x̑ c1−1, x̑ c1, . . . , x̑ c2, x̑ c2+1, . . . , x̑ M) x̆ = (x̑ 1, . . . , x̑ c1−1, x̑ c2, . . . , x̑ c1, x̑ c2+1, . . . , x̑ M) i.e. the vertices x̑ c1, . . . , x̑ c2 are rearranged in reverse order. 4.4. If F(x̆) < F(x̑ ), then x̑ = x̆, m = 0, otherwise m = m + 1 5. 4.5. If m < N2, then go to step4.2.
If F(x̑ ) < F(x∗), then x
∗ = x̑ If n < N1, then n = n + 1, go to step 3
Guided local search was proposed by Voudouris and Tsang [29]. The algorithm consists of two phases - local search and penalty modification. The use of a penalty function that increases the value of the goal function makes it possible to avoid local optima in local search. In this paper, local search consists of the formation of a new solution by a permutation called "2-opt".
1.
Initialization 1.1. Setting the scaling factor of the penalty function , and > 0 (for large the entire search space is explored, for small the search becomes directed) 1.2. Setting the maximum number of iterations 1 iterations 2, where no new best solution is found; vertex vector lengths . 1.3. An ordered set of vertices is specified = {1, . . . , } and the edge weight matrix [ ], , ∈ ; the maximum number of local search 1.4. Specifying the Cost Function (Goal Function) – vertex vector. 1.5. Specifying the penalty function – edge weight ( , +1), , +1 ∈ , ( , ) = , 1 + ∑ , +1 −1 =1 where , +1– edge penalty ( , +1), , +1 ∈ 1.6. Specifying an Extended Cost Function (Goal Function)
( , ) = ( )+ ⋅ ( , ) → 1.7. Setting the utility function ( , , ) = { , 1 , 1+ , +1 1+ , 1 , +1 , 1 ≤ < =
, ∈ 1, 1.9.
The current solution is set ̑ , and ̑ = ∗.
= 0, , ∈ 1,
Iteration number = 1.
Local search based on 2-opt
= 0 1.8. Set by randomly ordering the set , the best vertex vector ∗. 3.2. Two vertices 1 и 2, are randomly selected from the vector ̑ and the selection of these vertices continues until the condition 1 < 2 − 1 < − 1 is satisfied. 3.3. Based on the vector i.e. the vertices ̑ 1, . . . , ̑ 2 are rearranged in reverse order. 3.4. If ( ̆, ) < ( ̑ , ), then ̑ = ̆,
= 0, otherwise = + 1 3.5. If 4.1. ∗ =
The penalties are modified < 2, then go to step3.2.
( ̑ , , ) 4.2. If 1 ≤ ∗ < , then ̑ ∗, ̑ ∗+1 = ̑ ∗, ̑ ∗+1 5.
If ( ̑ ) < ( ∗), then ∗ = ̑ .
If ∗ = , then ̑ , ̑1 = ̑ , ̑1 + 1 If 9. Partial optimization metaheuristic under special intensification conditions
Partial optimization metaheuristic under special intensification conditions was proposed by Taillard and Voss [30]. The algorithm consists of four phases - the choice of the number of the component (part) of the solution, the creation of a set of components closest to the selected one, the optimization procedure, and the analysis of the resulting solution. The larger the number of nearest components, the larger the neighbourhood. In the optimization procedure (for example, search with tabus), only the nearest components of the solution are changed (in the case of the problem of finding the optimal path, these are vertices). In this paper, the creation of a neighbourhood consists of forming a new solution by a permutation called "2-opt".The method consists of the following steps: 1.
Initialization 1.1. Setting the maximum number of nearest components , the maximum number of iterations 1; the maximum number of search iterations with tabus 2; the size of neighbourhood ; solution = {1, . . . , } and the edge weight matrix [ ], , ∈ length ; maximum length of the tabu list 1.2. An ordered set of vertices is specified
. 1.3. Specifying the Cost Function (Goal Function)
, – edge weight ( , +1), , +1 ∈ ,
1.5. The current solution is set ̑ , and ̑ = ∗.
= ∅.
Iteration number = 1.
The number of the solution component is randomly selected , and ̑ ∉
Optimization procedure - use of search with prohibitions 5.1. Initializing the tabu list = ∅
Two vertices 1 и 2, are randomly selected from the vector ̑ and the selection of these ̑ = ( ̑1, . . . , ̑ 1−1, ̑ 1, . . . , ̑ 2, ̑ 2+1, . . . , ̑ ) = ( ̑1, . . . , ̑ 1−1, ̑ 2, . . . , ̑ 1, ̑ 2+1, . . . , ̑ ) i.e. the vertices ̑ 1, . . . , ̑ 2 are rearranged in reverse order. − 1 ∧ 1, 2 ∈ is satisfied.
A pair of tabu edges is created = (( 1 − 1, 1), ( 2 − 1, 2)) for the vertex vector If < ∧ ( , , +1) ∈ or =
∧ ( , 1) ∈ , then go to step 5.3.2 If ≤ , then go to step 5.3.3.
If < , then = + 1, go to step 5.3.6 If ∉ ̑ , then ̑ = ̑ ∪ { }, = + 1,
neighbourhood ̑ a solution with the lowest price is selected ∗, i.e. ∗ = 5.3.5. = 1 5.3.4. 5.3.6. 5.3.7. 5.3.8. 5.3.9. 5.4. From
( ) 5.6. ̑ = ∗. 5.8. If | | > list . 5.9. If
< 2, then
If ̑ = ∗, then 6.
If
< 1 и | 10. Quantitative study 5.5. If ( ∗ ) ≥ ( ̑ ), then go to step 5.9 5.7. A pair of edges is placed at the start of the tabu list . otherwise ∗ = ̑ , \ (a weaker version is possible = ∅) | < , then = + 1, go to step 3 , then a pair of edges that were tabued earlier is pushed from the end of the tabu = + 1, go to step 5.3 ∪ { } (a stronger version is possible
The quantitative study of the proposed optimization methods was carried out using the Matlab package. For the traveling salesman problem, the search for a solution was carried out on the standard database berlin52. For this database, the optimal path length is 7542.
In this paper, for a self-organizing feature map, the annealing temperature decrease function is determined by the formula ( ) = 0 and is shown in Fig.1. In this case, the initial effective width of the topological neighbourhood is 1, the initial temperature is 106, and the cooling coefficient is 0.94.
1 )and is presented in Fig.2 ( )
The dependence (Fig. 2) of the effective width of the topological neighbourhood on the annealing temperature shows that the effective width of the topological neighbourhood decreases with decreasing temperature.
The results of comparing the proposed SOFM learning method with the existing one based on the criteria of time and path length are presented in Table 1, where M is the number of input layer neurons (or the length of the vertex coordinate vector), N^h is the number of output layer neurons, N is the maximum number of iterations.
According to Table 1, the proposed teaching method gives a faster and more accurate result than the existing teaching method.
In this paper, for single-solution human-based metaheuristics, the maximum number of iterations is 100, and the neighbourhood size is 50. The penalty function scaling factor is 70, the greed parameter is 0.3, the maximum number of nearest components is 10, and the maximum length of the prohibition list is 3.
The results of the comparison of the proposed methods with the taboo search method based on the length of the path are presented in Table 2.
Table 2 Comparison of Proposed Single-Solution Human-Based Metaheuristics with Taboo Search Method 7919 8296
According to Table 2, the proposed single-solution human-based metaheuristics give a more accurate result than the taboo search, and the partial optimization metaheuristic under special intensification conditions is the most accurate. 11. Conclusions 1. The urgent task of increasing the efficiency of methods for solving the traveling salesman problem was undertaken by creating methods based on artificial neural networks and single-solution human-based metaheuristics. 2. The proposed modification of the learning method for a self-organizing feature map uses: setting weights of the winning neuron and its neighbours based on the calculation of the centre of gravity, this allows for accelerating the training of this neural network due to parallelization (in case of GPU use); the effective dynamic width of the topological neighbourhood for calculating the topological neighbourhood function, which allows to explore the entire search space at the initial iterations and make the search directed at the final iterations, this ensures high accuracy of the search through this neural network. 3. A modification of single-solution human-based metaheuristics is proposed that allows potential integer solutions and uses a 2-opt permutation in the case of a local search neighbourhood creation, and a 4-opt permutation in the case of a global search, which allows adapting these metaheuristics to solve the traveling salesman problem.
The proposed methods make it possible to expand the scope of application of the self-organizing feature map and single-solution human-based metaheuristics, which is confirmed by their adaptation to the traveling salesman problem and contributes improve efficiency of intelligent computational systems.
Prospects for further research are the study of the implementation of the proposed method on a broad class of artificial intelligence problems. 12.References [1] Rothlauf F. Design of modern heuristics: Principles and application / F. Rothlauf. – New York:
Springer-Verlag, 2011. – 267 p. [2] Nakib A. Metaheuristics for Medicine and Biology / Nakib A., Talbi El-G. – Berlin: Springer
Verlag, 2017. – 211 p. [3] Engelbrecht A.P. Computational Intelligence: an introduction / A.P. Engelbrecht. – Chichester,
West Sussex: Wiley & Sons, 2007. – 630 p. [4] Yu X. Introduction to evolutionary algorithms / X. Yu, M. Gen. – London: Springer-Verlag, 2010.
– 433 p. [5] Subbotin S. Diagnostic Rule Mining Based on Artificial Immune System for a Case of Uneven Distribution of Classes in Sample / S. Subbotin, A. Oliinyk, V. Levashenko, E. Zaitseva // Communications. – Vol.3. – 2016. – P.3-11. [6] Yang X.-S. Nature-inspired Algorithms and Applied Optimization / X.-S. Yang. – Charm:
Springer, 2018. – 330 pp. [7] Blum C. Hybrid Metaheuristics. Powerful Tools for Optimization / C. Blum, G. R. Raidl. – Charm:
Springer, 2016. – 157 p. [8] Martí R., Handbook of Heuristics / R. Martí, P.M. Pardalos, M.G.C. Resende. – Charm: Springer, 2018. – 1289 p.