Charles Ofria, Ph.D. - US grants

EIA-0219229
Torng, Eric K
Michigan State University

ITR: Evaluating Phylogeny Reconstruction Algorithms with Digital Organisms

The investigators study methods of determining the historic relationship
between species using only knowledge of currently existing organisms, a technique called "phylogenetic tree reconstruction". Many tree reconstruction algorithms are known, but it is difficult to properly test them for the very
reason that the algorithms are useful -- the original trees are lost to
history.

The studies proposed make use of a new evaluation methodology based on an
artificial evolving system called Avida. In Avida, populations of digital
organisms (self-replicating computer programs) experience natural selection
as they compete for limited resources, and will evolve into new species
often with entirely new genes. The history of such a system can be
monitored, and hence a reconstruction from the final state can have its
accuracy measured.

The proposed activity has several broader impacts on society. It is a core
activity in the Center for Biological Modeling, a new interdisciplinary
research and education center at Michigan State University. Undergraduate
students including underrepresented minorities will be involved by studying
small, self-contained questions. Finally, enhanced understanding of
phylogeny reconstruction algorithms will improve our ability to interpret
the
sequences of genes, aiding in drug design and helping efforts to reconstruct
an evolutionary "tree of life".

Interdisciplinary (99) This project is developing Avida-ED, an educational simulation based on a proven artificial life research platform. In the digital environment of Avida-ED, one can observe the evolution of self-replicating, autonomous digital organisms, and perform experiments to test evolutionary hypotheses in ways that no other tool allows. This unprecedented ability to introduce experimental evolution in biology classrooms lets students learn about basic principles of scientific method and see for themselves how evolutionary theory is confirmed. We are developing and testing the Avida-ED environment, formally accessing its pedagogic efficacy in the classroom for undergraduate science and non-science majors, and distributing the software and associated materials to biology educators. The project is addressing significant science education challenges identified in national standards in a novel, rigorous, and promising manner. Our initial results show that by being able to observe the evolutionary mechanism in action, students come to understand the key biological insight of how evolution produces complex information. The intellectual merit of this project is the novel use of information technology - artificial life - that was inspired by evolutionary principles, and has become a revolutionary research tool for biologists. The broader impacts of this project lie in the application of this simulation and the developed materials in a wide range of undergraduate science curricula.

Evolution has a remarkable ability to design organisms possessing novel features that enable them to survive, and even thrive, in challenging environments. To a human observer, the biochemical and physiological complexity of living organisms is amazing, leading some to disbelieve that such biological designs could have been accomplished by evolution alone. Considering the levels of biocomplexity found throughout nature - the development of an embryo from a single-cell; the delicate balance of an ecosystem in a rainforest; all the way to the reasoning power of the human brain, complex and elegant adaptive designs abound. As we slowly understand more details about how evolution produces such complex traits, it becomes clear that this is a powerful constructive force that we need to fully understand in order to harness its potential in solving difficult computational design problems.
The twin goals of this project are to learn more about the mechanisms by which evolution produces innovative complex features, and then to apply this newfound understanding to develop a new generation of evolution-based algorithms for solving computational problems. In the process, we will use a mathematical framework for the study of complexity in biological systems to better understand the natural design process. We will start this work by answering fundamental questions in evolutionary biology and ecology including: Why do complex designs arise faster in multi-species ecosystems? If organisms have the capacity to modify their environment and communicate with one another, will this spur open-ended complexity growth? and How can we harness these forces to solve design problems?
The evolving system that we use in this study is an artificial one, based on self-replicating computer programs, that nonetheless exhibit the key characteristics of natural evolving systems - most notably the ability to produce novel complex traits and innovative solutions to problems. These "digital organisms" exist in a user-defined computational environment, and their genomes are composed can theoretically perform any computable mathematical function. Indeed, we have witnessed a wide variety of unexpected and innovative adaptations arise through evolution in Avida. This system allows us to explore fundamental questions in evolutionary biology with speed, detail and precision that would not be possible in any natural system. Ideally it is a tool that will allow us to fully understand the origins of biocomplexity, and constructively make use of these same forces that were able to produce human intelligence in the natural world.

Natural evolution has an amazing ability to produce elegant solutions to the challenges faced by living systems. As these challenges become more complex, so too must the organisms that respond to them. Evolution is clearly a powerful force, yet it is difficult to gather sufficient data to understand how complex traits arise and are incorporated into the working whole. The twin goals for this project are to understand how evolution designs complex functions, and to apply this knowledge to solving complicated computational problems. To accomplish this, the investigators will use "digital organisms" as a model system. These are self-replicating computer programs, subject to mutations and selection, that evolve complex features de novo in a natural evolutionary process. The investigators will use this system both for research purposes and as the basis of a teaching platform in biology classrooms and museum kiosks.

