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.

A Modeling Analysis of Changing Global Land Use as affected by Changing Demands for Wood Products

The 21st century has brought new challenges for forest management at a time when globalization in world trade is increasing and global climate change is becoming increasingly apparent. In addition to various goods and services like food, feed, timber or biofuels being provided to humans, forest ecosystems are a large store of terrestrial carbon and account for a major part of the carbon exchange between the atmosphere and the land surface. Depending on the stage of the ecosystems and/or management regimes, forests can be either sinks, or sources of carbon. At the global scale, rapid economic development and a growing world population have raised much concern over the use of natural resources, especially forest resources. The challenging question is how can the global demands for forest commodities be satisfied in an increasingly globalised economy, and where could they potentially be produced? For this purpose, wood demand estimates need to be integrated in a framework, which is able to adequately handle the competition for land between major land-use options such as residential land or agricultural land. This thesis is organised in accordance with the requirements to integrate the simulation of forest changes based on wood extraction in an existing framework for global land-use modelling called LandSHIFT. Accordingly, the following neuralgic points for research have been identified: (1) a review of existing global-scale economic forest sector models (2) simulation of global wood production under selected scenarios (3) simulation of global vegetation carbon yields and (4) the implementation of a land-use allocation procedure to simulate the impact of wood extraction on forest land-cover. Modelling the spatial dynamics of forests on the global scale requires two important inputs: (1) simulated long-term wood demand data to determine future roundwood harvests in each country and (2) the changes in the spatial distribution of woody biomass stocks to determine how much of the resource is available to satisfy the simulated wood demands. First, three global timber market models are reviewed and compared in order to select a suitable economic model to generate wood demand scenario data for the forest sector in LandSHIFT. The comparison indicates that the ‘Global Forest Products Model’ (GFPM) is most suitable for obtaining projections on future roundwood harvests for further study with the LandSHIFT forest sector. Accordingly, the GFPM is adapted and applied to simulate wood demands for the global forestry sector conditional on selected scenarios from the Millennium Ecosystem Assessment and the Global Environmental Outlook until 2050. Secondly, the Lund-Potsdam-Jena (LPJ) dynamic global vegetation model is utilized to simulate the change in potential vegetation carbon stocks for the forested locations in LandSHIFT. The LPJ data is used in collaboration with spatially explicit forest inventory data on aboveground biomass to allocate the demands for raw forest products and identify locations of deforestation. Using the previous results as an input, a methodology to simulate the spatial dynamics of forests based on wood extraction is developed within the LandSHIFT framework. The land-use allocation procedure specified in the module translates the country level demands for forest products into woody biomass requirements for forest areas, and allocates these on a five arc minute grid. In a first version, the model assumes only actual conditions through the entire study period and does not explicitly address forest age structure. Although the module is in a very preliminary stage of development, it already captures the effects of important drivers of land-use change like cropland and urban expansion. As a first plausibility test, the module performance is tested under three forest management scenarios. The module succeeds in responding to changing inputs in an expected and consistent manner. The entire methodology is applied in an exemplary scenario analysis for India. A couple of future research priorities need to be addressed, particularly the incorporation of plantation establishments; issue of age structure dynamics; as well as the implementation of a new technology change factor in the GFPM which can allow the specification of substituting raw wood products (especially fuelwood) by other non-wood products.

Estudio psicométrico del test de Bohem de Conceptos Básicos en la población asturiana.

Realizar un estudio de las propiedades psicométricas del test de Boehm de Conceptos Básicos (BTBC) a partir de las respuestas emitidas por escolares asturianos. 153 alumnos de Preescolar-1, 136 de Preescolar-2 y 205 de primero de EGB del Principado de Asturias, distribuidos en función del sexo y la clase social. Muestreo aleatorio estratificado con afijación proporcional dentro de la población escolar. Cálculo de los coeficientes de fiabilidad, validez e indices de dificultad y discriminación. Baremación de la prueba para la población asturiana. Para cada uno de los análisis se toma individualmente los tres grupos resultantes de los niveles escolares a los que pertenecen los sujetos de la muestra, pretendiendo con ello observar el comportamiento del test en cada grupo de edad. BTBC, WIPPSI, WIC y test de matrices progresivas de colores de Raven. Calificación académica en Lenguaje. La fiabilidad se calculó por tres métodos: dos mitades, alpha de Cronbach y zeta de Carmines. La validez se calculó por medio de correlaciones con otros tests y el análisis de componentes principales. Fiabilidad: para los dos grupos de Preescolar, los coeficientes son relativamente altos en todos los casos, produciéndose una baja significativa en el grupo de primero de EGB; también se observa que los resultados alcanzados son levemente inferiores a los aportados en el manual de la versión castellana. Validez: el test tiene una aceptable relación con las pruebas elegidas como criterio y con la calificación en lenguaje; se corrobora que el BTBC es un test multidimensional. Dificultad y discriminación: en la primera mitad los índices de dificultad son muy altos, de los que se derivan unos niveles de discriminación muy bajos para la mayor parte de los ítems; la segunda parte del test tiene unos índices de dificultad con valores más bajos y la discriminación mejora; al mismo tiempo, los resultados indican que los ítems aun cuando presentan una diferenciación en dificultad entre los correspondientes a la primera y segunda mitad, no mantienen un riguroso orden de dificultad creciente. Baremación: los datos obtenidos indican la necesidad de que se realice una unica baremación para todos los sujetos en los dos cursos de Preescolar y tres baremaciones, según los tres niveles de clase social, para el primer curso de EGB. En términos generales, se concluye que los valores obtenidos en los diferentes análisis caen dentro de niveles 'razonablemente' aceptables, no pudiendo olvidar nunca las especiales características de esta prueba.

