Search results

Title: Evolution of distributed behavior
Creator: Knoester, David B.
Date: 2011
Collection: Electronic Theses & Dissertations
Description: In this dissertation, we describe a study in the evolution of distributed behavior, where evolutionary algorithms are used to discover behaviors for distributed computing systems. We define distributed behavior as that in which groups of individuals must both cooperate in working towards a common goal and coordinate their activities in a harmonious fashion. As such, communication among individuals is necessarily a key component of distributed behavior, and we have identified three classes of...
Show moreIn this dissertation, we describe a study in the evolution of distributed behavior, where evolutionary algorithms are used to discover behaviors for distributed computing systems. We define distributed behavior as that in which groups of individuals must both cooperate in working towards a common goal and coordinate their activities in a harmonious fashion. As such, communication among individuals is necessarily a key component of distributed behavior, and we have identified three classes of distributed behavior that require communication: data-driven behaviors, where semantically meaningful data is transmitted between individuals; temporal behaviors, which are based on the relative timing of individuals' actions; and structural behaviors, which are responsible for maintaining the underlying communication network connecting individuals. Our results demonstrate that evolutionary algorithms can discover groups of individuals that exhibit each of these different classes of distributed behavior, and that these behaviors can be discovered both in isolation (e.g., evolving a purely data-driven algorithm) and in concert (e.g., evolving an algorithm that includes both data-driven and structural behaviors). As part of this research, we show that evolutionary algorithms can discover novel heuristics for distributed computing, and hint at a new class of distributed algorithm enabled by such studies.The majority of this research was conducted with the Avida platform for digital evolution, a system that has been proven to aid researchers in understanding the biological process of evolution by natural selection. For this reason, the results presented in this dissertation provide the foundation for future studies that examine how distributed behaviors evolved in nature. The close relationship between evolutionary biology and evolutionary algorithms thus aids our study of evolving algorithms for the next generation of distributed computing systems.
Show less

Title: The evolution of a key innovation in an experimental population of Escherichia coli : a tale of opportunity, contingency, and co-option
Creator: Blount, Zachary David
Date: 2011
Collection: Electronic Theses & Dissertations
Description: The importance of historical contingency in evolution has been extensively debated over the last few decades, but direct empirical tests have been rare. Twelve initially identical populations of E. coli were founded in 1988 to investigate this issue. They have since evolved for more than 50,000 generations in a glucose-limited medium that also contains a citrate. However, the inability to use citrate as a carbon source under oxic conditions is a species-defining trait of ...
Show moreThe importance of historical contingency in evolution has been extensively debated over the last few decades, but direct empirical tests have been rare. Twelve initially identical populations of E. coli were founded in 1988 to investigate this issue. They have since evolved for more than 50,000 generations in a glucose-limited medium that also contains a citrate. However, the inability to use citrate as a carbon source under oxic conditions is a species-defining trait of E. coli. A weakly Cit+ variant capable of aerobic citrate utilization finally evolved in one population just prior to 31,500 generations. Shortly after 33,000 generations, the population experienced a several-fold expansion as strongly Cit+ variants rose to numerical dominance (but not fixation). The Cit+ trait was therefore a key innovation that increased both population size and diversity by opening a previously unexploited ecological opportunity.The long-delayed and unique evolution of the Cit+ innovation might be explained by two possible hypotheses. First, evolution of the Cit+ function may have required an extremely rare mutation. Alternately, the evolution of Cit+ may have been contingent upon one or more earlier mutations that had accrued over the population's history. I tested these hypotheses in a series of experiments in which I "replayed" evolution from different points in the population's history. I observed no Cit+ mutants among 8.4 x 1012 ancestral cells, nor among 9 x 1012 cells from 60 clones sampled in the first 15,000 generations. However, I observed a significantly greater tendency to evolve Cit+ among later clones. These results indicate that one or more earlier mutations potentiated the evolution of Cit+ by increasing the rate of mutation to Cit+ to an accessible, though still very low, level. The evolution of the Cit+ function was therefore contingent on the particular history of the population in which it occurred.I investigated the Cit+ innovation's history and genetic basis by sequencing the genomes of 29 clones isolated from the population at various time points. Analysis of these genomes revealed that at least 3 distinct clades coexisted for more than 10,000 generations prior to the innovation's evolution. The Cit+ trait originated in one clade by a tandem duplication that produced a new regulatory module in which a silent citrate transporter was placed under the control of an aerobically-expressed promoter. Subsequent increases in the copy number of this new regulatory module refined the initially weak Cit+ phenotype, leading to the population expansion. The 3 clades varied in their propensity to evolve the novel Cit+ function, though genotypes able to do so existed in all 3, implying that potentiation involved multiple mutations.My findings demonstrate that historical contingency can significantly impact evolution, even under the strictest of conditions. Moreover, they suggest that contingency plays an especially important role in the evolution of novel innovations that, like Cit+, require prior construction of a potentiating genetic background, and are thus not easily evolved by gradual, cumulative selection. Contingency may therefore have profoundly shaped life's evolution given the importance of evolutionary novelties in the history of life. Finally, the genetic basis of the Cit+ function illustrates the importance of promoter capture and altered gene regulation in mediation the exaptation events that often underlie evolutionary innovations.
Show less

