Creating Neural Network and Single Solution Human-Based Metaheuristic Methods of Solving the Traveling Salesman Problem Anait Karapetyan 1, Eugene Fedorov 1, Oleksii Smirnov 2 1 Cherkasy State Technological University, 460 Shevchenko ave, Cherkasy, 18006, Ukraine 2 Central Ukrainian National Technical University, 8 Universytetskyi ave., Kropyvnytskyi, 25006, Ukraine Abstract 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 human- based 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. Keywords 1 Travelling salesman problem, single solution human-based metaheuristics, self-organizing feature map, simulated annealing, dynamic effective width of the topological neighbourhood, rule of the centre of gravity calculation, 2-opt and 4-opt permutations. 1. Introduction A harsh socio-economic environment in Ukraine is a consequence of the war that Russia started and the direct cause of the increase in the destruction of civil infrastructure and, as a result, the loss of life and damage to property. Human and material recourse shortages are the cause for the integration of new information technologies that make it possible to increase the efficiency of rescue units’ performance. One of these tasks that requires using new models and methods is optimizing the time for the rescue units to travel to the location of destruction. There is an urgent need to develop methods aimed at solving combinatorial optimization problems used in intelligent computational systems. Optimization methods that find the exact solution have high computational complexity. Random search methods do not guarantee convergence. Optimization methods that find an approximate solution through local search have a high probability of hitting a local extremum. In this regard, there is a problem of insufficient efficiency of optimization methods, which needs to be addressed. Metaheuristics (or modern heuristics) and artificial neural networks are used to speed up finding a quasi-optimal solution to optimization problems and reduce the probability of hitting a local extremum. The object of inquiry. The process of finding solutions to optimization problems. MoMLeT+DS 2022: 4th International Workshop on Modern Machine Learning Technologies and Data Science, November, 25-26, 2022, Lviv- Leiden, Ukraine EMAIL: a.r.karapetyan@gmail.com (A. Karapetyan); fedorovee75@ukr.net (E. Fedorov); Dr.smirnovoa@gmail.com (O. Smirnov) ORCID: 0000-0002-7412-3252 (A. Karapetyan); 0000-0003-3841-7373 (E. Fedorov); 0000-0001-9543-874X (O. Smirnov) ©️ 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings (CEUR-WS.org) 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. To achieve this goal, it is necessary to solve the following tasks: Create an optimization method on an artificial neural network. Create an optimization method based on single-solution human-based metaheuristics. Conduct a quantitative study of the proposed optimization method. 2. Problem statement 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  P  1 ( f ( x ,W )  d  ) 2  min i.e. they result in the minimum mean square error (the difference 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. 3. Literature Review 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. 4. Self-organizing feature map 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. The training method consists of the following steps: 1. Training iteration number 𝑛 = 1, initialization of all network weights 𝑤𝑖𝑗 (𝑛), 𝑖 ∈ 1, 𝑀,𝑗 ∈ 1, 𝑁ℎ so that the point with coordinates (𝑤𝑖1 (𝑛), . . . , 𝑤𝑖𝑀 (𝑛)) is located on the is on the surface of an M -dimensional sphere of radius 𝑅 ∈ (0,1], where 𝑀 – the number of input layer neurons (or the length of the vertex coordinate vector), 𝑁 ℎ -the number of neurons in the output layer, usually 𝑀 ≤ 𝑁 ℎ ≤ 3𝑀. A set of vertex coordinates is specified {𝒙𝜇 |𝒙𝜇 ∈ 𝑅 𝑀 }, 𝜇 ∈ 1, 𝑀, where 𝒙𝜇 – 𝜇 - vertex coordinate vector. Initial shortest distance 𝑑(𝑛) =0. The maximum number of iterations N is set. 2. Calculation of the distance to all neurons of the network The distance 𝑑𝜇𝑗 from the  vertex to each j neuron is determined by the formula: 𝑑𝜇𝑗 = ∑𝑀 2 𝑖=1(𝑥𝜇𝑖 − 𝑤𝑖𝑗 (𝑛)) , 𝜇 ∈ 1, 𝑀, 𝑗 ∈ 1, 𝑁 ℎ 3. Calculation of the shortest distance and selection of the neuron with the shortest distance. The smallest distance is calculated 𝑑𝜇 = 𝑚𝑖𝑛𝑑𝜇𝑗 , 𝜇 ∈ 1, 𝑀, 𝑗 ∈ 1, 𝑁 (1) 𝑗 and the winning neuron is selected 𝑗𝜇∗ for which the distance 𝑑𝜇𝑗 is the shortest. 𝑗𝜇∗ = 𝑎𝑟𝑔 𝑚𝑖𝑛 𝑑𝜇𝑗 , 𝜇 ∈ 1, 𝑀, 𝑗 ∈ 1, 𝑁ℎ . 𝑗 4. 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 example, 𝜌2 (𝑗, 𝑗 ∗ ) 𝑒𝑥𝑝 (− ) , 𝜌(𝑗, 𝑗 ∗ ) < 𝜎(𝑛) ℎ𝑗,𝑗 ∗ (𝑛) = { 2𝜎 2 (𝑛) 0, 𝜌(𝑗, 𝑗 ∗ ) ≥ 𝜎(𝑛) 𝜌(𝑗, 𝑗 ∗ ) = 𝑚𝑖𝑛{ |𝑗 − 𝑗 ∗ |, 𝑁 (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 1 𝜎(𝑛) = 𝜎0 𝑒𝑥𝑝 (− ), 𝑇(𝑛) 𝑇(𝑛) = 𝛽 𝑛 𝑇(0), 𝜎0 – initial effective width of the topological neighbourhood, 𝑇(0) – start temperature, 𝛽 – cooling rate. 5. Checking the completion condition of training 1 𝑑(𝑛 + 1) = ∑𝑀 𝑑 , 𝑀 𝜇=1 𝜇 If 𝑛 < 𝑁, then 𝑛 = 𝑛 + 1, go to step 2. 6. Calculating the distance to all neurons in the network 𝑑𝜇𝑗 = ∑𝑀 2 𝑖=1(𝑥𝜇𝑖 − 𝑤𝑖𝑗 (𝑛)) , 𝜇 ∈ 1, 𝑀, 𝑗 ∈ 1, 𝑁 ℎ 7. Selecting the neuron with the shortest distance 𝑗𝜇∗ = 𝑎𝑟𝑔 𝑚𝑖𝑛 𝑑𝜇𝑗 , 𝜇 ∈ 1, 𝑀, 𝑗 ∈ 1, 𝑁ℎ 𝑗 The result is a vector of top-rank pairs ((1, 𝑗1∗ ), . . . , (𝑀, 𝑗𝑀 ∗ )) 5. Iterated local search 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). The method consists of the following steps: 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 [𝑑𝑖𝑗 ], 𝑖, 𝑗 ∈ 1, 𝑀. 1.3. Specifying the Cost Function (Goal Function) 𝐹(𝑥) = 𝑑𝑥𝑀,𝑥1 + ∑𝑀−1𝑖=1 𝑑𝑥𝑖 ,𝑥𝑖+1 → 𝑚𝑖𝑛, 𝑥 where 𝑑𝑥𝑀,𝑥1 – edge weight (𝑥𝑖 , 𝑥𝑖+1 ), 𝑥𝑖 , 𝑥𝑖+1 ∈ 𝑉, 𝑥 – vertex vector. 1.4. Set by randomly ordering the set 𝑉, the best vertex vector 𝑥 ∗ . 1.5. Local search based on 2-opt 1.5.1. 𝑚 = 0 1.5.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. 1.5.3. Based on the vector 𝑥 ∗ = (𝑥1∗ , . . . , 𝑥𝑐1−1 ∗ ∗ , 𝑥𝑐1 ∗ , . . . , 𝑥𝑐2 ∗ , 𝑥𝑐2+1 , . . . , 𝑥𝑀∗ ) The vector is created 𝑥 = (𝑥1∗ , . . . , 𝑥𝑐1−1 ∗ ∗ , 𝑥𝑐2 ∗ , . . . , 𝑥𝑐1 ∗ , 𝑥𝑐2+1 , . . . , 𝑥𝑀∗ ), ∗ ∗ i.e. vertexes 𝑥𝑐1 , . . . , 𝑥𝑐2 are transmitted in reverse order. 1.5.4. If 𝐹(𝑥) < 𝐹(𝑥 ), then 𝑥 ∗ = 𝑥, 𝑚 = 0, otherwise 𝑚 = 𝑚 + 1 ∗ 1.5.5. If 𝑚 < 𝑁2 , then go to step 1.5.2. 2. Iteration number 𝑛 = 1. 3. Performing a perturbation (generation of a solution 𝑥̑ from a solution 𝑥 ∗ based on 4-opt) 3.1. Three vertices are randomly selected from the 𝑥 ∗ vector: 𝑐1 = 2 + (𝑀/4) ∗ 𝑈(0,1), 𝑐2 = 𝑐1 + 1 + (𝑀/4) ∗ 𝑈(0,1), 𝑐3 = 𝑐2 + 1 + (𝑀/4) ∗ 𝑈(0,1), where 𝑈(0,1) – a function that returns a uniformly distributed random number in a range [0,1] 3.2. Based on the vector ∗ x ∗ = (x1∗ , . . . , xc1−1 ∗ ∗ , xc1 ∗ , . . . , xc2−1 ∗ , xc2 ∗ , . . . , xc3−1 ∗ , xc3 , . . . , xM ) The vector is created ∗ x̑ = (x1∗ , . . . , xc1−1∗ ∗ , xc3 , . . . , xcM ∗ , xc2 ∗ , . . . , xc3−1 ∗ , xc1 ∗ , . . . , xc2−1 ) 4. Local search based on 2-opt 4.1. m = 0 4.2. Two vertices c1 и c2, are randomly selected from the vector x ∗ and the selection of these vertices continues until the condition 1 < c2 − c1 < M − 1 is satisfied. 4.3. Based on the vector x̑ = (x̑ 1 , . . . , x̑ c1−1 , 𝑥̑ 𝑐1 , . . . , 𝑥̑ 𝑐2 , 𝑥̑ 𝑐2+1 , . . . , 𝑥̑ 𝑀 ) The vector is created 𝑥̆ = (𝑥̑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 𝑚 < 𝑁2 , then go to step 4.2. 5. If 𝐹(𝑥̑ ) < 𝐹(𝑥 ∗ ), then 𝑥 ∗ = 𝑥̑ 6. If 𝑛 < 𝑁1 , then 𝑛 = 𝑛 + 1, go to step 3 The result is 𝑥 ∗ . 6. Search with variable neighbourhood Variable neighbourhood search was proposed by Mladenović and Hansen [28] and used a local search in an growing neighbourhood. This algorithm is based on three principles:  is a local minimum for one neighbourhood, possibly not a local minimum for another neighbourhood;  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 solution by a permutation called "2-opt". The method consists of the following steps: An example of numbered list is as following. 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; maximum neighbourhood size 𝑁3 ; vertex vector lengths 𝑀. 1.2. An ordered set of vertices is specified 𝑉 = {1, . . . , 𝑀} and the edge weight matrix [𝑑𝑖𝑗 ], 𝑖, 𝑗 ∈ 1, 𝑀. 1.3. Specifying the Cost Function (Goal Function) 𝐹(𝑥) = 𝑑𝑥𝑀,𝑥1 + ∑𝑀−1 𝑖=1 𝑑𝑥𝑖 ,𝑥𝑖+1 → 𝑚𝑖𝑛, 𝑥 where 𝑑𝑥𝑀,𝑥1 – edge weight (𝑥𝑖 , 𝑥𝑖+1 ), 𝑥𝑖 , 𝑥𝑖+1 ∈ 𝑉, 𝑥 – vertex vector. 1.4. Is set by randomly ordering the set 𝑉, the best vertex vector𝑥 ∗ . 2. Iteration number 𝑛 = 0. 3. Neighbourhood size𝑍 = 1 4. Create a neighbourhood 𝑈𝑥 ∗ solutions 𝑥 ∗ based on 2-opt 4.1. 𝑧 = 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 𝑥 ∗ = (𝑥1∗ , . . . , 𝑥𝑐1−1 ∗ ∗ , 𝑥𝑐1 ∗ , . . . , 𝑥𝑐2 ∗ , 𝑥𝑐2+1 , . . . , 𝑥𝑀 ∗ ) the vector is created 𝑥𝑧 = (𝑥1∗ , . . . , 𝑥𝑐1−1 ∗ ∗ , 𝑥𝑐2 ∗ , . . . , 𝑥𝑐1 ∗ , 𝑥𝑐2+1 ∗ , . . . , 𝑥𝑀 ) ∗ ∗ i.e. the vertices 𝑥𝑐1 , . . . , 𝑥𝑐2 are rearranged in reverse order. 4.4. If 𝑥𝑧 ∉ 𝑈𝑥 ∗ , то 𝑈𝑥 ∗ = 𝑈𝑥 ∗ ∪ {𝑥𝑧 }, 𝑧 = 𝑧 + 1 4.5. If 𝑧 ≤ 𝑍, then go to step 4.2. 5. Vector 𝑥̑ is randomly selected from the neighbourhood 𝑈𝑥 ∗ 6. Local search based on 2-opt 6.1. 𝑚 = 0 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 , 𝑥̑ 𝑐1 , . . . , 𝑥̑ 𝑐2 , 𝑥̑ 𝑐2+1 , . . . , 𝑥̑ 𝑀 ) the vector is created 𝑥̆ = (𝑥̑1 , . . . , 𝑥̑ 𝑐1−1 , 𝑥̑ 𝑐2 , . . . , 𝑥̑ 𝑐1 , 𝑥̑ 𝑐2+1 , . . . , 𝑥̑ 𝑀 ) i.e. the vertices𝑥̑ 𝑐1 , . . . , 𝑥̑ 𝑐2 are rearranged in reverse order. 6.4. If 𝐹(𝑥̆) < 𝐹(𝑥̑ ), then 𝑥̑ = 𝑥̆, 𝑚 = 0, otherwise 𝑚 = 𝑚 + 1 6.5. If 𝑚 < 𝑁2 , then go to step 6.2. 7. If 𝐹(𝑥̑ ) < 𝐹(𝑥 ∗ ), then 𝑥 ∗ = 𝑥̑ , 𝑛 = 0, go to step 3, otherwise 𝑛 = 𝑛 + 1 8. If 𝑍 < 𝑁3 , then 𝑍 = 𝑍 + 1, go to step 4 9. If 𝑛 < 𝑁1 , then go to step 3 The result is 𝑥 ∗ . 7. Greedy randomized adaptive search 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". The method consists of the following steps: 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, 𝑀. 1.4. Specifying the Cost Function (Goal Function) 1.5. 𝐹(𝑥) = 𝑑𝑥𝑀,𝑥1 + ∑𝑀−1𝑖=1 𝑑𝑥𝑖 ,𝑥𝑖+1 → 𝑚𝑖𝑛, 𝑥 where 𝑑𝑥𝑀,𝑥1 – edge weight (𝑥𝑖 , 𝑥𝑖+1 ), 𝑥𝑖 , 𝑥𝑖+1 ∈ 𝑉, 𝑥 – vertex vector. Set by randomly ordering the set 𝑉, the best vertex vector 𝑥 ∗ . 2. Iteration number 𝑛 = 1. 3. Running a greedy randomized procedure 3.1. A vertex v cur is randomly selected from the plurality of vertices. From a set of vertices V, a vertex is randomly selected v cur The initialization of the set of forbidden vertices is V tabu = {v cur }, number of forbidden vertices l = 1, x̑ 1 = v cur 3.2. Creating a set of allowed vertices 𝑉̃ = 𝑉\𝑉 𝑡𝑎𝑏𝑢 , initialization of the set of restricted candidates 𝑉 𝑅𝐶𝐿 = ∅, vertex number 𝑗 = 1 𝑚𝑖𝑛 𝑚𝑖𝑛 𝑣𝑐𝑢𝑟 ,𝑣̃ 𝑚𝑎𝑥 𝑚𝑎𝑥 𝑣𝑐𝑢𝑟 ,𝑣̃ ̃| 𝑠 ̃| 𝑠 3.3. 𝑑 𝑠∈1,|𝑉 ,𝑑 𝑠∈1,|𝑉 , 𝑚𝑖𝑛 𝑚𝑖𝑛𝑚𝑎𝑥 3.4. If 𝑑𝑣 𝑐𝑢𝑟 ,𝑣̃𝑗 ≤ 𝑑 , then 𝑉 𝑅𝐶𝐿 = 𝑉 𝑅𝐶𝐿 ∪ {𝑣̃𝑗 } 3.5. If 𝑗 < |𝑉̃ |, then 𝑗 = 𝑗 + 1, go to step 3.3 3.6. From a set 𝑉 𝑅𝐶𝐿 a vertex is randomly selected 𝑣 𝑐𝑢𝑟 , 𝑉 𝑡𝑎𝑏𝑢 = 𝑉 𝑡𝑎𝑏𝑢 ∪ {𝑣 𝑐𝑢𝑟 }, 𝑥̑ 𝑙+1 = 𝑣 𝑐𝑢𝑟 3.7. If 𝑙 < 𝑀, then 𝑙 = 𝑙 + 1, go to step 3.2 4. Local search based on 2-opt 4.1. 𝑚 = 0 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 ) the vector is created 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 4.5. If m < N2 , then go to step4.2. 5. If F(x̑ ) < F(x ∗ ), then x ∗ = x̑ 6. If n < N1 , then n = n + 1, go to step 3 The result is 𝑥 ∗ . 8. Guided local search 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". The method consists of the following steps: 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 ; 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, 𝑀. 1.4. Specifying the Cost Function (Goal Function) 𝐹(𝑥) = 𝑑𝑥𝑀,𝑥1 + ∑𝑀−1 𝑖=1 𝑑𝑥𝑖 ,𝑥𝑖+1 → 𝑚𝑖𝑛, 𝑥 where 𝑑𝑥𝑀,𝑥1 – edge weight (𝑥𝑖 , 𝑥𝑖+1 ), 𝑥𝑖 , 𝑥𝑖+1 ∈ 𝑉, 𝑥 – vertex vector. 1.5. Specifying the penalty function 𝑀−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.8. Set by randomly ordering the set 𝑉, the best vertex vector 𝑥 ∗ . 1.9. The current solution is set 𝑥̑ , and 𝑥̑ = 𝑥 ∗ . 1.10. Penalties are initialized 𝑤𝑖𝑗 = 0, 𝑖, 𝑗 ∈ 1, 𝑀 2. Iteration number 𝑛 = 1. 3. Local search based on 2-opt 3.1. 𝑚 = 0 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 𝑥̑ = (𝑥̑1 , . . . , 𝑥̑ 𝑐1−1 , 𝑥̑ 𝑐1 , . . . , 𝑥̑ 𝑐2 , 𝑥̑ 𝑐2+1 , . . . , 𝑥̑ 𝑀 ) the vector is created 𝑥̆ = (𝑥̑1 , . . . , 𝑥̑ 𝑐1−1 , 𝑥̑ 𝑐2 , . . . , 𝑥̑ 𝑐1 , 𝑥̑ 𝑐2+1 , . . . , 𝑥̑ 𝑀 ) i.e. the vertices 𝑥̑ 𝑐1 , . . . , 𝑥̑ 𝑐2 are rearranged in reverse order. 3.4. If 𝐹𝐴 (𝑥̆, 𝑤) < 𝐹𝐴 (𝑥̑ , 𝑤), then 𝑥̑ = 𝑥̆, 𝑚 = 0, otherwise 𝑚 = 𝑚 + 1 3.5. If 𝑚 < 𝑁2 , then go to step3.2. 4. The penalties are modified 4.1. 𝑖 ∗ = 𝑎𝑟𝑔 𝑚𝑎𝑥 𝑓𝑈 (𝑥̑ , 𝑤, 𝑖) 𝑖 4.2. If 1 ≤ 𝑖 ∗ < 𝑀, then 𝑤𝑥̑ 𝑖∗ ,𝑥̑ 𝑖∗+1 = 𝑤𝑥̑ 𝑖∗ ,𝑥̑ 𝑖∗+1 + 1 If 𝑖 ∗ = 𝑀, then 𝑤𝑥̑ 𝑀,𝑥̑ 1 = 𝑤𝑥̑ 𝑀,𝑥̑ 1 + 1 5. If 𝐹(𝑥̑ ) < 𝐹(𝑥 ∗ ), then 𝑥 ∗ = 𝑥̑ . 6. If 𝑛 < 𝑁1 , then 𝑛 = 𝑛 + 1, go to step 3 The result is 𝑥 ∗ . 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 length 𝑀; maximum length of the tabu list 𝐿𝑚𝑎𝑥 . 1.2. An ordered set of vertices is specified 𝑉 = {1, . . . , 𝑀} and the edge weight matrix [𝑑𝑖𝑗 ], 𝑖, 𝑗 ∈ 1, 𝑀. 1.3. Specifying the Cost Function (Goal Function) 𝐹(𝑥) = 𝑑𝑥𝑀,𝑥1 + ∑𝑀−1 𝑖=1 𝑑𝑥𝑖 ,𝑥𝑖+1 → 𝑚𝑖𝑛, 𝑥 where 𝑑𝑥𝑀,𝑥1 – edge weight (𝑥𝑖 , 𝑥𝑖+1 ), 𝑥𝑖 , 𝑥𝑖+1 ∈ 𝑉, 𝑥 – vertex vector. 1.4. Set by randomly ordering the set 𝑉, the best vertex vector 𝑥 ∗ . 1.5. The current solution is set 𝑥̑ , and 𝑥̑ = 𝑥 ∗ . 1.6. Initialization of the set of tabu vertices 𝑉 𝑡𝑎𝑏𝑢 = ∅. 2. Iteration number 𝑛 = 1. 3. The number of the solution component is randomly selected 𝑗, and 𝑥̑𝑗 ∉ 𝑉 𝑡𝑎𝑏𝑢 4. Creating a set of vertex numbers 𝑉 𝑈 4.1. All vertices 𝑥̑ 𝑖 are sorted by proximity to the vertex 𝑥̑𝑗 4.2. Q of the top (closest) vertices are selected, from which a set 𝑉 𝑈 is created 5. Optimization procedure - use of search with prohibitions 5.1. Initializing the tabu list 𝑇 = ∅ 5.2. Search iteration number with tabus 𝑚 = 1. 5.3. Creating a neighbourhood 𝑈𝑥̑ solution 𝑥̑ based on 2-opt 5.3.1. 𝑧 = 1 5.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 ∧ 𝑐1, 𝑐2 ∈ 𝑉 𝑈 is satisfied. 5.3.3. Based on the vector 𝑥̑ = (𝑥̑1 , . . . , 𝑥̑ 𝑐1−1 , 𝑥̑ 𝑐1 , . . . , 𝑥̑ 𝑐2 , 𝑥̑ 𝑐2+1 , . . . , 𝑥̑ 𝑀 ) the vector is created 𝑥𝑧 = (𝑥̑ 1 , . . . , 𝑥̑ 𝑐1−1 , 𝑥̑ 𝑐2 , . . . , 𝑥̑ 𝑐1 , 𝑥̑ 𝑐2+1 , . . . , 𝑥̑ 𝑀 ) i.e. the vertices 𝑥̑ 𝑐1 , . . . , 𝑥̑ 𝑐2 are rearranged in reverse order. 5.3.4. A pair of tabu edges is created 𝐸𝑧 = ((𝑐1 − 1, 𝑐1), (𝑐2 − 1, 𝑐2)) for the vertex vector 𝑥𝑧 5.3.5. 𝑗 = 1 5.3.6. If 𝑗 < 𝑀 ∧ (𝑥𝑧𝑗 , 𝑥𝑧,𝑗+1 ) ∈ 𝑇 or 𝑗 = 𝑀 ∧ (𝑥𝑧𝑀 , 𝑥𝑧1 ) ∈ 𝑇, then go to step 5.3.2 5.3.7. If 𝑗 < 𝑀, then 𝑗 = 𝑗 + 1, go to step 5.3.6 5.3.8. If 𝑥𝑧 ∉ 𝑈𝑥̑ , then 𝑈𝑥̑ = 𝑈𝑥̑ ∪ {𝑥𝑧 }, 𝑧 = 𝑧 + 1, 5.3.9. If 𝑧 ≤ 𝑍, then go to step 5.3.3. 5.4. From neighbourhood 𝑈𝑥̑ a solution with the lowest price is selected 𝑥𝑧 ∗ , i.e. 𝑧 ∗ = 𝑎𝑟𝑔 𝑚𝑖𝑛 𝐹(𝑥𝑧 ) 𝑧 5.5. If 𝐹(𝑥𝑧 ∗ ) ≥ 𝐹(𝑥̑ ), then go to step 5.9 5.6. 𝑥̑ = 𝑥𝑧 ∗ . 5.7. A pair of edges is placed at the start of the tabu list . 5.8. If |𝑇| > 𝐿𝑚𝑎𝑥 , then a pair of edges that were tabued earlier is pushed from the end of the tabu list 𝑇. 5.9. If 𝑚 < 𝑁2 , then 𝑚 = 𝑚 + 1, go to step 5.3 6. If 𝑥̑ = 𝑥 ∗ , then 𝑉 𝑡𝑎𝑏𝑢 = 𝑉 𝑡𝑎𝑏𝑢 ∪ {𝑗} (a stronger version is possible 𝑉 𝑡𝑎𝑏𝑢 = 𝑉 𝑡𝑎𝑏𝑢 ∪ 𝑉 𝑈 ), otherwise 𝑥 ∗ = 𝑥̑ , 𝑉 𝑡𝑎𝑏𝑢 = 𝑉 𝑡𝑎𝑏𝑢 \𝑉 𝑈 (a weaker version is possible 𝑉 𝑡𝑎𝑏𝑢 = ∅) 7. If 𝑛 < 𝑁1 и |𝑉 𝑡𝑎𝑏𝑢 | < 𝑀, then 𝑛 = 𝑛 + 1, go to step 3 The result is 𝑥 ∗ . 10. Quantitative study 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. Figure 1: Annealing temperature decrease function The dependence (Fig. 1) of the annealing temperature on the iteration number shows that the annealing temperature decreases with an increase in the iteration number. In this case, the effective width of the topological neighbourhood according to the formula 𝜎(𝑛) = 1 𝜎0 𝑒𝑥𝑝 (− )and is presented in Fig.2 𝑇(𝑛) Figure 2. Effective Width of Topological Neighbourhood 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. Table 1 Comparison of the proposed SOFM training method with the existing one based on the criteria of time and path length Criteria Head Proposed method Existing method Time 𝑀⋅𝑁 𝑀 ⋅ 𝑁 ⋅ (𝑀 ⋅ 𝑁 ℎ ) (in case of use of GPU) Path length 7919 8510 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 № п/п Metaheuristics Best path length found 1 Iterative local search 8176 2 Search with variable neighborhood 8154 3 Greedy randomized adaptive search 8097 4 Guided local search 8034 5 Partial optimization metaheuristic under 7919 special intensification conditions 6 Taboo Search 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. [9] Yang X.-S. Optimization Techniques and Applications with Examples / X.-S. Yang. – Hoboken, New Jersey: Wiley & Sons, 2018. – 364 p. [10] Gendreau M. Handbook of Metaheuristics / M. Gendreau, J.-Y. Potvin. – New York: Springer, 2010. – 640 p. [11] Doerner K.F. Metaheuristics. Progress in Complex Systems Optimization / K.F. Doerner, M. Gendreau, P. Greistorfer, W. Gutjahr, R.F. Hartl, M. Reimann. – New York: Springer, 2007. – 408 p. [12] Chopard B. An Introduction to Metaheuristics for Optimization / B. Chopard, M. Tomassini. – New York: Springer, 2018. – 230 p. [13] Bozorg‐Haddad O. Meta-heuristic and Evolutionary Algorithms for Engineering Optimization / O. Bozorg‐Haddad, M. Solgi, H. Loaiciga. – Hoboken, New Jersey: Wiley & Sons, 2017. – 293 p. [14] Babayigit B. A clonal selection algorithm for array pattern nulling by controlling the positions of selected elements / B. Babayigit, K. Guney, A. Akdagli // Progress In Electromagnetics Research. – Vol. 6. – 2008. – P. 257-66. [15] Radosavljević J. Metaheuristic Optimization in Power Engineering / J. Radosavljević. – New York: The Institution of Engineering and Technology, 2018. – 536 p. [16] Du K.-L. Search and Optimization by Metaheuristics. Techniques and Algorithms Inspired by Nature / K.-L. Du, M.N.S Swamy. – Charm: Springer, 2016. – 434 p. [17] Alba E., Nakib A., Siarry P. Metaheuristics for Dynamic Optimization. – Berlin: Springer-Verlag, 2013. – 398 p. [18] Kobayashi M. Quaternionic Hopfield neural networks with twin-multistate activation function. Neurocomputing 267, 304–310 (2017) [19] Haykin S. Neural Networks and Learning Machines. Upper Saddle River, New Jersey: Pearson Education. Inc., 2009. 906 p. [20] K.-L. Du, K. M. S. Swamy, Neural Networks and Statistical Learning, Springer-Verlag, London, 2014. [21] Russell S. Artificial Intelligence: a Modem Approach / S. Russell, P. Norvig. – Englewood Cliffs, NJ: Prentice Hall PTR, 2020. – 1136 p p. [22] M. Tim Jones. Artificial Intelligence: A Systems Approach. Hingham, MA: INFINITY SCIENCE PRESS LLC, 2008. – 498 p. [23] The method of intelligent image processing based on a three-channel purely convolutional neural network / Fedorov, E., Lukashenko, V., Patrushev, V., Rudakov, K., Mitsenko, S. // CEUR Workshop Proceedings, 2018, 2255, pp. 336–351. [24] T Kohonen (2012) Self-organizing and associative memory, 3rd edn. Springer, New York [25] T Kohonen. Essentials of the self-organizing map. Neural Networks Volume 37, January 2013, Pages 52-65 https://doi.org/10.1016/j.neunet.2012.09.018 [26] Parallel computational algorithms in thermal processes in metallurgy and mining / Shvachych, G.G., Ivaschenko, O.V., Busygin, V.V., Fedorov, Ye.Ye. // Naukovyi Visnyk Natsionalnoho Hirnychoho Universytetu, 2018, Vol. 4, pp. 129–137 [27] Automated control of temperature regimes of alloyed steel products based on multiprocessors computing systems / Shlomchak, G., Shvachych, G., Moroz, B., Fedorov, E., Kozenkov, D. // Metalurgija, 2019, 58(3-4), pp. 299–302 [28] Talbi El-G. Metaheuristics: from design to implementation / El-G. Talbi. – Hoboken, New Jersey: Wiley & Sons, 2009. – 618 p. [29] Glover F. Handbook of Metaheuristics / F. Glover, G.A. Kochenberger. – Dordrecht: Kluwer Academic Publishers, 2003. – 570 p. [30] Brownlee J. Clever Algorithms: Nature-Inspired Programming Recipes / J. Brownlee. – Melbourne: Brownlee, 2011. – 436 p.