Evolving Distributed Algorithms with Genetic Programming

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.

Die Natur als Erholungs(t)raum

Zur Erholung in die Natur gehen oder doch lieber zur Natursimulation greifen? Intuitiv würden die meisten Menschen der Natur einen größeren Erholungswert zusprechen als einer Natursimulation. Aber ist die Natur tatsächlich erholsamer? In der Naturerholungsforschung (Restorative Environment Research) kommen häufig Natursimulationen zum Einsatz, um die erholsame Wirkung von Natur zu ermitteln. Problematisch ist dabei, dass deren ökologische Validität und Vergleichbarkeit noch nicht empirisch abgesichert ist. Vorliegende Arbeit setzt an dieser methodischen und empirischen Lücke an. Sie überprüft sowohl die ökologische Validität als auch die Vergleichbarkeit von Natursimulationen. Dazu wird die erholsame Wirkung von zwei Natursimulationen im Vergleich zu der physisch-materiellen Natur empirisch untersucht und verglichen. Darüber hinaus werden Aspekte des subjektiven Erlebens und der Bewertung im Naturerholungskontext exploriert. Als bedeutsamer Wirkmechanismus wird die erlebnisbezogene Künstlichkeit/Natürlichkeit angesehen, die sich auf die Erlebnisqualität von Natursimulationen und der physisch-materiellen Natur bezieht: Natursimulationen weisen im Vergleich zur physisch-materiellen Natur eine reduzierte Erlebnisqualität auf (erlebnisbezogene Künstlichkeit), z.B. eine reduzierte Qualität und Quantität der Sinnesansprache. Stellt man einen derartigen Vergleich nicht nur mit der physisch-materiellen Natur, sondern mit unterschiedlichen Natursimulationstypen an, dann zeigen sich auch hier Unterschiede in der erlebnisbezogenen Künstlichkeit. Beispielsweise unterscheidet sich ein Naturfoto von einem Naturfilm durch das Fehlen von auditiven und bewegten Stimuli. Diese erlebnisbezogene Künstlichkeit kann die erholsame Wirkung von Natur - direkt oder indirekt über Bewertungen - hemmen. Als Haupthypothese wird angenommen, dass mit zunehmendem Ausmaß an erlebnisbezogener Künstlichkeit die erholsame Wirkung der Natur abnimmt. Dem kombinierten Feld- und Laborexperiment liegt ein einfaktorielles Vorher-Nachher-Design zugrunde. Den 117 Probanden wurde zunächst eine kognitiv und affektiv belastende Aufgabe vorgelegt, danach folgte die Erholungsphase. Diese bestand aus einem Spaziergang, der entweder in der physisch-materiellen Natur (urbaner Park) oder in einer der beiden audio-visuellen Natursimulationen (videogefilmter vs. computergenerierter Spaziergang durch selbigen urbanen Park) oder auf dem Laufband ohne audio-visuelle Darbietung stattfand. Die erlebnisbezogene Künstlichkeit/Natürlichkeit wurde also wie folgt operationlisiert: die physische Natur steht für die erlebnisbezogene Natürlichkeit. Die beiden Natursimulationen stehen für die erlebnisbezogene Künstlichkeit. Die computergenerierte Version ist im Vergleich zur Videoversion erlebnisbezogen künstlicher, da sie weniger fotorealistisch ist. Die Zuordnung zu einer der vier experimentellen Erholungssettings erfolgte nach dem Zufallsprinzip. Die Effekte von moderater Bewegung wurden in den Natursimulationen durch das Laufen auf dem Laufband kontrolliert. Die Beanspruchungs- bzw. Erholungsreaktionen wurden auf kognitiver (Konzentriertheit, Aufmerksamkeitsleistung) affektiver (3 Befindlichkeitsskalen: Wachheit, Ruhe, gute Stimmung) und physiologischer (Alpha-Amylase) Ebene gemessen, um ein umfassendes Bild der Reaktionen zu erhalten. Insgesamt zeigen die Ergebnisse, dass die beiden Natursimulationen trotz Unterschiede in der erlebnisbezogenen Künstlichkeit/Natürlichkeit zu relativ ähnlichen Erholungsreaktionen führen, wie die physisch-materielle Natur. Eine Ausnahme stellen eine der drei affektiven (Wachheit) und die physiologische Reaktion dar: Probanden der physisch-materiellen Naturbedingung geben an wacher zu sein und weisen - wider erwarten - eine höhere physiologische Erregung auf. Demnach ist die physisch-materielle Natur nicht grundsätzlich erholsamer als die Natursimulationen. Die Hypothese ließ sich somit nicht bestätigen. Vielmehr deuten sich komplexe Erholungsmuster und damit auch unterschiedliche Erholungsqualitäten der Settings an, die einer differenzierten Betrachtung bedürfen. Für die ökologische Validität von Natursimulationen gilt, dass diese nur mit Einschränkung als ökologisch valide bezeichnet werden können, d.h. nur für bestimmte, aber nicht für alle Erholungsreaktionen. Die beiden Natursimulationen führen ebenfalls trotz Unterschiede in der erlebnisbezogenen Künstlichkeit zu ähnlichen Erholungsreaktionen und können somit als gleichwertig behandelt werden. Erstaunlicherweise kommt es hier zu ähnlichen Erholungsreaktionen, obwohl die bestehenden Unterschiede von den Probanden wahrgenommen und die erlebnisbezogen künstlichere computergenerierte Version negativer bewertet wird. Aufgrund der nicht erwartungskonformen Ergebnisse muss das Erklärungskonzept der erlebnisbezogenen Künstlichkeit/Natürlichkeit infrage gestellt werden. Alternative Erklärungskonzepte für die Ergebnisse („Ungewissheit“, mentale räumliche Modelle), die sich andeutenden unterschiedlichen Erholungsqualitäten der Settings, methodische Einschränkungen sowie die praktische Bedeutung der Ergebnisse werden kritisch diskutiert.

