Traveling salesman route planning method based on novel shuffled frog leaping algorithm

Abstract

The invention discloses a traveling salesman route planning method based on a novel shuffled frog leaping algorithm, and the method comprises the steps: (1) reading problem information which comprisesthe coordinates of all visited cities and the scale of a problem; (2) initializing algorithm parameters; (3) generating an initial candidate population, and calculating fitness; (4) selecting an evolutionary population by adopting a reverse roulette strategy; (5) establishing an independent optimal subgroup, and dividing the subgroups according to individual fitness; (6) allocating an exclusive global optimal solution to each subgroup, and performing local search on each subgroup; (7) shuffling each subgroup, enhancing local search, putting the subgroups back to the candidate population, andre-selecting an iterative population to participate in the next iteration; and (8) judging whether the number of iterations reaches a maximum value or not, if so, terminating the iteration, and outputting an individual with optimal fitness, wherein the individual is the order of accessing the city by the traveling salesman. The method has the advantages of being high in search speed, high in search capacity and short in planned route.

Description

technical field [0001] The invention relates to the technical field of path planning, in particular to a traveling salesman route planning method based on a novel hybrid leapfrog algorithm. Background technique [0002] Most optimization problems in real life are combinatorial optimization problems. Traveling salesman problem (TSP) is one of the most representative problems among many combinatorial optimization problems, which can be simply described as an optimization problem of finding the shortest Hamiltonian circuit between multiple cities. In engineering practice, many practical problems can be transformed into TSP for solution, such as circuit printing, logistics transportation, robot path planning, network wiring and other engineering problems. However, the traveling salesman problem has been proven to be an NP-hard problem. As the scale of the problem increases, its feasible solution set also increases exponentially, and a "combinatorial explosion phenomenon" inevit...

AI Technical Summary

Problems solved by technology

However, the traveling salesman route planning method using the traditional hybrid leapfrog algorithm still has the following shortcomings: slow convergence, easy to fall into local optimum, and low solution accuracy

In the simulation experiment, compared with the traditional Leapfrog Algorithm, the average planning time of the improved algorithm is increased from 7.87s to 5.34s, and the success rate is increased from 86.7% to 100%, but it requires higher adjustment accuracy of the step size , otherwise it will be difficult to achieve the intended purpose

Images