CN-121994261-A - Improved self-adaptive ant colony algorithm path planning method and system

CN121994261ACN 121994261 ACN121994261 ACN 121994261ACN-121994261-A

Abstract

Initializing, loading traveling business problem instance data of a plurality of places based on basic parameters and dynamic parameters of an improved self-adaptive ant colony algorithm, constructing a distance matrix among places based on Euclidean distance, and initializing a symmetrical pheromone matrix; iterative optimization, namely gradually constructing a complete path by each ant from a randomly selected initial place through an improved state transition probability rule, calculating the path length of each ant, recording the current iterative optimal path and the length thereof, stopping the operation of the algorithm when the iterative times reach the preset value, counting the results of multiple rounds of operation to obtain the average optimal distance of the multiple rounds of operation and the minimum distance in the multiple rounds of operation, namely obtaining an optimal planning path, introducing a self-adaptive volatilization mechanism, dynamically adjusting the pheromone volatilization rate according to the iterative times, and solving the problem of local optimization.

Inventors

PENG CHENG
HUANG TAO
MA WENBO
MA JIAYUAN
GAO ZHU
BU MIN

Assignees

宁夏师范大学

Dates

Publication Date: 20260508
Application Date: 20251029

Claims (10)

1. An improved self-adaptive ant colony algorithm path planning method is characterized by comprising the following steps: initializing, namely loading traveling business problem instance data of a plurality of places based on improved self-adaptive ant colony algorithm basic parameters and dynamic parameters, constructing distance matrixes among places based on Euclidean distances, and initializing symmetrical pheromone matrixes; Iterative optimization, namely gradually constructing a complete path by each ant from a randomly selected initial place through an improved state transition probability rule, calculating the path length of each ant, recording the current iterative optimal path and the length thereof, and carrying out evaluation by dynamically adjusting a volatilization coefficient optimization algorithm in the iterative process, carrying out parameter adjustment if a search is detected to fall into a stagnation state every time through set iteration, reducing a weight factor of the importance of the pheromone, and improving the weight factor of the importance of heuristic information; And stopping the operation of the algorithm when the iteration times reach the preset value, and counting the results of the multi-round operation to obtain the average optimal distance of the multi-round operation and the minimum distance in the multi-round operation, thereby obtaining the optimal planning path.
2. The improved adaptive ant colony algorithm path planning method according to claim 1, wherein when each ant starts from a randomly selected initial place and gradually builds a complete path through an improved state transition probability rule, the improved adaptive ant colony algorithm base parameters include ant colony scale, maximum iteration number and pheromone constant, the dynamic parameters include initializing pheromone heuristic factor alpha and expected heuristic factor beta, and setting a dynamic adjustment range of the pheromone volatilizing coefficient ρ, and the parameter is adaptive to the adjustment interval.
3. The improved adaptive ant colony algorithm based path planning method of claim 1, wherein when an ant is located at a current location i, the probability of selecting a next location j is determined by: Wherein, the Representing the concentration of pheromones from location i to location j, α being a weight factor for the importance of the pheromones; Heuristic information, generally inversely proportional to the distance between two places, β is a weight factor of importance of the heuristic information, and allowed represents a set of places that ant k can select next, ensuring that the ant will not repeatedly access places that have been accessed.
4. The improved adaptive ant colony algorithm path planning method according to claim 1, wherein as the number of iterations increases, the dynamic adjustment of the volatility coefficient ρ of the pheromone increases is as follows: Wherein, the The dynamic adjustment range of ρ is [0.05,0.3], and ρ is linearly increased to 0.3.
5. The improved adaptive ant colony algorithm path planning method of claim 1, wherein the search continues to be stopped by decreasing α to 0.95 times of the search, increasing β to 1.05 times of the search, and by restoring α to 1.05 times of the search, and by restoring β to 0.95 times of the search.
6. The improved adaptive ant colony algorithm path planning method of claim 1 wherein at the end of each generation of evolution, the current optimal solution is stored in the elite ant set along with the corresponding ants themselves, and then symmetric updates are made as the group of elite ants is given larger pheromone increments, while updating the pheromones of i to j and j to i and keeping the matrix symmetric, as follows: Optimal path Wherein Q is a pheromone constant, For a globally optimal path to be used, To enhance strength.
7. The improved adaptive ant colony algorithm path planning method of claim 1 wherein, when increasing elite ant pheromone increment, the pheromone update rule is as follows: wherein ρ represents the volatilization coefficient of the pheromone, namely the volatilization rate of the pheromone is simulated by using a chemical reaction constant method, describing the natural volatilization state of the pheromone along with time, The incremental amount of pheromone remained on the path of the ant from the place i to the place j in the iteration is obtained.
8. An improved self-adaptive ant colony algorithm path planning system is characterized by comprising an initialization module, an iterative optimization module and a termination module, The initialization module is used for loading traveling business problem instance data of a plurality of places based on improved self-adaptive ant colony algorithm basic parameters and dynamic parameters, constructing distance matrixes among places based on Euclidean distances, and initializing symmetrical pheromone matrixes; The iteration optimization module is used for gradually constructing a complete path by each ant from a randomly selected initial place through an improved state transition probability rule, calculating the path length of each ant, recording the current iteration optimal path and the length thereof, carrying out evaluation by dynamically adjusting a volatilization coefficient optimization algorithm in the iteration process, carrying out parameter adjustment if a search falling into a stagnation state is detected through each set iteration, reducing a weight factor of the importance of the pheromone, and improving the weight factor of the importance of heuristic information; and the termination module is used for stopping the operation of the algorithm when the iteration times reach the preset value, and counting the results of the multi-round operation to obtain the average optimal distance of the multi-round operation and the minimum distance in the multi-round operation, thus obtaining the optimal planning path.
9. A computer device comprising a processor and a memory, the memory being configured to store a computer executable program, the processor reading part or all of the computer executable program from the memory and executing the computer executable program, the processor executing part or all of the computer executable program to implement the improved adaptive ant colony algorithm-based path planning method according to any of claims 1-7.
10. A computer readable storage medium, characterized in that a computer program is stored in the computer readable storage medium, which computer program, when being executed by a processor, enables the improved adaptive ant colony algorithm based path planning method according to any of claims 1-7.