Populations of digital organisms are tractable and transparent, allowing researchers to study all aspects of the evolutionary design process. For example, the lineage of an evolved individual can easily be traced and the contributions of each mutation along the way can be quantified. The investigators will use these techniques to study several fundamental questions: How contingent are the outcomes of adaptive evolution on small random events? When populations reach evolutionary dead-ends, is it due to a single, severe 'wrong turn' in multidimensional genotypic space, or is this a more gradual process? How vital are deleterious mutations to promoting adaptive evolution? Are neutral mutations more important? How can these forces be harnessed to solve computational design problems? Finally, can harmful populations ( e.g., pathogens or evolving computer viruses) be forced into evolutionary dead-ends?

This planning grant serves to establish the basis for a new Industry/University Cooperative Research Center for Software-Intensive Ultra-Large-Scale Systems. This proposed center will initially comprise of five research sites, at the University of Virginia, Michigan State University, the University of California San Diego, Vanderbilt University and the University of Washington. The research focus of this proposed center is on software for complex systems. The Center will conduct basic and applied research in traditional and emerging areas of software theory and practice, including research at the intersection of computer science and other disciplines, to include economics, cognition and anthropology. The research will address important problems and opportunities in six key areas: software language, software analysis and synthesis, software design, trustworthy software, software infrastructure and sentient software.

ABSTRACT
0750787
Cheng
Michigan State

The Problem. Computing technology now affects nearly every dimension of modern society: managing
critical infrastructure such as power grids and telecommunication networks; supporting electronic commerce
and medical information systems; and controlling the operation of aircraft and automobiles. This pervasiveness of computing technology, coupled with its rapidly increasing complexity, gives rise to the need for computer systems that are able to adapt to changing conditions. In the last decade, extensive research has been conducted on many aspects of self-adaptive software systems. Examples include adaptive software mechanisms [1 20]; software-architecture-based techniques for supporting dynamic adaptation [21 38]; adaptable and extensible operating systems [39 42]; and requirements-level and formal methods-based techniques [43 52]. This research has greatly improved our understanding of adaptive software and several key supporting concepts, including computational reflection [53 55], separation of concerns [12, 56], component-based design [57, 58], and transparent interception of program flow [59 61].
Despite these advances, designing an adaptive software system remains a very challenging task. We speculate
that much of the difficulty is due to the fact that adaptive software is being designed and implemented using
traditional tools and environments intended for the development of non-adaptive software. We contend that the
full potential of dynamically adaptive software systems cannot be realized without fundamental advances in
the corresponding development environments. Such environments must enable developers to explicitly address
those aspects of the design problem that distinguish adaptive systems from non-adaptive systems. These issues
include anticipating how the software may need to adapt in the future, constructing decision-making software
to govern the adaptation, and ensuring that system integrity is not compromised by adaptation.

The increasing interaction between computing technology and the physical world requires that systems be able to adapt to changing conditions, compensate for hardware and software failures, fend off attacks, and optimize performance, all with minimal human intervention. Robust operation is especially important among collections of small devices, such as micro-robots and sensors that need to perform complex distributed tasks despite adverse operating conditions. Digital evolution offers a means to produce robust computational behaviors and customize them for target hardware and environments. In digital evolution, populations of self-replicating computer programs are subject to random mutations in dynamic environments, leading to evolution by natural selection.

This infrastructure project will construct a testbed to support digital evolution of complex distributed behaviors and their evaluation on heterogeneous computing systems. The testbed will include terrestrial mobile robots, custom-built robotic fish, and stationary sensors, as well as a rack-mounted parallel processor for on-line software evolution. The testbed will support research projects addressing energy-efficient mobility control for swarms of mobile devices; adaptive communication protocols; and self-adaptive and self-healing software. To maximize its impact, the testbed will be integrated with existing facilities, creating a rich computing and communication fabric for experimental research.

Proposal Number 0820220

Title: ORCHID: Harnessing Digital Evolution in Design High-Assurance Adaptive Systems

PIs: Betty Cheng, Philip McKinley, Charles Ofria, and Xiaobo Tan

A robust cyber-infrastructure must be able to monitor the environment and its own behavior, adapt to changing conditions, and protect itself from component failures. The hallmark of the Orchid project is to introduce the fundamental biological principle, evolution, into the development process for adaptive real-world software systems. The project will use and extend the Avida digital evolution software platform to address three primary tasks: (1) exploiting the automatic generation of software models and search capacity of digital evolution to enable the developer to identify viable system configurations; (2) generating novel strategies to adapt from one system behavior to another in response to changing environmental conditions; and (3) providing assurance for adaptive systems by revealing latent properties within a given configuration in order to distinguish generated configurations and remove unwanted behavior. A prototype system will be developed and used to conduct an experimental case study in the design of self-adaptive aquatic mobile sensor networks for homeland security and environmental monitoring. In addition, an instructional system, Avida-EDAS, will be developed to enable students to evolve models of adaptive software, conduct experiments to assess the impact of adverse environmental conditions, and observe the effects of different adaptation strategies on system execution.

