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.

Numerical Feasibility Study for Treated Wastewater Recharge as a Tool to Impede Saltwater Intrusion in the Coastal Aquifer of Gaza – Palestine

The ongoing depletion of the coastal aquifer in the Gaza strip due to groundwater overexploitation has led to the process of seawater intrusion, which is continually becoming a serious problem in Gaza, as the seawater has further invaded into many sections along the coastal shoreline. As a first step to get a hold on the problem, the artificial neural network (ANN)-model has been applied as a new approach and an attractive tool to study and predict groundwater levels without applying physically based hydrologic parameters, and also for the purpose to improve the understanding of complex groundwater systems and which is able to show the effects of hydrologic, meteorological and anthropogenic impacts on the groundwater conditions. Prediction of the future behaviour of the seawater intrusion process in the Gaza aquifer is thus of crucial importance to safeguard the already scarce groundwater resources in the region. In this study the coupled three-dimensional groundwater flow and density-dependent solute transport model SEAWAT, as implemented in Visual MODFLOW, is applied to the Gaza coastal aquifer system to simulate the location and the dynamics of the saltwater–freshwater interface in the aquifer in the time period 2000-2010. A very good agreement between simulated and observed TDS salinities with a correlation coefficient of 0.902 and 0.883 for both steady-state and transient calibration is obtained. After successful calibration of the solute transport model, simulation of future management scenarios for the Gaza aquifer have been carried out, in order to get a more comprehensive view of the effects of the artificial recharge planned in the Gaza strip for some time on forestall, or even to remedy, the presently existing adverse aquifer conditions, namely, low groundwater heads and high salinity by the end of the target simulation period, year 2040. To that avail, numerous management scenarios schemes are examined to maintain the ground water system and to control the salinity distributions within the target period 2011-2040. In the first, pessimistic scenario, it is assumed that pumping from the aquifer continues to increase in the near future to meet the rising water demand, and that there is not further recharge to the aquifer than what is provided by natural precipitation. The second, optimistic scenario assumes that treated surficial wastewater can be used as a source of additional artificial recharge to the aquifer which, in principle, should not only lead to an increased sustainable yield of the latter, but could, in the best of all cases, revert even some of the adverse present-day conditions in the aquifer, i.e., seawater intrusion. This scenario has been done with three different cases which differ by the locations and the extensions of the injection-fields for the treated wastewater. The results obtained with the first (do-nothing) scenario indicate that there will be ongoing negative impacts on the aquifer, such as a higher propensity for strong seawater intrusion into the Gaza aquifer. This scenario illustrates that, compared with 2010 situation of the baseline model, at the end of simulation period, year 2040, the amount of saltwater intrusion into the coastal aquifer will be increased by about 35 %, whereas the salinity will be increased by 34 %. In contrast, all three cases of the second (artificial recharge) scenario group can partly revert the present seawater intrusion. From the water budget point of view, compared with the first (do nothing) scenario, for year 2040, the water added to the aquifer by artificial recharge will reduces the amount of water entering the aquifer by seawater intrusion by 81, 77and 72 %, for the three recharge cases, respectively. Meanwhile, the salinity in the Gaza aquifer will be decreased by 15, 32 and 26% for the three cases, respectively.

Characterization of the molecular clockwork in the cockroach Rhyparobia maderae

