Optimization of traveling salesman problem using affinity propagation clustering and genetic algorithm

• Autorzy: El-Samak A. F. , Ashour W.

Identyfikatory

DOI

10.1515/jaiscr-2015-0032

• Języki publikacji: EN

Abstrakty

EN

Combinatorial optimization problems, such as travel salesman problem, are usually NPhard 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.

Słowa kluczowe

EN

combinatorial optimization problem; travel salesman problem; genetic algorithm; evolutionary computation algorithm; affinity propagation clustering technique; AP

PL

problem optymalizacji kombinatorycznej; algorytm genetyczny; obliczenia ewolucyjne; AP

• Wydawca: University of Social Sciences
• Czasopismo: Journal of Artificial Intelligence and Soft Computing Research
• Rocznik: 2015
• Tom: Vol. 5, No. 4
• Strony: 239--245
• Opis fizyczny: Bibliogr. 18 poz., rys.

Twórcy

autor

El-Samak A. F.

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

autor

Ashour W.

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

Bibliografia

• [1] Liao Y.-F., Yau D.-H., Chen C.-L., Evolutionary algorithm to traveling salesman problems, Computers & Mathematics with Applications, Vol. 64, Issue 5, pages 788–797, 2012.
• [2] Leung, K.S., Jin H.D., & Xu, Z.B., An expanding self-organizing neural network for the traveling salesman problem, Neurocomputing, 62, 267–292.Masutti, T.A.S., & de Castro, L.N. (2004).
• [3] Masutti, T.A.S., & de Castro, L.N., A selforganizing neural network using ideas from the immune system to solve the traveling salesman problem, Information Sciences, Vol. 179, Issue 10, pages 1454–1468, April 2009.
• [4] Lo, C.C., & Hsu, C.C., Annealing framework with learning memory, IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, Vol. 28, Issue 5, pages 648-661, 1998.
• [5] Jayalakshmi, G.A., & Sathiamoorthy, A hybrid genetic algorithm – A new approach to solve traveling salesman problem, International Journal of Computational Engineering Science, Vol. 2, Issue 2, pages 339–355, 2001.
• [6] Tsai, H.K., Yang, J.M., Tsai, Y.F., & Kao, C.Y., Heterogeneous election genetic algorithms for traveling salesman problems, Engineering Optimization, Vol. 35, Issue 3, pages 297–311, 2003.
• [7] Dorigo, M., & Gambardella, L.M., Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, Vol. 1, Issue 1, pages 53-66, 1997.
• [8] Liu, J.L., Rank-based ant colony optimization applied to dynamic traveling salesman problems, Engineering Optimization, Vol. 37, Issue 8, pages 831–847, 2005.
• [9] Puris, A., Bello, R., & Herrera, Analysis of the efficacy of a two-stage methodology for ant colony optimization: Case of study with TSP and QAP, Expert Systems with Applications, Vol. 37, Issue 7, pages 5443–5453, 2010.
• [10] Laporte, G., & Palekar U, Some applications of the clustered travelling salesman problem, The Journal of the Operational Research Society, Vol. 53, Issue 9, pages 972–976, 2002.
• [11] Anily, S., Bramel, J., & Hertz, A., A 5/3-approximation algorithm for the clustered traveling salesman tour and path problems, Operations Research Letters, Vol. 24, Issue1, pages 29-35, 1999.
• [12] Ding Chao, Cheng Ye, He Miao, Two-Level Genetic Algorithm for Clustered Traveling Salesman Problem with Application in Large-Scale TSPs, Tsinghua Science & Technology, Vol. 12, Issue 4, Pages 459–465, August 2007.
• [13] Tanasanee Phienthrakul, Clustering Evolutionary Computation for Solving Travelling Salesman Problems, International Journal of Advanced Computer Science and Information Technology (IJACSIT), Vol. 3, Issue 3, Page: 243-262, 2014.
• [14] B. J. Frey and D. Dueck. Response to Comment on Clustering by Passing Messages Between Data Points. Science, Vol. 319, Issue 5864, pages 726, 8 February 2008.
• [15] Goldberg, D. E. 1989a, Genetic Algorithms in Search, Optimization, and Machine Learning,Reading, MA: Addison-Wesley.
• [16] B. Hassanabadi, C.Shea, L.Zhang, S.Valaee, Clustering in Vehicular Ad Hoc Networks using Affinity Propagation, Original Research Article Ad Hoc Networks, Vol. 13, Part B, Feb. 2014, Pages 535–548.
• [17] F. Torrent-Fontbona, V. Muoz, B. Lpez Solving large immobile location–allocation by affinity propagation and simulated annealing, Expert Systems with Applications, Vol. 40, Issue 11, 1 Sep. 2013, Pages 4593-4599.
• [18] http://www2.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB9 5/tsp/