A Hybrid Genetic-Ant Colony Algorithm for Travelling Salesman Problem

Abstract

Travelling salesman problem is a well-known problem in optimization algorithms. In this study, we propose a hybrid genetic-ant colony algorithm to solve this problem. There are no certain formulas to determine the parameters of ant colony algorithm. Usually, programmers use the trial and error method to find best values. We use the genetic algorithm to optimize best parameter values of ant colony algorithm. In this way, the success rate of ant colony algorithm is maximized.

Keywords

• Ant colony algorithm,Genetic algorithm,Path planning,Hybrid genetic-ant colony algorithm

References

1. S. Koziel and X.-S. Yang, Computational optimization, methods and algorithms, vol. 356. Springer, 2011.
2. M. Mitchell, An Introduction to genetic algorithms. MIT Press, 1998.
3. J. Kennedy and R. Eberhart, “Particle swarm optimization,” Neural Networks, 1995. Proceedings., IEEE Int. Conf., vol. 4, pp. 1942–1948 vol.4, 1995.
4. M. Dorigo, M. Birattari, and T. Stutzle, “Ant colony optimization,” IEEE Comput. Intell. Mag., vol. 1, no. 4, pp. 28–39, 2006.
5. A. Mucherino, O. Seref, O. Seref, O. E. Kundakcioglu, and P. Pardalos, “Monkey search: a novel metaheuristic search for global optimization,” in AIP conference proceedings, 2007, vol. 953, no. 1, pp. 162–173.
6. C. Yang, X. Tu, and J. Chen, “Algorithm of marriage in honey bees optimization based on the wolf pack search,” Proc. 2007 Int. Conf. Intell. Pervasive Comput. IPC 2007, pp. 462–467, 2007.
7. X.-S. Yang and S. Deb, “Cuckoo search via Lévy flights,” in Nature & Biologically Inspired Computing, 2009. NaBIC 2009. World Congress on, 2009, pp. 210–214.
8. W. Pan, “Knowledge-Based Systems A new Fruit Fly Optimization Algorithm : Taking the financial distress model as an example,” Knowledge-Based Syst., vol. 26, pp. 69–74, 2012.

9. A. Kaveh and N. Farhoudi, “A new optimization method: Dolphin echolocation,” Adv. Eng. Softw., vol. 59, pp. 53–70, 2013.
10. S. Mirjalili and A. Lewis, “The Whale Optimization Algorithm,” Adv. Eng. Softw., vol. 95, pp. 51–67, 2016.
11. X. Chen, Y. Kong, X. Fang, and Q. Wu, “A fast two-stage ACO algorithm for robotic path planning,” Neural Comput. Appl., vol. 22, no. 2, pp. 313–319, 2013.
12. M. a. P. Garcia, O. Montiel, O. Castillo, R. Sepúlveda, and P. Melin, “Path planning for autonomous mobile robot navigation with ant colony optimization and fuzzy cost function evaluation,” Appl. Soft Comput., vol. 9, no. 3, pp. 1102–1110, 2009.
13. J. E. Aghazadeh Heris and M. A. Oskoei, “Modified genetic algorithm for solving n-queens problem,” 2014 Iran. Conf. Intell. Syst., pp. 1–5, 2014.
14. A. C. Nearchou, “Path planning of a mobile robot using genetic heuristics,” Robotica, vol. 16, no. 5, pp. 575–588, 1998.
15. A. C. Nearchou and N. A. Aspragathos, “A genetic path planning algorithm for redundant articulated robots,” Robotica, vol. 15, no. 2, p. S0263574797000234, Mar. 1997.
16. J. Ni, K. Wang, H. Huang, L. Wu, and C. Luo, “Robot path planning based on an improved genetic algorithm with variable length chromosome,” 2016 12th Int. Conf. Nat. Comput. Fuzzy Syst. Knowl. Discov., pp. 145–149, 2016.
17. M. S. Saad, H. Jamaluddin, and I. Z. M. Darus, “Implementation of PID controller tuning using differential evolution and genetic algorithms,” Int. J. Innov. Comput. Inf. Control, vol. 8, no. 11, pp. 7761–7779, 2012.
18. R. K. Tan and Ş. Bora, “Parameter Tuning Algorithms in Modeling And Simulation,” Int. J. Eng. Sci. Appl., vol. 1, no. 2, pp. 58–66, 2017.
19. N. M. Razali and J. Geraghty, “Genetic Algorithm Performance with Different Selection Strategies in Solving TSP,” Int. Conf. Comput. Intell. Intell. Syst., 2011.