Using 2-Opt based evolution strategy for travelling salesman problem

Kenan Karagul, Erdal Aydemir, Sezai Tokat

Abstract


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.


Keywords


Travelling salesman problems; TSP; harmony search; HS; (µ+1) evolution strategy; 2-Opt; TSPLIB.

Full Text:

PDF

References


Laporte G, The Traveling Salesman Problem: An overview of exact and approximate algorithms, European Journal of Operational Research, Vol. 59, pp. 231-247, (1992).

Croes GA, A Method for Solving Travelling-Salesman Problems. Operations Research, Vol. 6, No. 6, pp. 791-812, (1958).

Holland JH, Adaptation in Natural and Artificial Systems. MIT Press, Cambridge, Mass., USA, (1975).

Kirkpatrick S, Gelatt JrCD, Vecchi MP, Optimization by simulated annealing. Science, Vol. 220, No. 4598, pp. 671–680, (1983).

Geem ZW, Kim JH, Loganathan GV, A new heuristic optimization algorithm: harmony search. Simulation, Vol. 76, No. 2, pp. 60–68, (2001).

Yang XS, Harmony Search as a Metaheuristic Algorithm. in Music-Inspired Harmony Search Algorithm. 2009, Springer Berlin / Heidelberg. pp. 1-14, (2009).

Sureja N, New Inspirations in Nature: A Survey. International Journal of Computer Applications & Information Technology, pp.21-24, (2012).

Abdel-Raouf O, Metwally MAB, A Survey of Harmony Search Algorithm. International Journal of Computer Applications, pp.17-26, (2013).

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).

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).

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).

Fiechter CN, A parallel tabu search algorithm for large traveling salesman problems. Discrete Applied Mathematics, Vol. 51, No. 3, pp. 243–267, (1994).

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).

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).

Chu SC, Roddick JF, Pan JS, Ant colony system with communication strategies. Information Sciences, Vol. 167, No. 1–4, pp. 63–76, (2004).

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).

Yang XS, Nature-Inspired Metaheuristic Algorithms. Luniver Press, (2010).

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).

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).

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).

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).

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).

Kumbharana SN, Pandey GM, Solving Travelling Salesman Problem using Firefly Algorithm. International Journal for Research in Science & Advanced Technologies, pp. 53-57, (2013a).

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).

Wang L, Xu Y, Mao Y, Fei M, A Discrete Harmony Search Algorithm. Communications in Computer and Information Science, pp. 37-43, (2010).

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).

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).

Jian H, Qi-yuan P, Diversity Maintaining Harmony Search and Its TSP Solution. Application Research of Computer, pp. 3583-3586, (2013).

Weyland, D, A critical analysis of the harmony search algorithm—How not to solve Sudoku. Operations Research Perspectives, Vol. 2, pp. 97–105, (2015).

Rechenberg I., Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog Verlag, Stuttgart, (1973).

Geem ZW, Novel derivative of harmony search algorithm for discrete design variables. Applied Mathematics and Computations, Vol.199, pp. 223-230, (2008).

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).

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).

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).

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).

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).

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).

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).

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).

Reinelt, G, TSPLIB95. Retrieved Oct., 2013 from https://www.iwr.uni-heidelberg.de/groups/comopt/software. (2013).

Kay, M, Matlog: Logistics Engineering Matlab Toolbox. Retrieved Apr., 2014 from. www.ise.ncsu.edu/kay/matlog/ (2014).




DOI: http://dx.doi.org/10.11121/ijocta.01.2016.00268

Refbacks

  • There are currently no refbacks.


Copyright (c) 2016 Kenan Karagul, Erdal Aydemir, Sezai Tokat

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

footer_771

   ithe_170     crossref_284         ind_131_43_x_117_117  Scopus  EBSCO_Host    ULAKBIM    PROQUEST   ZBMATH more...