Der Wechsel von Tag und Nacht erzeugt einen regelmäßigen Rhythmus von verschiedenen Umweltreizen, allen voran Licht und Temperatur. Fast jedes bis zum heutigen Tage untersuchte Lebewesen besitzt einen endogenen Mechanismus zur Zeitwahrnehmung, und diese "innere Uhr" befähigt Lebewesen dazu, sich vorausschauend an rhythmische Umwelt-Änderungen anzupassen. Circadiane Rhythmen bestehen auch ohne jegliche äußere Reize und basieren auf einem molekularen Rückkopplungs-Mechanismus, der Rhythmen in Genexpression und Proteinkonzentration von etwa 24 Stunden erzeugt. Obwohl sich die grundsätzlichen Mechanismen und Komponenten dieses molekularen Uhrwerks in allen Insekten ähneln, zeigte sich jedoch immer mehr, dass es im Detail doch wesentliche Unterschiede zwischen verschiedenen Insektengruppen gibt. Während das molekulare Uhrwerk der Fruchtfliege Drosophila melanogaster inzwischen sehr gut untersucht ist, fehlen bei den meisten Insektengruppen immernoch eingehende Untersuchungen. Fast nichts ist über die molekulare Basis von circadianen Rhythmen bei der Schabe Rhyparobia maderae bekannt, obwohl diese Art bereits seit Langem als Modellorganismus in der Chronobiologie dient. Um mit der Forschung am molekularen, circadianen System von R. maderae zu beginnen, wurde die Struktur und das Expressionsprofil der core feedback loop Gene per, tim1 und cry2 analysiert. Mittels degenerierten Primern und RACE konnte das vollständige offene Leseraster (OLR) von rmPer und rmCry2, und ein Teil des rmTim1 OLR kloniert werden. Eine phylogenetische Analyse gruppierte rmPER und rmCRY2 gemeinsam mit den Orthologa hemimetaboler Insekten. Viele bei D. melanogaster funktionell charakterisierte Domänen sind bei diesen Proteinen konserviert, was auf eine ähnliche Funktion in der inneren Uhr von R. maderae hinweist. Mittels quantitativer PCR konnte gezeigt werden, dass die mRNA von rmPer, rmTim1 und rmCry2 in verschiedenen Lichtregimen in der gleichen Phasenlage Tageszeit-abhängig schwankt. Die Phasenlage stellte sich bei unterschiedlichen Photoperioden jeweils relativ zum Beginn der Skotophase ein, mit Maxima in der ersten Hälfte der Nacht. Auch im Dauerdunkel zeigen sich Rhythmen in der rmTim1 und rmCry2 Expression. Die Amplitude der rmPer Expressionsrhythmen war jedoch so gering, dass keine signifikanten Unterschiede zwischen den einzelnen Zeitgeberzeiten (ZT) festgestellt werden konnten. Mittels Laufrad-Assays wurde untersucht wie Kurz- und Langtag Lichtregime die Verhaltensrhythmen beeinflussen. Es konnten nur Unterschiede in der Periodenlänge unter freilaufenden Bedingungen festgestellt werden, wenn höhere Lichtintensitäten (1000lx) zur Synchronisation (entrainment) genutzt wurden. Die Periode des freilaufenden Rhythmus war bei Tieren aus dem Kurztag länger. Die photoperiodische Plastizität zeigte sich also auch auf Verhaltensebene, obwohl höhere Lichtintensitäten notwendig waren um einen Effekt zu beobachten. Basierend auf den Sequenzen der zuvor klonierten OLR wurden gegen rmPER, rmTIM1 und rmCRY2 gerichtete Antikörper hergestellt. Die Antikörper gegen rmPER und rmTIM1 erkannten in western blots sehr wahrscheinlich spezifisch das jeweilige Protein. Zeitreihen von Gehirngewebe-Homogenisaten zeigten keinen offensichtlichen circadianen Rhythmus in der Proteinkonzentration, wahrscheinlich auf Grund einer Oszillation mit niedriger Amplitude. In Immunhistochemischen Färbungen konnte nur mit dem gegen rmPER gerichteten Antikörper aus Kaninchen ein Signal beobachtet werden. Beinahe jede Zelle des Zentralnervensystems war rmPER-immunreaktiv im Zellkern. Es konnten keine Unterschiede zwischen den untersuchten ZTs festgestellt werden, ähnlich wie bei den western blot Zeitreihen. In dieser Studie konnten erstmals molekulare Daten der circadianen Uhr von R. maderae erfasst und dargestellt werden. Die Uhrgene per, tim1 und cry2 werden in dieser Schabenart exprimiert und ihre Domänenstruktur sowie das circadiane Expressionsmuster ähneln dem hypothetischen ursprünglichen Insektenuhrwerk, welches der circadianen Uhr von Vertebraten nahesteht. Das molekulare Uhrwerk von R. maderae kann sich an unterschiedliche Photoperioden anpassen, und diese Anpassungen manifestieren sich im Expressionsprofil der untersuchten Uhrgene ebenso wie im Verhalten.