Design And Implementation Of Parallel Ant Colony Optimization Based On Linux Cluster

Ant Colony Optimization(ACO)，as a new simulated evolution algorithm,has the characteristics as the combination of positive feedback, meta heuristicand distributed computing. Positive feedback helps ACO to find better solutionsfaster, metaheuristic features contribute to ACO easier to find better solutions,and distributed computing is conducive to realize the parallel computing of antcolony in order to find the optimization route.In addition, in recent years, with the development of computer technology,especially the emergence of high-performance computers and high-speednetworks, an inexpensive, high-performance parallel computer clusterenvironment gradually becomes a research topic in the field of parallelcomputing. This type of computers can provide users with low-cost, highefficient performance computing environment and fast, flexible and reliablecomputing services. In view of the distributed features of the ACO, this paperdesigns and realizes the parallelization of ant colony algorithm based on theLinux cluster environment, and the algorithm is applied to the traveling salesman problem.The main works and research results of this article are as follows:(1) Based on the analysis of the existing ant colony optimization algorithmand the neighborhood search algorithm, the neighborhood search algorithm wasused to optimize the initial solution which generated by the ant colonyoptimization algorithm. This method not only can take the advantage of strongconvergence characteristics of the ant colony optimization algorithm，but alsocan improve the quality of the initial solution by using the neighborhood searchalgorithm, therefore, guiding the optimization searching process of thesubsequent ants.(2) Linux based cluster was confirmed by studying and analyzing theexisting software and hardware environment of cluster. The parallelprogramming environment based on MPICH was established and configured bystudying and analyzing a variety of parallel programming environments.(3) Under the Linux cluster environment, according to the thought that antsis distributed equally on many processors, we design and realizes theparallelization of ant colony optimization algorithm, compare the ant system optimization algorithm and the ant colony system algorithm with thesealgorithms which have optimized by adding neighborhood search algorithm, andanalyze the performance indicators such as acceleration ratio through examples.