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.
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
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
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
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
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
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
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
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
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
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
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
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
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.
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
Moorthy, S.K. (2012) Evolving Optimal Solutions by Nature Inspired Algorithms. PhD Thesis, University of Pune, Pune.
Potvin, J.-Y. (1996) Genetic Algorithms for the Traveling Salesman Problem. Annals of Operations Research, 63, 337-370. https://doi.org/10.1007/BF02125403
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.
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.
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
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
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
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.
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
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
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
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
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
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
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
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
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
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
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
Helsgaun, K. (2006) An Effective Implementation of K-opt Moves for the Lin-Kernighan TSP Heuristic. Roskilde University, Roskilde, 109.
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
Reinelt, G. (1995) TSPLIB. https://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
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
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.
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
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
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
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.
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
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
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