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: Experimental evolution and ecological consequences : new niches and changing stoichiometry
Creator: Turner, Caroline B.
Date: 2015
Collection: Electronic Theses & Dissertations
Description: Evolutionary change can alter the ecological conditions in which organisms live and continue to evolve. My dissertation research used experimental evolution to study two aspects of evolutionary change with ecological consequences: the generation of new ecological niches and evolution of the elemental composition of biomass. I worked with the long-term evolution experiment (LTEE), which is an ongoing experiment in which E. coli have evolved under laboratory conditions for more than 60,000...
Show moreEvolutionary change can alter the ecological conditions in which organisms live and continue to evolve. My dissertation research used experimental evolution to study two aspects of evolutionary change with ecological consequences: the generation of new ecological niches and evolution of the elemental composition of biomass. I worked with the long-term evolution experiment (LTEE), which is an ongoing experiment in which E. coli have evolved under laboratory conditions for more than 60,000 generations. The LTEE began with extremely simple ecological conditions. Twelve populations were founded from a single bacterial genotype and growth was limited by glucose availability. In Chapter 1, I focused on a population within the LTEE in which some of the bacteria evolved the ability to consume a novel resource, citrate. Citrate was present in the growth media throughout the experiment, but E. coli is normally unable to consume it under aerobic conditions. The citrate consumers (Cit+) coexisted with a clade of bacteria which were unable to consume citrate (Cit-). Specialization on glucose, the standard carbon source in the LTEE, was insufficient to explain the frequency-dependent coexistence of Cit- with Cit+. Instead Cit– evolved to cross-feed on molecules released by Cit+. The evolutionary innovation of citrate consumption led to a more complex ecosystem in which two co-existing ecotypes made use of five different carbon sources.After 10,000 generations of coexistence, Cit- went extinct from the population (Chapter 2). I conducted replay experiments, re-evolving for 500 generations 20 replicate populations from prior to extinction. Cit- was retained in all populations, indicating that the extinction was not deterministic. Furthermore, when I added small numbers of Cit- to the population after extinction, Cit- was able to reinvade. It therefore appears that the Cit- extinction was not due to exclusion by Cit+, but rather to unknown laboratory variation.Chapter 3 shifts focus to studying evolutionary changes in stoichiometry, the ratio of different elements within organisms’ biomass. Variation in stoichiometry between organisms has important ecological consequences, but the evolutionary origin of that variation had not previously been studied experimentally. Growth in the LTEE is carbon limited and nitrogen and phosphorus are abundant. Additionally, daily transfer to fresh media selects for increased growth rate, which other research has suggested correlates to higher phosphorus content. Consistent with our predictions based on this environment, clones isolated after 50,000 generations of evolution had significantly higher nitrogen and phosphorus content than ancestral clones. There was no change in the proportion of carbon in biomass, but the total amount of carbon retained in biomass increased, indicating that the bacteria also evolved higher carbon use efficiency.To test whether the increases in nitrogen and phosphorus observed in the LTEE were a result of carbon limitation or were side effects of other selective factors in the experiment, I evolved clones from the LTEE for 1000 generations under nitrogen rather than carbon limitation (Chapter 4). The stoichiometry of the bacteria did change over the course of 1000 generations, indicating that evolution of stoichiometry can occur over relatively short time frames. Unexpectedly however, the evolved bacteria had higher nitrogen and phosphorus content. It appears that the bacteria were initially poor at incorporating nitrogen into biomass, but evolved improved nitrogen uptake.
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: Evolution of cooperation in the light of information theory
Creator: Mirmomeni, Masoud
Date: 2015
Collection: Electronic Theses & Dissertations
Description: Cooperation is ubiquitous in different biological levels and is necessary for evolution to shape the life and create new forms of organization. Genes cooperate in controlling cells; cells efficiently collaborate together to produce cohesive multi-cellular organisms; members of insect colonies and animal clans cooperate in protecting the colony and providing food. Cooperation means that members of a group bear a cost, c, for another individuals to earn a benefit, b. While cooperators of the...
Show moreCooperation is ubiquitous in different biological levels and is necessary for evolution to shape the life and create new forms of organization. Genes cooperate in controlling cells; cells efficiently collaborate together to produce cohesive multi-cellular organisms; members of insect colonies and animal clans cooperate in protecting the colony and providing food. Cooperation means that members of a group bear a cost, c, for another individuals to earn a benefit, b. While cooperators of the group help others by paying a cost, defectors receive the benefits of this altruistic behavior without providing any service in return to the group. To address this dilemma, here we use a game theoretic approach to model and study evolutionary dynamics that can lead to unselfish behavior. Evolutionary game theory is an approach to study frequency-dependent systems. In evolutionary games the fitness of individuals depends on the relative abundance of the various types in the population. We explore different strategies and different games such as iterated games between players with conditional strategies, multi player games, and iterated games between fully stochastic strategies in noisy environments to find the necessity conditions that lead to cooperation. Interestingly, we see that in all of these games communication is the key factor for maintaining cooperation among selfish individuals. We show that communication and information exchange is necessary for the emergence of costly altruism, and to maintain cooperation in the group there should be minimum rate of communication between individuals. We quantify this minimum amount of information exchange, which is necessary for individuals to exhibit cooperative behavior, by defining a noisy communication channel between them in iterated stochastic games and measuring the communication rate (in bits) during the break down of cooperation.
Show less

