Exploring selection mechanisms for an agent-based distributed evolutionary algorithm

ABSTRACT

In this paper we propose an agent-based model of evolutionary algorithms (EAs) which extends seamlessly from concurrent single-host to distributed multi-host installations. Since the model is based on locally executable selection, we focus on the comparison of two selection mechanisms which accomplish with such a restriction: the classical tournament method and a new one called autonomous selection. Using the latter method the population size changes during runtime, hence it is not only interesting as a new selection mechanism, but also from the perspective of scalable networks.

REFERENCES

• 1: Maribel García Arenas , Pierre Collet , A. E. Eiben , Márk Jelasity , Juan J. Merelo Guervós , Ben Paechter , Mike Preuß , Marc Schoenauer, A Framework for Distributed Evolutionary Algorithms, Proceedings of the 7th International Conference on Parallel Problem Solving from Nature, p.665-675, September 07-11, 2002
• 2: Johan Berntsson, G2DGA: an adaptive framework for internet-based distributed genetic algorithms, Proceedings of the 2005 workshops on Genetic and evolutionary computation, June 25-26, 2005, Washington, D.C. [doi>10.1145/1102256.1102333]
• 3: E. Cantú-Paz. Topologies, migration rates, and multi-population parallel genetic algorithms. In W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. Jakiela, and R. E. Smith, editors, Proceedings of the Genetic and Evolutionary Computation Conference, volume 1, pages 91--98, Orlando, Florida, USA, 13-17 July 1999. Morgan Kaufmann.
• 4: Erick Cantu-Paz, Efficient and Accurate Parallel Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2000
• 5: Diego Doval , Donal O'Mahony, Overlay Networks: A Scalable Alternative for P2P, IEEE Internet Computing, v.7 n.4, p.79-82, July 2003 [doi>10.1109/MIC.2003.1215663]
• 6: A. Eiben, E. Marchiori, and V. Valkó. Evolutionary algorithms with on-the-fly population size adjustment. In Parallel Problem Solving from Nature - PPSN VIII, volume 3242 of LNCS, pages 41--50, Birmingham, UK, September 2004. Springer-Verlag.
• 7: Agoston E. Eiben , J. E. Smith, Introduction to Evolutionary Computing, SpringerVerlag, 2003
• 8: I. Hidalgo and F. Fernández. Balancing the computatione Evolutionary Computation, 2005. The 2005 IEEE Congress on, volume 2, pages 1645--1652. IEEE Press, 2005.
• 9: Márk Jelasity , Alberto Montresor , Ozalp Babaoglu, Gossip-based aggregation in large dynamic networks, ACM Transactions on Computer Systems (TOCS), v.23 n.3, p.219-252, August 2005 [doi>10.1145/1082469.1082470]
• 10: M. Jelasity and M. van Steen. Large-scale newscast computing on the Internet. Technical Report IR-503, Vrije Universiteit Amsterdam, Department of Computer Science, Amsterdam, The Netherlands, October 2002.
• 11: J. L. J. Laredo, P. Castillo, A. Mora, and J. Merelo. Estudio preliminar sobre auto adaptación en agentes evolutivos sobre arquitecturas heterogéneas. In XVII Jornadas de Paralelismo - XVII JP, pages 389--394, September 2006.
• 12: J. Laredo, E. Eiben, M. Schoenauer, P. Castillo, A. Mora, F. Fernández, and J. Merelo. Self-adaptive gossip policies for distributed population-based algorithms, 2007. http://arxiv.org/abs/cs/0703117.
• 13: E. Lawler, J. Lenstra, A. R. Kan, and D. Shmoys. The travelling salesman problem: A guided tour of combinatorial optimization. New York: Wiley and Sons, 1985.
• 14: W. Lee. Parallelizing evolutionary computation: A mobile agent-based approach. Expert Systems with Applications, 32(2):318--328, 2007.
• 15: Penny Nii, The blackboard model of problem solving, AI Magazine, v.7 n.2, p.38-53, Summer 1986
• 16: R. Steinmetz and K. Wehrle. What is this peer-to-peer about? In R. Steinmetz and K. Wehrle, editors, Peer-to-Peer Systems and Applications, volume 3485 of Lecture Notes in Computer Science, pages 9--16. Springer, 2005.
• 17: J.-P. Vacher , T. Galinho , F. Lesage , A. Cardon, Genetic Algorithms in a Multi-Agent System, Proceedings of the IEEE International Joint Symposia on Intelligence and Systems, p.17, March 21-23, 1998
• 18: E. Viveros and B. Barán. Algoritmos genéticos asíncronos combinados para una red heterogénea de computadoras. In Conferencia Internacional de Ciencia y Tecnología parael Desarrollo, 1997. http://www.cnc.una.py/cms/invest/download.php?id=46205,66.
• 19: S. Voulgaris, M. Jelasity, and M. van Steen. A robust and scalable peer-to-peer gossiping protocol. In Moro, Sartori, and Singh, editors, Agents and Peer-to-Peer Computing, volume 2872 of Lecture Notes in Computer Science (LNCS), pages 47--58. Springer Berlin/Heidelberg, 2004.
• 20: A Comparative Study of Five Parallel Genetic Algorithms using the Traveling Salesman Problem, Proceedings of the 12th. International Parallel Processing Symposium on International Parallel Processing Symposium, p.345, March 30-April 03, 1998

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms

Keywords:
genetic algorithms, multi-agents systems, parallelization, performance analysis, self-adaptation