Description

Improved self-adaptive ant colony algorithm path planning method and system Technical Field The invention belongs to the technical field of intelligent optimization and path planning, and particularly relates to an improved self-adaptive ant colony algorithm-based path planning method and system. Background The path planning has extremely wide application in the fields of mobile robotics, unmanned, logistics distribution, unmanned aerial vehicle track planning and the like. Typical path planning problems can generally be abstracted into a variant of a traveler Problem (TSP, travelling Salesman Problem), but the Problem is an NP-hard Problem in combinatorial optimization, and as the Problem size increases, the solution space grows in steps, and it is difficult to find an answer for a traditional accurate algorithm. In order to solve the above problems, the ant colony algorithm can be used to find the shortest path meeting the actual requirements. The ant colony algorithm (Ant Colony Optimization, ACO) is a population intelligence-based algorithm developed from the hint of natural ant foraging behavior. The basic principle is that ants release certain pheromones (chemical substances) during the process of finding food, and the self travel route is marked by the pheromones. After multiple calculation solutions, the shortest path is finally obtained. Although the universality is strong in theory, the traditional ant colony algorithm has some defects, and the effect is poor in path planning. The ant colony algorithm has pheromone positive feedback, which can cause the algorithm to easily sink into a local optimal solution and cannot find a global optimal path. Meanwhile, the performance of the ant colony algorithm is affected by a plurality of parameters such as alpha, beta, rho and the like, and the parameters are manually set and lack of certain autonomy, so that the ant searching efficiency and the result quality directly depend on the value condition of each parameter when the ant colony algorithm runs. These defects restrict the ant colony algorithm to be applied to the complex path planning problem, and the algorithm performance and application range must be improved by improving the algorithm. In the prior art, patent with publication number CN120198035A provides an intelligent unmanned aerial vehicle food material distribution method, which comprises the steps of obtaining to-be-distributed order information and unmanned aerial vehicle parameter information, determining a target distribution strategy according to the to-be-distributed order information and the unmanned aerial vehicle parameter information, carrying out food material distribution according to the target distribution strategy, obtaining a real-time environment information image of the unmanned aerial vehicle in real time in a distribution process, comparing the real-time environment information image with an initial environment information image to obtain incremental image information, and adjusting the target distribution strategy or controlling the unmanned aerial vehicle to carry out intelligent obstacle avoidance according to the incremental image information. According to the method, the global distribution path planning and the local intelligent obstacle avoidance are combined, manual frequent intervention and adjustment are not needed, the autonomy and the efficiency of unmanned aerial vehicle distribution are improved, real-time coping with environmental changes is emphasized, the path can be dynamically adjusted according to actual conditions, the patent with the publication number of CN120252762A provides a three-dimensional path planning method of a mobile robot based on a self-adaptive ant colony algorithm, three-dimensional search space of the mobile robot is rasterized, each grid represents a three-dimensional position point and a neighborhood thereof, the existing ant colony algorithm is improved, attenuation factors which are inversely related to iterative search times are introduced, heuristic information among nodes is adjusted by utilizing the attenuation factors, so that the heuristic information has a larger initial effect on the ant colony algorithm, the ant is guided to search towards a target node at the initial stage, the search efficiency of the iterative search is improved, the attenuation factors are gradually reduced along with the increase of the iterative search times, the effect of the heuristic information on the later stage of the ant colony algorithm is reduced, the guiding effect of the inter-path pheromone concentration on the path search is increased, and the method is more suitable for solving the problem of complex path searching in the three-dimensional space and better solving the problem of the variation of the steering and the change of the height. Disclosure of Invention In order to solve the problems in the prior art, the invention provides an improved self-adaptive ant colony algorithm path pl