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.

Femtosecond pulse shaping using differential evolutionary algorithm and wavelet operators

Evolutionary meta-algorithms for pulse shaping of broadband femtosecond duration laser pulses are proposed. The genetic algorithm searching the evolutionary landscape for desired pulse shapes consists of a population of waveforms (genes), each made from two concatenated vectors, specifying phases and magnitudes, respectively, over a range of frequencies. Frequency domain operators such as mutation, two-point crossover average crossover, polynomial phase mutation, creep and three-point smoothing as well as a time-domain crossover are combined to produce fitter offsprings at each iteration step. The algorithm applies roulette wheel selection; elitists and linear fitness scaling to the gene population. A differential evolution (DE) operator that provides a source of directed mutation and new wavelet operators are proposed. Using properly tuned parameters for DE, the meta-algorithm is used to solve a waveform matching problem. Tuning allows either a greedy directed search near the best known solution or a robust search across the entire parameter space.

Reconfiguration of distribution systems by a modified genetic algorithm

In this paper a genetic algorithm based reconfiguration method is proposed to minimize the real power losses of distribution systems. The main innovation of this research work is that new types of crossover and mutation operators are proposed, such that the best possible results are obtained, with an acceptable computational effort. The crossover and mutation operators were developed so as to take advantage of the particular characteristics of distribution systems (as the radial topology). Simulation results indicate that the proposed method is very efficient, being able to find excellent configurations, with low computational effort, especially for larger systems. ©2007 IEEE.

A genetic algorithm for crop rotation

In the last few years, crop rotation has gained attention due to its economic, environmental and social importance which explains why it can be highly beneficial for farmers. This paper presents a mathematical model for the Crop Rotation Problem (CRP) that was adapted from literature for this highly complex combinatorial problem. The CRP is devised to find a vegetable planting program that takes into account green fertilization restrictions, the set-aside period, planting restrictions for neighboring lots and for crop sequencing, demand constraints, while, at the same time, maximizing the profitability of the planted area. The main aim of this study is to develop a genetic algorithm and test it in a real context. The genetic algorithm involves a constructive heuristic to build the initial population and the operators of crossover, mutation, migration and elitism. The computational experiment was performed for a medium dimension real planting area with 16 lots, considering 29 crops of 10 different botanical families and a two-year planting rotation. Results showed that the algorithm determined feasible solutions in a reasonable computational time, thus proving its efficacy for dealing with this practical application.

Global optimization using a genetic algorithm with hierarchically structured population

This paper applies a genetic algorithm with hierarchically structured population to solve unconstrained optimization problems. The population has individuals distributed in several overlapping clusters, each one with a leader and a variable number of support individuals. The hierarchy establishes that leaders must be fitter than its supporters with the topological organization of the clusters following a tree. Computational tests evaluate different population structures, population sizes and crossover operators for better algorithm performance. A set of known benchmark test problems is solved and the results found are compared with those obtained from other methods described in the literature, namely, two genetic algorithms, a simulated annealing, a differential evolution and a particle swarm optimization. The results indicate that the method employed is capable of achieving better performance than the previous approaches in regard as the two criteria usually employed for comparisons: the number of function evaluations and rate of success. The method also has a superior performance if the number of problems solved is taken into account. (C) 2013 Elsevier B.V. All rights reserved.

A genetic algorithm based method for deregulated electricity market dispatch

In a deregulated electricity market, optimizing dispatch capacity and transmission capacity are among the core concerns of market operators. Many market operators have capitalized on linear programming (LP) based methods to perform market dispatch operation in order to explore the computational efficiency of LP. In this paper, the search capability of genetic algorithms (GAs) is utilized to solve the market dispatch problem. The GA model is able to solve pool based capacity dispatch, while optimizing the interconnector transmission capacity. Case studies and corresponding analyses are performed to demonstrate the efficiency of the GA model.

On Solving the Maximum Betweenness Problem Using Genetic Algorithms

In this paper a genetic algorithm (GA) is applied on Maximum Betweennes Problem (MBP). The maximum of the objective function is obtained by finding a permutation which satisfies a maximal number of betweenness constraints. Every permutation considered is genetically coded with an integer representation. Standard operators are used in the GA. Instances in the experimental results are randomly generated. For smaller dimensions, optimal solutions of MBP are obtained by total enumeration. For those instances, the GA reached all optimal solutions except one. The GA also obtained results for larger instances of up to 50 elements and 1000 triples. The running time of execution and finding optimal results is quite short.

Automatically Evolving Rotation-invariant Texture Image Descriptors by Genetic Programming

