Research On Parallel Performance Analysis And Optimization Based On Ant Colony Algorithm

The Ant Colony Algorithm(ACA)was first successfully used to solve Traveling Salesman Problem(TSP).Because of its strong robustness,ease of integration with other methods and natural parallelism,the ant colony algorithm is widely used to solve job scheduling problems,track planning problems,vehicle routing problems,etc.At the same time,it has achieved certain results in practical fields such as robotics and data mining.The ant colony algorithm needs to update the concentration of pheromone in the path after each iteration cycle.However,after the basic ant colony algorithm finishes the update process,it can easily enter the stagnation state after being trapped in the local optimal solution.Therefore,the global optimal solution cannot be found,and at the same time,the problem of slow convergence speed is also encountered.How to solve the above problems and improve the execution speed and scalability of the ant colony algorithm when the data scale is increasing has become a hot issue in the field.To solve the problem that the above algorithm is easy to fall into the local optimal solution and has a slow convergence rate,based on the existing research,this paper uses the enhanced pheromone update mechanism to process the solution set information matrix to determine whether the algorithm is close to a stagnant state.If the algorithm is close to a stagnant state,a new pheromone smoothing mechanism is used to process the information matrix to reduce or eliminate the algorithm stagnation.An Ant Colony Optimization Improvement(ACOI)algorithm based on a pheromone optimization mechanism is proposed to make the algorithm continue along the global optimum of the solution.The goal of the solution is to perform the search process.The parallel analysis of the improved ACOI algorithm is combined with the commonly used parallelism framework.For the problem that the serial ACOI algorithm has a long execution time on a single machine,the parallelization method of ACOI algorithm based on OpenMP is proposed and the algorithm execution time is shortened.Aiming at the problem of scalability in high-performance clusters when the data size of ACOI algorithm increases,using the characteristics of parallelism between MPI nodes,a parallel method of ACOI algorithm based on MPI is proposed,which effectively solves the problem of scalability.Aiming at the problem of high communication cost and low utilization rate in the pure MPI parallel method on the cluster,based on the OpenMP+MPI hybrid model,the ACOI algorithm parallelization method based on the hybrid programming model is proposed.