- 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",