In computer vision, training a model that performs classification effectively is highly dependent on the extracted features, and the number of training instances. Conventionally, feature detection and extraction are performed by a domain-expert who, in many cases, is expensive to employ and hard to find. Therefore, image descriptors have emerged to automate these tasks. However, designing an image descriptor still requires domain-expert intervention. Moreover, the majority of machine learning algorithms require a large number of training examples to perform well. However, labelled data is not always available or easy to acquire, and dealing with a large dataset can dramatically slow down the training process. In this paper, we propose a novel Genetic Programming based method that automatically synthesises a descriptor using only two training instances per class. The proposed method combines arithmetic operators to evolve a model that takes an image and generates a feature vector. The performance of the proposed method is assessed using six datasets for texture classification with different degrees of rotation, and is compared with seven domain-expert designed descriptors. The results show that the proposed method is robust to rotation, and has significantly outperformed, or achieved a comparable performance to, the baseline methods.

An Indirect Genetic Algorithm for a Nurse Scheduling Problem

This paper describes a Genetic Algorithms approach to a manpower-scheduling problem arising at a major UK hospital. Although Genetic Algorithms have been successfully used for similar problems in the past, they always had to overcome the limitations of the classical Genetic Algorithms paradigm in handling the conflict between objectives and constraints. The approach taken here is to use an indirect coding based on permutations of the nurses, and a heuristic decoder that builds schedules from these permutations. Computational experiments based on 52 weeks of live data are used to evaluate three different decoders with varying levels of intelligence, and four well-known crossover operators. Results are further enhanced by introducing a hybrid crossover operator and by making use of simple bounds to reduce the size of the solution space. The results reveal that the proposed algorithm is able to find high quality solutions and is both faster and more flexible than a recently published Tabu Search approach.

Genetic Aspects Of Athletic Performance: The African Runners Phenomenon.

The current dominance of African runners in long-distance running is an intriguing phenomenon that highlights the close relationship between genetics and physical performance. Many factors in the interesting interaction between genotype and phenotype (eg, high cardiorespiratory fitness, higher hemoglobin concentration, good metabolic efficiency, muscle fiber composition, enzyme profile, diet, altitude training, and psychological aspects) have been proposed in the attempt to explain the extraordinary success of these runners. Increasing evidence shows that genetics may be a determining factor in physical and athletic performance. But, could this also be true for African long-distance runners? Based on this question, this brief review proposed the role of genetic factors (mitochondrial deoxyribonucleic acid, the Y chromosome, and the angiotensin-converting enzyme and the alpha-actinin-3 genes) in the amazing athletic performance observed in African runners, especially the Kenyans and Ethiopians, despite their environmental constraints.

Genetic Predictors Of Long-term Response To Growth Hormone (gh) Therapy In Children With Gh Deficiency And Turner Syndrome: The Influence Of A Socs2 Polymorphism.

There is great interindividual variability in the response to GH therapy. Ascertaining genetic factors can improve the accuracy of growth response predictions. Suppressor of cytokine signaling (SOCS)-2 is an intracellular negative regulator of GH receptor (GHR) signaling. The objective of the study was to assess the influence of a SOCS2 polymorphism (rs3782415) and its interactive effect with GHR exon 3 and -202 A/C IGFBP3 (rs2854744) polymorphisms on adult height of patients treated with recombinant human GH (rhGH). Genotypes were correlated with adult height data of 65 Turner syndrome (TS) and 47 GH deficiency (GHD) patients treated with rhGH, by multiple linear regressions. Generalized multifactor dimensionality reduction was used to evaluate gene-gene interactions. Baseline clinical data were indistinguishable among patients with different genotypes. Adult height SD scores of patients with at least one SOCS2 single-nucleotide polymorphism rs3782415-C were 0.7 higher than those homozygous for the T allele (P < .001). SOCS2 (P = .003), GHR-exon 3 (P= .016) and -202 A/C IGFBP3 (P = .013) polymorphisms, together with clinical factors accounted for 58% of the variability in adult height and 82% of the total height SD score gain. Patients harboring any two negative genotypes in these three different loci (homozygosity for SOCS2 T allele; the GHR exon 3 full-length allele and/or the -202C-IGFBP3 allele) were more likely to achieve an adult height at the lower quartile (odds ratio of 13.3; 95% confidence interval of 3.2-54.2, P = .0001). The SOCS2 polymorphism (rs3782415) has an influence on the adult height of children with TS and GHD after long-term rhGH therapy. Polymorphisms located in GHR, IGFBP3, and SOCS2 loci have an influence on the growth outcomes of TS and GHD patients treated with rhGH. The use of these genetic markers could identify among rhGH-treated patients those who are genetically predisposed to have less favorable outcomes.

Transmission Of Intra-cellular Genetic Information: A System Proposal.

