Signed LMS based Adaptive Ant System

Print
2nd National Conference on Computing, Communication and Sensor Network
© 2011 by IJCA Journal
Number 4 - Article 2
Year of Publication: 2011
Authors:
Abhishek Paul
Sumitra Mukhopadhyay

Abhishek Paul and Sumitra Mukhopadhyay. Signed LMS based Adaptive Ant System. IJCA Special Issue on 2nd National Conference- Computing, Communication and Sensor Network (CCSN) (4):7-12, 2011. Full text available. BibTeX

@article{key:article,
	author = {Abhishek Paul and Sumitra Mukhopadhyay},
	title = {Signed LMS based Adaptive Ant System},
	journal = {IJCA Special Issue on 2nd National Conference- Computing, Communication and Sensor Network (CCSN)},
	year = {2011},
	number = {4},
	pages = {7-12},
	note = {Full text available}
}

Abstract

There are various metaheuristic algorithms which are used to solve the Traveling Salesman problem. Ant colony optimization (ACO) is one such algorithm, which is inspired by the foraging behavior of ants. In this paper, we have proposed a modified model, entitled as Signed Adaptive Ant System (SAAS) for pheromone updation of the Ant-System; SAAS exploits the properties of Adaptive Filters. The proposed algorithm is implemented using sign-LMS (Least Mean Square) based algorithm. It imparts no information about the correction factor of the LMS adaptive algorithm but provides the sign value of each function in the correction factor of the LMS algorithm. SAAS modifies its properties in accordance to the requirement of surrounding domain and for the betterment of its performance in dynamic environment. The proposed algorithm is also easier for hardware implementation. The results of an experimental evaluation, conducted to evaluate the usefulness of the new strategy, are well described. Our algorithm shows effective results as compared to other existing approaches.

Reference

  • D.G. Goldberg, “Genetic Algorithms in Search, Optimization and Machine Learning”, Addison- Wesley, Reading, MA, 1989.
  • H.G. Bayer and H.P. Schwefel, “Evolutionary Strategis: A Comprehensive Introduction”, Journal of Natural Computing, 2004, pp. 3-52.
  • J. Kennedy and R.C. Eberhart, “ Particle Swarm Optimization”, in Proc. IEEE, Int. Conf. On Neural Networks, Piscataway, NJ, 1995, pp. 1942-1948.
  • M. Dorigo and L.M. Gambardella, “Ant Colony System: A cooperative learning approach to the travelling salesman problem”, in IEEE Trans. Evol. Comput., 1997, pp. 53-66.
  • K M. Dorigo, V. Maniezzo, and A. Colorni, “The ant system: Optimization by a colony of cooperating agents”, in IEEE Trans. Syst., Man Cybern. Part B, 1996, pp. 29–41.
  • A. Paul and S.Mukhopadhyay, “An Adaptive Pheromone Updation of the Ant System using LMS Technique”, in Proc. Int. Conf. on Modelling, Optimization and Computing (ICMOC-2010), AIP, 2010, vol. 1298, pp. 498-503.
  • S. Haykin, Adaptive Filter Theory, Prentice Hall, 3rd edition, 1996.
  • [online] [TSPLIB]: http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/.
  • V. Maniezzo and A. Colorni, “ The Ant System applied to the quadratic assignment problem”, IEEE Trans. of Data Knowledge Engrg., 1999, vol.11, no. 5, pp. 769-778.
  • A. Colorni, M. Dorigo, V. Maniezzo, and M. Trubian, “ Ant System for job-shop scheduling”, JORBEL-Belgian J. Operations Res., Stat. Comput. Sci., 1994, vol. 34, no. 1, pp.39.
  • L.M.Gambardella, E.D.Taillard, andG.Agazzi, “MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows,” in New Ideas in Optimization, D.Corne et.al.,Eds. McGraw Hill, London, UK, 1999, pp.63–76.