Zur Kurzanzeige

Evolving Distributed Algorithms with Genetic Programming

dc.date.accessioned2009-05-11T09:01:58Z
dc.date.available2009-05-11T09:01:58Z
dc.date.issued2009-05-11T09:01:58Z
dc.identifier.uriurn:nbn:de:hebis:34-2009051127217
dc.identifier.urihttp://hdl.handle.net/123456789/2009051127217
dc.format.extent11183983 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoeng
dc.rightsUrheberrechtlich geschützt
dc.rights.urihttps://rightsstatements.org/page/InC/1.0/
dc.subjectGenetic Programmingeng
dc.subjectDistributed Systemseng
dc.subjectDistributed Algorithmeng
dc.subjectEvolutionary Algorithmeng
dc.subjectRule-based Genetic Programmingeng
dc.subjectRBGPeng
dc.subjectextended Rule-based Genetic Programmingeng
dc.subjecteRBGPeng
dc.subjectStandard Genetic Programmingeng
dc.subjectSGPeng
dc.subjectExtended Standard Genetic Programmingeng
dc.subjecteSGPeng
dc.subjectLinear Genetic Programmingeng
dc.subjectLGPeng
dc.subjectFragletseng
dc.subjectElectioneng
dc.subjectCritical Sectioneng
dc.subjectMutual Exclusioneng
dc.subjectGreatest Common Divisoreng
dc.subjectLearning Classifier Systemseng
dc.subjectLCSeng
dc.subjectMetaheuristic Optimizationeng
dc.subjectRuggednesseng
dc.subjectEpistasiseng
dc.subjectNeutralityeng
dc.subjectRedundancyeng
dc.subjectRobustnesseng
dc.subjectCorrectnesseng
dc.subjectAdequacyeng
dc.subjectBloateng
dc.subjectOverfittingeng
dc.subjectPositional Epistasiseng
dc.subjectRoutingeng
dc.subjectProtocolseng
dc.subjectPremature Convergenceeng
dc.subjectNeedle-In-A-Haystackeng
dc.subjectAll-Or-Nothingeng
dc.subjectIndexed Memoryeng
dc.subjectGlobal Memoryeng
dc.subjectLocal Memoryeng
dc.subjectStackeng
dc.subjectAutomatically Defined Functioneng
dc.subjectADFeng
dc.subjectMessage Handlereng
dc.subjectAnsynchroneeng
dc.subject.ddc004
dc.titleEvolving Distributed Algorithms with Genetic Programmingeng
dc.typeDissertation
dcterms.abstractDistributed 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.eng
dcterms.accessRightsopen access
dcterms.creatorWeise, Thomas
dc.contributor.corporatenameKassel, Universität, FB 16, Elektrotechnik/Informatik
dc.contributor.refereeGeihs, Kurt (Prof. Dr.)
dc.contributor.refereeTschudin, Christian (Prof. Dr.)
dc.description.everythingDiese Arbeit wurde 2011 mit dem Dissertationspreis des VDI-Nordhessen ausgezeichnet.ger
dc.subject.ccsC.0 GENERAL [Instruction set design]
dc.subject.ccsC.0 GENERAL [Systems specification methodology]
dc.subject.ccsC.1.4 Parallel Architectures [Distributed architectures]
dc.subject.ccsC.2.2 Network Protocols
dc.subject.ccsC.2.4 Distributed Systems
dc.subject.ccsD.1.2 Automatic Programming
dc.subject.ccsD.1.3 Concurrent Programming [Distributed programming]
dc.subject.ccsD.2.0 General
dc.subject.ccsD.2.1 Requirements/Specifications [Methodologies]
dc.subject.ccsD.3.0 General
dc.subject.ccsD.3.2 Language Classifications [Concurrent, distributed, and parallel languages]
dc.subject.ccsG.1.6 Optimization
dc.subject.ccsI.2.2 Automatic Programming [Program synthesis]
dc.subject.ccsI.2.5 Programming Languages and Software
dc.subject.ccsI.6.0 General
dc.subject.ccsI.6.8 Types of Simulation [Parallel]
dc.subject.msc90-02 Research exposition (monographs, survey articles)eng
dc.subject.msc90-08 Computational methodseng
dc.subject.msc90B18 Communication networkseng
dc.subject.msc68M12 Network protocolseng
dc.subject.msc68M14 Distributed systemseng
dc.subject.msc94A99 None of the above, but in this sectioneng
dc.subject.msc90B40 Search theoryeng
dc.subject.msc90C56 Derivative-free methodseng
dc.subject.msc90C59 Approximation methods and heuristicseng
dc.subject.msc90C90 Applications of mathematical programmingeng
dc.subject.msc92B20 Neural networks, artificial life and related topicseng
dc.subject.msc68T05 Learning and adaptive systemseng
dc.subject.swdGenetische Programmierungger
dc.subject.swdVerteilter Algorithmusger
dc.date.examination2009-05-04


Dateien zu dieser Ressource

Thumbnail
Name:
DissertationThomasWeise.pdf
Größe:
8.022Mb
Format:
PDF
Öffnen

Das Dokument erscheint in:

Zur Kurzanzeige