Estudio sobre indicadores de validez del Reversal Test.

Comprobar la siguiente hipótesis: si ciertamente el Reversal es un test de madurez, sus resultados pueden constituir un índice predictivo del rendimiento en otras áreas. 740 alumnos de primero de EGB de centros de la región asturiana a través de un procedimiento aleatorio por conjuntos. La población se estratificó según: sexo, hábitat, régimen de enseñanza y asistencia o no de los alumnos a centros preescolares en el curso anterior. Para comprobar la hipótesis planteada, se relacionan los datos obtenidos en este test con los resultados de aquellos otros indicadores del rendimiento de los alumnos de primero de EGB: evaluación o exploración inicial de los alumnos efectuada por el docente al comenzar primero de EGB, los resultados del test de aptitudes cognoscitivas primaria I, y finalmente, la evaluación final al terminar el nivel de primero. Cuestionario 'ad hoc' con respuestas cerradas en escala y paramétrica, destinado a los docentes. Reversal y Test de aptitudes cognoscitivas primaria I. Calificación final en el área de Matemáticas, Lenguaje y global y calificaciones obtenidas por los alumnos en dos pruebas objetivas (Lenguaje y Matemáticas) expresamente preparadas con este fin. Análisis de las relaciones entre el reversal y las puntuaciones obtenidas en los demás indicadores. Cálculo de la validez de este test como instrumento predictivo a través de sus correlaciones con los demás indicadores utilizados.. Diferencias en función del nivel de maduración y el sexo: los alumnos clasificados con bajo nivel de maduración por el Reversal, obtienen las puntuaciones inferiores en todas las variables utilizadas; superioridad de las niñas respecto a los niños, aunque las diferencias no llegan a ser significativas. Interacción de variables en función del grado de madurez y el sexo: las correlaciones más elevadas se dan entre los índices de rendimiento y la madurez cognoscitiva evaluada por los docentes al comenzar el curso; se obtienen coeficientes diferentes con los diversos grupos entre rendimiento y test de aptitudes cognoscitivas, en los índices entre personalización y rendimiento se refleja claramente la influencia del nivel de maduración y el sexo. Relaciones entre el reversal y otros indicadores del rendimiento en función de la preescolarización: las correlaciones más altas se dan entre el Reversal y el Test de inteligencia primaria I; respecto al rendimiento de fin de curso los índices también son claramente representativos; los índices tienden a ser más bajos y desiguales en las relaciones entre el Reversal y la madurez cognoscitiva inicial evaluada por los docentes. Gran utilidad del Reversal como instrumento de diagnóstico y predicción. Se recomienda su utilización en los docentes por su facilidad de aplicación, valoración e interpretación. Este test permite obtener una información sobre el nivel de maduración del niño y 'pistas' de posibles anomalías o retrasos en las áreas perceptiva, espacial, etc..

Performance-Driven Microfabrication-Oriented Methodology for MEMS Conceptual Design with Application in Microfluidic Device Design

Performance and manufacturability are two important issues that must be taken into account during MEMS design. Existing MEMS design models or systems follow a process-driven design paradigm, that is, design starts from the specification of process sequence or the customization of foundry-ready process template. There has been essentially no methodology or model that supports generic, high-level design synthesis for MEMS conceptual design. As a result, there lacks a basis for specifying the initial process sequences. To address this problem, this paper proposes a performance-driven, microfabrication-oriented methodology for MEMS conceptual design. A unified behaviour representation method is proposed which incorporates information of both physical interactions and chemical/biological/other reactions. Based on this method, a behavioural process based design synthesis model is proposed, which exploits multidisciplinary phenomena for design solutions, including both the structural components and their configuration for the MEMS device, as well as the necessary substances for the chemical/biological/other reactions. The model supports both forward and backward synthetic search for suitable phenomena. To ensure manufacturability, a strategy of using microfabrication-oriented phenomena as design knowledge is proposed, where the phenomena are developed from existing MEMS devices that have associated MEMS-specific microfabrication processes or foundry-ready process templates. To test the applicability of the proposed methodology, the paper also studies microfluidic device design and uses a micro-pump design for the case study.

Aplicación conjunta de la teoría clásica de respuesta al test y la teoría de respuesta al ítem para el diseño de protocolos de evaluación del rendimiento en el área de Matemáticas.

