Relative Investigation of Ant Colony Optimization and Genetic Algorithm based Solution to Travelling Salesperson Problem

Authors

  • Chandel A Department of Computer Science, Himachal Pradesh University, India
  • Singh VK Department of Computer Science, Himachal Pradesh University, India

Keywords:

Ant, Colony, Genetic, Algorithm, Travelling, Salesperson

Abstract

Travelling salesperson problem is a nondeterministic polynomial hard problem in combinatorial optimization studied in Operations Research and theoretical computer science. To solve this problem, we used two popular meta-heuristics techniques-Ant Colony Optimization and Genetic Algorithm. Both techniques are applied to solve a TSP with same dataset. We then compare them. For Ant Colony Optimization, we studied the effect of some parameters (number of ants, evaporation and number of iterations) on the produced results. On the other hand, we studied chromosome population, crossover probability and mutation probability parameters that effect Genetic Algorithm results.

References

M.Dorigo and T.Stutze, “Research Paper on Ant Colony Optimization”, MIT Press, Cambridge (2004).

E. Lawer and J. Rooney, “Research Paper on The Travelling Salesman Problem”, John Wiley & Sons, New York (1985).

M. Dorigo, “PhD thesis Optimization, Learning and Natural Algorithms”, Politecnico di Milano, Italy (1992).

M. Dorigo and A. Colorni, “Research Paper on Ant System: Optimization by a Cooperating Agents”, IEEE Trans Syst Man Cabernet Part B, p. 29-41 (1996).

M. Dorigo and A. Colorni, “Technical Report on a Positive Feedback Strategy”, Politecnico di Milano, Italy (1991).

M. Dorigo and L.M. Gambardella, “Ant Colony System: A Cooperative Learning Approach to the Travelling Salesman Problem”, IEEE Transactions on Evolutionary Computation, Vol 1 (1997).

S. Camazine and J.L.Deneubourg,”Research Paper on Self-Organization in Biological Systems”, Princeton University Press, Princeton (2001).

J.L. Deneubourg and S. Goss, “The self-organization exploratory pattern of the Argentine ant”, J Insect Behavior, pages 59-68 (1990).

Vikram Jeet Singh and Ashwani Chandel, “Evolving E-Governance through Cloud Computing based environment”, International Journal of Advanced Research in Computer and Communication Engineering (IJARCCE), Vol 3 Issue 4.

Ashwani Chandel and Manu Sood, “Searching and Optimization Techniques in Artificial Intelligence: A Comparative Study and Complexity Analysis”, International Journal of Advanced Research in Computer Engineering and Technology (IJARCET), Vol 3 Issue 3 (2014).

Vikram Jeet Singh, Vikram Kumar and Kishori Lal Bansal, “Research on Application of Perceived QoS Guarantee through Infrastructure specific Traffic Parameter Optimization”, International Journal of Computer Network and Information Security (IJCNIS), Issue 3, MECS Publisher-Hong Kong (2014).

Ashwani Chandel and Vikram Jeet Singh, “Research on the Design Architecture & Services over a State Wide Area Network: A case of Himachal Pradesh”, International Journal of Advanced Research in Computer Engineering & Technology (IJARCET), Volume 4, Issue 2 (2015)

Downloads

Published

2015-03-31

How to Cite

[1]
A. Chandel and V. J. Singh, “Relative Investigation of Ant Colony Optimization and Genetic Algorithm based Solution to Travelling Salesperson Problem”, Int. J. Comp. Sci. Eng., vol. 3, no. 3, pp. 192–195, Mar. 2015.

Issue

Vol. 3 No. 3 (2015): IJCSE March Edition

Section

Research Article

License

Creative Commons License

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

Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.