OPTIMIZATION OF TRAVELING SALESMAN PROBLEM USING AFFINITY PROPAGATION CLUSTERING AND GENETIC ALGORITHM
OPTIMIZATION OF TRAVELING SALESMAN PROBLEM USING AFFINITY PROPAGATION CLUSTERING AND GENETIC ALGORITHM
复制标题
DOI：
10.1515/jaiscr-2015-0032
复制
发表时间：
2015-10-01
影响因子：
2.8
通讯作者：
Ashour, Wesam
中科院分区：
文献类型：
--
作者：
El-Samak, Ahmad Fouad;Ashour, Wesam
组合优化问题，例如旅行商问题，通常是NP难的，并且该问题的解空间非常大。因此，可行解的集合不能逐一评估。简单遗传算法是目前最常用的进化计算算法之一，它能很好地解决TSP问题，但计算时间较长。本文采用仿射传播聚类技术（AP）优化遗传算法（GA）求解TSP问题的性能。其核心思想是将城市聚类成更小的类，并分别用遗传算法求解每个类，从而在更少的计算时间内获得最优解。数值实验表明，该算法对TSP问题的求解效果优于简单遗传算法。
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.