One of the great challenges of the scientific community on theories of genetic information, genetic communication and genetic coding is to determine a mathematical structure related to DNA sequences. In this paper we propose a model of an intra-cellular transmission system of genetic information similar to a model of a power and bandwidth efficient digital communication system in order to identify a mathematical structure in DNA sequences where such sequences are biologically relevant. The model of a transmission system of genetic information is concerned with the identification, reproduction and mathematical classification of the nucleotide sequence of single stranded DNA by the genetic encoder. Hence, a genetic encoder is devised where labelings and cyclic codes are established. The establishment of the algebraic structure of the corresponding codes alphabets, mappings, labelings, primitive polynomials (p(x)) and code generator polynomials (g(x)) are quite important in characterizing error-correcting codes subclasses of G-linear codes. These latter codes are useful for the identification, reproduction and mathematical classification of DNA sequences. The characterization of this model may contribute to the development of a methodology that can be applied in mutational analysis and polymorphisms, production of new drugs and genetic improvement, among other things, resulting in the reduction of time and laboratory costs.

Characterization Of Microsatellite Markers Developed From Prosopis Rubriflora And Prosopis Ruscifolia (leguminosae - Mimosoideae), Legume Species That Are Used As Models For Genetic Diversity Studies In Chaquenian Areas Under Anthropization In South America.

Prosopis rubriflora and Prosopis ruscifolia are important species in the Chaquenian regions of Brazil. Because of the restriction and frequency of their physiognomy, they are excellent models for conservation genetics studies. The use of microsatellite markers (Simple Sequence Repeats, SSRs) has become increasingly important in recent years and has proven to be a powerful tool for both ecological and molecular studies. In this study, we present the development and characterization of 10 new markers for P. rubriflora and 13 new markers for P. ruscifolia. The genotyping was performed using 40 P. rubriflora samples and 48 P. ruscifolia samples from the Chaquenian remnants in Brazil. The polymorphism information content (PIC) of the P. rubriflora markers ranged from 0.073 to 0.791, and no null alleles or deviation from Hardy-Weinberg equilibrium (HW) were detected. The PIC values for the P. ruscifolia markers ranged from 0.289 to 0.883, but a departure from HW and null alleles were detected for certain loci; however, this departure may have resulted from anthropic activities, such as the presence of livestock, which is very common in the remnant areas. In this study, we describe novel SSR polymorphic markers that may be helpful in future genetic studies of P. rubriflora and P. ruscifolia.

Cognitive And Behavioral Heterogeneity In Genetic Syndromes.

this study aimed to investigate the cognitive and behavioral profiles, as well as the psychiatric symptoms and disorders in children with three different genetic syndromes with similar sociocultural and socioeconomic backgrounds. thirty-four children aged 6 to 16 years, with Williams-Beuren syndrome (n=10), Prader-Willi syndrome (n=11), and Fragile X syndrome (n=13) from the outpatient clinics of Child Psychiatry and Medical Genetics Department were cognitively assessed through the Wechsler Intelligence Scale for Children (WISC-III). Afterwards, a full-scale intelligence quotient (IQ), verbal IQ, performance IQ, standard subtest scores, as well as frequency of psychiatric symptoms and disorders were compared among the three syndromes. significant differences were found among the syndromes concerning verbal IQ and verbal and performance subtests. Post-hoc analysis demonstrated that vocabulary and comprehension subtest scores were significantly higher in Williams-Beuren syndrome in comparison with Prader-Willi and Fragile X syndromes, and block design and object assembly scores were significantly higher in Prader-Willi syndrome compared with Williams-Beuren and Fragile X syndromes. Additionally, there were significant differences between the syndromes concerning behavioral features and psychiatric symptoms. The Prader-Willi syndrome group presented a higher frequency of hyperphagia and self-injurious behaviors. The Fragile X syndrome group showed a higher frequency of social interaction deficits; such difference nearly reached statistical significance. the three genetic syndromes exhibited distinctive cognitive, behavioral, and psychiatric patterns.

Ssr-based Genetic Diversity And Structure Of Garlic Accessions From Brazil.

Garlic is a spice and a medicinal plant; hence, there is an increasing interest in 'developing' new varieties with different culinary properties or with high content of nutraceutical compounds. Phenotypic traits and dominant molecular markers are predominantly used to evaluate the genetic diversity of garlic clones. However, 24 SSR markers (codominant) specific for garlic are available in the literature, fostering germplasm researches. In this study, we genotyped 130 garlic accessions from Brazil and abroad using 17 polymorphic SSR markers to assess the genetic diversity and structure. This is the first attempt to evaluate a large set of accessions maintained by Brazilian institutions. A high level of redundancy was detected in the collection (50 % of the accessions represented eight haplotypes). However, non-redundant accessions presented high genetic diversity. We detected on average five alleles per locus, Shannon index of 1.2, HO of 0.5, and HE of 0.6. A core collection was set with 17 accessions, covering 100 % of the alleles with minimum redundancy. Overall FST and D values indicate a strong genetic structure within accessions. Two major groups identified by both model-based (Bayesian approach) and hierarchical clustering (UPGMA dendrogram) techniques were coherent with the classification of accessions according to maturity time (growth cycle): early-late and midseason accessions. Assessing genetic diversity and structure of garlic collections is the first step towards an efficient management and conservation of accessions in genebanks, as well as to advance future genetic studies and improvement of garlic worldwide.