Experimental Comparison between Genetic Algorithm and Ant Colony Optimization on Traveling Salesman Problem

Authors

  • Muhammed Yaseen Morshed Adib  Computer Science and Engineering, Stamford University Bangladesh, Dhaka-1217, Dhaka, Bangladesh
  • Jannatun Razia  Computer Science and Engineering, Ahsanullah University o Science and Technology, Dhaka-1208, Dhaka, Bangladesh
  • Md. Toufiqur Rahman  Computer Science and Engineering, Ahsanullah University o Science and Technology, Dhaka-1208, Dhaka, Bangladesh

DOI:

https://doi.org/10.32628/IJSRSET218135

Keywords:

Bio-inspired optimization, Traveling Salesman Problem, Swarm Intelligence, Genetic Algorithm, Ant Colony Optimization, Meta-heuristic

Abstract

This paper is based on bio-inspired optimization algorithms. Optimization is the process of selecting the best element by following some rules and criteria from some set of available alternatives. In this paper, we have solved Traveling Salesman Problem (TSP) using Swarm Intelligence algorithms and we have compared them. First we have implemented the basic Genetic Algorithm (GA) on TSP. Then we have implemented Ant Colony Optimization (ACO) Algorithm on TSP. In optimization problem, Genetic Algorithm (GA) and Ant Colony Optimization (ACO) Algorithm have been known as good meta-heuristic techniques. GA is designed by adopting the natural law of evolution, while ACO is inspired by the foraging behavior of ant species. Balancing the exploitation-exploration tradeoff is required in ACO. In contrast with the GA implementation, ACO was much easier to control.

References

  1. Dr. M. S. Alam, Continuous Optimization with evolutionary and swarm intelligence algorithms, PhD Thesis, Bangladesh University of Engineering and Technology, September 2013.
  2. Bäck, T., Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press,USA, 1996.
  3. Mühlenbein, H., “The Breeder Genetic Algorithm – a provable optimal search algorithm and its application”, IEEE Colloquium on Applications of Genetic Algorithms, Digest No. 94/067, London, March 15, 1994.
  4. Dorigo, M. and Stützle, T., Ant Colony Optimization. MIT Press, Cambridge, MA, 2004.
  5. Li, K., Kang, L., Zhang, W., Li, B., (2008), Comparative Analysis of Genetic Algorithm and Ant Colony Algorithm on Solving Traveling Salesman Problem, , in IEEE International Workshop. Semantic Computing and Systems.
  6. J. Luo and D. El Baz, "A Survey on Parallel Genetic Algorithms for Shop Scheduling Problems," 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), Vancouver, BC, 2018.
  7. Maumita Bhattacharya, Evolutionary Approaches to Expensive Optimisation, International Journal of Advanced Research in Artificial Intelligence, Vol. 2, No. 3, 2013.
  8. M.-R. Akbarzadeh-T, M. Davarynejad and N. Pariz, Adaptive fuzzy fitness granulation for evolutionary optimization, International Journal of Approximate Reasoning, June 2008.
  9. M. Davarynejad, M. -. Akbarzadeh-T and C. A. Coello Coello, Auto-tuning fuzzy granulation for evolutionary optimization, 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence), Hong Kong, 2008
  10. Nita H. Shah, Mandeep Mittal, Handbook of Research on Promoting Business Process Improvement Through inventory control techniques, IGI Global Publisher of Timely Knowledge, 2017
  11. Roman V. Yampolskiy, Neuroevolution Methods Show Significant Success, Evoloution News and Science today, 2020
  12. Oonsivilai, Anant & Oonsivilai, Ratchadaporn. (2009). A genetic algorithms programming application in natural cheese products. WSEAS TRANSACTIONS on SYSTEMS. 8. 44-54.
  13. Shidhanta Poddar, Parallel Genetic Algorithm,
  14. Valdez, Fevrier, Swarm Intelligence: A Review of Optimization Algorithms Based on Animal Behavior, Recent Advances of Hybrid Intelligent Systems Based on Soft Computing.
  15. St, Thomas & Dorigo, Marco. (1999). ACO Algorithms for the Traveling Salesman Problem.
  16. Zukhri, Zainudin & Paputungan, Irving. (2013). A Hybrid Optimization Algorithm based on Genetic Algorithm and Ant Colony Optimization. International Journal of Artificial Intelligence & Applications. 4. 63-75. 10.5121/ijaia.2013.4505.

International Journal of Scientific Research in Science, Engineering and Technology

Downloads

Published

2021-02-28

Issue

Volume 8, Issue 1, January-February-2021

Section

Research Articles

License

Copyright (c) IJSRSET

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
Muhammed Yaseen Morshed Adib, Jannatun Razia, Md. Toufiqur Rahman "Experimental Comparison between Genetic Algorithm and Ant Colony Optimization on Traveling Salesman Problem" International Journal of Scientific Research in Science, Engineering and Technology (IJSRSET), Print ISSN : 2395-1990, Online ISSN : 2394-4099, Volume 8, Issue 1, pp.155-162, January-February-2021. Available at doi : https://doi.org/10.32628/IJSRSET218135