Peer-to-peer evolutionary algorithms with adaptive autonomous selection

ABSTRACT

In this paper we describe and evaluate a fully distributed P2P evolutionary algorithm (EA) with adaptive autonomous selection. Autonomous selection means that decisions regarding survival and reproduction are taken by the individuals themselves independently, without any central control.This allows for a fully distributed EA, where not only reproduction (crossover and mutation) but also selection is performed at local level. An unwanted consequence of adding and removing individuals in a non-synchronized manner is that the population size gets out of control too. This problem is resolved by addingan adaptation mechanism allowing individuals to regulate their own selection pressure. The key tothis is a gossiping algorithm that enables individuals to maintain estimates on the size andthe fitness of the population. The algorithm is experimentally evaluated on a test problem to show the viability of the idea and to gain insight into the run-time dynamics of such an algorithm. The results convincingly demonstrate the feasibility of a fully decentralized EA in which the population size can be kept stable.

REFERENCES

• 1: E. Alba and B. Dorronsoro. The exploration/exploitation tradeoff in dynamic cellular genetic algorithms. IEEE Transactions on Evolutionary Computation, 9(2):126--142, 2005.
• 2: E. Alba, B. Dorronsoro, M. Giacobini, and M. Tomassini. Decentralized cellular evolutionary algorithms. In S. Olariu and A. Y. Zomaya, editors, Handbook of Bioinspired Algorithms and Applications, volume 7 of Chapman and HallCRC Computer and Information Science Series, pages 103--120. 2005.
• 3: E. Alba and M. Tomassini. Parallelism and evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 6(5):443--462, 2002.
• 4: E. Cantú-Paz and D. Goldberg. Efficient Parallel Genetic Algorithms: Theory and Practice. Computer Methods in Applied Mechanics and Engineering, 186:221--238, 2000.
• 5: Kenneth A. De Jong , Jayshree Sarma, On Decentralizing Selection Algorithms, Proceedings of the 6th International Conference on Genetic Algorithms, p.17-23, July 15-19, 1995
• 6: A. Eiben, R. Hinterding, and Z. Michalewicz. Parameter control in evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 3(2):124--141, 1999.
• 7: A. E. Eiben , Marc Schoenauer , D. W. F. van Krevelen , M. C. Hobbelman , M. A. ten Hagen , R. C. van het Schip, Autonomous selection in evolutionary algorithms, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277235]
• 8: Agoston E. Eiben , J. E. Smith, Introduction to Evolutionary Computing, SpringerVerlag, 2003
• 9: L. J. Eshelman. The chc adaptive search algorithm: How to have safe search when engaging in nontraditional genetic recombination. In G. J. E. Rawlins, editor, Proceedings of the First Workshop on Foundations of Genetic Algorithms, pages 265--283. Morgan Kaufmann, 1991.
• 10: C. Fry and M. Reiter. Really truly trackerless bittorrent. Technical Report CMU-CS-06-148, Carnegie Mellon University, Aug. 2006.
• 11: Martina Gorges-Schleuter, A Comparative Study of Global and Local Selection in Evolution Strategies, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.367-377, September 27-30, 1998
• 12: Márk Jelasity , Rachid Guerraoui , Anne-Marie Kermarrec , Maarten van Steen, The peer sampling service: experimental evaluation of unstructured gossip-based implementations, Proceedings of the 5th ACM/IFIP/USENIX international conference on Middleware, October 18-22, 2004, Toronto, Canada
• 13: 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]
• 14: M. Jelasity, S. Volgaris, R. Guerraoui, A. -M. Kermarrec, and M. van Steen. Gossip based peer sampling. Technical report, Vrije Universiteit, 2004.
• 15: A Gossip Protocol for Subgroup Multicast, Proceedings of the 21st International Conference on Distributed Computing Systems, p.25, April 16-19, 2001
• 16: G. P. Jesi. Peersim, a peer-to-peer simulator. http://peersim.sourceforge.net/.
• 17: David Kempe , Alin Dobra , Johannes Gehrke, Gossip-Based Computation of Aggregate Information, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.482, October 11-14, 2003
• 18: V. K. Koumousis and C. P. Katsaras. A saw-tooth genetic algorithm combining the effects of variable population size and reinitialization to enhance performance. IEEE Trans. Evolutionary Computation, 10(1):19--28, 2006.
• 19: N. Melab , M. Mezmaz , E-G. Talbi, Parallel Hybrid Multi-Objective Island Model in Peer-to-Peer Environment, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 6, p.190.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.327]
• 20: G. Pierre and M. van Steen. Globule: A Collaborative Content Delivery Network. IEEE Communications Magazine, 44(8):127--133, Aug. 2006.
• 21: Günter Rudolph, On Risky Methods for Local Selection under Noise, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.169-177, September 27-30, 1998
• 22: Marco Tomassini, Spatially Structured Evolutionary Algorithms: Artificial Evolution in Space and Time (Natural Computing Series), Springer-Verlag New York, Inc., Secaucus, NJ, 2005

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms, Experimentation

Keywords:
autonomous selection, distributed EA, gossiping, newscast protocol, parameter adaptation