An Approximate Algorithm for the Steiner Tree Problem based on Ant Colony Algorithm

Abstract

Ant colony optimization (ACO) is a well-known heuristic intelligent method which is used to solve combinatorial optimization problem and can obtain high-quality results in a reasonable execution time. Steiner Tree Problem (STP) is a classic NPcomplete problem. The computational complexity of the exact algorithm increases exponentially with the increment of the size of the problem. In this paper, we propose an ant colony optimization algorithm with data parallelism to solve the STP. The simulation results show that the algorithm has good performance in result quality.