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

Journal of Industrial Engineering International

مقاله 8، دوره 7، شماره 15، بهمن 2011، صفحه 68-75   

نویسندگان

M Yousefikhoshbakht¹؛ E Mahmoodabadi²؛ M Sedighpour³

¹M.Sc., Young Researchers Club, Hamedan Branch, Islamic Azad University, Hamedan, Iran

²M.Sc., Dept. of Mathematics, Faculty of Science, Bu-Ali Sina University, Hamedan,

³M.Sc., Hamedan Branch, Islamic Azad University, Hamedan, Iran

چکیده

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.

کلیدواژه‌ها

Ant colony optimization؛ Traveling salesman problem؛ NP-hard Problems؛ Meta-Heuristic Algorithms