Title: Ecological effects on the evolution of cooperative behaviors
Creator: Connelly, Brian Dale
Date: 2012
Collection: Electronic Theses & Dissertations
Description: Cooperative behaviors abound in nature and can be observed across the spectrum of life, from humans and primates to bacteria and other microorganisms. A deeper understanding of the forces that shape cooperation can offer key insights into how groups of organisms form and co-exist, how life transitioned to multicellularity, and account for the vast diversity present in ecosystems. This knowledge lends itself to a number of applications, such as understanding animal behavior and engineering...
Show moreCooperative behaviors abound in nature and can be observed across the spectrum of life, from humans and primates to bacteria and other microorganisms. A deeper understanding of the forces that shape cooperation can offer key insights into how groups of organisms form and co-exist, how life transitioned to multicellularity, and account for the vast diversity present in ecosystems. This knowledge lends itself to a number of applications, such as understanding animal behavior and engineering cooperative multi-agent systems, and may further help provide a fundamental basis for new industrial and medical treatments targeting communities of cooperating microorganisms.Although these behaviors are common, how evolution selected for and maintained them remains a difficult question for which several theories have been introduced. These theories, such as inclusive fitness and group selection, generally focus on the fitness costs and benefits of the behavior in question, and are often invoked to examine whether a trait with some predetermined costs and benefits could be maintained as an evolutionarily-stable strategy. Populations, however, do not exist and evolve in a vacuum. The environment in which they find themselves can play a critical role in shaping the types of adaptations that organisms accumulate, since one behavior may be highly beneficial in one environment, yet a hindrance in another. Ever-changing environments further complicate this picture, as maintaining a repertoire of behaviors for surviving in different environments is often costly. In addition to these environmental forces, the number and composition of other organisms with which individuals interact impose additional constraints. The combination of these factors results in significantly more complex dynamics.Using computational models and microbial populations, this dissertation examines several ways in which ecological factors can affect the evolution of cooperative behaviors. First, environmental disturbance is examined, in which a cooperative act enables organisms and their surrounding neighbors to survive a periodic kill event (population bottleneck) of varying severity. Resource availability is then studied, where populations must determine how much resource to allocate to cooperation. Finally, the effect that social structure, which define the patterns of interactions among the individuals in a population, is investigated.
Show less