Title: An analysis of fitness in long-term asexual evolution experiments
Creator: Wiser, Michael J.
Date: 2015
Collection: Electronic Theses & Dissertations
Description: Evolution is the central unifying concept of modern biology. Yet it can be hard to study in natural system, as it unfolds across generations. Experimental evolution allows us to ask questions about the process of evolution itself: How repeatable is the evolutionary process? How predictable is it? How general are the results? To address these questions, my collaborators and I carried out experiments both within the Long-Term Evolution Experiment (LTEE) in the bacteria Escherichia coli, and the...
Show moreEvolution is the central unifying concept of modern biology. Yet it can be hard to study in natural system, as it unfolds across generations. Experimental evolution allows us to ask questions about the process of evolution itself: How repeatable is the evolutionary process? How predictable is it? How general are the results? To address these questions, my collaborators and I carried out experiments both within the Long-Term Evolution Experiment (LTEE) in the bacteria Escherichia coli, and the digital evolution software platform Avida. In Chapter 1, I focused on methods. Previous research in the LTEE has relied on one particular way of measuring fitness, which we know becomes less precise as fitness differentials increase. I therefore decided to test whether two alternate ways of measuring fitness would improve precision, using one focal population. I found that all three methods yielded similar results in both fitness and coefficient of variation, and thus we should retain the traditional method.In Chapter 2, I turned to measuring fitness in each of the populations. Previous work had considered fitness to change as a hyperbola. A hyperbolic function is bounded, and predicts that fitness will asymptotically approach a defined upper bound; however, we knew that fitness in these populations routinely exceeded the asymptotic limit calculated from a hyperbola fit to the earlier data. I instead used to a power law, a mathematical function that does not have an upper bound. I found that this function substantially better describes fitness in this system, both among the whole set of populations, and in most of the individual populations. I also found that the power law models fit on just early subsets of the data accurately predict fitness far into the future. This implies that populations, even after 50,000 generations of evolution in consistent environment, are so far from the tops of fitness peaks that we cannot detect evidence of those peaks.In Chapter 3, I examined to how variance in fitness changes over long time scales. The among-population variance over time provides us information about the adaptive landscape on which the populations have been evolving. I found that among-population variance remains significant. Further, competitions between evolved pairs of populations reveal additional details about fitness trajectories than can be seen from competitions against the ancestor. These results demonstrate that our populations have been evolving on a complex adaptive landscape.In Chapter 4, I examined whether the patterns found in Chapter 2 apply to a very different evolutionary system, Avida. This system incorporates many similar evolutionary pressures as the LTEE, but without the details of cellular biology that underlie nearly all organic life. I find that in both the most complex and simplest environments in Avida, fitness also follows the same power law dynamics as seen in the LTEE. This implies that power law dynamics may be a general feature of evolving systems, and not dependent on the specific details of the system being studied.
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: Balancing convergence and diversity in evolutionary single, multi and many objectives
Creator: Seada, Haitham
Date: 2017
Collection: Electronic Theses & Dissertations
Description: "Single objective optimization targets only one solution, that is usually the global optimum. On the other hand, the goal of multiobjective optimization is to represent the whole set of trade-off Pareto-optimal solutions to a problem. For over thirty years, researchers have been developing Evolutionary Multiobjective Optimization (EMO) algorithms for solving multiobjective optimization problems. Unfortunately, each of these algorithms were found to work well on a specific range of objective...
Show more"Single objective optimization targets only one solution, that is usually the global optimum. On the other hand, the goal of multiobjective optimization is to represent the whole set of trade-off Pareto-optimal solutions to a problem. For over thirty years, researchers have been developing Evolutionary Multiobjective Optimization (EMO) algorithms for solving multiobjective optimization problems. Unfortunately, each of these algorithms were found to work well on a specific range of objective dimensionality, i.e. number of objectives. Most researchers overlooked the idea of creating a cross-dimensional algorithm that can adapt its operation from one level of objective dimensionality to the other. One important aspect of creating such algorithm is achieving a careful balance between convergence and diversity. Researchers proposed several techniques aiming at dividing computational resources uniformly between these two goals. However, in many situations, only either of them is difficult to attain. Also for a new problem, it is difficult to tell beforehand if it will be challenging in terms of convergence, diversity or both. In this study, we propose several extensions to a state-of-the-art evolutionary many-objective optimization algorithm - NSGA-III. Our extensions collectively aim at (i) creating a unified optimization algorithm that dynamically adapts itself to single, multi- and many objectives, and (ii) enabling this algorithm to automatically focus on either convergence, diversity or both, according to the problem being considered. Our approach augments the already existing algorithm with a niching-based selection operator. It also utilizes the recently proposed Karush Kuhn Tucker Proximity Measure to identify ill-converged solutions, and finally, uses several combinations of point-to-point single objective local search procedures to remedy these solutions and enhance both convergence and diversity. Our extensions are shown to produce better results than state-of-the-art algorithms over a set of single, multi- and many-objective problems."--Pages ii-iii.
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

