Evolving Distributed Algorithms with Genetic Programming

Authors

Abstract

In this article, we evaluate the applicability of Genetic Programming (GP) for the evolution of distributed algorithms. We carry out a large-scale experimental study in which we tackle three well-known problems from distributed computing with six different program representations. For this purpose, we first define a simulation environment in which phenomena such as asynchronous computation at changing speed and messages taking over each other, i.e., out-of-order message delivery, occur with high probability. Second, we define extensions and adaptations of established GP approaches (such as treebased and Linear Genetic Programming) in order to make them suitable for representing distributed algorithms. Third, we introduce novel rule-based Genetic Programming methods designed especially with the characteristic difficulties of evolving algorithms (such as epistasis) in mind. Based on our extensive experimental study of these approaches, we conclude that GP is indeed a viable method for evolving non-trivial, deterministic, non-approximative distributed algorithms. Furthermore, one of the two rule-based approaches is shown to exhibit superior performance in most of the tasks and thus can be considered as an interesting idea also for other problem domains.

Keywords

Standard Genetic Programming, SGP, Linear Genetic Programming, LGP, Rule-based Genetic Programming, RBGP, Distributed Algorithms and Systems, Election, Critical Section/Mutual Exclusion, Greatest Common Divisor, GCD, Loops, Communication, Epistasis, Neutrality, Causality, Robustness in Optimization

BibTeX

@article{WT2011EVDAWGP,
  author                    = {Thomas Weise and K{\={e}} T{\'{a}}ng},
  title                     = {{Evolving Distributed Algorithms with Genetic Programming}},
  publisher                 = {{IEEE Computer Society: {Washington, DC, USA}}},
  journal                   = {IEEE Transactions on Evolutionary Computation (IEEE-EC)},
  number                    = {2},
  volume                    = {16},
  year                      = {2011},
  doi                       = {10.1109/TEVC.2011.2112666},
  key                       = {WT2011EVDAWGP},
},

Links