Title: Mechanisms of adaptation and speciation : an experimental study using artificial life
Creator: Anderson, Carlos Jesus
Date: 2013
Collection: Electronic Theses & Dissertations
Description: Detailed experimental studies in evolutionary biology are sometimes difficult--even with model organisms. Theoretical models alleviate some of these difficulties and often provide clean results, but they cannot always capture the complexity of dynamic evolutionary processes. Artificial life systems are tools that fall somewhere between model organisms and theoretical models that have been successfully used to study evolutionary biology. These systems simulate simple organisms that replicate,...
Show moreDetailed experimental studies in evolutionary biology are sometimes difficult--even with model organisms. Theoretical models alleviate some of these difficulties and often provide clean results, but they cannot always capture the complexity of dynamic evolutionary processes. Artificial life systems are tools that fall somewhere between model organisms and theoretical models that have been successfully used to study evolutionary biology. These systems simulate simple organisms that replicate, acquire random mutations, and reproduce differentially; as a consequence, they evolve naturally (i.e., evolution itself is not simulated). Here I use the software Avida to study several open questions on the genetic mechanisms of adaptation and speciation.In Chapter 1 (p. 13), I investigated whether beneficial alleles during adaptation came from new mutations or standing genetic variation--alleles already present in the population. I found that most beneficial alleles came from standing genetic variation, but new mutations were necessary for long-term evolution. I also found that adaptation from standing genetic variation was faster than from new mutations. Finally, I found that recombination brought together beneficial combinations of alleles from standing genetic variation.In Chapter 2 (p. 31), I investigated the probability of compensatory adaptation vs. reversion. Compensatory adaptation is the fixation of mutations that ameliorate the effects of deleterious mutations while the original deleterious mutations remain fixed. I found that compensatory adaptation was very common, but the window of opportunity for reversion was increased when the initial fitness of the population was high, the population size was large, and the mutation rate was high. The reason that the window of opportunity for reversion was constrained was that negative epistatic interactions with compensatory mutations prevented the revertant from being beneficial to the population.In Chapter 3 (p. 58), I showed experimentally that compensatory adaptation can lead to reproductive isolation (specifically, postzygotic isolation). In addition, I found that the strength of this isolation was independent of the effect size of the original deleterious mutations. Finally, I found that both deleterious and compensatory mutations contribute equally to reproductive isolation.Reproductive isolation between populations often evolves as a byproduct of independent adaptation to new environments, but the selective pressures of these environments may be divergent (`ecological speciation') or uniform (`mutation-order speciation'). In Chapter 4 (p. 75), I compared directly the strength of postzygotic isolation generated by ecological and mutation-order processes with and without migration. I found that ecological speciation generally formed stronger isolation than mutation-order speciation and that mutation-order speciation was more sensitive to migration than ecological speciation.Under the Dobzhansky-Muller model of speciation, hybrid inviability or sterility results from the evolution of genetic incompatibilities (DMIs) between species-specific alleles. This model predicts that the number of pairwise DMIs between species should increase quadratically through time, but the few tests of this `snowball effect' have had conflicting results. In Chapter 5 (p. 101), I show that pairwise DMIs accumulated quadratically, supporting the snowball effect. I found that more complex genetic interactions involved alleles that rescued pairwise incompatibilities, explaining the discrepancy between the expected accumulations of DMIs and observation.
Show less

Title: Applying evolutionary computation techniques to address environmental uncertainty in dynamically adaptive systems
Creator: Ramirez, Andres J.
Date: 2013
Collection: Electronic Theses & Dissertations
Description: A dynamically adaptive system (DAS) observes itself and its execution environment at run time to detect conditions that warrant adaptation. If an adaptation is necessary, then a DAS changes its structure and/or behavior to continuously satisfy its requirements, even as its environment changes. It is challenging, however, to systematically and rigorously develop a DAS due to environmental uncertainty. In particular, it is often infeasible for a human to identify all possible combinations of...
Show moreA dynamically adaptive system (DAS) observes itself and its execution environment at run time to detect conditions that warrant adaptation. If an adaptation is necessary, then a DAS changes its structure and/or behavior to continuously satisfy its requirements, even as its environment changes. It is challenging, however, to systematically and rigorously develop a DAS due to environmental uncertainty. In particular, it is often infeasible for a human to identify all possible combinations of system and environmental conditions that a DAS might encounter throughout its lifetime. Nevertheless, a DAS must continuously satisfy its requirements despite the threat that this uncertainty poses to its adaptation capabilities. This dissertation proposes a model-based framework that supports the specification, monitoring, and dynamic reconfiguration of a DAS to explicitly address uncertainty. The proposed framework uses goal-oriented requirements models and evolutionary computation techniques to derive and fine-tune utility functions for requirements monitoring in a DAS, identify combinations of system and environmental conditions that adversely affect the behavior of a DAS, and generate adaptations on-demand to transition the DAS to a target system configuration while preserving system consistency. We demonstrate the capabilities of our model-based framework by applying it to an industrial case study involving a remote data mirroring network that efficiently distributes data even as network links fail and messages are dropped, corrupted, and delayed.
Show less

Title: Elucidating the evolutionary origins of collective animal behavior
Creator: Olson, Randal S.
Date: 2015
Collection: Electronic Theses & Dissertations
Description: Despite over a century of research, the evolutionary origins of collective animal behavior remain unclear. Dozens of hypotheses explaining the evolution of collective behavior have risen and fallen in the past century, but until recently it has been difficult to perform controlled behavioral evolution experiments to isolate these various hypotheses and test their individual effects. In this dissertation, I outline a relatively new method using digital models of evolution to perform controlled...
Show moreDespite over a century of research, the evolutionary origins of collective animal behavior remain unclear. Dozens of hypotheses explaining the evolution of collective behavior have risen and fallen in the past century, but until recently it has been difficult to perform controlled behavioral evolution experiments to isolate these various hypotheses and test their individual effects. In this dissertation, I outline a relatively new method using digital models of evolution to perform controlled behavioral evolution experiments. In particular, I use these models to directly explore the evolutionary consequence of the selfish herd, predator confusion, and the many eyes hypotheses, and demonstrate how the models can lend key insights useful to behavioral biologists, computer scientists, and robotics researchers. This dissertation lays the groundwork for the experimental study of the hypotheses surrounding the evolution of collective animal behavior, and establishes a path for future experiments to explore and disentangle how the various hypothesized benefits of collective behavior interact over evolutionary time.
Show less

Title: Out of the box optimization using the parameter-less population pyramid
Creator: Goldman, Brian W.
Date: 2015
Collection: Electronic Theses & Dissertations
Description: The Parameter-less Population Pyramid (P3) is a recently introduced method for performing evolutionary optimization without requiring any user-specified parameters. P3’s primary innovation is to replace the generational model with a pyramid of multiple populations that are iteratively created and expanded. In combination with local search and advanced crossover, P3 scales to problem difficulty, exploiting previously learned information before adding more diversity.Across seven problems, each...
Show moreThe Parameter-less Population Pyramid (P3) is a recently introduced method for performing evolutionary optimization without requiring any user-specified parameters. P3’s primary innovation is to replace the generational model with a pyramid of multiple populations that are iteratively created and expanded. In combination with local search and advanced crossover, P3 scales to problem difficulty, exploiting previously learned information before adding more diversity.Across seven problems, each tested using on average 18 problem sizes, P3 outperformed all five advanced comparison algorithms. This improvement includes requiring fewer evaluations to find the global optimum and better fitness when using the same number of evaluations. Using both algorithm analysis and comparison we show P3’s effectiveness is due to its ability to properly maintain, add, and exploit diversity. Unlike the best comparison algorithms, P3 was able to achieve this quality without any problem-specific tuning. Thus, unlike previous parameter-less methods, P3 does not sacrifice quality for applicability. Therefore we conclude that P3 is an efficient, general, parameter-less approach to black-box optimization that is more effective than existing state-of-the-art techniques.Furthermore, P3 can be specialized for gray-box problems, which have known, limited, non-linear relationships between variables. Gray-Box P3 leverages the Hamming-Ball Hill Climber, an exceptionally efficient form of local search, as well as a novel method for performing crossover using the known variable interactions. In doing so Gray-Box P3 is able to find the global optimum of large problems in seconds, improving over Black-Box P3 by up to two orders of magnitude.
Show less

Title: Automatically addressing uncertainty in autonomous robots with computational evolution
Creator: Clark, Anthony Joseph
Date: 2016
Collection: Electronic Theses & Dissertations
Description: Autonomous robotic systems are becoming prevalent in our daily lives. Many robots are still restricted to manufacturing settings where precision and repetition are paramount. However, autonomous devices are increasingly being designed for applications such as search and rescue, remote sensing, and tasks considered too dangerous for people. In these cases, it is crucial to continue operation even when some unforeseen adversity decreases performance levels---a robot with diminished performance...
Show moreAutonomous robotic systems are becoming prevalent in our daily lives. Many robots are still restricted to manufacturing settings where precision and repetition are paramount. However, autonomous devices are increasingly being designed for applications such as search and rescue, remote sensing, and tasks considered too dangerous for people. In these cases, it is crucial to continue operation even when some unforeseen adversity decreases performance levels---a robot with diminished performance is still successful if it is able to deal with uncertainty, which includes any unexpected change due to unmodeled dynamics, changing control strategies, or changes in functionality resulting from damage or aging.The research presented in this dissertation seeks to improve such autonomous systems through three evolution-based techniques. First, robots are optimized offline so that they best exploit available material characteristics, for instance flexible materials, with respect to multiple objectives (e.g., speed and efficiency). Second, adaptive controllers are evolved, which enable robots to better respond to unforeseen changes to themselves and their environments. Finally, adaptation limits are discovered using a proposed mode discovery algorithm. Once the boundaries of adaptation are known, self-modeling is applied online to determine the current operating mode and select/generate an appropriate controller.These three techniques work together to create a holistic method, which will enable autonomous robotic systems to automatically handle uncertainty. The proposed methods are evaluated using robotic fish as a test platform. Such systems can benefit in multiple ways from the integration of flexible materials. Moreover, robotic fish operate in complex, nonlinear environments, enabling thorough testing of the proposed methods.
Show less

Title: Hybrid structural and behavioral diversity techniques for effective genetic programming
Creator: Burks, Armand Rashad
Date: 2017
Collection: Electronic Theses & Dissertations
Description: "Sustaining the diversity of evolving populations is a fundamental issue in genetic programming. We describe a novel measure of structural diversity for tree-based genetic programming, and we demonstrate its utility compared to other diversity techniques. We demonstrate our technique on the real-world application of tuberculosis screening from X-ray images. We then introduce a new paradigm of genetic programming that involves simultaneously maintaining structural and behavioral diversity in...
Show more"Sustaining the diversity of evolving populations is a fundamental issue in genetic programming. We describe a novel measure of structural diversity for tree-based genetic programming, and we demonstrate its utility compared to other diversity techniques. We demonstrate our technique on the real-world application of tuberculosis screening from X-ray images. We then introduce a new paradigm of genetic programming that involves simultaneously maintaining structural and behavioral diversity in order to further improve the efficiency of genetic programming. Our results show that simultaneously promoting structural and behavioral diversity improves genetic programming by leveraging the benefits of both aspects of diversity while overcoming the shortcomings of either technique in isolation. The hybridization increases the behavioral diversity of our structural diversity technique, and increases the structural diversity of the behavioral diversity techniques. This increased diversity leads to performance gains compared to either technique in isolation. We found that in many cases, our structural diversity technique provides significant performance improvement compared to other state-of-the-art techniques. Our results from the experiments comparing the hybrid techniques indicate that the largest performance gain was typically attributed to our structural diversity technique. The incorporation of the behavioral diversity techniques provide additional improvement in many cases."--Page ii.
Show less

MSU Libraries

Digital Repository

You are here