Modified particle swarm optimization for solving traveling salesman problem based on a Hadoop MapReduce framework

摘要

Parallel algorithms, such as the particle swarm algorithm (PSO), take a long time when solving large-scale problems. In this letter, an improved particle swarm optimization algorithm based on the MapReduce distributed computation framework is proposed to solve Traveling Salesman Problem (TSP). However, MapReduce is not suitable for iterative programs because the performance may be lowered by frequent disk I/O operations. We combine swarm grouping mechanism with crossover operation of genetic algorithm, named enhanced modified hybrid PSO (EMHPSO), based on our proposed Hadoop MapReduce to execute the path building in a distributed computer cluster. The algorithm divides the swarm into many groups, and each group flies toward its own global best particle which can share the information simultaneously in order to correct their path. To improve the precision of the solution, a modified local optimization strategy 2-opt is also adapted in EMHPSO. The experimental results show that Hadoop has a very great accelerating effect on the grouping PSO when the city scale of TSP or the number of ants is relatively large.