Frontiers in Computing and Intelligent Systems ISSN: 2832-6024 | Vol. 9, No. 2, 2024 4 A Hill‐Climbing Differential Evolutionary Algorithm for solving Multiple Travelling Salesman Problem Jinhua Bian, Xiaoxia Zhang School of Computer Science and Software Engineering, University of Science and Technology Liaoning, Anshan Liaoning, 114051, China Abstract: The Multiple Travelling Salesman Problem (MTSP) is a basic deformation of the Travelling Salesman Problem (TSP), which is a typical NP-Hard problem. For combinatorial optimization problems shaped like MTSP, researchers often use intelligent optimization algorithms such as genetic algorithms, differential evolutionary algorithms, simulated annealing algorithms and other intelligent optimization algorithms to approximate the solution. However, typical intelligent optimization algorithms have the disadvantage of being prone to local convergence and failing to produce theoretically optimal solutions. Based on this, we propose an HCA&DE algorithm that improves the DE algorithm by using the hill-climbing algorithm, and carry out data experiments using the solution set of TSPLIB, which proves the practicality and effectiveness of the algorithm. Keywords: MTSP Problem; Differential Evolution Algorithm; Hill Climbing Algorithm. 1. Introduction The Multiple Travelling Salesman Problem is a variant of the classic combinatorial optimization problem---the Travelling Salesman problem, which is described as [1-2]: there are n cities and m travelers, which need to visit a certain number of cities and return to their respective starting points, and each city needs to be visited at least once, and the goal is to make the total trip of these m travelers the shortest. The Travelling Salesman Problem has a broader utility compared to the traveler problem, and is more applicable to problems such as logistics and transportation, and path planning. For the MTSP problem, many researchers used different improved optimization algorithms to solve it, Pin Liu [3] divided the algorithm into a K-means clustering phase and a genetic algorithm phase, thus speeding up the algorithm running efficiency and ensuring a balanced distribution of the workload among the travelers; Cong Bao[4]proposed an ant- watching mechanism as well as a modal algorithm based on comparative crossover, which significantly improves the quality of the offspring solution; Hong Rui Zhu[5]improved the fast uniparental genetic algorithm to enhance the diversity of the population and thus avoid falling into local optimums; Yafei Dong[6]introduced a new population partitioning method and heterogeneous evolutionary mechanism, as well as a guided and unguided jumping mechanism on the basis of the frog-jumping algorithm, thus improving the efficiency of the co-evolutionary process and ultimately obtaining a high- quality solution; Bing Sun[7], based on the balanced multi- traveler problem's optimization objective, constructed a new type of evaluation function and designed a dual chromosome coding method, thus improving the computational ability of the algorithm. In this paper, for the shortcomings of Differential Evolutionary Algorithm which is easy to fall into local optimum and unable to obtain the optimal solution, an improved DE algorithm based on Hill-Climbing algorithm- HCA&DE algorithm is proposed according to the strategy of Hill-Climbing algorithm, which utilizes the crossover operators such as 2-opt, insert-opt ,3-opt to local search for the solution set, to improve the algorithm's ability to local search, and performs the data experiments by using the TSPLIB dataset. The experiments prove the superiority and effectiveness of the improved algorithm. 2. Algorithm Design 2.1. Differential Evolutionary Algorithm The idea of Differential Evolutionary Algorithm is similar to genetic algorithm, which is an intelligent optimization algorithm that simulates the criterion of biological selection and survival of the fittest in nature. It consists of four main operations: initial population, simulated mutation, simulated crossover, and natural selection. the DE algorithm retains the global search strategy based on population, and reduces the complexity of the genetic operation by adopting the real number coding, the simple mutation operation based on difference, and the one-to-one competition survival strategy. Unlike the GA algorithm, the DE algorithm links the mutation operation to the crossover operation, where the mutated individuals are parametrically mixed with some pre- determined target individuals to generate test individuals and complete the crossover operation. The mutation operation of the difference algorithm utilizes the difference vectors xp1, xp2 of two individuals randomly selected from the population as the source of random variation of the third individual xp3, and generates the mutated individuals by weighting the difference vectors and summing them with the third individual according to a certain rule, which is calculated by the formula:          1 2 3 1ij p j p j p jv t x t x t x t    (1) After the mutation operation, we perform a crossover operation to crossover the mutated individual with the probability of a particular parent individual, firstly, we set the mutation probability Pc, and then we generate the mutation random number and dimension random number for each dimension of the individual, when the random number of a certain dimension is less than Pc or the dimension random number is equal to the number of the current dimension, then the current dimension value of the new individual equals to the current dimension value of the mutated individual, or else it equals to the current dimension value of the parent individual. individual's current dimension value, otherwise it 5 is equal to the parent's current dimension value. The formula is as follows: rand(i)j or Pcrand tv rand(i) j and Pcrand tx tu ijij ijij ij   )1( )( )1( { (2) randij is a random decimal between [0,1], Pc is the crossover probability, Pc∈[0, 1], and rand (i) is a random integer between [1,n]. This crossover strategy ensures that at least one component of xi (t+1) is contributed by the corresponding component of xi (t). After the above crossover and selection algorithms, the selection operation is executed, using tournament one-to-one selection, i.e., the parent individual is compared with its own children, and whoever is better adapted survives. This concludes the round of Differential Evolutionary Algorithm. The pseudo-code of DE algorithm is shown in Algorithm 1. Algorithm 1: DE algorithm Input: Population:P；Dimension:D；Generation:R； Output: The Best solution path: BestPath 1： r←1(initialization): 2： for i = 1 to P do 3： for j=1 to D do 4： 5： end 6： end 7： while( )or( )do 8： for i=1 to P do 9： //Mutation and Crossover operation 10： for j=1 to D do 11： 12： 13： end 14： //Selection operation 15： if then 16： 17： if then 18： 19： end 20： else 21： 22： end 23： end 24： r←r+1; 25： end 26： return the Best solution path BestPath 2.2. Hill Climbing Algorithm Figure 1. Flowchart of HCA search algorithm The Hill-Climbing algorithm is a typical local optimal search algorithm, which uses various crossover operators to generate the neighbors of the current solution, and iterates using the better individuals in the generated neighboring solutions to keep updating the current optimal solution until there is no better solution in the current generated neighboring solutions. For the MTSP problem, the more classical crossover operators include 2-opt, double-bridge-swap, insert-swap, etc. These operators are able to form new neighboring individuals flexibly and extensively, thus effectively forming and updating the current optimal solution. As a typical local search algorithm, hill-climbing algorithm can effectively solve the problem that DE algorithm is easy to fall into the local optimum and cannot obtain the optimal solution. The performance of Hill-Climbing algorithm depends on the selection of crossover operators, and in this paper, 2-opt, insert-opt and 3-opt are selected as the crossover operators of Hill-Climbing algorithm. 2-opt-swap algorithm is to exchange all the cities in the two cities in the reverse order to form a new path. insert-opt algorithm is to randomly select the cities in an interval and randomly insert a sequence of cities in the segment into another position of the solution set. 3-opt algorithm is to randomly select the cities in an interval and randomly insert a sequence of cities into the solution set. another location. The 3-opt algorithm is to randomly select three cities, exchange their order and generate a new path. The flowchart of the Hill-Climbing algorithm designed in this paper is shown in Figure 1. 3. HCA&DE Algorithm 3.1. HCA&DE Algorithm Introduction HCA&DE algorithm is a combination algorithm of Differential Evolutionary Algorithm and Hill-Climbing search algorithm, he has the powerful global search performance of Differential Evolutionary Algorithm, and at the same time, the local search ability of DE algorithm is enhanced by the Hill-Climbing algorithm, which makes the HCA&DE algorithm have both powerful local search ability and global search ability, and it can search for better solutions more efficiently. The HCA&DE algorithm includes initialization, mutation, crossover, selection, 2-opt, insert-opt, 3-opt and other operations. First, initialize the population and randomly generate N paths that meet the requirements. After that, we set the 6 crossover and mutation probabilities of DE algorithm and start to calculate the number of iterations of HCA & DE algorithm, perform the regular DE mutation, crossover and selection operations, update the current population solution and then select an city path solution set i from the current population in a roulette wheel way, and then enter into the Hill-Climbing search algorithm, which first performs the 2- opt algorithm to form the neighbors of the current solution, then the 2-opt algorithm to form the neighbors of the current solution. opt algorithm to form the neighbor S of the current solution, if the fitness of all the individuals in the current neighbor S is lower than the fitness of the current optimal solution, then enter insert-swap swap algorithm, if the fitness of all the individuals in the neighbor of the current solution formed by the insert-swap algorithm is lower than the fitness of the current optimal solution, then enter the 3-opt algorithm, and if it still can't replace the optimal solution, then the HCA&DE will be used. The current round of HCA&DE algorithm ends, so that the number of HCA&DE iterations is increased by 1. If one of the solutions generated during the execution of the three local search algorithms is better than the current optimal solution, the current optimal solution is updated immediately and the search is restarted by jumping to the 2-opt algorithm. The HCA&DE algorithm ends when the upper limit of the HCA&DE algorithm iterations is reached. 3.2. HCA&DE Algorithm Design Step1: Initialize HCA&DE parameters: set DE mutation probability 0.08, crossover probability 0.65, HCA&DE algorithm iteration number upper limit is 800, Population size Pop_Size=500, make current HCA&DE iteration count variable g=0, greedy initialization to generate initial population P. Step2: Randomly select three solution sets from the current population, perform DE algorithm mutation operation to generate new city solution paths, and calculate the fitness of the new solutions. Step3: Select city solution sets from the current population and perform DE algorithm crossover operation with mutated individuals to generate new city solution paths and calculate the fitness of new solutions. Step4:Perform the DE algorithm selection operation, update the current population, and select an city solution set by the rule of “roulette”. Step5:Start Hill-Climbing algorithm and select an initial solution i in the rule of “roulette”. Step6:Execute 2-opt crossover algorithm, randomly select two cities at a time, exchange their order in the solution set, and form the neighbor Si1 of the current solution, if there is a better solution than the current solution i in Si1, update the current solution and re-execute Step6, otherwise go to Step7. Step7:Execute insert-swap crossover operator to randomly select a city in an interval and randomly insert this sequence of cities into another position in the solution set to form the neighbor Si2 of the current solution, if there exists a solution in Si2 that is better than the current solution i, then update the current solution and execute Step6, otherwise go to Step8. Step8:Perform 3-opt algorithm operation, randomly select three cities at a time to form the neighbor Si3 of the current solution, if there exists a better solution than the current solution i in Si3, update the current solution and execute Step6, otherwise go to Step9. Step9:make g=g+1,if g<800 then go to Step2,otherwise it represents that the upper limit of iteration number of HCA&DE algorithm is reached at this time, end HCA&DE algorithm. 4. Experiment The HCA&DE algorithm proposed in this paper is implemented in Codeblocks software using C++. In order to test the performance of the HCA&DE algorithm in solving the multi-starting-point MTSP problem and to compare the difference in performance between the HCA&DE algorithm and the ordinary DE algorithm, we use the TSPLIB test dataset and choose three city datasets with a large difference in the number of cities, for each test set, we set the number of travel quotients as 4, 8, and 12, and set fixed starting points for each of them, after which the algorithm is run for testing. In order to set the optimal HCA&DE algorithm parameters for the multi-starting point MTSP problem, we utilize the eil51 dataset, which has fewer cities and is relatively easy to compute the optimal solution, for the parameter test, and finally determine the optimal crossover probability parameter for the DE algorithm to be 0.65, the variance probability to be 0.08, the population size to be 500, and the upper limit of the iteration number of the HCA&DE algorithm to be 800. Table 1 gives the optimal paths generated by DE algorithm, HCA algorithm and HCA&DE algorithm under the test of dataset with city size of 51,100,150. The data show that under the same parameter settings, HCA&DE is not only able to find a better path to the city solution set, but also the solution differences are more stable than the ordinary DE algorithm and HCA algorithm, which proves that HCA&DE can jump out of the localoptimum timely when the algorithm falls into the local optimum, ensure the diversity of the population solution, and find the optimal solution with a greater probability. Table 1. Running results of DE algorithm, HCA algorithm and HCA&DE algorithm Number of cities Number of Salesman DE HCA HCA&DE Best Average Best Average Best Average 51 4 507 530 516 543 497 513 8 673 702 656 708 613 640 12 987 1033 946 979 876 891 100 4 26475 28571 24968 26092 23377 23609 8 27876 31016 27348 31648 25099 26002 12 32547 34879 31954 33399 30174 30453 150 4 30153 31797 30092 32017 28176 28791 8 39880 43097 38987 40188 34049 36804 12 48901 50013 49073 49975 38042 40035 7 5. Conclusion In this paper, for the shortcomings of DE algorithm which is easy to fall into local optimization, the hill-climbing search algorithm is introduced to enhance the local search ability of DE algorithm, so that DE algorithm can jump out of the local optimization in time and obtain the optimal solution more efficiently. The experimental data proves that for the multi- start MTSP problem, the results of the HCA&DE algorithm proposed in this paper are proved to be better than the ordinary DE algorithm and the ordinary hill-climbing search algorithm, and the probability of obtaining the optimal solution is larger, which proves that the HCA&DE algorithm combines the local search ability of the HCA algorithm and the global search ability of the DE algorithm, and proves the effectiveness of the HCA&DE algorithm. However, the time complexity of HCA&DE algorithm is larger, and with the increase of city scale, the time complexity of HCA&DE algorithm needs to be further improved. Acknowledgments This work it was supported by National College Students' innovation and entrepreneurship training program project (No. ???). References [1] Zhao Xiaoqiang,Tuo Mingfu. An applied study of task planning problem based on multi-traveler problem model for solving workload equalization[J]. Internet of Things Technology, 2024,14(07): 84-89.DOI:10.16667/j.issn.2095- 1302. 2024.07.022. [2] YANG Hua, CHEN Yanhua, LI Hongyi. Automatic preparation method of contact network maintenance plan based on multi-traveler problem[J]. Electrified Railway,2023,34(01): 81-85.DOI:10.19587/j.cnki.1007-936x.2023.01.016. [3] Liu Pin. Research based on two-stage heuristic algorithm for multi-traveler problem[D].Northern-Nationalities-University, 2024. DOI:10.27754/d.cnki.gbfmz.2024.000383. [4] Bao Cong.Research on Evolutionary Algorithms for Access- Constrained Multi-Traveler Problem[D]. Nanjing University of Information Engineering, 2023.DOI: 10.27248/ d.cnki. gnjqc. 2023.001033. [5] H.R. Zhu. Research on Improving Monophilic Genetic Algorithm to Solve Multi-TravelerProblem[D]. West-China- NormalUniversity,2023.DOI:10.27859/d.cnki.gxhsf.2023.000 111. [6] Dong Yafei. Optimization study of two classes of complex multi-traveler problems based on evolutionary algorithms[D]. Chongqing University, 2022.DOI: 10.27670/ d.cnki. gcqdu. 2022.002674. [7] SUN Bing, WANG Chuan, YANG Qiang, et al. Evolutionary algorithms for the multiple starting point equilibrium multi- traveler problem[J]. Computer Engineering and Design, 2023, 44(07):2030-2038.DOI:10.16208/j.issn1000-7024. 2023.07.015.