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.

Managing Quality Properties of Web Service Compositions

Web services from different partners can be combined to applications that realize a more complex business goal. Such applications built as Web service compositions define how interactions between Web services take place in order to implement the business logic. Web service compositions not only have to provide the desired functionality but also have to comply with certain Quality of Service (QoS) levels. Maximizing the users' satisfaction, also reflected as Quality of Experience (QoE), is a primary goal to be achieved in a Service-Oriented Architecture (SOA). Unfortunately, in a dynamic environment like SOA unforeseen situations might appear like services not being available or not responding in the desired time frame. In such situations, appropriate actions need to be triggered in order to avoid the violation of QoS and QoE constraints. In this thesis, proper solutions are developed to manage Web services and Web service compositions with regard to QoS and QoE requirements. The Business Process Rules Language (BPRules) was developed to manage Web service compositions when undesired QoS or QoE values are detected. BPRules provides a rich set of management actions that may be triggered for controlling the service composition and for improving its quality behavior. Regarding the quality properties, BPRules allows to distinguish between the QoS values as they are promised by the service providers, QoE values that were assigned by end-users, the monitored QoS as measured by our BPR framework, and the predicted QoS and QoE values. BPRules facilitates the specification of certain user groups characterized by different context properties and allows triggering a personalized, context-aware service selection tailored for the specified user groups. In a service market where a multitude of services with the same functionality and different quality values are available, the right services need to be selected for realizing the service composition. We developed new and efficient heuristic algorithms that are applied to choose high quality services for the composition. BPRules offers the possibility to integrate multiple service selection algorithms. The selection algorithms are applicable also for non-linear objective functions and constraints. The BPR framework includes new approaches for context-aware service selection and quality property predictions. We consider the location information of users and services as context dimension for the prediction of response time and throughput. The BPR framework combines all new features and contributions to a comprehensive management solution. Furthermore, it facilitates flexible monitoring of QoS properties without having to modify the description of the service composition. We show how the different modules of the BPR framework work together in order to execute the management rules. We evaluate how our selection algorithms outperform a genetic algorithm from related research. The evaluation reveals how context data can be used for a personalized prediction of response time and throughput.

Entwicklung und Förderung von Datenkompetenz in den Klassen 1-6

Der vorliegende Band ist unter der Betreuung von Rolf Biehler am Fachbereich Mathematik/Informatik der Universität Kassel als Wissenschaftliche Hausarbeit für das 1. Staatsexamen entstanden. Die Förderung von Datenkompetenz in den Klassen 1 – 6 ist ein in der deutschsprachigen didaktischen Literatur kaum beachtetes Thema. In der vorliegenden Arbeit wird die umfangreiche englischsprachige Literatur zu diesem Thema erschlossen und ausgewertet, um der Fragestellung, wie sich Datenkompetenz entwickelt und wie man diese Entwicklung im Unterricht geeignet fördern kann, nachzugehen. Alle Phasen im Prozess der Datenanalyse werden dabei aufgegriffen: Die Wahl einer Fragestellung und die Erhebung von Daten, die Organisation und graphische Darstellung sowie die Beschreibung und Interpretation von Daten mithilfe statistischer Verfahren. Die innovative Werkzeugsoftware TinkerPlots (http://www.keypress.com/x5715.xml) wird im Hinblick auf die Möglichkeit, Datenkompetenz zu fördern untersucht, und exemplarische Unterrichtsideen werden damit konkretisiert. Intention der Arbeit ist, einen Beitrag dazu zu leisten, dass der Stellenwert von Datenkompetenz in den Klassen 1-6 neu überdacht wird.

Optimization of the Mechanical and Optical Properties of Tunable Optical Sensor Arrays (TOSA) for a Nanospectrometer in the Visible and Near Infrared Spectral Range

Tunable Optical Sensor Arrays (TOSA) based on Fabry-Pérot (FP) filters, for high quality spectroscopic applications in the visible and near infrared spectral range are investigated within this work. The optical performance of the FP filters is improved by using ion beam sputtered niobium pentoxide (Nb2O5) and silicon dioxide (SiO2) Distributed Bragg Reflectors (DBRs) as mirrors. Due to their high refractive index contrast, only a few alternating pairs of Nb2O5 and SiO2 films can achieve DBRs with high reflectivity in a wide spectral range, while ion beam sputter deposition (IBSD) is utilized due to its ability to produce films with high optical purity. However, IBSD films are highly stressed; resulting in stress induced mirror curvature and suspension bending in the free standing filter suspensions of the MEMS (Micro-Electro-Mechanical Systems) FP filters. Stress induced mirror curvature results in filter transmission line degradation, while suspension bending results in high required filter tuning voltages. Moreover, stress induced suspension bending results in higher order mode filter operation which in turn degrades the optical resolution of the filter. Therefore, the deposition process is optimized to achieve both near zero absorption and low residual stress. High energy ion bombardment during film deposition is utilized to reduce the film density, and hence the film compressive stress. Utilizing this technique, the compressive stress of Nb2O5 is reduced by ~43%, while that for SiO2 is reduced by ~40%. Filters fabricated with stress reduced films show curvatures as low as 100 nm for 70 μm mirrors. To reduce the stress induced bending in the free standing filter suspensions, a stress optimized multi-layer suspension design is presented; with a tensile stressed metal sandwiched between two compressively stressed films. The stress in Physical Vapor Deposited (PVD) metals is therefore characterized for use as filter top-electrode and stress compensating layer. Surface micromachining is used to fabricate tunable FP filters in the visible spectral range using the above mentioned design. The upward bending of the suspensions is reduced from several micrometers to less than 100 nm and 250 nm for two different suspension layer combinations. Mechanical tuning of up to 188 nm is obtained by applying 40 V of actuation voltage. Alternatively, a filter line with transmission of 65.5%, Full Width at Half Maximum (FWHM) of 10.5 nm and a stopband of 170 nm (at an output wavelength of 594 nm) is achieved. Numerical model simulations are also performed to study the validity of the stress optimized suspension design for the near infrared spectral range, wherein membrane displacement and suspension deformation due to material residual stress is studied. Two bandpass filter designs based on quarter-wave and non-quarter-wave layers are presented as integral components of the TOSA. With a filter passband of 135 nm and a broad stopband of over 650 nm, high average filter transmission of 88% is achieved inside the passband, while maximum filter transmission of less than 1.6% outside the passband is achieved.