In this paper, a recently developed nature-inspired optimization algorithm called the hydrological cycle algorithm (HCA) is evaluated on the traveling salesman problem (TSP). The HCA is based on the continuous movement of water drops in the natural hydrological cycle. The HCA performance is tested on various geometric structures and standard benchmarks instances. The HCA has successfully solved TSPs and obtained the optimal solution for 20 of 24 benchmarked instances, and near-optimal for the rest. The obtained results illustrate the efficiency of using HCA for solving discrete domain optimization problems. The solution quality and number of iterations were compared with those of other metaheuristic algorithms. The comparisons demonstrate the effectiveness of the HCA.
References
[1]
Shah-Hosseini, H. (2007) Problem Solving by Intelligent Water Drops. 2007 IEEE Congress on Evolutionary Computation, 1, 3226-3231.
https://doi.org/10.1109/CEC.2007.4424885
[2]
Eskandar, H., Sadollah, A., Bahreininejad, A. and Hamdi, M. (2012) Water Cycle Algorithm—A Novel Metaheuristic Optimization Method for Solving Constrained Engineering Optimization Problems. Computers & Structures, 110-111, 151-166.
https://doi.org/10.1016/j.compstruc.2012.07.010
[3]
Alijla, B.O., Wong, L.-P., Lim, C.P., Khader, A.T. and Al-Betar, M.A. (2014) A Modified Intelligent Water Drops Algorithm and Its Application to Optimization Problems. Expert Systems with Applications, 41, 6555-6569.
https://doi.org/10.1016/j.eswa.2014.05.010
[4]
Wedyan, A., Whalley, J. and Narayanan, A. (2017) Hydrological Cycle Algorithm for Continuous Optimization Problems. Journal of Optimization, 2017, Article ID: 3828420. https://doi.org/10.1155/2017/3828420
[5]
Msallam, M.M. and Hamdan, M. (2011) Improved Intelligent Water Drops Algorithm Using Adaptive Schema. International Journal of Bio-Inspired Computing, 3, 103. https://doi.org/10.1504/IJBIC.2011.039909
[6]
Shah-Hosseini, H. (2009) The Intelligent Water Drops Algorithm: A Nature-Inspired Swarm-Based Optimization Algorithm. International Journal of Bio-Inspired Computing, 1, 71-79. https://doi.org/10.1504/IJBIC.2009.022775
[7]
Wu, X.-B., Liao, J. and Wang, Z.-C. (2015) Water Wave Optimization for the Traveling Salesman Problem. 11th International Conference of Intelligent Computing Theories and Methodologies, Fuzhou, 20-23 August 2015, 137-146.
https://doi.org/10.1007/978-3-319-22180-9_14
[8]
Srour, A., Othman, Z.A. and Hamdan, A.R. (2014) A Water Flow-Like Algorithm for the Travelling Salesman Problem. Advances in Electrical and Computer Engineering, 2014, 1-14. https://doi.org/10.1155/2014/436312
[9]
Rabanal, P., Rodríguez, I. and Rubio, F. (2009) Applying River Formation Dynamics to Solve NP-Complete Problems. In: Chiong, R., Ed., Nature-Inspired Algorithms for Optimisation, Springer, Berlin Heidelberg, 333-368.
https://doi.org/10.1007/978-3-642-00267-0_12
[10]
Zhan, S., Lin, J., Zhang, Z. and Zhong, Y. (2016) List-Based Simulated Annealing Algorithm for Traveling Salesman Problem. Computational Intelligence and Neuroscience, 2016, 1-12. https://doi.org/10.1155/2016/1712630
[11]
Geng, X., Chen, Z., Yang, W., Shi, D. and Zhao, K. (2011) Solving the Traveling Salesman Problem Based on an Adaptive Simulated Annealing Algorithm with Greedy Search. Applied Soft Computing, 11, 3680-3689.
https://doi.org/10.1016/j.asoc.2011.01.039
[12]
Braun, H. (1991) On Solving Travelling Salesman Problems by Genetic Algorithms. In: Parallel Problem Solving from Nature, Springer-Verlag, Berlin/Heidelberg, 129-133. https://doi.org/10.1007/BFb0029743
[13]
Grefenstette, J., Gopal, R., Rosmaita, B. and Van Gucht, D. (1985) Genetic Algorithms for the Traveling Salesman Problem. Proceedings of the First International Conference on Genetic Algorithms, Pittsburgh, July 1985, 160-168.
[14]
Larranaga, P., Kuijpers, C.M.H., Murga, R.H., Inza, I. and Dizdarevic, S. (1999) Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators. Artificial Intelligence Review, 13, 129-170.
https://doi.org/10.1023/A:1006529012972
[15]
Moorthy, S.K. (2012) Evolving Optimal Solutions by Nature Inspired Algorithms. PhD Thesis, University of Pune, Pune.
[16]
Potvin, J.-Y. (1996) Genetic Algorithms for the Traveling Salesman Problem. Annals of Operations Research, 63, 337-370. https://doi.org/10.1007/BF02125403
[17]
Rao, A. and Hedge, S. (2015) Literature Survey on Travelling Salesman Problem Using Genetic Algorithms. International Journal of Advanced Research in Education Technology, 2, 42.
[18]
Vaishnav, P., Choudhary, N. and Jain, K. (2017) Traveling Salesman Problem Using Genetic Algorithm: A Survey. International Journal of Scientific Research in Computer Science, Engineering and Information Technology, 2, 105-108.
[19]
Dorigo, M. and Gambardella, L.M. (1997) Ant Colonies for the Travelling Salesman Problem. BioSystems, 43, 73-81. https://doi.org/10.1016/S0303-2647(97)01708-5
[20]
Stutzle, T. and Hoos, H.H. (1997) MAX-MIN Ant System and Local Search for the Traveling Salesman Problem. Proceedings of 1997 IEEE International Conference on Evolutionary Computation, Indianapolis, 13-16 April 1997, 309-314.
https://doi.org/10.1109/ICEC.1997.592327
[21]
Gambardella, L.M. and Dorigo, M. (1996) Solving Symmetric and Asymmetric TSPs by Ant Colonies. Proceedings of IEEE International Conference on Evolutionary Computation, Nagoya, 20-22 May 1996, 622-627.
https://doi.org/10.1109/ICEC.1996.542672
[22]
Hlaing, Z.C.S.S. and Khine, M.A. (2011) An Ant Colony Optimization Algorithm for Solving Traveling Salesman Problem. International Conference on Information Communication and Management, 16, 54-59.
[23]
Zhong, W., Zhang, J. and Chen, W. (2007) A Novel Discrete Particle Swarm Optimization to Solve Traveling Salesman Problem. 2007 IEEE Congress on Evolutionary Computation, Singapore, 25-28 September 2007, 3283-3287.
https://doi.org/10.1109/CEC.2007.4424894
[24]
Wang, X., Mu, A. and Zhu, S. (2013) ISPO: A New Way to Solve Traveling Salesman Problem. Intelligent Control and Automation, 4, 122-125.
https://doi.org/10.4236/ica.2013.42017
[25]
Wang, K.-P., Huang, L., Zhou, C.-G. and Pang, W. (2003) Particle swarm optimization for traveling salesman problem. Proceedings of the 2003 International Conference on Machine Learning and Cybernetics, Xi’an, 2-5 November 2003, 1583-1585.
https://doi.org/10.1109/ICMLC.2003.1259748
[26]
Shi, X.H., Liang, Y.C., Lee, H.P., Lu, C. and Wang, Q.X. (2007) Particle Swarm Optimization-Based Algorithms for TSP and Generalized TSP. Information Processing Letters, 103, 169-176. https://doi.org/10.1016/j.ipl.2007.03.010
[27]
Osaba, E., Yang, X.-S., Diaz, F., López-Garcia, P. and Carballedo, R. (2016) An Improved Discrete Bat Algorithm for Symmetric and Asymmetric Traveling Salesman Problems. Engineering Applications of Artificial Intelligence, 48, 59-71.
https://doi.org/10.1016/j.engappai.2015.10.006
[28]
Saji, Y., Riffi, M.E. and Ahiod, B. (2014) Discrete Bat-Inspired Algorithm for Travelling Salesman Problem. 2014 Second World Conference on Complex Systems, Agadir, 10-12 November 2014, 28-31. https://doi.org/10.1109/ICoCS.2014.7060983
[29]
Basu, S. (2012) Tabu Search Implementation on Traveling Salesman Problem and Its Variations: A Literature Survey. American Journal of Operations Research, 2, 163-173. https://doi.org/10.4236/ajor.2012.22019
[30]
Held, M., Hoffman, A.J., Johnson, E.L. and Wolfe, P. (1984) Aspects of the Traveling Salesman Problem. IBM Journal of Research and Development, 28, 476-486.
https://doi.org/10.1147/rd.284.0476
[31]
Hoffman, K.L. and Padberg, M. (2013) Traveling Salesman Problem. In: Encyclopedia of Operations Research and Management Science, Kluwer Academic Publishers, Dordrecht, 849-853. https://doi.org/10.1007/978-1-4419-1153-7_1068
[32]
Li, M., Chen, X., Li, X., Ma, B. and Vitanyi, P.M.B. (2004) The Similarity Metric. IEEE Transactions on Information Theory, 50, 3250-3264.
https://doi.org/10.1109/TIT.2004.838101
[33]
Helsgaun, K. (2000) An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic. European Journal of Operational Research, 126, 106-130.
https://doi.org/10.1016/S0377-2217(99)00284-2
[34]
Helsgaun, K. (2006) An Effective Implementation of K-opt Moves for the Lin-Kernighan TSP Heuristic. Roskilde University, Roskilde, 109.
[35]
Rocki, K. and Suda, R. (2012) Accelerating 2-opt and 3-opt Local Search Using GPU in the Travelling Salesman Problem. 2012 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, Ottawa, 13-16 May 2012, 705-706.
https://doi.org/10.1109/CCGrid.2012.133
[36]
Reinelt, G. (1995) TSPLIB.
https://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
[37]
Reinelt, G. (1991) TSPLIB—A Traveling Salesman Problem Library. ORSA Journal on Computing, 3, 376-384. https://doi.org/10.1287/ijoc.3.4.376
[38]
Gülcü, S.D., Gülcü, S., Kahramanli, H., Campus, A.K. and Selcuklu, K. (2013) Solution of Travelling Salesman Problem Using Intelligent Water Drops Algorithm. Proceedings of the 2nd International Conference on Information Technology and Computer Networks, Montreal, 27-28August 2016.
[39]
Saenphon, T., Phimoltares, S. and Lursinsap, C. (2014) Combining New Fast Opposite Gradient Search with Ant Colony Optimization for Solving Travelling Salesman Problem. Engineering Applications of Artificial Intelligence, 35, 324-334.
https://doi.org/10.1016/j.engappai.2014.06.026
[40]
Chen, S.-M. and Chien, C.-Y. (2011) Solving the Traveling Salesman Problem Based on the Genetic Simulated Annealing Ant Colony System with Particle Swarm Optimization Techniques. Expert Systems with Applications, 38, 14439-14450.
https://doi.org/10.1016/j.eswa.2011.04.163
[41]
Chen, W.-N., Zhang, J., Chung, H.S.-H., Zhong, W.-L., Wu, W.-G. and Shi, Y. (2010) A Novel Set-Based Particle Swarm Optimization Method for Discrete Optimization Problems. IEEE Transactions on Evolutionary Computation, 14, 278-300.
https://doi.org/10.1109/TEVC.2009.2030331
[42]
Wang, M., Fu, Q., Tong, N., Li, M. and Zhao, Y. (2016) An Improved Firefly Algorithm for Traveling Salesman Problems. Proceedings of the 2015 4th National Conference on Electrical, Electronics and Computer Engineering, Xi’an, 12-13 December 2015.
[43]
Tsai, C.-F., Tsai, C.-W. and Tseng, C.-C. (2004) A New Hybrid Heuristic Approach for Solving Large Traveling Salesman Problem. Information Sciences, 166, 67-81.
https://doi.org/10.1016/j.ins.2003.11.008
[44]
Masutti, T.A.S. and de Castro, L.N. (2009) A Self-Organizing Neural Network Using Ideas from the Immune System to Solve the Traveling Salesman Problem. Information Sciences, 179, 1454-1468. https://doi.org/10.1016/j.ins.2008.12.016
[45]
Ouaarab, A., Ahiod, B. and Yang, X.-S. (2014) Discrete Cuckoo Search Algorithm for the Travelling Salesman Problem. Neural Computing and Applications, 24, 1659-1669. https://doi.org/10.1007/s00521-013-1402-2
