Evolving Distributed Algorithms with Genetic Programming

Created by W.Langdon from gp-bibliography.bib Revision:1.4202

  author =       "Thomas Weise and Ke Tang",
  title =        "Evolving Distributed Algorithms with Genetic
  journal =      "IEEE Transactions on Evolutionary Computation",
  year =         "2012",
  volume =       "16",
  number =       "2",
  pages =        "242--265",
  month =        apr,
  keywords =     "genetic algorithms, genetic programming, Algorithm
                 design and analysis, Approximation algorithms,
                 Computational modelling, Distributed algorithms,
                 Optimisation, Protocols, Critical section, GCD, LGP,
                 SGP, distributed algorithms, election, distributed
                 greatest common divisor DGCD fraglets, mutual
                 exclusion, rule-based genetic programming, SBSE",
  ISSN =         "1089-778X",
  DOI =          "doi:10.1109/TEVC.2011.2112666",
  size =         "24 pages",
  abstract =     "In this paper, 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 tree-based and linear GP) in order
                 to make them suitable for representing distributed
                 algorithms. Third, we introduce novel rule-based GP
                 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.",
  notes =        "Indexed memory, scope, MOGP, Pareto (size v fitness
                 not just for anti bloat reasons), GCD, Election
                 (distributed smallest), mutual exclusion-distributed
                 locking, LCS, rule-based genetic programming RBGP,
                 eRBGP, Turing complete, tree GP, linear GP LGP, ADF,
                 for loop, while loop, jmp, call, fraglets
                 \cite{conf/wac/YamamotoT05}, interrupt service routine,
                 various network connections. Statements like evolved
                 'algorithm is not correct' section VI-B which seem at
                 odds with rest of text. Population 512, 700+
                 generation, homologous multipoint crossover, subtree
                 crossover, 4 types of mutation. comparison with random
                 walk. GP run 8 minutes. marginal fairness CSMA. Also
                 known as \cite{6026925}",

Genetic Programming entries for Thomas Weise Ke Tang