Artificial micro RNA system in Dictyostelium discoideum

Dictyostelium discoideum is a social amoeba that serves as a model system for RNA interference and related mechanisms. Its position between plants and animals enables evolutionary snapshot of mechanisms and protein machinery involved in investigated subjects. MiRNAs are small regulatory RNAs that are evolutionary conserved and present in animals, plants, viruses and some prokaryotes. They have roles in development, cell growth and differentiation, apoptosis and their miss-regulation is associated with many diseases such as cancer, neurodegenerative disorders and diabetes. Recently, through sequencing of DNA libraries miRNAs have been discovered in D. discoideum. In this work, it has been shown that heterologues miRNA let-7 can be expressed and processed in D. discoideum. Expression of let-7 miRNA in social amoeba resulted in a strong developmental phenotype suggesting an overload of the processing/silencing system or/and endogenous targets. The various effects on prel-7 strain have been observed and characterized, serving as a background for postulation of miRNA roles. An artificial miRNA system has been established and imposed to D. discoideum, showing that miRNAs in Dictyostelium could mediate gene expression on the level of mRNA stability and on the posttranscriptional level. Furthermore, presence of translational inhibition as a type of gene control was shown for the first time in this organism. Due to it new structures representing co-localities of miRNA and target mRNA have been detected. Taken together, this work shows functional artificial miRNA system and postulates roles of endogenous small RNA in social amoeba.

Evaluation of breeding strategies for polledness in dairy cattle using a newly developed simulation framework for quantitative and Mendelian traits

Background: Intensified selection of polled individuals has recently gained importance in predominantly horned dairy cattle breeds as an alternative to routine dehorning. The status quo of the current polled breeding pool of genetically-closely related artificial insemination sires with lower breeding values for performance traits raises questions regarding the effects of intensified selection based on this founder pool. Methods: We developed a stochastic simulation framework that combines the stochastic simulation software QMSim and a self-designed R program named QUALsim that acts as an external extension. Two traits were simulated in a dairy cattle population for 25 generations: one quantitative (QMSim) and one qualitative trait with Mendelian inheritance (i.e. polledness, QUALsim). The assignment scheme for qualitative trait genotypes initiated realistic initial breeding situations regarding allele frequencies, true breeding values for the quantitative trait and genetic relatedness. Intensified selection for polled cattle was achieved using an approach that weights estimated breeding values in the animal best linear unbiased prediction model for the quantitative trait depending on genotypes or phenotypes for the polled trait with a user-defined weighting factor. Results: Selection response for the polled trait was highest in the selection scheme based on genotypes. Selection based on phenotypes led to significantly lower allele frequencies for polled. The male selection path played a significantly greater role for a fast dissemination of polled alleles compared to female selection strategies. Fixation of the polled allele implies selection based on polled genotypes among males. In comparison to a base breeding scenario that does not take polledness into account, intensive selection for polled substantially reduced genetic gain for this quantitative trait after 25 generations. Reducing selection intensity for polled males while maintaining strong selection intensity among females, simultaneously decreased losses in genetic gain and achieved a final allele frequency of 0.93 for polled. Conclusions: A fast transition to a completely polled population through intensified selection for polled was in contradiction to the preservation of high genetic gain for the quantitative trait. Selection on male polled genotypes with moderate weighting, and selection on female polled phenotypes with high weighting, could be a suitable compromise regarding all important breeding aspects.