research-article

Percolation analyses in a swarm based algorithm for shortest-path finding

Authors:

Bruno Panerai Velloso,

Mauro RoisembergAuthors Info & Claims

SAC '08: Proceedings of the 2008 ACM symposium on Applied computing

Pages 1861 - 1865

https://doi.org/10.1145/1363686.1364136

Published: 16 March 2008 Publication History

Get Access

Abstract

In this paper we show that the convergence in the Ant Colony Optimization (ACO) algorithm can be described as a "phase- transition" phenomenon. The analysis of the ACO with the Percolation Theory approach includes: the pheromone evaporation and the number of agents parameters, so, for a given routing environment, it is possible to select these parameters in order to ensure convergence and to avoid overhead in the algorithm. The objective of this work is to present some experiments that support our hypothesis and to show the methodology used to correlate some algorithm parameters and how they influence in its general performance.

References

[1]

H. M. Balch T. Social potentials for scalable multi-robot formations. IEEE International Conference on Robotics and Automation, 2000.

Crossref

Google Scholar

[2]

T. G. Bonabeau E., Dorigo M. Swarm Intelligence: From Natural to Artificial Systems. MIT Press, Cambridge, MA, 1999.

Digital Library

Google Scholar

[3]

A. R. C. Behavior-Based Robotics. MIT Press, Cambridge, MA, 1998.

Google Scholar

[4]

A. Efros. Fisica y Geometria del Desorden. Ed. Mir, Moscow, 1987. traslated. Belosov, S.

Google Scholar

[5]

W. H. S. Kwang M. S. Ant colony optimization for routing and load-balancing: Survey and new direction. IEEE Transaction on systems, man, and cybernetics, Vol 33(No. 5), September 2003.

Digital Library

Google Scholar

[6]

H. R. Leung H. Phase transition in a swarm algorithm for self-organized construction. Physical Review, (E. 68), 2003.

Google Scholar

[7]

K. R. Leung H. Self-organized construction of spatial structures by swarms of autonomous mobile agents. Master's thesis, College of Engineering. University of Cincinnate., 2003.

Google Scholar

[8]

A. A. Stauffer D. Percolation Theory. Taylor and Francis, London, 1992.

Google Scholar

Cited By

View all

Yi BYang FQiao HXu C(2010)Bidirectional Search Algorithm Based-On Index for Shortest Path Problem2010 International Conference on Computational Intelligence and Software Engineering10.1109/CISE.2010.5676739(1-4)Online publication date: Dec-2010
https://doi.org/10.1109/CISE.2010.5676739
Raghavendra GBorase APrasanna K(2009)Performance analysis for the enhancement of ACO algorithms using Fourier transform2009 World Congress on Nature & Biologically Inspired Computing (NaBIC)10.1109/NABIC.2009.5393476(708-712)Online publication date: Dec-2009
https://doi.org/10.1109/NABIC.2009.5393476

Index Terms

Percolation analyses in a swarm based algorithm for shortest-path finding
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Discrete space search
      2. Game tree search

Recommendations

Theory of swarm intelligence
GECCO Comp '14: Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation

Social animals as found in fish schools, bird flocks, bee hives, and ant colonies are able to solve highly complex problems in nature. This includes foraging for food, constructing astonishingly complex nests, and evading or defending against predators. ...
Theory of Swarm Intelligence
GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation

Social animals as found in fish schools, bird flocks, bee hives, and ant colonies are able to solve highly complex problems in nature. This includes foraging for food, constructing astonishingly complex nests, and evading or defending against predators. ...
Hybridization strategies for continuous ant colony optimization and particle swarm optimization applied to data clustering

Ant colony optimization (ACO) and particle swarm optimization (PSO) are two popular algorithms in swarm intelligence. Recently, a continuous ACO named ACOR was developed to solve the continuous optimization problems. This study incorporated ACOR with ...

Comments

Information & Contributors

Information

Published In

SAC '08: Proceedings of the 2008 ACM symposium on Applied computing

March 2008

2586 pages

ISBN:9781595937537

DOI:10.1145/1363686

Conference Chairs:
Roger L. Wainwright
University of Tulsa
,
Hisham M. Haddad
Kennesaw State University

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 March 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SAC '08

Sponsor:

SIGAPP

SAC '08: The 2008 ACM Symposium on Applied Computing

March 16 - 20, 2008

Fortaleza, Ceara, Brazil

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
233
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Yi BYang FQiao HXu C(2010)Bidirectional Search Algorithm Based-On Index for Shortest Path Problem2010 International Conference on Computational Intelligence and Software Engineering10.1109/CISE.2010.5676739(1-4)Online publication date: Dec-2010
https://doi.org/10.1109/CISE.2010.5676739
Raghavendra GBorase APrasanna K(2009)Performance analysis for the enhancement of ACO algorithms using Fourier transform2009 World Congress on Nature & Biologically Inspired Computing (NaBIC)10.1109/NABIC.2009.5393476(708-712)Online publication date: Dec-2009
https://doi.org/10.1109/NABIC.2009.5393476

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Theory of swarm intelligence

Theory of Swarm Intelligence

Hybridization strategies for continuous ant colony optimization and particle swarm optimization applied to data clustering

Comments

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Other Metrics

Article Metrics

Other Metrics

Cited By

Login options

Full Access

PDF

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Theory of swarm intelligence

Theory of Swarm Intelligence

Hybridization strategies for continuous ant colony optimization and particle swarm optimization applied to data clustering

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Get Access

Login options

Full Access

View options

PDF

eReader

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations