Search results

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: 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 wholeset of trade-off Pareto-optimal solutions to a problem. For over thirty years, researchershave been developing Evolutionary Multiobjective Optimization (EMO) algorithms forsolving multiobjective optimization problems. Unfortunately, each of these algorithmswere found to work well on a specific range of objective...
Show moreSingle 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 wholeset of trade-off Pareto-optimal solutions to a problem. For over thirty years, researchershave been developing Evolutionary Multiobjective Optimization (EMO) algorithms forsolving multiobjective optimization problems. Unfortunately, each of these algorithmswere found to work well on a specific range of objective dimensionality, i.e. number ofobjectives. Most researchers overlooked the idea of creating a cross-dimensional algorithmthat 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 betweenconvergence and diversity. Researchers proposed several techniques aiming at dividingcomputational 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 totell beforehand if it will be challenging in terms of convergence, diversity or both. In thisstudy, we propose several extensions to a state-of-the-art evolutionary many-objectiveoptimization algorithm – NSGA-III. Our extensions collectively aim at (i) creating a unifiedoptimization algorithm that dynamically adapts itself to single, multi- and manyobjectives, and (ii) enabling this algorithm to automatically focus on either convergence,diversity or both, according to the problem being considered. Our approach augmentsthe already existing algorithm with a niching-based selection operator. It also utilizes therecently proposed Karush Kuhn Tucker Proximity Measure to identify ill-converged solutions,and finally, uses several combinations of point-to-point single objective local searchprocedures to remedy these solutions and enhance both convergence and diversity. Ourextensions are shown to produce better results than state-of-the-art algorithms over a setof single, multi- and many-objective problems.
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. We pose this as a gain-aware multicast Delay Tolerant Network (DTN) routing problem in a Social Wireless Network (SWN) setting. Commercial parameters in this framework include the revenue out of selling a product, discount, rebate, content expiry time, and a content-specific...
Show moreThe 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. We pose this as a gain-aware multicast Delay Tolerant Network (DTN) routing problem in a Social Wireless Network (SWN) setting. Commercial parameters in this framework include the revenue out of selling a product, discount, rebate, content expiry time, and a content-specific redemption function. These parameters are inputs provided by a content generator. Network parameters are decided based on a Social Wireless Network’s characteristics such as consumers’ interest profiles and their social bindings summarized in their mobility profiles. We explore two solution approaches. First, we investigate stochastic design methods for gain-aware DTN protocol design including prediction-based dissemination mechanisms. We develop a predictive gain utility which is used for deciding relative importance of an immediate peer in comparison with potential future peers. We propose two versions of the utility; the first one, Predictive Gain Utility Routing-Individual (PGUR-I) uses node-specific information, and the second one, Predictive Gain Utility Routing-Aggregated (PGUR-A) implements a more scalable version by probabilistically aggregating node interaction information across consumers with similar consumption interests. In the second approach, we explore learning mechanisms including evolutionary learning and reinforcement learning for synthetizing communication protocols. We explore evolutionary learning, specifically, evolving state machines for protocol synthesis. A specific network protocol is coded as a genotype and its resulting state machine behavior manifests in the form of the corresponding phenotype, leading to specific performance. Using the developed framework, we explore the evolutionary design of Medium Access Control (MAC) protocols including ALOHA, S-ALOHA and Carrier Sensing Multiple Access (CSMA). Finally, we leverage Reinforcement Learning (RL), which enables nodes to gather local information and make efficient routing decisions in runtime.
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: 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: 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 moreSustaining 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.
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: 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

MSU Libraries

Digital Repository

You are here