<abstract xmlns="http://www.w3.org/1999/xhtml"><p> Combinatorial optimization problems, such as travel salesman problem, are usually NP-hard and the solution space of this problem is very large. Therefore the set of feasible solutions cannot be evaluated one by one. The simple genetic algorithm is one of the most used evolutionary computation algorithms, that give a good solution for TSP, however, it takes much computational time. In this paper, Affinity Propagation Clustering Technique (AP) is used to optimize the performance of the Genetic Algorithm (GA) for solving TSP. The core idea, which is clustering cities into smaller clusters and solving each cluster using GA separately, thus the access to the optimal solution will be in less computational time. Numerical experiments show that the proposed algorithm can give a good results for TSP problem more than the simple GA.</p></abstract>

Combinatorial optimization problems, such as travel salesman problem, are usually NP-hard and the solution space of this problem is very large. Therefore the set of feasible solutions cannot be evaluated one by one. The simple genetic algorithm is one of the most used evolutionary computation algorithms, that give a good solution for TSP, however, it takes much computational time. In this paper, Affinity Propagation Clustering Technique (AP) is used to optimize the performance of the Genetic Algorithm (GA) for solving TSP. The core idea, which is clustering cities into smaller clusters and solving each cluster using GA separately, thus the access to the optimal solution will be in less computational time. Numerical experiments show that the proposed algorithm can give a good results for TSP problem more than the simple GA.

Optimization of Traveling Salesman Problem Using Affinity Propagation Clustering and Genetic Algorithm

Computer Engineering Department, Islamic University of Gaza, Gaza, Palestine

Journal of Artificial Intelligence and Soft Computing Research

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Combinatorial optimization problems, such as travel salesman problem, are usually NP-hard and the solution space of this problem is very large. Therefore the...

Optimization of Traveling Salesman Problem Using Affinity Propagation Clustering and Genetic Algorithm

Publicado en línea: 29 oct 2015

Páginas: 239 - 245

DOI: https://doi.org/10.1515/jaiscr-2015-0032

© 2015

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.