The Bio/computational Evolution in Action CONsortium (BEACON) is a Science and Technology Center (STC) that enables research on evolutionary dynamics in natural and artificial systems and training of multi-disciplinary scientists in bio/computation, with a unique focus on the intersection of evolutionary biology, computer science, and engineering. The Center will enhance the development of applications of computational methods in biology, the use of artificial intelligence in computer science, and the enhancement of genetic algorithms in engineering design. Evolution by natural selection defines an algorithmic approach to finding solutions for complex problems; computer scientists and engineers have harnessed similar algorithms to a diversity of challenges that require optimization over multiple competing dimensions. Likewise, biologists have begun to employ digital modeling of the evolutionary process to examine evolution of complex biological structures and patterns in areas such as paleontology and the gene networks, which defy experimental manipulation in vivo. The Center will promote these interdisciplinary efforts by coordinating activities through three thrust groups: (1) Evolution of Genomes, Networks, and Evolvability, (2) Evolution of Behavior and Intelligence, and (3) Evolution of Communities and Collective Dynamics.

This center has the potential to transform both biology and computational sciences by developing digital experiments to test and apply fundamental principles of evolutionary biology. The possible impacts will be far reaching: from cyber-security to everyday computing applications, from the evolution of disease resistance to the self-organization of social behavior. The BEACON center will train the next generation of interdisciplinary scientists and educate the public about evolution and its role in solving real-world problems through significant educational outreach for K12 students and science museums.

Recent science education reform efforts (Vision and Change in Undergraduate Education: A Call to Action, the AP Biology Frameworks and the Next Generation Science Standards [http://www.nextgenscience.org/]) emphasize the importance of evolution as a major unifying theme in the science curriculum and in understanding life processes. They further identify inquiry-based laboratory experiences as key to helping students gain a better understanding of evolution and highlight the need for controlled studies to test such interventions. A major impediment in involving students in the experimental study of evolutionary processes is that the evolutionary process is difficult or impossible to demonstrate in the classroom. Current efforts rely on simulations with limited opportunities to test hypotheses and to learn how science is practiced. This project specifically and directly addresses these challenges through ongoing development and testing of Avida-ED, an educational software tool derived from an experimental digital tool used by scientists to study bio/computational evolution. It was first developed under an NSF CCLI award (031484). Activities planned will provide in-depth faculty development through a national series of workshops, and an expansion of an ongoing national study of the effectiveness of this approach for learning about evolution and the nature of science.

Avida-ED engages students in observation and manipulation of populations of self-replicating, autonomous digital organisms while they are actively evolving. It is built on top of a proven experimental evolution research platform, so students can perform experiments to test evolutionary hypotheses that they generate on their own in the same modeling system used by scientists. Evidence from on-going national classroom studies indicates the unique value of being able to directly observe evolution in action in this digital environment. Pilot studies show that Avida-ED is effective in (i) overcoming common misconceptions about evolutionary mechanisms and (ii) increasing acceptance of evolutionary science. This study examines these issues in more detail, including cognitive and non-cognitive elements of active learning when using digital evolution models. These constitute some of the first quasi-experimental classroom studies in evolution education. Other activities planned include a series of national workshops to provide profession development in the use of Avida-ED to over 150 faculty

This project is funded jointly by the Directorate for Biological Sciences and the Directorate of Education and Human Resources, Division of Undergraduate Education in support of efforts to address the challenges posed in Vision and Change in Undergraduate Education: A Call to Action http://visionandchange.org/finalreport/

This project investigates fundamental questions about how evolution produces shifts in what it means to be an individual organism and how those shifts affect subsequent evolution. What is an individual organism varies greatly. With bacteria, an individual consists of a single cell, while in mammals individuals might have trillions of cells, all coordinating different roles (blood, skin, and so forth) Some species, such as the honey bee, form highly coordinated colonies (with queens, foragers, guards, and so forth) that behave like an individual organism. The evolution of previously distinct entities (cells or insects) into new types of unified individuals (bodies or colonies) are challenging to study because evolution occurs over long time scales. Instead, the researchers will use computer simulations in which they will manipulate environmental conditions to see how they promote or constrain the evolution of complex individuals. The researchers will also develop web-based software to let others easily explore these evolutionary transitions, with a goal of simplifying experimentation by fellow researchers, facilitating student learning, and promoting citizen science.

This project will be divided into three conceptual stages: (1) Formation: Under what selective conditions do formerly solitary organisms unite to form a higher-level individual unit? (2) Differentiation: Once higher-level units have been formed, how do the preexisting traits of the lower-level individuals (such as phenotypic plasticity or environmental interactions) influence the evolution of division-of-labor strategies? (3) Complexification: How do different types of division-of-labor mechanisms facilitate the evolution of new, more complex features (such as developmental patterns or tightly-coordinated task performance)? The researchers will use an experimental-evolution approach with digital study organisms that operate in a 2D virtual world. Digital evolution systems allow the researchers to observe all genomes in a population, track all interactions, and record perfect phylogenies. Each digital cell has a fully-functional genetic program, theoretically capable of performing any algorithmic processes. Evolution in these systems frequently produce unexpected survival strategies with complex environmental and inter-cellular interactions, far beyond a traditional simulation. Probing the conditions that produce major transitions in an open-ended and transparent system will contribute to a deeper understanding of our natural origins, generate numerous hypotheses that can be tested concisely in laboratory experiments, and promote ideas for how computational algorithms can be produced that coordinate at a scale comparable to biological systems.