IJBTT

ACO, Its Modification and Variants

	International Journal of Computer Trends and Technology (IJCTT)
	© 2014 by IJCTT Journal
	Volume-9 Number-6
	Year of Publication : 2014
	Authors : Akash Tayal , Prerna Khurana , Priyanka Mittal , Sanjana Chopra
	DOI :  10.14445/22312803/IJCTT-V9P159

Akash Tayal , Prerna Khurana , Priyanka Mittal , Sanjana Chopra."ACO, Its Modification and Variants". International Journal of Computer Trends and Technology (IJCTT) V9(6):310-326, March 2014. ISSN:2231-2803. www.ijcttjournal.org. Published by Seventh Sense Research Group.

Abstract -
Ant colony optimization (ACO) is a P based metaheuristic algorithm which has been proven as a successful technique and applied to a number of combinatorial optimization problems and is also applied to the Traveling salesman problem (TSP). TSP is a well-known NP-complete combinatorial optimization (CO) problem and has an extensive application background. The presented paper proposes an improved version of Ant Colony Optimization (ACO) by modifying its parameters to yield an optimal result. Also this paper shows the experimental results and comparison between the original ACO and Modified ACO. Further this paper proposes two variants of ACO according to their specific application. Various city distributions have also been discussed and compared.

References
1. Magnus Erik Hvass Pedersen, Hvass Laboratories, “Good Parameters for Particle Swarm Optimization”, Technical Report no. HL10012010
2. M. Dorigo and T. Strutzle, “Ant colony optimization,” MIT Press, Cambridge, MA, 2004
3. M. Dorigo, G.D. Caro, andL.M. Gambardella, “Ant algorithms for discrete optimization,” ArtificialLife, vol. 5, no. 2, page 137, 1999
4. T. Stutzle and H.H. Hoos, “Max-min ant system,” Future Generation Comput. Syst., vol. 16, no. 8,page 889, 2000
5. J. Kennedy and C. E. Russell, “Swarm intelligence,” in Morgan Kaufmann, Academic Press, 2001
6. P. N. Suganthan, N. Hansen, J. J. Liang, et al., “Problem definitions and evaluation criteria for the cec 2005 special session on real-parameter optimization,” Tech. Rep. 2005005, Nanyang Technological University, Singapore; IIT Kanpur, India, 2005.
7. M. I. Aouad, R. Schott, and O. Zendra, “A tabu search heuristic for scratch-pad memory management,” in Proceedings of the International Conference on Software Engineering and Technology (ICSET `10), vol. 64, pp. 386–390, WASET, Rome, Italy, 2010.
8. S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671–680, 1983. View at Scopus
9. “Practical GeniticAlgorithms” – Haupt and Haupt , second edition
10. “Metaheuristics – from Design to Implementation” by El-Ghazali Talbi
11. Vittorio Maniezzo, Luca Maria Gambarde, Fabio de Luigi. http://www.cs.unibo.it/bison/publications/ACO.pdf
12. Monash University CSE 460 lecture notes http://www.csse.monash.edu.au/~berndm/CSE460/Lectures/cse460-9.pdf
13. “Ant colonies for the traveling salesman problem” http://www.idsia.ch/~luca/acs-bio97.pdf
14. Dorigo, M. and Gambardella, L. M., Ant colonies for the travelling salesman problem, Biosystems, 43(2):73–81, 1997.
15. Chengming, Q., An ant colony algorithm with stochastic local search for the VRP, 8rd International Conference on Innovative Computing Information and Control, Los Alamitos, CA, USA, pp. 464–468, IEEE Computer Society, 2008.
16. Lee, Z.-J., Su, S.-F., Chuang, C.-C., and Liu, K.-H., Genetic algorithm with ant colony optimization (GA-ACO) for multiple sequence alignment, Applied Soft Computing, 8(1):55–78, 2008.
17. Jun-Qing Li, Q.-K. P. and Xie, S.-X., A hybrid variable neighborhood search algorithm for solving multi-objective flexible job shop problems, Computer Science and Information Systems, 7(4):907–930, 2010.
18. Negulescu, S., Dzitac, I., and Lascu, A., Synthetic genes for artificial ants. Diversity in ant colony optimization algorithms, INT J COMPUT COMMUN, ISSN 1841-9836, 5(2):216– 223, 2010.
19. Zhang, X., Duan, H., and Jin, J., DEACO: Hybrid ant colony optimization with differential evolution, IEEE Congress on Evolutionary Computation, 921–927, IEEE Computer Society, 2008.
20. Serbencu, A., Minzu, V., and Serbencu, A., An ant colony system based metaheuristic for solving single machine scheduling problem, The Annals of Dunarea De Jos University of Galati, 3:19–24, 2007.
21. Neumann, F., Sudholt, D., and Witt, C., Rigorous analyses for the combination of ant colony optimization and local search. Ant Colony Optimization and Swarm Intelligence, LNCS Berlin, Heidelberg, 5217:132–143, Springer-Verlag, 2008.
22. Gan, R., Guo, Q., Chang, H., and Yi, Y., Improved ant colony optimization algorithm for the traveling salesman problems, Journal of Systems Engineering and Electronics, 21(2):329– 333, 2010.
23. Jovanovic, R., Tuba, M., and Simian, D., Comparison of different topologies for islandbased multi-colony ant algorithms for the minimum weight vertex cover problem, WSEAS Transactions on Computers, 9(1):83–92, 2010.
24. Stutzle, T. and Dorigo, M., ACO algorithms for the traveling salesman problem, Evolutionary Algorithms in Engineering and Computer Science: Recent Advances in Genetic Algorithms, Evolution Strategies, Evolutionary Programming, Genetic Programming and Industrial Applications, K Miettinen, P Niettaanmaki, M M Makela and J Periaux, editors, p. 500, Willey, 1999.
25. Stutzle, T. and Hoos, H. H., MAX-MIN ant system, Future Generation Computer Systems, 16(9):889–914, 2000.
26. Wong, K. Y. and See, P. C., A new minimum pheromone threshold strategy (MPTS) for max-min ant system, Applied Soft Computing, 9(3):882–888, 2009.
27. Huang, H., Yang, X., Hao, Z., and Cai, R., A novel ACO algorithm with adaptive parameter, Computational Intelligence and Bioinformatics, LNCS, 4115:12–21, Springer-Verlag Berlin Heidelberg, 2006.
28. White, C. and Yen, G., A hybrid evolutionary algorithm for traveling salesman problem, IEEE Congress on Evolutionary Computation, 2:1473–1478, IEEE Computer Society, 2004.
29. Duan, H. and Yu, X., Hybrid ant colony optimization using memetic algorithm for traveling salesman problem, Approximate Dynamic Programming and Reinforcement Learning, 92–95, IEEE Computer Society, 2007.
30. Reinelt, G., TSPLIB - a traveling salesman problem library, ORSA Journal on Computing, 3(4):376–384, 1991.
31. Jovanovic, R. and Tuba, M., Ant colony optimization algorithm with pheromone correction strategy for the minimum connected dominating set problem, Computer Science and Information Systems (ComSIS), 10(1):133–149, 2013, DOI:10.2298/CSIS110927038J.
32. Jovanovic, R., Tuba, M., and Simian, D., An object-oriented framework with corresponding graphical user interface for developing ant colony optimization based algorithms, WSEAS Transactions on Computers, 7(12):1948–1957, 2008. 33. E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy-Kan and D.B. Shmoys, “The Travelling Salesman Problem,” New York:Wiley, 1985.
34. J.L. Bentley, “Fast algorithms for geometric traveling salesman problems,” ORSA Journal on Computing, Vol. 4, pp. 387–411, 1992.
35. M. Dorigo and L.M. Gambardella, “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation, Vol.1, No.1, pp. 53-66, 1997.
36. M. Dorigo, V. Maniezzo and A.Colorni, “The ant system: Optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics–Part B, Vol. 26, No. 2, pp. 1-13, 1996.
37. Matthijs den Besten, Thomas Stützle, and Marco Dorigo. Ant colony optimization for the total weighted tardiness problem. In PPSN VI: Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, pages 611–620, London, UK, 2000.Springer-Verlag. ISBN 3-540-41056-2.
38. Thomas Eiter and Georg Gottlob. Hypergraph transversal computation and related problems in logic and ai. In JELIA ’02: Proceedings of the European Conference on Logics in Artificial Intelligence, pages549–564, London, UK, 2002. Springer-Verlag. ISBN 3-540-44190-5.
39. Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol 57). North-Holland Publishing Co., Amsterdam, The Netherlands, The Netherlands,2004. ISBN 0444515305.
40. Christine Solnon. Solving permutation constraint satisfaction problems with artificial ants. In in Proceedings of ECAI’2000, IOS,pages 118–122. Press, 2000.
41. G. Bilchev and I. Parmee (1995) The Ant Colony Metaphor for Searching Continuous Design Spaces, Proceedings of the AISB Workshop on Evolutionary Optimization, Berlin, pp. 25-39.
42. L. Kuhn (2002) Ant Colony Optimization for Continuous Spaces, thesis, Department of Information Technology and Electrical Engineering, University of Queensland, Australia.
43. M. Matsumoto and T. Nishimura (1998) Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator, ACM Transactions on Modeling and Computer Simulation, vol. 8, no. 1, pp. 3-30.
44. E. Chong and S. Zak (2001) An Introduction to Optimization, 2nd Edition, New York, Wiley-Interscience.
45. W. Sun and Y. Yuan (2006) Optimization Theory and Methods: Nonlinear Programming, New York, Springer.
46. E. Bonabeau, M. Dorigo, and G. Theraulaz (1999) Swarm Intelligence: From Natural to Artificial Systems, New York, Oxford University Press
47. R. Marler and J. Arora (2004) Survey of Multi-Objective Optimization Methods for Engineering, Structural and Multidisciplinary Optimization, vol. 26, no. 6, pp. 369-395.
48. K. Miettinen (1998) Nonlinear Multiobjective Optimization, New York, Springer.
49. Y. Donoso and R. Fabregat (2007) Multi-Objective Optimization in Computer Networks Using Metaheuristics, Chicago, Auerbach.
50. I. Das and J. Dennis (1997) A Closer Look at Drawbacks of Minimizing Weighted Sums of Objectives for Pareto Set Generation in Multicriteria Optimization Problems, Structural and Multidisciplinary Optimization, vol. 14, no. 1, pp. 63-69.
51. J. Sanchis, M. Martinez, X. Blasco, and J. Salcedo (2007) A New Perspective on Multiobjective Optimization by Enhanced Normalized Normal Constraint Method, Structural and Multidisciplinary Optimization, Springer Berlin.
52. M. Matsumoto and T. Nishimura (2000) Dynamic Creation of Pseudorandom Number Generators, Monte Carlo and Quasi-Monte Carlo Methods 1998, Springer, pp. 56-69.
53. I. Egorov (2003) IOSO NM Version 1, User Guide, IOSO Technology Center.
54. M. Kong and P. Tian (2005) A Binary Ant Colony Optimization for the Unconstrained Function Optimization Problem, Lecture Notes in Computer Science, Vol. 3801, pp. 682-687.
55. Q. Zhang, “Research on Ant Colony Algorithm and its Applications”, Computer Knowledge and Technology, Vol. 5, No.9, 2009, pp. 2396-2398.
56. C. Blum, A. Roli and M. Dorigo, “HC-ACO: The hyper-cube framework for Ant Colony Optimization”, Proceedings of MIC 2001-meta-heuristics International Conference, Porto, Portugal, July 16-21, 2001, pp.399-404.
57. L. Chen and Z. Pan, “Ant colony optimization approach for test scheduling of system on chip”, Journal of Chongqing University of Posts and Telecommunications, Vol.21, No.2, 2009, pp.212-217.
58. M. L. Spangler, K. R. Robbins, J. K. Bertrand and M. Macneil, “Ant colony optimization as a method for strategic genotype sampling”, Animal genetics, Vol. 40, No. 3, 2009, pp.308-314.
59. W. Tsai and F. Tsai, “A New Approach for Solving Large Traveling Salesman Problem Using Evolutionary Ant Rules,” IJCNN 2002, IEEE.
60. H. Md. Rais, Z. A. Othman, and A. R. Hamdan, “Improved dynamic ant colony system (DACS) on symmetric Traveling Salesman Problem (TSP) ,” International Conference on Intelligence and Advanced Systems, IEEE, 2007.
61. J. Han and Y. Tian, “An improved ant colony optimization algorithm based on dynamic control of solution construction and mergence of local search solutions,” Fourth International Conference on Natural Computation, IEEE, 2008.
62. M. Colpan, “Solving geometric tsp with ants,” the pennsylvania state university, 2005
63. C.-M. Pintea and D. Dumitrescu, “Improving ant system using a local updating rule,” Proceedings of the Seventh International Symposium and Numeric Algorithms for Scientific Computing (SYNASC’05), IEEE 2005.
64. R. Gan, Q. Guo, H. Chang, and Y. Yi, “Improved ant colony optimization algorithm for the traveling salesman problems,” Jouranl of Systems Engineering and Electronics, April 2010, pp 329-333.
65. C.-X. Wang, D.-Wu. Cui, Y.-K. Zhang, and Z.-R. Wang, “A novel ant colony system based on delauney triangulation and self-adaptive mutation for tsp,” International Joural of Information Technology, Vol.12, No.3, 2006.
66. Z. A. Othman, H. Md. Rais, and A. R. Hamdan,” Strategies DACS3increasing its performances,” European Journal of Scientific Research, 2009.
67. K. S. Hung, S. F. Su, and S. J. Lee, “Improving ant colony optimization for solving traveling salesman problem,” Journal of Advanced Computational Intelligence and Intelligent Informatics, 2007.
68. D. X. Yu, “Hybrid ant colony optimization using memetic algorithm for traveling salesman problem,” in Proceedings of the 2007 IEEE Symposium on Approximate Dynamic Programming and Reinforcement Learning (ADPRD 2007).
69. L. Min and J. Yant, “A shortest path routing based on ant algorithm,” Journal of Communication and Computer, ISSN1548-7709, USA, September 2005.
70. Marco Dorigo, Vittorio Maniezzo, and Alberto Colorni. The ant system: Optimization by a colony of coorperating agents. IEEE Trans. on Systems, Man and Cybernetics- Part B, 26(1):29–41, 1996.

Keywords
Ant Colony Optimization (ACO), Artificial Ants (AA), Combinatorial Optimization (CO), Particle Swarm Optimization (PSO), Travelling Salesman Problem (TSP)