Adaptive ant-colony algorithm for semantic query routing

• Autorzy: Gómez Santillán C. , Cruz Reyes L. , Schaeffer E. , Meza E. , Rivera Zarate G.
• Konferencja: International Seminar on Computational Intelligence held at Tijuana, Mexico on January of 2010
• Języki publikacji: EN

Abstrakty

EN

The most prevalent P2P application today is file sha ring, both among scientific users and the general public. Afundamental process in file sharing systems is the search mechanism. The unstructured nature of real-world largescale complex systems poses a challenge to the search me thods, because global routing and directory services are impractical to implement. This paper presents a new antcolony algorithm, Adaptive Neighboring-Ant Search (AdaNAS), for the semantic query routing problem (SQRP) in a P2P network. The proposed algorithm incor porates an adaptive control parameter tuning technique for runtime estimation of the time-to-live (TTL) of the ants. AdaNAS uses three strategies that take advantage of the local environment: learning, characterization, and explo ration. Two classical learning rules are used to gain ex perience on past performance using three new learning functions based on the distance traveled and the resources found by the ants. The experimental results show that the AdaNAS algorithm outperforms the NAS algorithm where the TTLvalue is not tuned at runtime.

Słowa kluczowe

EN

parameter tuning; search algorithm; peer-to-peer; adaptive algorithm; local environment; ant colony algorithms

• Wydawca: Łukasiewicz Industrial Research Institute for Automation and Measurements PIAP
• Czasopismo: Journal of Automation Mobile Robotics and Intelligent Systems
• Rocznik: 2011
• Tom: Vol. 5, No. 1
• Strony: 85--94
• Opis fizyczny: Bibliogr. 30 poz., rys.

Twórcy

autor

Gómez Santillán C.

autor

Cruz Reyes L.

autor

Schaeffer E.

autor

Meza E.

autor

Rivera Zarate G.

• Instituto Tecnológico de Ciudad Madero (ITCM). 1ro. de Mayo y Sor Juana I. de la Cruz s/n CP. 89440, Tamaulipas, México. Tel.: [phone] Ext. 3024 and Instituto Politécnico Nacional, Centro de Investigación en CienciaAplicada yTecnología Avan,

Bibliografia

