Evolving Distributed Algorithms with Genetic Programming

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

@PhdThesis{Weise:thesis,
  author =       "Thomas Weise",
  title =        "Evolving Distributed Algorithms with Genetic
                 Programming",
  school =       "Department of Electrical Engineering and Computer
                 Science, University of Kassel",
  year =         "2009",
  address =      "Germany",
  month =        may,
  keywords =     "genetic algorithms, genetic programming",
  URL =          "https://kobra.bibliothek.uni-kassel.de/bitstream/urn:nbn:de:hebis:34-2009051127217/3/DissertationThomasWeise.pdf",
  size =         "264 pages",
  abstract =     "Distributed systems are one of the most vital
                 components of the economy. The most prominent example
                 is probably the internet, a constituent element of our
                 knowledge society. During the recent years, the number
                 of novel network types has steadily increased. Amongst
                 others, sensor networks, distributed systems composed
                 of tiny computational devices with scarce resources,
                 have emerged. The further development and heterogeneous
                 connection of such systems imposes new requirements on
                 the software development process. Mobile and wireless
                 networks, for instance, have to organize themselves
                 autonomously and must be able to react to changes in
                 the environment and to failing nodes alike. Researching
                 new approaches for the design of distributed algorithms
                 may lead to methods with which these requirements can
                 be met efficiently. In this thesis, one such method is
                 developed, tested, and discussed in respect of its
                 practical utility.

                 Our new design approach for distributed algorithms is
                 based on Genetic Programming, a member of the family of
                 evolutionary algorithms. Evolutionary algorithms are
                 metaheuristic optimization methods which copy
                 principles from natural evolution. They use a
                 population of solution candidates which they try to
                 refine step by step in order to attain optimal values
                 for predefined objective functions.

                 The synthesis of an algorithm with our approach starts
                 with an analysis step in which the wanted global
                 behavior of the distributed system is specified. From
                 this specification, objective functions are derived
                 which steer a Genetic Programming process where the
                 solution candidates are distributed programs. The
                 objective functions rate how close these programs
                 approximate the goal behavior in multiple randomized
                 network simulations. The evolutionary process step by
                 step selects the most promising solution candidates and
                 modifies and combines them with mutation and crossover
                 operators. This way, a description of the global
                 behavior of a distributed system is translated
                 automatically to programs which, if executed locally on
                 the nodes of the system, exhibit this behavior.

                 In our work, we test six different ways for
                 representing distributed programs, comprising
                 adaptations and extensions of well-known Genetic
                 Programming methods (SGP, eSGP, and LGP), one
                 bio-inspired approach (Fraglets), and two new program
                 representations called Rule-based Genetic Programming
                 (RBGP, eRBGP) designed by us. We breed programs in
                 these representations for three well-known example
                 problems in distributed systems: election algorithms,
                 the distributed mutual exclusion at a critical section,
                 and the distributed computation of the greatest common
                 divisor of a set of numbers.

                 Synthesizing distributed programs the evolutionary way
                 does not necessarily lead to the envisaged results. In
                 a detailed analysis, we discuss the problematic
                 features which make this form of Genetic Programming
                 particularly hard. The two Rule-based Genetic
                 Programming approaches have been developed especially
                 in order to mitigate these difficulties. In our
                 experiments, at least one of them (eRBGP) turned out to
                 be a very efficient approach and in most cases, was
                 superior to the other representations.",
  zusammenfassung = "Verteilte Systeme stellen eine der wichtigsten
                 Komponenten der Wirtschaft dar. Das wohl bekannteste
                 solche System, das Internet, ist zentraler Bestandteil
                 unserer Wissensgesellschaft. In den letzten Jahren hat
                 die Anzahl neuartiger Netzwerke stetig zugenommen. So
                 entstanden unter Anderem mit Sensornetzen auch
                 verteilte Systeme, die aus kleinen, in ihren Ressourcen
                 stark begrenzten, Knoten bestehen. Die stetige
                 Weiterentwicklung und heterogene Vermaschung solcher
                 Systeme stellt neue Anforderungen an die
                 Softwarearchitekten. Mobile und kabellose Netze mussen
                 sich beispielsweise selbststuandig organisieren und
                 autonom auf ausfallende Knoten oder sich uandernde
                 Umgebungsvariablen reagieren. Um diesen Anforderungen
                 entgegenzutreten ist es daher notwendig, neue Methoden
                 fuur den Entwurf verteilter Systeme verstuarkt zu
                 erforschen. Ziel dieser Arbeit ist es, einen solchen
                 neuen Ansatz zu entwickeln, zu erproben und im Hinblick
                 auf seine praktische Anwendbarkeit zu
                 diskutieren.

                 Unser neuer Ansatz zur Synthese verteilter Algorithmen
                 basiert auf der Genetischen Programmierung, einem
                 Mitglied der Familie der evolutionuaren Algorithmen.
                 Evolutionuare Algorithmen sind der natuurlichen
                 Evolution nachempfundene, metaheuristische
                 Optimierungsverfahren. Sie verwenden eine Population
                 von vielen Luosungskandidaten und versuchen, diese
                 schrittweise immer weiter anzupassen, um optimale Werte
                 fuur vorher definierte Zielfunktionen zu erreichen.

                 Die Erzeugung eines verteilten Algorithmus mit unserem
                 Ansatz beginnt mit einer Analysephase, in der das
                 gewuunschte globale Verhalten eines Systems
                 spezifiziert wird. Aus dieser Spezifikation werden
                 Zielfunktionen abgeleitet, die den Prozess der
                 Genetischen Programmierung steuern, bei dem die
                 Luosungskandidaten verteilte Programme sind. Die
                 Zielfunktionen bewerten, wie weit diese Programme das
                 spezifizierte Verhalten in mehreren zufallsbasierten
                 Netzwerksimulation annuahern. Schritt fuur Schritt
                 wuahlt der evolutionuare Prozess die
                 vielversprechendsten Luosungskandidaten aus und
                 veruandert und kombiniert sie mit Hilfe von Mutations-
                 und Crossover-Operatoren. Auf diese Weise wird die
                 Beschreibung des globalen Verhaltens eines verteilten
                 Systems vollautomatisch in Programme umgerechnet, die
                 dieses Verhalten erreichen, wenn sie lokal auf seinen
                 Knoten ausgefuuhrt werden. In unserer Arbeit testen wir
                 sechs verschiedene Darstellungsformen verteilter
                 Programme auf ihre Tauglichkeit zu diesem Zweck. Drei
                 davon sind Anpassungen und Erweiterungen bekannter
                 Ansuatze (SGP, eSGP, LGP), eine stammt aus der
                 biologisch-inspirierten Forschung (Fraglets) und zwei
                 neue Methoden, genannt Regelbasierte Genetische
                 Programmierung, wurden von uns selbst entwickelt (RBGP,
                 eRBGP). In unseren Experimenten zuuchten wir mit diesen
                 Darstellungsformen Programme fuur drei bekannte
                 Beispielprobleme in verteilten Systemen:
                 Wahlalgorithmen, den verteilte wechselseitige
                 Ausschluss am kritischen Abschnitt und die verteilte
                 Berechnung des gruossten gemeinsamen Teilers einer
                 Menge von natuurlichen Zahlen.

                 Die evolutionuare Synthese von verteilten Programmen
                 fuuhrt nicht immer zum gewuunschten Ziel. In einer
                 ausfuuhrlichen Analyse legen wir die Eigenschaften dar,
                 welche diese Form der Genetischen Programmierung
                 besonders schwer machen. Die beiden regelbasierten
                 Ansuatze wurden speziell auf Basis dieser Analyse
                 entworfen. In den Experimenten stellte sich einer der
                 beiden (die erweiterte regelbasierte Genetische
                 Programmierung eRBGP) als besonders effizient
                 heraus.

                 Eine ausfuuhrliche deutsche Zusammenfassung dieser
                 Dissertation ist in Chapter E auf Seite 207
                 enthalten.",
  notes =        "1st Reviewer: Prof. Dr. Kurt Geihs (University of
                 Kassel) 2nd Reviewer: Prof. Dr. Christian Tschudin
                 (University of Basel) Date of Defense: 2009-05-04",
}

Genetic Programming entries for Thomas Weise

Citations