Title: Evolution of decision-making systems
Creator: Schossau, Jorden D.
Date: 2017
Collection: Electronic Theses & Dissertations
Description: Adaptive biological or engineered systems are adaptive because they can make decisions. Some systems such as viruses use their molecular composition – genetic information – to decide when to become lysogenic (dormant) or lytic (active). Others, such as self-driving cars, must use spatiotemporal information about obstacles, speed, and previous signs to determine when to turn or begin braking. Computational models of systems allow us to both engineer better systems, and create better scientific...
Show moreAdaptive biological or engineered systems are adaptive because they can make decisions. Some systems such as viruses use their molecular composition – genetic information – to decide when to become lysogenic (dormant) or lytic (active). Others, such as self-driving cars, must use spatiotemporal information about obstacles, speed, and previous signs to determine when to turn or begin braking. Computational models of systems allow us to both engineer better systems, and create better scientific understanding about the dynamic world. The practice of modeling decision-making started with the study of interactions between rational agents on the spectrum of conflict and cooperation began with Von Neumann and Morgenstern's Theory of Game and Economic Behavior.Scenarios, called "games", are models designed and studied to increase understanding of conflict and cooperation between these agents. The games discussed here are Prisoner's Dilemma and Volunteer's Dilemma. Modern methods of analysis for games involving populations of interacting agents fail to predict the final strategy distribution among all agents. In chapter 2 I develop a new computational agent-based simulation used as an inductive study system to compare the deductive predictive capabilities of an analytical model that is capable of predicting the final distribution under idealized conditions. Lastly, I show a novel finding that the agent-based model suggests probabilistic, or mixed, strategies (such as probabilistic gene expression) are a result of the development and maintenance of cooperation in Volunteer's Dilemma.Game theory fails to provide tractable models for more complex decision-making situations, such as those with complex spatial or temporal dimensions. In these cases an algorithm of conditional logic may be used to simulate decision-making behavior. Yet still there are systems for which the use of an algorithm as a model is inadequate due to incomplete knowledge of the system. Perhaps the model makes too many generalizations, is limited by atomic discretization, or is otherwise incomplete. In these cases it is useful to compensate for deficits by using probabilistic logic. That is, we assume that a stochastic process can roughly describe those subprocesses not fully modeled.Lastly, algorithms as decision strategies can incorporate temporal information in the decision-making process. There are two ways temporal information can be used in an individual's conditional logic: evolutionary, and lifetime. The evolutionary approach has proved much more flexible as a means to discover and tune models of unknown decision-making processes. Neuroevolution is a machine learning method that uses evolutionary algorithms to train artificial neural networks as models of decision-making systems. There is currently a wide diversity of methods for neuroevolution that all share common structures of the types of problems being solved: those generally being cognitive tasks. Toward this end it would be useful if there were some properties common to all cognitive systems that could be incorporated into the optimizing objective function in order to enhance or simplify the evolutionary process. In chapter 3 and 4 I explore new methods of improving model discovery through neuroevolution and discuss the applicability of these methods for probabilistic models.
Show less

