Parallel Performance of an Ant Colony Optimization Algorithm for TSP

MAX-MIN ant colony system (MMAS) has been one of the most effective ant colony optimization algorithm for the traveling salesman problem (TSP) up to the present. Despite the intrinsic parallelism, problems such as excessive memory occupation and overlong communication cost arise in the parallel process for large-scale numerical examples. In this paper, for parallel optimization of MMAS, some strategies are proposed: a) by comparing the current solution with the optimal solution, unnecessary ergodic paths and iterations are abandoned, which accelerates the searching process; b) for generating distance matrix and updating pheromone matrix, communications are replaced by calculations, which reduces memory occupation and communication cost enormously. MMAS with the above strategies is implemented on the Sunway Blue Light supercomputer based on MPI. As a result, high feasibility and effectiveness are verified.