A modified elite ACO based avoiding premature convergence for travelling salesmen problem

Subject Areas : Mathematical Optimization

M Yousefikhoshbakht ¹ , E Mahmoodabadi ² , M Sedighpour ³

1 - M.Sc., Young Researchers Club, Hamedan Branch, Islamic Azad University, Hamedan, Iran
2 - M.Sc., Dept. of Mathematics, Faculty of Science, Bu-Ali Sina University, Hamedan,
3 - M.Sc., Hamedan Branch, Islamic Azad University, Hamedan, Iran

Received: 2015-05-17 Accepted : 2015-05-17 Published : 2011-11-01

Keywords: Ant colony optimization, Traveling salesman problem, NP-hard Problems, Meta-Heuristic Algorithms,

Abstract :

The Travelling Salesmen Problem (TSP) is one of the most important and famous combinational optimization problems that aim to find the shortest tour. In this problem, the salesman starts to move from an arbitrary place called depot and after visiting all nodes, finally comes back to depot. Solving this problem seems hard because program statement is simple and leads this problem belonging to NP-hard programs.In this paper, the researchers present a modified Elite Ant System (EAS) which is different from common EAS. There is a linear function used here for increasing coefficient pheromone of the best route activated when a better solution is achieved. This process will avoid the premature convergence and makes better solutions. The results on several standard instances show that this new algorithm would gain more efficient solutions compared to other algorithms.