Title: The evolution of neural plasticity in digital organisms
Creator: Sheneman, Leigh
Date: 2017
Collection: Electronic Theses & Dissertations
Description: Learning is a phenomenon that organisms throughout nature demonstrate and that machinelearning aims to replicate. In nature, it is neural plasticity that allows an organismto integrate the outcomes of their past experiences into their selection of future actions.While neurobiology has identified some of the mechanisms used in this integration, how theprocess works is still a relatively unclear and highly researched topic in the cognitive sciencefield. Meanwhile in the field of machine...
Show moreLearning is a phenomenon that organisms throughout nature demonstrate and that machinelearning aims to replicate. In nature, it is neural plasticity that allows an organismto integrate the outcomes of their past experiences into their selection of future actions.While neurobiology has identified some of the mechanisms used in this integration, how theprocess works is still a relatively unclear and highly researched topic in the cognitive sciencefield. Meanwhile in the field of machine learning, researchers aim to create algorithms thatare also able to learn from past experiences; this endeavor is complicated by the lack ofunderstanding how this process takes place within natural organisms.In this dissertation, I extend the Markov Brain framework [1, 2] which consists of evolvablenetworks of probabilistic and deterministic logic gates to include a novel gate type{feedback gates. Feedback gates use internally generated feedback to learn how to navigatea complex task by learning in the same manner a natural organism would. The evolutionarypath the Markov Brains take to develop this ability provides insight into the evolutionof learning. I show that the feedback gates allow Markov Brains to evolve the ability tolearn how to navigate environments by relying solely on their experiences. In fact, the probabilisticlogic tables of these gates adapt to the point where the an input almost alwaysresults in a single output, to the point of almost being deterministic. Further, I show thatthe mechanism the gates use to adapt their probability table is robust enough to allow theagents to successfully complete the task in novel environments. This ability to generalizeto the environment means that the Markov Brains with feedback gates that emerge fromevolution are learning autonomously; that is without external feedback. In the context ofmachine learning, this allows algorithms to be trained based solely on how they interact withthe environment. Once a Markov Brain can generalize, it is able adapt to changing sets of stimuli, i.e. reversal learn. Machines that are able to reversal learn are no longer limited tosolving a single task. Lastly, I show that the neuro-correlate is increased through neuralplasticity using Markov Brains augmented with feedback gates. The measurement of isbased on Information Integration Theory[3, 4] and quanties the agent's ability to integrateinformation.
Show less

Title: Economic gain-aware routing protocols for device-to-device content dissemination
Creator: Hajiaghajani Memar, Faezeh
Date: 2017
Collection: Electronic Theses & Dissertations
Description: "The objective of this dissertation is to investigate Device-to-Device content dissemination protocols for maximizing the economic gain of dissemination for given combinations of commercial and network parameters. " -- Abstract.

Title: The evolution of complexity and robustness in small populations
Creator: LaBar, Thomas
Date: 2018
Collection: Electronic Theses & Dissertations
Description: "A central goal of evolutionary biology is to understand a population's evolutionary trajectory from fundamental population-level characteristics. The mathematical framework of population genetics provides the tools to make these predictions. And while population genetics provides a well-studied framework to understand how adaptation and neutral evolution quantitatively alter population fitness, less attention has been paid to using population genetics to predict qualitative evolutionary...
Show more"A central goal of evolutionary biology is to understand a population's evolutionary trajectory from fundamental population-level characteristics. The mathematical framework of population genetics provides the tools to make these predictions. And while population genetics provides a well-studied framework to understand how adaptation and neutral evolution quantitatively alter population fitness, less attention has been paid to using population genetics to predict qualitative evolutionary outcomes. For instance, do different populations evolve alternative genetic mechanisms to encode similar phenotypic traits, and if so, which processes lead to these differences? This dissertation investigates the role of population size in altering the qualitative outcome of evolution. It is difficult to experimentally investigate qualitative evolutionary outcomes, especially in small populations, due to the time required for novel evolutionary features to appear. To get around this constraint, I use digital experimental evolution. While digital evolution experiments lack aspects of biological realism, in some regards they are the only methodology that can approach the complexity of biological systems while maintaining the ease of analysis present in mathematical models. Digital evolution experiments can never prove that certain evolutionary trajectories occur in biological populations, but they can suggest hypotheses to test in more realistic model systems. First, I explore the role of population size in determining the evolution of both genomic and phenotypic complexity. Previous hypotheses have argued that small population size may lead to increases in complexity and I test aspects of those hypotheses here. Second, I introduce the novel concept of 'drift robustness' and argue that drift robustness is a strong factor in the evolution of small populations. Finally, I end with a project on the role of genome size in enhancing the extinction risk of small populations. I conclude with a broader discussion of the consequences of this research, some limitations of the results, and some ideas for future research."--Page ii.
Show less

Title: A differential evolution approach to feature selection in genomic prediction
Creator: Whalen, Ian
Date: 2018
Collection: Electronic Theses & Dissertations
Description: The use of genetic markers has become widespread for prediction of genetic merit in agricultural applications and is a beginning to show promise for estimating propensity to disease in human medicine. This process is known as genomic prediction and attempts to model the mapping between an organism's genotype and phenotype. In practice, this process presents a challenging problem. Sequencing and recording phenotypic traits are often expensive and time consuming. This leads to datasets often...
Show moreThe use of genetic markers has become widespread for prediction of genetic merit in agricultural applications and is a beginning to show promise for estimating propensity to disease in human medicine. This process is known as genomic prediction and attempts to model the mapping between an organism's genotype and phenotype. In practice, this process presents a challenging problem. Sequencing and recording phenotypic traits are often expensive and time consuming. This leads to datasets often having many more features than samples. Common models for genomic prediction often fall victim to overfitting due to the curse of dimensionality. In this domain, only a fraction of the markers that are present significantly affect a particular trait. Models that fit to non-informative markers are in effect fitting to statistical noise, leading to a decrease in predictive performance. Therefore, feature selection is desirable to remove markers that do not appear to have a significant effect on the trait being predicted. The method presented here uses differential evolution based search for feature selection. This study will characterize differential evolution's efficacy in feature selection for genomic prediction and present several extensions to the base search algorithm in an attempt to apply domain knowledge to guide the search toward better solutions.
Show less

Title: Deconstructing the correlated nature of ancient and emergent traits : an evolutionary investigation of metabolism, morphology, and mortality
Creator: Grant, Nkrumah Alions
Date: 2020
Collection: Electronic Theses & Dissertations
Description: Phenotypic correlations are products of genetic and environmental interactions, yet the nature of these correlations is obscured by the multitude of genes organisms possess. My dissertation work focused on using 12 populations of Escherichia coli from Richard Lenski's long-term evolution experiment (LTEE) to understand how genetic correlations facilitate or impede an organism's evolution. In chapter 1, I describe how ancient correlations between aerobic and anaerobic metabolism have...
Show morePhenotypic correlations are products of genetic and environmental interactions, yet the nature of these correlations is obscured by the multitude of genes organisms possess. My dissertation work focused on using 12 populations of Escherichia coli from Richard Lenski's long-term evolution experiment (LTEE) to understand how genetic correlations facilitate or impede an organism's evolution. In chapter 1, I describe how ancient correlations between aerobic and anaerobic metabolism have maintained - and even improved - the capacity of E. coli to grow in an anoxic environment despite 50,000 generations of relaxed selection for anaerobic growth. I present genomic evidence illustrating substantially more mutations have accumulated in anaerobic-specific genes and show parallel evolution at two genetic loci whose protein products regulate the aerobic-to-anaerobic metabolic switch. My findings reject the "if you don't use it, you lose it" notion underpinning relaxed selection and show modules with deep evolutionary roots can overlap more, hence making them harder to break. In chapter 2, I revisit previous work in the LTEE showing that the fitness increases measured for the 12 populations positively correlated with an increase in cell size. This finding was contrary to theory predicting smaller cells should have evolved. Sixty thousand generations have surpassed since that initial study, and new fitness data collected for the 12 populations show fitness has continued to increase over this period. Here, I asked whether cell size also continued to increase. To this end, I measured the size of cells for each of the 12 populations spanning 50,000 generations of evolution using a particle counter, microscopy, and machine learning. I show cell size has continued to increase and that it remains positively correlated with fitness. I also present several other observations including heterogeneity in cell shape and size, parallel mutations in cell-shape determining genes, and elevated cell death in the single LTEE population that evolved a novel metabolism - namely the ability to grow aerobically on citrate. This last observation formed the basis of my chapter 3 research where my collaborators and I fully examine the cell death finding and the associated genotypic and phenotypic consequences of the citrate metabolic innovation.
Show less

Title: Optimizing for Mental Representations in the Evolution of Artificial Cognitive Systems
Creator: Kirkpatrick, Douglas Andrew
Date: 2021
Collection: Electronic Theses & Dissertations
Description: Mental representations, or sensor-independent internal models of the environment, are used to interpret the world and make decisions based upon that understanding. For example, a human sees dark clouds in the sky, recalls that often dark clouds mean rain (a mental representation), and consequently decides to wear a raincoat. I seek to identify, understand, and encourage the evolution of these representations in silico. Previous work identified an information-theoretic tool, referred to as R,...
Show moreMental representations, or sensor-independent internal models of the environment, are used to interpret the world and make decisions based upon that understanding. For example, a human sees dark clouds in the sky, recalls that often dark clouds mean rain (a mental representation), and consequently decides to wear a raincoat. I seek to identify, understand, and encourage the evolution of these representations in silico. Previous work identified an information-theoretic tool, referred to as R, that measures mental representations in artificial cognitive systems (e.g., Markov Brains or Recurrent Neural Networks). Further work found that selecting for R, along with task performance, in the evolution of artificial cognitive systems leads to better overall performance on a given task. Here I explore the implications and opportunities of this modified selection process, referred to as R-augmentation. After an overview of common methods, techniques, and computational substrates in Chapter 1, a series of working chapters experimentally demonstrate the capabilities and possibilities of R-augmentation. First, in Chapter 2, I address concerns regarding potential limitations of R-augmentation. This includes an refutation of suspected negative impacts on the system’s ability to generalize within-domain and the system’s robustness to sensor noise. To the contrary, the systems evolved with R-augmentation tend to perform better than those evolved without, in the context of noisy environments and different computational components. In Chapter 3 I examine how R-augmentation works across different cognitive structures, focusing on the evolution of genetic programming related structures and the effect that augmentation has on the distribution of their representations. For Chapter 4, in the context of the all-component Markov Brain (referred to as a Buffet Brain, see [Hintze et al., 2019]) I analyze potential reasons that explain why R-augmentation works; the mechanism seems to be based on evolutionary dynamics as opposed to structural or component differences. Next, I demonstrate a novel usage of R-augmentation in Chapter 5; with R-augmentation, one can use far fewer training examples during evolution and the resulting systems still perform approximately as well as those that were trained on the full set of examples. This advantage in increased performance at low sample size is found in some examples of in-domain and out-domain generalization, with the ”worst-case” scenario being that the networks created by R-augmentation perform as well as their unaugmented equivalents. Lastly, in Chapter 6 I move beyond R-augmentation to explore using other neuro-correlates - particularly the distribution of representations, called smearedness - as part of the fitness function. I investigate the possibility of using MAP-Elites to identify an optimal value of smearedness for augmentation or for use as an optimization method in its own right. Taken together, these investigations demonstrate both the capabilities and limitations of R-augmentation, and open up pathways for future research.
Show less

Title: Digital Evolution in Experimental Phylogenetics and Evolution Education
Creator: Kohn, Cory
Date: 2021
Collection: Electronic Theses & Dissertations
Description: The creation and evaluation of known evolutionary histories and the implementation of student investigatory experiences on evolution are difficult endeavors that have only recently been feasible. The research presented in this dissertation is related in their shared use of digital evolution with Avidians as a model study system, both to conduct science research in experimental phylogenetics and to conduct education research in curricular intervention to aid student understanding.I first...
Show moreThe creation and evaluation of known evolutionary histories and the implementation of student investigatory experiences on evolution are difficult endeavors that have only recently been feasible. The research presented in this dissertation is related in their shared use of digital evolution with Avidians as a model study system, both to conduct science research in experimental phylogenetics and to conduct education research in curricular intervention to aid student understanding.I first present background discussions on the Avidian digital evolution study system—as implemented in Avida and Avida-ED—and its favorable use in experimental phylogenetics and biology education owing to its greater biological realism than computational simulations, and greater utility and generality than biological systems. Prior work on conducting experimental evolution for use in phylogenetics and work on developing undergraduate lab curricula using experimental evolution are also reviewed. I establish digital evolution as an effective method for phylogenetic inference validation by demonstrating that results from a known Avidian evolutionary history are concordant, under similar conditions, to established biological experimental phylogenetics work. I then further demonstrate the greater utility and generality of digital evolution over biological systems by experimentally testing how phylogenetic accuracy may be reduced by complex evolutionary processes operating singly or in combination, including absolute and relative degrees of evolutionary change between lineages (i.e., inferred branch lengths), recombination, and natural selection. These results include that directional selection aids phylogenetic inference, while stabilizing selection impedes it. By evaluating clade accuracy and clade resolvability across treatments, I evaluate measures of tree support and its presentation in the form of consensus topologies and I offer several general recommendations for systematists. Using a larger and more biologically realistic experimental design, I systematically examine a few of the complex processes that are hypothesized to affect phylogenetic accuracy—natural selection, recombination, and deviations from the model of evolution. By analyzing the substitutions that occurred and calculating selection coefficients for derived alleles throughout their evolutionary trajectories to fixation, I show that molecular evolution in these experiments is complex and proceeding largely as would be expected for biological populations. Using these data to construct empirical substitution models, I demonstrate that phylogenetic inference is incredibly robust to significant molecular evolution model deviations. I show that neutral evolution in the presence of always-occurring population processes, such as clonal or Hill-Robertson interference and lineage sorting, result in reduced clade support, and that selection and especially recombination, including their joint occurrence, restore this otherwise-reduced phylogenetic accuracy. Finally, this work demonstrates that inferred branch lengths are often quite inaccurate despite clade support being accurate. While phylogenetic inference methods performed relatively well in both theoretically facile and challenging molecular evolution scenarios, their accuracy in clade support might be a remarkable case of being right for misguided reasons, since branch length inference were largely inaccurate, and drastically different models of evolution made little difference. This work highlights the need for further research that evaluates phylogenetic methods under experimental conditions and suggests that digital evolution has a role here. Finally, I examine student understanding of the importance of biological variation in the context of a course featuring a digital evolution lab. I first describe the Avida-ED lab curriculum and its fulfillment of calls for reform in education. Then I describe the specific education context and other course features that aim to address student conceptualization of variation. I present a modified published assessment on transformational and variational understanding and findings regarding student understanding of variation within an evolution education progression. Finally, I offer suggestions on incorporating course material to engage student understanding of variation.
Show less

MSU Libraries

Digital Repository

Enabled Filters

Pages

Pages

MSU Libraries

Digital Repository

You are here

Search results

Pages

Pages