Research Article
BibTex RIS Cite

A Hybrid Genetic-Ant Colony Algorithm for Travelling Salesman Problem

Year 2017, Volume: 1 Issue: 3, 86 - 90, 30.09.2017

Emel Soylu Ali Uysal

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

  • S. Koziel and X.-S. Yang, Computational optimization, methods and algorithms, vol. 356. Springer, 2011.
  • M. Mitchell, An Introduction to genetic algorithms. MIT Press, 1998.
  • J. Kennedy and R. Eberhart, “Particle swarm optimization,” Neural Networks, 1995. Proceedings., IEEE Int. Conf., vol. 4, pp. 1942–1948 vol.4, 1995.
  • M. Dorigo, M. Birattari, and T. Stutzle, “Ant colony optimization,” IEEE Comput. Intell. Mag., vol. 1, no. 4, pp. 28–39, 2006.
  • 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.
  • 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.
  • 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.
  • 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.
  • A. Kaveh and N. Farhoudi, “A new optimization method: Dolphin echolocation,” Adv. Eng. Softw., vol. 59, pp. 53–70, 2013.
  • S. Mirjalili and A. Lewis, “The Whale Optimization Algorithm,” Adv. Eng. Softw., vol. 95, pp. 51–67, 2016.
  • 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.
  • 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.
  • 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.
  • A. C. Nearchou, “Path planning of a mobile robot using genetic heuristics,” Robotica, vol. 16, no. 5, pp. 575–588, 1998.
  • 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.
  • 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.
  • 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.
  • 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.
  • N. M. Razali and J. Geraghty, “Genetic Algorithm Performance with Different Selection Strategies in Solving TSP,” Int. Conf. Comput. Intell. Intell. Syst., 2011.

Year 2017, Volume: 1 Issue: 3, 86 - 90, 30.09.2017

Emel Soylu Ali Uysal

Abstract

References

  • S. Koziel and X.-S. Yang, Computational optimization, methods and algorithms, vol. 356. Springer, 2011.
  • M. Mitchell, An Introduction to genetic algorithms. MIT Press, 1998.
  • J. Kennedy and R. Eberhart, “Particle swarm optimization,” Neural Networks, 1995. Proceedings., IEEE Int. Conf., vol. 4, pp. 1942–1948 vol.4, 1995.
  • M. Dorigo, M. Birattari, and T. Stutzle, “Ant colony optimization,” IEEE Comput. Intell. Mag., vol. 1, no. 4, pp. 28–39, 2006.
  • 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.
  • 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.
  • 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.
  • 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.
  • A. Kaveh and N. Farhoudi, “A new optimization method: Dolphin echolocation,” Adv. Eng. Softw., vol. 59, pp. 53–70, 2013.
  • S. Mirjalili and A. Lewis, “The Whale Optimization Algorithm,” Adv. Eng. Softw., vol. 95, pp. 51–67, 2016.
  • 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.
  • 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.
  • 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.
  • A. C. Nearchou, “Path planning of a mobile robot using genetic heuristics,” Robotica, vol. 16, no. 5, pp. 575–588, 1998.
  • 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.
  • 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.
  • 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.
  • 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.
  • N. M. Razali and J. Geraghty, “Genetic Algorithm Performance with Different Selection Strategies in Solving TSP,” Int. Conf. Comput. Intell. Intell. Syst., 2011.
There are 19 citations in total.

Details

Subjects Engineering
Journal Section Articles
Authors

Emel Soylu

Ali Uysal

Publication Date September 30, 2017
Published in Issue Year 2017 Volume: 1 Issue: 3

Cite

IEEE E. Soylu and A. Uysal, “A Hybrid Genetic-Ant Colony Algorithm for Travelling Salesman Problem”, IJESA, vol. 1, no. 3, pp. 86–90, 2017.
 Download Cover Image

ISSN 2548-1185
e-ISSN 2587-2176
Period: Quarterly
Founded: 2016
Publisher: Nisantasi University
e-mail:ilhcol@gmail.com