Diseñar y validar un protocolo de evaluación que sirva para estimar la competencia curricular en el área de matemáticas al final de la Educación Primaria o al inicio de la secundaria obligatoria. Es decir, lo que se pretende es construir un test de rendimiento en matemáticas que será baremado, tanto clásicamente como según la más moderna respuesta al ítem. 603 estudiantes de sexto de Educación Primaria en el Sector Educativo del Nalón (Asturias). Se trabaja con un error muestral muy pequeño (1,5 por ciento) y un nivel de confianza del 95 por ciento. Previamente a la aplicación del instrumento se realizó un estudio piloto con el fin de realizar una primera depuración de ítems para construir y validar estadísticamente una prueba que permitiera estimar el nivel curricular del alumnado en el área de matemáticas al final de la Educación Primaria. El trabajo se inicio con el análisis del currículo del área en tercer ciclo: decretos de mínimos y curricular de Educación Primaria. También se revisaron los documentos elaborados por el MEC, libros de texto de la principales editoriales y el material de refuerzo y recuperación disponible en el EOEP-Nalón (Asturias). Estas tareas sirven para diseñar la tabla de especificaciones de la prueba y construir un primera banco de ítems. Se diseña una matriz de especificaciones con un total de 46 entradas organizadas en dos ejes: a) Bloques de contenidos: numeración, operaciones, geometría, medidas y organización de la información; b) Capacidades matemáticas: conocimientos básicos, algoritmos, estrategias intermedias y resolución de problemas. El protocolo de evaluación implementado en la aplicación final consistió en una batería de 41 preguntas. A los 34 ítems seleccionados de la prueba piloto se unieron 7 más. El análisis de los resultados se llevo a cabo del programa SPSS V.8.0. Se calculan estadísticos de posición y dispersión, puntuaciones típicas y transformadas, ajuste a normalidad y descarte de diferencias entre los grupos de corte de la muestra. Buscando definir las características métricas se estiman los índices de fiabilidad y validez externa. a) La batería del estudio presenta buenos índices de fiabilidad, tanto en los coeficientes de test referidos a la norma, como al criterio; b) El valor del índice de fiabilidad es siempre una primera aproximación al estudio de unidimensionalidad de la escala. Un alfa superior a 0,86 parece indicar cierto grado de unidimensionalidad, lo que permitiría intentar el ajuste de los datos a algún modelo derivado de la Teoría de Respuesta al Ítem , y superar de esta forma los rudimentos de la Teoría Clásica de Respuesta a los Test; c) Se pueden establecer puntos de corte a partir del rendimiento en la prueba para identificar, tanto alumnos con dificultades en el área, como a posibles talentos matemáticos.

Quantifying rock fabrics: a test of autocorrelation of the spatial distribution of cristals

A novel test of spatial independence of the distribution of crystals or phases in rocks based on compositional statistics is introduced. It improves and generalizes the common joins-count statistics known from map analysis in geographic information systems. Assigning phases independently to objects in RD is modelled by a single-trial multinomial random function Z(x), where the probabilities of phases add to one and are explicitly modelled as compositions in the K-part simplex SK. Thus, apparent inconsistencies of the tests based on the conventional joins{count statistics and their possibly contradictory interpretations are avoided. In practical applications we assume that the probabilities of phases do not depend on the location but are identical everywhere in the domain of de nition. Thus, the model involves the sum of r independent identical multinomial distributed 1-trial random variables which is an r-trial multinomial distributed random variable. The probabilities of the distribution of the r counts can be considered as a composition in the Q-part simplex SQ. They span the so called Hardy-Weinberg manifold H that is proved to be a K-1-affine subspace of SQ. This is a generalisation of the well-known Hardy-Weinberg law of genetics. If the assignment of phases accounts for some kind of spatial dependence, then the r-trial probabilities do not remain on H. This suggests the use of the Aitchison distance between observed probabilities to H to test dependence. Moreover, when there is a spatial uctuation of the multinomial probabilities, the observed r-trial probabilities move on H. This shift can be used as to check for these uctuations. A practical procedure and an algorithm to perform the test have been developed. Some cases applied to simulated and real data are presented. Key words: Spatial distribution of crystals in rocks, spatial distribution of phases, joins-count statistics, multinomial distribution, Hardy-Weinberg law, Hardy-Weinberg manifold, Aitchison geometry

Intrinsic test of independence in contingency tables

A condition needed for testing nested hypotheses from a Bayesian viewpoint is that the prior for the alternative model concentrates mass around the small, or null, model. For testing independence in contingency tables, the intrinsic priors satisfy this requirement. Further, the degree of concentration of the priors is controlled by a discrete parameter m, the training sample size, which plays an important role in the resulting answer regardless of the sample size. In this paper we study robustness of the tests of independence in contingency tables with respect to the intrinsic priors with different degree of concentration around the null, and compare with other “robust” results by Good and Crook. Consistency of the intrinsic Bayesian tests is established. We also discuss conditioning issues and sampling schemes, and argue that conditioning should be on either one margin or the table total, but not on both margins. Examples using real are simulated data are given