Research On Parallel Minimum Steiner Tree Algorithm Based On Ant Colony Algorithm

The minimal steiner tree problem is a classical NP-hard problem in graph theory,and it is one of the basic problems in many fields.For example,the multicast routing problem has been constructed as the least-cost multicast tree problem in many studies,namely,the minimum steiner tree problem;the very large scale integration wiring problem is essentially the minimum steiner tree problem and so on.Therefore,the study of the minimum steiner tree problem is particularly important.For the NP-hard problem,the complexity required to solve the problem increases exponentially with the scale of the problem.People cannot guarantee the exact solution of the problem in polynomial time,and the approximation algorithm is a feasible way to obtain a near-optimal solution at a relatively low computational cost.Ant colony algorithm is a bionics optimization algorithm,which has strong robustness and implicit parallel search capability.Domestic and foreign scholars have done some research on the application of ant colony algorithm to the minimum steiner tree problem.However,the traditional serial ant colony algorithm can't adapt to the steiner tree problem of increasing scale.Therefore,under the condition that the basic principle of ant colony algorithm has been clarified,the use of parallel platforms and algorithms to solve the steiner tree problem is a potential research direction.This paper presents an ant colony optimization algorithm to solve the minimum steiner tree,and uses local search to optimize the solution.Then,by analyzing the characteristics of the algorithm,the Gunrock graph processing library is used to parallelize the algorithm.The related parameters of the ant colony algorithm have a very important influence on the performance of the algorithm.Therefore,in the testing of the algorithm,this paper first analyzes the influence of the parameters on the algorithm results through coarse and fine tuning of the parameters,and gives the optimal parameters combination.Under the optimal parameter combination,the average error rate of the average solution for all test cases in Stein Lib is 1.09%,and the average error rate of the optimal solution is 0.43%.For all test results,the error rate for most of the results was below 2%,and the error rate for all test cases was within 3.5%.Compared with other ant colony algorithms,the quality of the proposed algorithm is superior to other ant colony algorithms,and the parallel speed of the algorithm is faster an order of magnitude than the corresponding serial algorithm when the approximate ratio is guaranteed.Compared with the KMB algorithm,the quality of the parallel algorithm proposed in this paper is 8% betterthan the KMB algorithm,and runs about two times faster than the KMB algorithm on average.