Using 2-Opt based evolution strategy for travelling salesman problem

KENAN KARAGÜL, (Pamukkale University)
Erdal AYDEMİR, (Pamukkale University)
Sezai TOKAT (Suleyman Demirel University)
An International Journal of Optimization and Control: Theories & Applications (IJOCTA)
4 1
Yıl: 2016 Cilt: 6 Sayı: 2 Sayfa Aralığı: 2103 - 2113 Metin Dili: İngilizce İndeks Tarihi: 29-07-2022

Using 2-Opt based evolution strategy for travelling salesman problem

Öz:
Harmony search algorithm that matches the (µ+1) evolution strategy, is a heuristic method simulated by the process of music improvisation. In this paper, a harmony search algorithm is directly used for the travelling salesman problem. Instead of conventional selection operators such as roulette wheel, the transformation of real number values of harmony search algorithm to order index of vertex representation and improvement of solutions are obtained by using the 2-Opt local search algorithm. Then, the obtained algorithm is tested on two different parameter groups of TSPLIB. The proposed method is compared with classical 2-Opt which randomly started at each step and best known solutions of test instances from TSPLIB. It is seen that the proposed algorithm offers valuable solutions.
Anahtar Kelime:

Konular: Matematik İstatistik ve Olasılık
Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık
  • [1] Laporte G, The Traveling Salesman Problem: An overview of exact and approximate algorithms, European Journal of Operational Research, Vol. 59, pp. 231-247, (1992).
  • [2] Croes GA, A Method for Solving TravellingSalesman Problems. Operations Research, Vol. 6, No. 6, pp. 791-812, (1958).
  • [3] Holland JH, Adaptation in Natural and Artificial Systems. MIT Press, Cambridge, Mass., USA, (1975).
  • [4] Kirkpatrick S, Gelatt JrCD, Vecchi MP, Optimization by simulated annealing. Science, Vol. 220, No. 4598, pp. 671-680, (1983).
  • [5] Geem ZW, Kim JH, Loganathan GV, A new heuristic optimization algorithm: harmony search. Simulation, Vol. 76, No. 2, pp. 60-68, (2001).
  • [6] Yang XS, Harmony Search as a Metaheuristic Algorithm. in Music-Inspired Harmony Search Algorithm. 2009, Springer Berlin / Heidelberg. pp. 1-14, (2009).
  • [7] Sureja N, New Inspirations in Nature: A Survey. International Journal of Computer Applications & Information Technology, pp.21-24, (2012).
  • [8] Abdel-Raouf O, Metwally MAB, A Survey of Harmony Search Algorithm. International Journal of Computer Applications, pp.17-26, (2013)
  • [9] Freisleben B, Merz P, Genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems. in Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC '96), pp. 616-621, (1996).
  • [10] Chowdhury A, Ghosh A, Sinha S, Das S, Ghosh A, A novel genetic algorithm to solve travelling salesman problem and blocking flow shop scheduling problem. International Journal of Bio-Inspired Computation, Vol. 5, No. 5, pp. 303-314, (2013).
  • [11] Wang Y, Tian D, An improved simulated annealing algorithm for traveling salesman problem. in Proceedings of the International Conference on Information Technology and Software Engineering, Vol. 211 of Lecture Notes In Electrical Engineering, pp. 525-532, (2013).
  • [12] Fiechter CN, A parallel tabu search algorithm for large traveling salesman problems. Discrete Applied Mathematics, Vol. 51, No. 3, pp. 243- 267, (1994).
  • [13] Stüzle T, Hoos H, MAX-MIN Ant system and local search for the traveling salesman problem. Reference Future Generations Computer Systems, Vol. 16, No. 8, pp. 889-914, (1997).
  • [14] Randall M, Montgomery J, The accumulated experience Ant colony for the traveling salesman problem. International Journal of Computational Intelligence and Applications, Vol.3, No.2, pp. 189-198, (2003).
  • [15] Chu SC, Roddick JF, Pan JS, Ant colony system with communication strategies. Information Sciences, Vol. 167, No. 1-4, pp. 63-76, (2004).
  • [16] Wang KP, Huang L, Zhou CG, Pang W, Particle swarm optimization for traveling salesman problem. in Proceedings of the International Conference on Machine Learning and Cybernetics, pp. 1583-1585, (2003).
  • [17] Yang XS, Nature-Inspired Metaheuristic Algorithms. Luniver Press, (2010).
  • [18] Yang XS, Deb S, Engineering optimisation by cuckoo search. International Journal of Mathematical Modelling and Numerical Optimisation, Vol. 1, No. 4, pp. 330-343, (2010).
  • [19] Ouyang X, Zhou Y, Luo Q, Chen H, A novel discrete cuckoo search algorithm for spherical traveling salesman problem. Applied Mathematics & Information Sciences, Vol. 7, No. 2, pp. 777-784, (2013).
  • [20] Ouaarab A, Ahiod B, Yang, XS, Discrete Cuckoo Search Algorithm for the Travelling Salesman Problem. Neural Computing and Applications, Vol.24, No.7-8, pp 1659-1669, (2014a).
  • [21] Ouaarab A, Ahiod B, Yang XS, "Improved and Discrete Cuckoo Search for Solving the Travelling Salesman Problem", X.-S. Yang In Cuckoo Search and Firefly Algorithm: Theory and Applications, Vol. 516, pp. 63-84, Switzerland: Springer(2014b).
  • [22] Jati GK, Suyanto S, Evolutionary Discrete Firefly Algorithms for Travelling Salesman Problem. Proceedings of the 2nd International Conference on Adaptive and Intelligent Systems, pp. 393-403, Klagenfurt, Austria: Springer, (2011).
  • [23] Kumbharana SN, Pandey GM, Solving Travelling Salesman Problem using Firefly Algorithm. International Journal for Research in Science & Advanced Technologies, pp. 53- 57, (2013a).
  • [24] Ismail MM, Che H, Mohd H, Mohamad SH, Jaafar HI, A Preliminary Study on Firefly Algorithm Approach for Travelling Salesman Problem. In: Science & Engineering Technology National Conference 2013, 3-4 July 2013, Kuala Lumpur, Malaysia, (2013).
  • [25] Wang L, Xu Y, Mao Y, Fei M, A Discrete Harmony Search Algorithm. Communications in Computer and Information Science, pp. 37- 43, (2010).
  • [26] Pan QK, Wang L, Gao L, A chaotic harmony search algorithm for the flow shop scheduling problem with limited buffers. Applied Soft Computing, Vol.11(8), pp. 5270- 5280, (2011).
  • [27] Yuan Y, Xu H, Yang J, A hybrid harmony search algorithm for the flexible job shop scheduling problem. Applied Soft Computing, Vol.13(7), pp. 3259-3272, (2013).
  • [28] Jian H, Qi-yuan P, Diversity Maintaining Harmony Search and Its TSP Solution. Application Research of Computer, pp. 3583- 3586, (2013).
  • [29] Weyland, D, A critical analysis of the harmony search algorithm--How not to solve Sudoku. Operations Research Perspectives, Vol. 2, pp. 97-105, (2015).
  • [30] Rechenberg I., Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog Verlag, Stuttgart, (1973).
  • [31] Geem ZW, Novel derivative of harmony search algorithm for discrete design variables. Applied Mathematics and Computations, Vol.199, pp. 223-230, (2008).
  • [32] Pang W, Wang KP, Zhou CG, Dong LJ, Fuzzy discrete particle swarm optimization for solving traveling salesman problem. in Proceedings of the 4th International Conference on Computer and Information Technology (CIT '04), pp. 796-800, (2004).
  • [33] Thamilselvan R, Balasubramanie P, A genetic algorithm with a Tabu search (GTA) for traveling salesman problem. International Journal of Recent Trends in Engineering, Vol. 1, No. 1, pp. 607-610, (2009).
  • [34] Kaveh A, Talatahari S, Particle swarm optimizer, ant colony strategy and harmony search scheme hybridized for optimization of truss structures. Computers and Structures, Vol. 87, No. 5-6, pp. 267-283, (2009).
  • [35] Yan Y, Zhao X, Xu J, Xiao, Z, A mixed heuristic algorithm for traveling salesman problem. in Proceedings of the 3rd International Conference on Multimedia Information Networking and Security (MINES '11), pp. 229-232, (2011).
  • [36] Chen SM, Chien CY, Parallelized genetic ant colony systems for solving the traveling salesman problem. Expert Systems with Applications, Vol. 38, No. 4, pp. 3873-3883, (2011a).
  • [37] Chen SM, Chien CY., Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques. Expert Systems with Applications, Vol. 38, No. 12, pp. 14439-14450, (2011b).
  • [38] Yun HY, Jeong SJ, Kim KS, Advanced Harmony Search with Ant Colony Optimization for Solving the Traveling Salesman Problem. Journal of Applied Mathematics, pp. 1-8, (2013).
  • [39] Kumbharana SN, Pandey GM, A comparative study of ACO, GA and SA for solving traveling salesman problem. International Journal of Societal Applications of Computer Science, Vol. 2, No. 2, pp. 224-228, (2013b).
  • [40] Reinelt, G, TSPLIB95. Retrieved Oct., 2013 from https://www.iwr.uniheidelberg.de/groups/comopt/software. (2013).
  • [41] Kay, M, Matlog: Logistics Engineering Matlab Toolbox. Retrieved Apr., 2014 from. www.ise.ncsu.edu/kay/matlog/ (2014).
APA Karagul K, Aydemir E, TOKAT S (2016). Using 2-Opt based evolution strategy for travelling salesman problem. , 2103 - 2113.
Chicago Karagul Kenan,Aydemir Erdal,TOKAT Sezai Using 2-Opt based evolution strategy for travelling salesman problem. (2016): 2103 - 2113.
MLA Karagul Kenan,Aydemir Erdal,TOKAT Sezai Using 2-Opt based evolution strategy for travelling salesman problem. , 2016, ss.2103 - 2113.
AMA Karagul K,Aydemir E,TOKAT S Using 2-Opt based evolution strategy for travelling salesman problem. . 2016; 2103 - 2113.
Vancouver Karagul K,Aydemir E,TOKAT S Using 2-Opt based evolution strategy for travelling salesman problem. . 2016; 2103 - 2113.
IEEE Karagul K,Aydemir E,TOKAT S "Using 2-Opt based evolution strategy for travelling salesman problem." , ss.2103 - 2113, 2016.
ISNAD Karagul, Kenan vd. "Using 2-Opt based evolution strategy for travelling salesman problem". (2016), 2103-2113.
APA Karagul K, Aydemir E, TOKAT S (2016). Using 2-Opt based evolution strategy for travelling salesman problem. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 6(2), 2103 - 2113.
Chicago Karagul Kenan,Aydemir Erdal,TOKAT Sezai Using 2-Opt based evolution strategy for travelling salesman problem. An International Journal of Optimization and Control: Theories & Applications (IJOCTA) 6, no.2 (2016): 2103 - 2113.
MLA Karagul Kenan,Aydemir Erdal,TOKAT Sezai Using 2-Opt based evolution strategy for travelling salesman problem. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), vol.6, no.2, 2016, ss.2103 - 2113.
AMA Karagul K,Aydemir E,TOKAT S Using 2-Opt based evolution strategy for travelling salesman problem. An International Journal of Optimization and Control: Theories & Applications (IJOCTA). 2016; 6(2): 2103 - 2113.
Vancouver Karagul K,Aydemir E,TOKAT S Using 2-Opt based evolution strategy for travelling salesman problem. An International Journal of Optimization and Control: Theories & Applications (IJOCTA). 2016; 6(2): 2103 - 2113.
IEEE Karagul K,Aydemir E,TOKAT S "Using 2-Opt based evolution strategy for travelling salesman problem." An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 6, ss.2103 - 2113, 2016.
ISNAD Karagul, Kenan vd. "Using 2-Opt based evolution strategy for travelling salesman problem". An International Journal of Optimization and Control: Theories & Applications (IJOCTA) 6/2 (2016), 2103-2113.
Sayfa Oluşturulma Tarihi
04-05-2024 10:38

İLETİŞİM

TÜBİTAK ULAKBİM TR Dizin

Yüzüncüyıl, İşçi Blokları Mahallesi

Muhsin Yazıcıoğlu Caddesi No:51/C

06530 Çankaya / ANKARA +90 (312) 298 92 00

trdizin@tubitak.gov.tr

TÜBİTAK ULAKBİM Ulusal Akademik Ağ ve Bilgi Merkezi Cahit Arf Bilgi Merkezi © Tüm Hakları Saklıdır. Gizlilik Politikası Kullanım Şartları