Comparative study between elephant herding optimization (EHO) and U-turning ant colony optimization (U-TACO) in solving symmetric traveling salesman problem (STSP)

  • Authors

    • Saman M. Almufti computer science
    • Ridwan Boya Marqas computer science
    • Renas R. Asaad computer science
    2019-08-25
    https://doi.org/10.14419/jacst.v8i2.29403
  • Swarm Intelligence (SI), Elephant Herding Optimization (EHO), U-Turning Ant Colony Optimization (U-TACO), Optimization, Symmetric Traveling Salesman Problem (STSP).
  • Swarm Intelligence is an active area of researches and one of the most well-known high-level techniques intended to generat, select or find a heuristic that optimize solutions of optimization problems.
    Elephant Herding optimization algorithm (EHO) is a metaheuristic swarm based search algorithm, which is used to solve various optimi-zation problems. The algorithm is deducted from the behavior of elephant groups in the wild. Were elephants live in a clan with a leader matriarch, while the male elephants separate from the group when they reach adulthood. This is used in the algorithm in two parts. First, the clan updating mechanism. Second, the separation mechanism.
    U-Turning Ant colony optimization (U-TACO) is a swarm-based algorithm uses the behavior of real ant in finding the shortest way be-tween its current location and a source of food for solving optimization problems. U-Turning Ant colony Optimization based on making partial tour as an initial state for the basic Ant Colony algorithm (ACO).
    In this paper, a Comparative study has been done between the previous mentioned algorithms (EHO, U-TACO) in solving Symmetric Traveling Salesman Problem (STSP) which is one of the most well-known NP-Hard problems in the optimization field. The paper pro-vides tables for the results obtained by EHO and U-TACO for various STSP problems from the TSPLIB95.

  • References

    1. [1] X. Yang, “Metaheuristic Optimization†Scholarpedia, 6(8), p.11472, 2011. https://doi.org/10.4249/scholarpedia.11472.
      [2] S. Almufti, "U-Turning Ant Colony Algorithm powered by Great Deluge Algorithm for the solution of TSP Problem", Hdl.handle.net, 2018. [Online].
      [3] S. Almufti, “Using Swarm Intelligence for solving NPHard Problems,†Academic Journal of Nawroz University, vol. 6, no. 3, pp. 46–50, 2017. https://doi.org/10.25007/ajnu.v6n3a78.
      [4] S. Almufti and A. Shaban, "U-Turning Ant Colony Algorithm for Solving Symmetric Traveling Salesman Problem", Academic Journal of Nawroz University, vol. 7, no. 4, pp. 45-49, 2018. https://doi.org/10.25007/ajnu.v6n4a270.
      [5] J. Rajpurohit, T. Sharma and A. Abraham, "Glossary of MetaheuristicAlgorithms", International Journal of Computer Information Systems and Industrial Management Applications, vol. 9, pp. 181-205, 2017.
      [6] R. Asaad and N. Abdulnabi, "Using Local Searches Algorithms with Ant Colony Optimization for the Solution of TSP Problems", Academic Jour-nal of Nawroz University, vol. 7, no. 3, pp. 1-6, 2018. https://doi.org/10.25007/ajnu.v7n3a193.
      [7] S. Chibani and A. Tari,†Elephant Herding Optimization for Service Selection in QoS-Aware Webâ€, International Journal of Computer and Infor-mation Engineering, 2017.
      [8] Y. Li, “Solving TSP by an ACO-and-BOA-based Hybrid Algorithmâ€. International Conference on Computer Application and System Modeling, pp. 189–192. IEEE Press, New York ,2010.
      [9] M. Dorigo,†Optimization, Learning and Natural Algorithmsâ€, PhD thesis, Politecnico di Milano, Italy, 1992.
      [10] C. Kahraman and G. Kayakutlu, Energy management - collective and computational intelligence with theory and applications. Cham, Switzerland: Springer, 2018. https://doi.org/10.1007/978-3-319-75690-5.
      [11] G. Wang, L. Dos Santos Coelho, X. Gao and S. Deb, "A new metaheuristic optimisation algorithm motivated by elephant herding behaviour", In-ternational Journal of Bio-Inspired Computation, vol. 8, no. 6, p. 394, 2016. https://doi.org/10.1504/IJBIC.2016.10002274.
      [12] G. Wang, S. Deb and L. Coelho, "Elephant Herding Optimization", 2015 3rd International Symposium on Computational and Business Intelligence (ISCBI), 2015. https://doi.org/10.1109/ISCBI.2015.8.
      [13] G. Wang, S. Deb, X. Zhao and Z. Cui, "A new monarch butterfly optimization with an improved crossover operator", Operational Research, vol. 18, no. 3, pp. 731-755, 2016. https://doi.org/10.1007/s12351-016-0251-z.
      [14] L. Barolli, F. Xhafa and J. Conesa, Advances on Broad-Band Wireless Computing, Communication and Applications. New York: Springer, 2017. https://doi.org/10.1007/978-3-319-49106-6.
      [15] P. Suganthan, N. Hansen, J. Liang, K. Deb, Y. Chen, A. Auger and S. Tiwari, “Problem definitions and evaluation criteria for the CEC 2005 spe-cial session on real-parameter optimizationâ€, Nanyang Technological University, Singapore, 2005.
      [16] 25A. Hossam, A. Bouzidi and M. Riffi, "Elephants Herding Optimization for Solving the Travelling Salesman Problem", Advances in Intelligent Systems and Computing, pp. 122-130, 2019. https://doi.org/10.1007/978-3-030-12065-8_12.
      [17] S. Almufti, “U-Turning Ant Colony Algorithm powered by Great Deluge Algorithm for the solution of TSP Problem†(2015). [online] Hdl.handle.net. Available at: http://hdl.handle.net/11129/1734.
      [18] M. Dorigo, “Optimization, Learning and Natural Algorithmsâ€, PhD thesis, Politecnico di Milano, Italy. (1992).
      [19] G. Reinelt, "TSPLIB", Elib.zib.de, 1997. [Online]. Available: http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html. [Accessed: 18- Feb- 2019].
      [20] S. Almufti, R. Asaad and B. Salim, “Review on Elephant Herding Optimization Algorithm Performance in Solving Optimization Problemsâ€. Inter-national Journal of Engineering & Technology, [S.l.], v. 7, n. 4, p. 6109-6114, may 2019. ISSN 2227-524X. Available at: <https://www.sciencepubco.com/index.php/ijet/article/view/28473/15566

  • Downloads

  • How to Cite

    M. Almufti, S., Boya Marqas, R., & R. Asaad, R. (2019). Comparative study between elephant herding optimization (EHO) and U-turning ant colony optimization (U-TACO) in solving symmetric traveling salesman problem (STSP). Journal of Advanced Computer Science & Technology, 8(2), 32-37. https://doi.org/10.14419/jacst.v8i2.29403