Dissertation
Evolving Distributed Algorithms with Genetic Programming
Zusammenfassung
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.
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.
Zitieren
@phdthesis{urn:nbn:de:hebis:34-2009051127217,
author={Weise, Thomas},
title={Evolving Distributed Algorithms with Genetic Programming},
school={Kassel, Universität, FB 16, Elektrotechnik/Informatik},
month={05},
year={2009}
}
0500 Oax 0501 Text $btxt$2rdacontent 0502 Computermedien $bc$2rdacarrier 1100 2009$n2009 1500 1/eng 2050 ##0##urn:nbn:de:hebis:34-2009051127217 3000 Weise, Thomas 4000 Evolving Distributed Algorithms with Genetic Programming / Weise, Thomas 4030 4060 Online-Ressource 4085 ##0##=u http://nbn-resolving.de/urn:nbn:de:hebis:34-2009051127217=x R 4204 \$dDissertation 4170 5550 {{Genetische Programmierung}} 5550 {{Verteilter Algorithmus}} 7136 ##0##urn:nbn:de:hebis:34-2009051127217
2009-05-11T09:01:58Z 2009-05-11T09:01:58Z 2009-05-11T09:01:58Z urn:nbn:de:hebis:34-2009051127217 http://hdl.handle.net/123456789/2009051127217 11183983 bytes application/pdf eng Urheberrechtlich geschützt https://rightsstatements.org/page/InC/1.0/ Genetic Programming Distributed Systems Distributed Algorithm Evolutionary Algorithm Rule-based Genetic Programming RBGP extended Rule-based Genetic Programming eRBGP Standard Genetic Programming SGP Extended Standard Genetic Programming eSGP Linear Genetic Programming LGP Fraglets Election Critical Section Mutual Exclusion Greatest Common Divisor Learning Classifier Systems LCS Metaheuristic Optimization Ruggedness Epistasis Neutrality Redundancy Robustness Correctness Adequacy Bloat Overfitting Positional Epistasis Routing Protocols Premature Convergence Needle-In-A-Haystack All-Or-Nothing Indexed Memory Global Memory Local Memory Stack Automatically Defined Function ADF Message Handler Ansynchrone 004 Evolving Distributed Algorithms with Genetic Programming Dissertation 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. open access Weise, Thomas Kassel, Universität, FB 16, Elektrotechnik/Informatik Geihs, Kurt (Prof. Dr.) Tschudin, Christian (Prof. Dr.) Diese Arbeit wurde 2011 mit dem Dissertationspreis des VDI-Nordhessen ausgezeichnet. C.0 GENERAL [Instruction set design] C.0 GENERAL [Systems specification methodology] C.1.4 Parallel Architectures [Distributed architectures] C.2.2 Network Protocols C.2.4 Distributed Systems D.1.2 Automatic Programming D.1.3 Concurrent Programming [Distributed programming] D.2.0 General D.2.1 Requirements/Specifications [Methodologies] D.3.0 General D.3.2 Language Classifications [Concurrent, distributed, and parallel languages] G.1.6 Optimization I.2.2 Automatic Programming [Program synthesis] I.2.5 Programming Languages and Software I.6.0 General I.6.8 Types of Simulation [Parallel] 90-02 Research exposition (monographs, survey articles) 90-08 Computational methods 90B18 Communication networks 68M12 Network protocols 68M14 Distributed systems 94A99 None of the above, but in this section 90B40 Search theory 90C56 Derivative-free methods 90C59 Approximation methods and heuristics 90C90 Applications of mathematical programming 92B20 Neural networks, artificial life and related topics 68T05 Learning and adaptive systems Genetische Programmierung Verteilter Algorithmus 2009-05-04
Die folgenden Lizenzbestimmungen sind mit dieser Ressource verbunden:
:Urheberrechtlich geschützt
Verwandte Dokumente
Anzeige der Dokumente mit ähnlichem Titel, Autor, Urheber und Thema.
-
Technischer ReportApplicability of Emergence Engineering to Distributed Systems Scenarios Zapf, Michael; Weise, Thomas (2009-01-09)
-
Technischer ReportOffline Emergence Engineering For Agent Societies Zapf, Michael; Weise, Thomas (2007-12-07)
-
Technischer ReportGlobal Optimization Algorithms and their Application to Distributed Systems Weise, Thomas; Skubch, Hendrik; Zapf, Michael; Geihs, Kurt (2008-10-14)