WCSE

An Improved Ant Colony Algorithm Based on Spark in TSP

Abstract— Traditional ant colony algorithm is easy to fall into local optimum and has slow convergence rate, Moreover, its speed of solving is not satisfactory in above medium scale traveling salesman problem. In order to improve the above problem, a parallel ant colony algorithm based on the coarse granularity of Spark is proposed in this paper. Based on the maximum and minimum ant colony system, this method is implemented in parallel with the Spark framework. At the same time, the following improvements have been made: By using the local search technology with three acceleration functions, the ability of the algorithm to jump out of the local optimal solution is greatly enhanced. Meanwhile, the termination condition of the traditional ant colony algorithm is modified, and the information entropy is used as the criterion of the algorithm convergence judgment, reducing the number of iterations and saving time. The experimental results show that the new parallel ant colony algorithm has a greater improvement than the traditional ant colony algorithm in the solving precision and solving speed.

Index Terms— ant colony algorithm, local search, accelerate, Spark, etc.

Qifan Wu
College of computer science and technology; Chongqing Key Laboratory of Software Theory & Technology; Chongqing University, CHINA
Qingsheng Zhu
Chongqing Key Laboratory of Software Theory & Technology; Chongqing University, CHINA

[Download]

Cite: Qifan Wu, Qingsheng Zhu, "An Improved Ant Colony Algorithm Based on Spark in TSP," Proceedings of 2018 the 8th International Workshop on Computer Science and Engineering, pp. 115-120, Bangkok, 28-30 June, 2018.