Application And Research Of Optimal Path Algorithm In Repair Problem Of Military Communication Lines

The maintenance of military communication lines is one of the most basic parts in the management of military communication network. With the development of military communication technology and the improvement of construction level, advanced requirements have been put forward to the communication department. The optimal repair path problem of communication lines is becoming research focus. The essence of the problem is the optimal routing problem of road network,which is a combinatorial optimization problem.It has a long history of the research of the optimal routing problem,and it is found that some classical algorithms, such as Dijkstra algorithm, are good at solving these Problems. With the uncertainty and complexity of optimizing targets, traditional algorithms have encountered great difficulties. However, many heuristic intelligent optimization algorithms are proposed to solve several of complex problems. As a bionic optimization method, ant colony algorithm has some advantages in distributed computing, self-organization and positive feedback, and it has been applied in various applications. While, there are still some shortcomings, such as partial optimal solution and slow convergence.First of all, the paper introduced the expression way and storage structure of road data. Then some typical algorithms of optimal path are discussed, which contains Dijkstra algorithm, Floyd algorithm and A-star algorithm. It is introduced in the aspect of basic idea, idiographic steps and algorithm analyses. Furthermore, the characteristics and weakness of them are analyzed.Secondly,ant colony algorithm is proposed based on the theory above. It is introduced in detail of the basic principles, mathematics model and implementation steps as well as various capability indicators of ant colony algorithm. Then analyzed the feasibility on solve the optimal routing problem by using ant colony algorithm.Finally, the research introduced four popular ant colony algorithms with improved rules. By simulation experiments of TSP problem, an improved algorithm is compared with basic algorithm on efficiency and solution quality. A new improved rule is proposed to solve the optimal repair path problem of military communication lines. The main idea of the rule is to adjust the pheromone distribution of the area determined by the start node and the destination node, so as to induce the blindness of ants'movement. It is also designed to limit the scope of the pheromone after each loop, in order to avoid falling into partial optimal solution. Then the parameters of ant colony algorithm are determined by experiments, and the improved algorithm is also compared with basic algorithm,elitist ant system. The result of experiment shows that the improved method can take advantage of global search and accurately find the optimization solution in a relatively short period, which has the great meaning for practical application.