• [1] Sakarayan G., A Content-Oriented Approach to Topology Evolution and Search in Peer-to-Peer Systems. PhD thesis, University of Rostock, 2004.
• [2] Wu L.-S., Akavipat R., Menczer F., “Adaptive query routing in peerWeb search”. In: Proc. 14 International WorldWideWeb Conference, 2005, pp. 1074 1075.
• [3] Michlmayr E. Ant Algorithms for Self-Organization in Social Networks, PhD thesis, Vienna University of Technology, 2007.
• [4] Mihail M., SaberiA.,Tetali P., “Random walks with look ahead in power law random graphs”, Internet Mathematics, no. 3, 2004.
• [5] Tempich C., Staab S.,WranikA., “REMINDIN': Semantic Query Routing in Peer-to-Peer Networks based on Social Metaphers” , in: 13 WorldWideWeb Conference (WWW), 2004.
• [6] Dorigo M., Gambardella L.M. ”Ant colony system: A cooperative learning approach to the traveling sales man problem”, IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, 1997, pp. 53 66.
• [7] Cruz L., Gómez C., Aguirre M., Schaeffer S., Turrubiates T., Ortega R., Fraire H., NAS algorithm for semantic query routing systems in complex networks. In: DCAI Advances in Soft Computing, vol. 50, 2008, pp. 284 292.
• [8] Diestel R., “Graph Theory” Graduate Texts in Mathematics, vol. 173, Springer-Verlag:NewYork, USA, 2000.
• [9] Costa L., Rodríguez F.A., Travieso G., Villas P.R., “Characterization of complex networks: A survey of measurements”, Advances in Physics, no. 56, 2007, pp. 167 242.
• [10] Erdos P., Rényi A.,On the evolution of random graphs, vol. 2, Akademiai Kiad'o, Budapest, Hungary, 1976. First publication in MTA Mat. Kut. Int. Kozl. 1960, pp. 482 525.
• [11] Gilbert E., “Random graphs”, Annals of Mathematical Statistics, 30(4), Dec. 1959, pp. 1141 1144.
• [12] Bollobás B., Random Graphs Cambridge Studies in Advanced Mathematics., vol. 73, Cambridge University Press, Cambridge, UK, 2 edition, 2001.
• [13] Adamic L., Huberman B., ”Power-law distribution of the World Wide Web”. Science, no. 287(5461), 2000, p. 2115.
• [14] Albert R., Jeong H., Barabási A., “Error and attack tolerance of complex networks”. Nature, no. 506, 2000, pp. 378 382.
• [15] Faloutsos M., Faloutsos P., Faloutsos C., “On power-law relationship on the internet topology”. ACM SIGCOMM Computer Communication Review, 1999, pp. 251 262.
• [16] Barabási A., Emergence of scaling in complex networks WileyVHC, 2003, pp. 69-82.
• [17] Newman M. E. J., “Power laws, pareto distributions andzipf's law”, Contemporary Physics, vol. 46(5), 2005, pp. 323 351.
• [18] Birattari M., The Problem of Tunning Mataheuristics as Seen From a Machine Learning Perspective. PhD thesis, Bruxelles University, 2004.
• [19] Glover F., Laguna M., Tabú Search. Kluwer Academic Publishers, 1986.
• [20] Holland J.H., Adaptation in natural and artificial systems. MITPress, Cambridge,MA,USA, 1992.
• [21] Amaral L., Ottino J., “Complex systems and networks: Challenges and opportunities for chemical and biological engineers”. Chemical Engineering Scientist, no. 59 2004, pp. 1653 1666.
• [22] Liu L., Xiao Long J., Kwock C.C., “Autonomy oriented computing from problem solving to complex system modeling”. In: Springer Science + Business Media Inc, 2005, pp. 27 54,
• [23] Wu C.-J., Yang K.-H., Ho. J.M., “AntSearch: An ant search algorithm in unstructured peer-to-peer networks”. In: ISCC, 2006, pp. 429 434.
• [24] Goldberg P., Papadimitriou C., “Reducibility among equilibrium problems”. In: Proceedings of the 38 annual ACM symposium on Theory of Computing, NewYork,NY, USA, 2005, pp. 61 70.
• [25] Michlmayr E., PanyA., Kappel G., “UsingTaxo nomies for Content-based Routing with Ants”. In: Proceedings of the Workshop on Innovations in Web Infrastruc'ture, 15 International World Wide Web Conference (WWW2006), May2006.
• [26] Ortega R., Estudio de las Propiedades Topológicas en Redes Complejas con Diferente Distribución del Grado y su Aplicación en la Búsqueda de Recursos Distribuidos, PhD thesis, Instituto Politécnico Nacional, México, 2009. (in Spanish)
• [27] Barabási A., Albert R., Jeong H., “Mean-field theory for scale-free random networks”, Physical Review Letters, no. 272, 1999, pp. 173 189.
• [28] Babaoglu O., Meling H., Montresor A., “Anthill: An framework for the development of agent-based peer to peer systems”. In: 22 InternationalConference On Distributed Computing Systems, ACM,2002.
• [29] Ridge E., Design of Expirements for the Tuning of Optimization Algorithms, PhD thesis,University ofYork, 2007.
• [30] Ridge E., Kudenko D., “Tuning the Performance of the MMAS Heuristic in Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics Lecture Notes in Computer Science, vol. 4638, T. Stutzle, M. Birattari, Eds. Berlin / Heidelberg: Springer, 2007, ISBN 978-3-540-74445-0, pp. 46-60.