51
|
Devert A, Weise T, Tang K. A study on scalable representations for evolutionary optimization of ground structures. EVOLUTIONARY COMPUTATION 2012; 20:453-479. [PMID: 22004002 DOI: 10.1162/evco_a_00054] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/31/2023]
Abstract
This paper presents a comparative study of two indirect solution representations, a generative and an ontogenic one, on a set of well-known 2D truss design problems. The generative representation encodes the parameters of a trusses design as a mapping from a 2D space. The ontogenic representation encodes truss design parameters as a local truss transformation iterated several times, starting from a trivial initial truss. Both representations are tested with a naive evolution strategy based optimization scheme, as well as the state of the art HyperNEAT approach. We focus both on the best objective value obtained and the computational cost to reach a given level of optimality. The study shows that the two solution representations behave very differently. For experimental settings with equal complexity, with the same optimization scheme and settings, the generative representation provides results which are far from optimal, whereas the ontogenic representation delivers near-optimal solutions. The ontogenic representation is also much less computationally expensive than a direct representation until very close to the global optimum. The study questions the scalability of the generative representations, while the results for the ontogenic representation display much better scalability.
Collapse
Affiliation(s)
- Alexandre Devert
- Nature Inspired Computation and Applications Laboratory (NICAL), School of Computer Science and Technology, University of Science and Technology of China, Hefei, China.
| | | | | |
Collapse
|
52
|
Doursat R, Sayama H, Michel O. Morphogenetic Engineering: Reconciling Self-Organization and Architecture. MORPHOGENETIC ENGINEERING 2012. [DOI: 10.1007/978-3-642-33902-8_1] [Citation(s) in RCA: 15] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 01/20/2023]
|
53
|
Doursat R, Sánchez C, Dordea R, Fourquet D, Kowaliw T. Embryomorphic Engineering: Emergent Innovation Through Evolutionary Development. MORPHOGENETIC ENGINEERING 2012. [DOI: 10.1007/978-3-642-33902-8_11] [Citation(s) in RCA: 13] [Impact Index Per Article: 1.1] [Reference Citation Analysis] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 01/09/2023]
|
54
|
D’Ambrosio DB, Goodell S, Lehman J, Risi S, Stanley KO. Multirobot Behavior Synchronization through Direct Neural Network Communication. INTELLIGENT ROBOTICS AND APPLICATIONS 2012. [DOI: 10.1007/978-3-642-33515-0_59] [Citation(s) in RCA: 8] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 12/29/2022]
|
55
|
|
56
|
Clune J, Lipson H. Evolving 3D objects with a generative encoding inspired by developmental biology. ACTA ACUST UNITED AC 2011. [DOI: 10.1145/2078245.2078246] [Citation(s) in RCA: 16] [Impact Index Per Article: 1.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 10/14/2022]
Abstract
This paper introduces an algorithm for evolving 3D objects with a generative encoding that abstracts how biological morphologies are produced. Evolving interesting 3D objects is useful in many disciplines, including artistic design (e.g. sculpture), engineering (e.g. robotics, architecture, or product design), and biology (e.g. for investigating morphological evolution). A critical element in evolving 3D objects is the representation, which strongly influences the types of objects produced. In 2007 a representation was introduced called Compositional Pattern Producing Networks (CPPN), which abstracts how natural phenotypes are generated. To date, however, the ability of CPPNs to create 3D objects has barely been explored. Here we present a new way to create 3D objects with CPPNs. Experiments with both interactive and target-based evolution demonstrate that CPPNs show potential in generating interesting, complex, 3D objects. We further show that changing the information provided to CPPNs and the functions allowed in their genomes biases the types of objects produced. Finally, we validate that the objects transfer well from simulation to the real-world by printing them with a 3D printer. Overall, this paper shows that evolving objects with encodings based on concepts from biological development can be a powerful way to evolve complex, interesting objects, which should be of use in fields as diverse as art, engineering, and biology.
Collapse
|
57
|
Togelius J, Yannakakis GN, Stanley KO, Browne C. Search-Based Procedural Content Generation: A Taxonomy and Survey. IEEE TRANSACTIONS ON COMPUTATIONAL INTELLIGENCE AND AI IN GAMES 2011. [DOI: 10.1109/tciaig.2011.2148116] [Citation(s) in RCA: 318] [Impact Index Per Article: 24.5] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/07/2022]
|
58
|
Secretan J, Beato N, D'Ambrosio DB, Rodriguez A, Campbell A, Folsom-Kovarik JT, Stanley KO. Picbreeder: a case study in collaborative evolutionary exploration of design space. EVOLUTIONARY COMPUTATION 2011; 19:373-403. [PMID: 20964537 DOI: 10.1162/evco_a_00030] [Citation(s) in RCA: 31] [Impact Index Per Article: 2.4] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/30/2023]
Abstract
For domains in which fitness is subjective or difficult to express formally, interactive evolutionary computation (IEC) is a natural choice. It is possible that a collaborative process combining feedback from multiple users can improve the quality and quantity of generated artifacts. Picbreeder, a large-scale online experiment in collaborative interactive evolution (CIE), explores this potential. Picbreeder is an online community in which users can evolve and share images, and most importantly, continue evolving others' images. Through this process of branching from other images, and through continually increasing image complexity made possible by the underlying neuroevolution of augmenting topologies (NEAT) algorithm, evolved images proliferate unlike in any other current IEC system. This paper discusses not only the strengths of the Picbreeder approach, but its challenges and shortcomings as well, in the hope that lessons learned will inform the design of future CIE systems.
Collapse
Affiliation(s)
- Jimmy Secretan
- Department of Electrical Engineering and Computer Science, University of Central Florida, USA.
| | | | | | | | | | | | | |
Collapse
|
59
|
Suchorzewski M. Evolving scalable and modular adaptive networks with Developmental Symbolic Encoding. EVOLUTIONARY INTELLIGENCE 2011; 4:145-163. [PMID: 21957432 PMCID: PMC3161195 DOI: 10.1007/s12065-011-0057-0] [Citation(s) in RCA: 8] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/01/2010] [Revised: 03/17/2011] [Accepted: 04/08/2011] [Indexed: 11/25/2022]
Abstract
Evolutionary neural networks, or neuroevolution, appear to be a promising way to build versatile adaptive systems, combining evolution and learning. One of the most challenging problems of neuroevolution is finding a scalable and robust genetic representation, which would allow to effectively grow increasingly complex networks for increasingly complex tasks. In this paper we propose a novel developmental encoding for networks, featuring scalability, modularity, regularity and hierarchy. The encoding allows to represent structural regularities of networks and build them from encapsulated and possibly reused subnetworks. These capabilities are demonstrated on several test problems. In particular for parity and symmetry problems we evolve solutions, which are fully general with respect to the number of inputs. We also evolve scalable and modular weightless recurrent networks capable of autonomous learning in a simple generic classification task. The encoding is very flexible and we demonstrate this by evolving networks capable of learning via neuromodulation. Finally, we evolve modular solutions to the retina problem, for which another well known neuroevolution method—HyperNEAT—was previously shown to fail. The proposed encoding outperformed HyperNEAT and Cellular Encoding also in another experiment, in which certain connectivity patterns must be discovered between layers. Therefore we conclude the proposed encoding is an interesting and competitive approach to evolve networks.
Collapse
Affiliation(s)
- Marcin Suchorzewski
- Artificial Intelligence Laboratory, West Pomeranian University of Technology, ul. Żołnierska 49, 71-210 Szczecin, Poland
| |
Collapse
|
60
|
Evolving homeostatic tissue using genetic algorithms. PROGRESS IN BIOPHYSICS AND MOLECULAR BIOLOGY 2011; 106:414-25. [PMID: 21419156 DOI: 10.1016/j.pbiomolbio.2011.03.004] [Citation(s) in RCA: 13] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 11/21/2022]
Abstract
Multicellular organisms maintain form and function through a multitude of homeostatic mechanisms. The details of these mechanisms are in many cases unknown, and so are their evolutionary origin and their link to development. In order to illuminate these issues we have investigated the evolution of structural homeostasis in the simplest of cases, a tissue formed by a mono-layer of cells. To this end, we made use of a 3-dimensional hybrid cellular automaton, an individual-based model in which the behaviour of each cell depends on its local environment. Using an evolutionary algorithm (EA) we evolved cell signalling networks, both with a fixed and an incremental fitness evaluation, which give rise to and maintain a mono-layer tissue structure. Analysis of the solutions provided by the EA shows that the two evaluation methods gives rise to different types of solutions to the problem of homeostasis. The fixed method leads to almost optimal solutions, where the tissue relies on a high rate of cell turnover, while the solutions from the incremental scheme behave in a more conservative manner, only dividing when necessary. In order to test the robustness of the solutions we subjected them to environmental stress, by wounding the tissue, and to genetic stress, by introducing mutations. The results show that the robustness very much depends on the mechanism responsible for maintaining homeostasis. The two evolved cell types analysed present contrasting mechanisms by which tissue homeostasis can be maintained. This compares well to different tissue types found in multicellular organisms. For example the epithelial cells lining the colon in humans are shed at a considerable rate, while in other tissue types, which are not as exposed, the conservative type of homeostatic mechanism is normally found. These results will hopefully shed light on how multicellular organisms have evolved homeostatic mechanisms and what might occur when these mechanisms fail, as in the case of cancer.
Collapse
|
61
|
Jin Y, Meng Y. Morphogenetic Robotics: An Emerging New Field in Developmental Robotics. ACTA ACUST UNITED AC 2011. [DOI: 10.1109/tsmcc.2010.2057424] [Citation(s) in RCA: 49] [Impact Index Per Article: 3.8] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/10/2022]
|
62
|
Lehman J, Stanley KO. Abandoning objectives: evolution through the search for novelty alone. EVOLUTIONARY COMPUTATION 2011; 19:189-223. [PMID: 20868264 DOI: 10.1162/evco_a_00025] [Citation(s) in RCA: 136] [Impact Index Per Article: 10.5] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/29/2023]
Abstract
In evolutionary computation, the fitness function normally measures progress toward an objective in the search space, effectively acting as an objective function. Through deception, such objective functions may actually prevent the objective from being reached. While methods exist to mitigate deception, they leave the underlying pathology untreated: Objective functions themselves may actively misdirect search toward dead ends. This paper proposes an approach to circumventing deception that also yields a new perspective on open-ended evolution. Instead of either explicitly seeking an objective or modeling natural evolution to capture open-endedness, the idea is to simply search for behavioral novelty. Even in an objective-based problem, such novelty search ignores the objective. Because many points in the search space collapse to a single behavior, the search for novelty is often feasible. Furthermore, because there are only so many simple behaviors, the search for novelty leads to increasing complexity. By decoupling open-ended search from artificial life worlds, the search for novelty is applicable to real world problems. Counterintuitively, in the maze navigation and biped walking tasks in this paper, novelty search significantly outperforms objective-based search, suggesting the strange conclusion that some problems are best solved by methods that ignore the objective. The main lesson is the inherent limitation of the objective-based paradigm and the unexploited opportunity to guide search through other means.
Collapse
Affiliation(s)
- Joel Lehman
- School of Electrical Engineering and Computer Science, University of Central Florida, Orlando, Florida 32816, USA.
| | | |
Collapse
|
63
|
The evolution of CSR life-history strategies in a plant model with explicit physiology and architecture. Ecol Modell 2011. [DOI: 10.1016/j.ecolmodel.2010.09.014] [Citation(s) in RCA: 16] [Impact Index Per Article: 1.2] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/19/2022]
|
64
|
|
65
|
Lobo D, Vico FJ. Evolution of form and function in a model of differentiated multicellular organisms with gene regulatory networks. Biosystems 2010; 102:112-23. [PMID: 20837096 DOI: 10.1016/j.biosystems.2010.08.003] [Citation(s) in RCA: 10] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/19/2010] [Revised: 07/10/2010] [Accepted: 08/27/2010] [Indexed: 10/19/2022]
Abstract
The emergence of novelties, as a generator of diversity, in the form and function of the organisms have long puzzled biologists. The study of the developmental process and the anatomical properties of an organism provides scarce information into the means by which its morphology evolved. Some have argued that the very nature of novelty is believed to be linked to the evolution of gene regulation, rather than to the emergence of new structural genes. In order to gain further insight into the evolution of novelty and diversity, we describe a simple computational model of gene regulation that controls the development of locomotive multicellular organisms through a fixed set of simple structural genes. Organisms, modeled as two-dimensional spring networks, are simulated in a virtual environment to evaluate their steering skills for path-following. Proposed as a behavior-finding problem, this fitness function guides an evolutionary algorithm that produces structures whose function is well-adapted to the environment (i.e., good path-followers). We show that, despite the fixed simple set of structural genes, the evolution of gene regulation yields a rich variety of body plans, including symmetries, body segments, and modularity, resulting in a diversity of original behaviors to follow a simple path. These results suggest that the sole variation in the regulation of gene expression is a sufficient condition for the emergence of novelty and diversity.
Collapse
Affiliation(s)
- Daniel Lobo
- Departamento de Lenguajes y Ciencias de la Computación, Universidad de Málaga, Severo Ochoa 4, 29590 Málaga, Spain.
| | | |
Collapse
|
66
|
Fontana A. A hypothesis on the role of transposons. Biosystems 2010; 101:187-93. [PMID: 20655980 DOI: 10.1016/j.biosystems.2010.07.002] [Citation(s) in RCA: 8] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/31/2010] [Revised: 07/06/2010] [Accepted: 07/08/2010] [Indexed: 11/26/2022]
Abstract
Genomic transposable elements, or transposons, are sequences of DNA that can move to different positions in the genome; in the process, they can cause chromosomal rearrengements and changes in gene expression. Despite their prevalence in the genomes of many species, their function is largely unknown: for this reason, they have been labelled "junk" DNA. "Epigenetic Tracking" is a model of development that, combined with a standard evolutionary algorithm, become an evo-devo method able to generate arbitrary shapes of any kind and complexity (in terms of number of cells, number of colours, etc.). The model of development has been also shown to be able to produce the artificial version of key biological phenomena such as the phenomenon of ageing, and the process of carcinogenesis. In this paper the evo-devo core of the method is explored and the result is a novel hypothesis on the biological role of transposons, according to which transposition in somatic cells during development drives cellular differentiation and transposition in germ cells is an indispensable tool to boost evolution. Thus, transposable elements, far from being "junk", have one of the most important roles in multicellular biology.
Collapse
|
67
|
Evolutionary development of tensegrity structures. Biosystems 2010; 101:167-76. [PMID: 20619314 DOI: 10.1016/j.biosystems.2010.06.005] [Citation(s) in RCA: 16] [Impact Index Per Article: 1.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/19/2010] [Revised: 06/24/2010] [Accepted: 06/28/2010] [Indexed: 11/20/2022]
Abstract
Contributions from the emerging fields of molecular genetics and evo-devo (evolutionary developmental biology) are greatly benefiting the field of evolutionary computation, initiating a promise of renewal in the traditional methodology. While direct encoding has constituted a dominant paradigm, indirect ways to encode the solutions have been reported, yet little attention has been paid to the benefits of the proposed methods to real problems. In this work, we study the biological properties that emerge by means of using indirect encodings in the context of form-finding problems. A novel indirect encoding model for artificial development has been defined and applied to an engineering structural-design problem, specifically to the discovery of tensegrity structures. This model has been compared with a direct encoding scheme. While the direct encoding performs similarly well to the proposed method, indirect-based results typically outperform the direct-based results in aspects not directly linked to the nature of the problem itself, but to the emergence of properties found in biological organisms, like organicity, generalization capacity, or modularity aspects which are highly valuable in engineering.
Collapse
|
68
|
Gauci J, Stanley KO. Autonomous Evolution of Topographic Regularities in Artificial Neural Networks. Neural Comput 2010; 22:1860-98. [PMID: 20235822 DOI: 10.1162/neco.2010.06-09-1042] [Citation(s) in RCA: 86] [Impact Index Per Article: 6.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/04/2022]
Abstract
Looking to nature as inspiration, for at least the past 25 years, researchers in the field of neuroevolution (NE) have developed evolutionary algorithms designed specifically to evolve artificial neural networks (ANNs). Yet the ANNs evolved through NE algorithms lack the distinctive characteristics of biological brains, perhaps explaining why NE is not yet a mainstream subject of neural computation. Motivated by this gap, this letter shows that when geometry is introduced to evolved ANNs through the hypercube-based neuroevolution of augmenting topologies algorithm, they begin to acquire characteristics that indeed are reminiscent of biological brains. That is, if the neurons in evolved ANNs are situated at locations in space (i.e., if they are given coordinates), then, as experiments in evolving checkers-playing ANNs in this letter show, topographic maps with symmetries and regularities can evolve spontaneously. The ability to evolve such maps is shown in this letter to provide an important advantage in generalization. In fact, the evolved maps are sufficiently informative that their analysis yields the novel insight that the geometry of the connectivity patterns of more general players is significantly smoother and more contiguous than less general ones. Thus, the results reveal a correlation between generality and smoothness in connectivity patterns. They also hint at the intriguing possibility that as NE matures as a field, its algorithms can evolve ANNs of increasing relevance to those who study neural computation in general.
Collapse
Affiliation(s)
- Jason Gauci
- Evolutionary Complexity Research Group, School of Electrical Engineering and Computer Science, University of Central Florida, Orlando, FL 32816, U.S.A
| | - Kenneth O. Stanley
- Evolutionary Complexity Research Group, School of Electrical Engineering and Computer Science, University of Central Florida, Orlando, FL 32816, U.S.A
| |
Collapse
|
69
|
|
70
|
Indirectly Encoding Neural Plasticity as a Pattern of Local Rules. FROM ANIMALS TO ANIMATS 11 2010. [DOI: 10.1007/978-3-642-15193-4_50] [Citation(s) in RCA: 34] [Impact Index Per Article: 2.4] [Reference Citation Analysis] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 12/12/2022]
|
71
|
Haasdijk E, Rusu AA, Eiben AE. HyperNEAT for Locomotion Control in Modular Robots. EVOLVABLE SYSTEMS: FROM BIOLOGY TO HARDWARE 2010. [DOI: 10.1007/978-3-642-15323-5_15] [Citation(s) in RCA: 24] [Impact Index Per Article: 1.7] [Reference Citation Analysis] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 01/11/2023]
|
72
|
Abstract
We present a novel approach toward evolving artificial embryogenies, which omits the graph representation of gene regulatory networks and directly shapes the dynamics of a system, i.e., its phase space. We show the feasibility of the approach by evolving cellular differentiation, a basic feature of both biological and artificial development. We demonstrate how a spatial hierarchy formulation can be integrated into the framework and investigate the evolution of a hierarchical system. Finally, we show how the framework allows the investigation of allometry, a biological phenomenon, and its role for evolution. We find that direct evolution of allometric change, i.e., the evolutionary adaptation of the speed of system states on transient trajectories in phase space, is advantageous for a cellular differentiation task.
Collapse
Affiliation(s)
- Till Steiner
- Honda Research Institute Europe GmbH, Offenbach am Main, Germany.
| | | | | |
Collapse
|
73
|
Jin Y, Sendhoff B. A systems approach to evolutionary multiobjective structural optimization and beyond. IEEE COMPUT INTELL M 2009. [DOI: 10.1109/mci.2009.933094] [Citation(s) in RCA: 108] [Impact Index Per Article: 7.2] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/09/2022]
|
74
|
|
75
|
Abstract
We have constructed a computational platform suitable for examining emergence of shape homeostasis in simple three-dimensional cellular systems. An embryo phenotype results from a developmental process starting with a single cell and its genome. When coupled to an evolutionary search, this platform can evolve embryos with particular stable shapes and high capacity for self-repair, even though repair is not genetically encoded or part of the fitness criteria. With respect to the genome, embryo shape and self-repair are emergent properties that arise from complex interactions among cells and cellular components via signaling and gene regulatory networks, during development or during repair. This report analyzes these networks and the underlying mechanisms that control embryo growth, organization, stability, and robustness to injury.
Collapse
|
76
|
Matos A, Suzuki R, Arita T. Heterochrony and artificial embryogeny: a method for analyzing artificial embryogenies based on developmental dynamics. ARTIFICIAL LIFE 2009; 15:131-160. [PMID: 19199381 DOI: 10.1162/artl.2009.15.2.15200] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.2] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/27/2023]
Abstract
Artificial embryogenies are an extension to evolutionary algorithms, in which genotypes specify a process to grow phenotypes. This approach has become rather popular recently, with new kinds of embryogenies being increasingly reported in the literature. Nevertheless, it is still difficult to analyze and compare the available embryogenies, especially if they are based on very different paradigms. We propose a method to analyze embryogenies based on growth dynamics, and how evolution is able to change them (heterochrony). We define several quantitative measures that allow us to establish the variation in growth dynamics that an embryogeny can create, the degree of change in growth dynamics caused by mutations, and the degree to which an embryogeny allows mutations to change the growth of a genotype, but without changing the final phenotype reached. These measures are based on an heterochrony framework, due to Alberch, Gould, Oster, & Wake (1979 Size and shape in ontogeny and phylogeny, Paleobiology, 5(3), 296-317) that is used in real biological organisms. The measures are general enough to be applied to any embryogeny, and can be easily computed from simple experiments. We further illustrate how to compute these measures by applying them to two simple embryogenies. These embryogenies exhibit rather different growth dynamics, and both allow for mutations that changed growth without affecting the final phenotype.
Collapse
Affiliation(s)
- Artur Matos
- Graduate School of Information Science, Nagoya University, Nagoya, Japan.
| | | | | |
Collapse
|
77
|
Stanley KO, D'Ambrosio DB, Gauci J. A hypercube-based encoding for evolving large-scale neural networks. ARTIFICIAL LIFE 2009; 15:185-212. [PMID: 19199382 DOI: 10.1162/artl.2009.15.2.15202] [Citation(s) in RCA: 133] [Impact Index Per Article: 8.9] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/27/2023]
Abstract
Research in neuroevolution-that is, evolving artificial neural networks (ANNs) through evolutionary algorithms-is inspired by the evolution of biological brains, which can contain trillions of connections. Yet while neuroevolution has produced successful results, the scale of natural brains remains far beyond reach. This article presents a method called hypercube-based NeuroEvolution of Augmenting Topologies (HyperNEAT) that aims to narrow this gap. HyperNEAT employs an indirect encoding called connective compositional pattern-producing networks (CPPNs) that can produce connectivity patterns with symmetries and repeating motifs by interpreting spatial patterns generated within a hypercube as connectivity patterns in a lower-dimensional space. This approach can exploit the geometry of the task by mapping its regularities onto the topology of the network, thereby shifting problem difficulty away from dimensionality to the underlying problem structure. Furthermore, connective CPPNs can represent the same connectivity pattern at any resolution, allowing ANNs to scale to new numbers of inputs and outputs without further evolution. HyperNEAT is demonstrated through visual discrimination and food-gathering tasks, including successful visual discrimination networks containing over eight million connections. The main conclusion is that the ability to explore the space of regular connectivity patterns opens up a new class of complex high-dimensional tasks to neuroevolution.
Collapse
Affiliation(s)
- Kenneth O Stanley
- School of Electrical Engineering and Computer Science, University of Central Florida, Orlando, FL 32816-2362, USA.
| | | | | |
Collapse
|
78
|
Yerushalmi U, Teicher M. Evolving synaptic plasticity with an evolutionary cellular development model. PLoS One 2008; 3:e3697. [PMID: 19002249 PMCID: PMC2577323 DOI: 10.1371/journal.pone.0003697] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/26/2008] [Accepted: 10/17/2008] [Indexed: 11/18/2022] Open
Abstract
Since synaptic plasticity is regarded as a potential mechanism for memory formation and learning, there is growing interest in the study of its underlying mechanisms. Recently several evolutionary models of cellular development have been presented, but none have been shown to be able to evolve a range of biological synaptic plasticity regimes. In this paper we present a biologically plausible evolutionary cellular development model and test its ability to evolve different biological synaptic plasticity regimes. The core of the model is a genomic and proteomic regulation network which controls cells and their neurites in a 2D environment. The model has previously been shown to successfully evolve behaving organisms, enable gene related phenomena, and produce biological neural mechanisms such as temporal representations. Several experiments are described in which the model evolves different synaptic plasticity regimes using a direct fitness function. Other experiments examine the ability of the model to evolve simple plasticity regimes in a task -based fitness function environment. These results suggest that such evolutionary cellular development models have the potential to be used as a research tool for investigating the evolutionary aspects of synaptic plasticity and at the same time can serve as the basis for novel artificial computational systems.
Collapse
Affiliation(s)
- Uri Yerushalmi
- The Leslie and Susan Gonda Interdisciplinary Brain Research Center, Bar-Ilan University, Ramat-Gan, Israel.
| | | |
Collapse
|
79
|
Neuroevolution and complexifying genetic architectures for memory and control tasks. Theory Biosci 2008; 127:187-94. [PMID: 18415134 PMCID: PMC2758373 DOI: 10.1007/s12064-008-0029-9] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/31/2007] [Accepted: 11/18/2007] [Indexed: 10/30/2022]
Abstract
The way genes are interpreted biases an artificial evolutionary system towards some phenotypes. When evolving artificial neural networks, methods using direct encoding have genes representing neurons and synapses, while methods employing artificial ontogeny interpret genomes as recipes for the construction of phenotypes. Here, a neuroevolution system (neuroevolution with ontogeny or NEON) is presented that can emulate a well-known neuroevolution method using direct encoding (neuroevolution of augmenting topologies or NEAT), and therefore, can solve the same kinds of tasks. Performance on challenging control and memory benchmark tasks is reported. However, the encoding used by NEON is indirect, and it is shown how characteristics of artificial ontogeny can be introduced incrementally in different phases of evolutionary search.
Collapse
|
80
|
Geard N, Wiles J. LinMap: visualizing complexity gradients in evolutionary landscapes. ARTIFICIAL LIFE 2008; 14:277-297. [PMID: 18489254 DOI: 10.1162/artl.2008.14.3.14304] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/26/2023]
Abstract
This article describes an interactive visualization tool, LinMap, for exploring the structure of complexity gradients in evolutionary landscapes. LinMap is a computationally efficient and intuitive tool for visualizing and exploring multidimensional parameter spaces. An artificial cell lineage model is presented that allows complexity to be quantified according to several different developmental and phenotypic metrics. LinMap is applied to the evolutionary landscapes generated by this model to demonstrate that different definitions of complexity produce different gradients across the same landscape; that landscapes are characterized by a phase transition between proliferating and quiescent cell lineages where both complexity and diversity are maximized; and that landscapes defined by adaptive fitness and complexity can display different topographical features.
Collapse
Affiliation(s)
- Nicholas Geard
- ARC Centre for Complex Systems, School of Information Technology and Electrical Engineering, The University of Queensland, Brisbane, Australia.
| | | |
Collapse
|
81
|
How a Generative Encoding Fares as Problem-Regularity Decreases. PARALLEL PROBLEM SOLVING FROM NATURE – PPSN X 2008. [DOI: 10.1007/978-3-540-87700-4_36] [Citation(s) in RCA: 12] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 01/11/2023]
|
82
|
Flamm C, Endler L, Müller S, Widder S, Schuster P. A minimal and self-consistent in silico cell model based on macromolecular interactions. Philos Trans R Soc Lond B Biol Sci 2007; 362:1831-9. [PMID: 17510017 PMCID: PMC2442397 DOI: 10.1098/rstb.2007.2075] [Citation(s) in RCA: 7] [Impact Index Per Article: 0.4] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 01/07/2023] Open
Abstract
A self-consistent minimal cell model with a physically motivated schema for molecular interaction is introduced and described. The genetic and metabolic reaction network of the cell is modelled by multidimensional nonlinear ordinary differential equations, which are derived from biochemical kinetics. The strategy behind this modelling approach is to keep the model sufficiently simple in order to be able to perform studies on evolutionary optimization in populations of cells. At the same time, the model should be complex enough to handle the basic features of genetic control of metabolism and coupling to environmental factors. Thereby, the model system will provide insight into the mechanisms leading to important biological phenomena, such as homeostasis, (circadian) rhythms, robustness and adaptation to a changing environment. One example of modelling a molecular regulatory mechanism, cooperative binding of transcription factors, is discussed in detail.
Collapse
Affiliation(s)
- Christoph Flamm
- Theoretical Biochemistry Group, Institut für Theoretische Chemie, Universität Wien, Währingerstrasse 17, 1090 Wien, Austria.
| | | | | | | | | |
Collapse
|
83
|
de Matos AMRDSC, Suzuki R, Arita T. Heterochrony and evolvability in neural network development. ARTIFICIAL LIFE AND ROBOTICS 2007. [DOI: 10.1007/s10015-007-0425-0] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 10/23/2022]
|
84
|
Roth F, Siegelmann H, Douglas RJ. The self-construction and -repair of a foraging organism by explicitly specified development from a single cell. ARTIFICIAL LIFE 2007; 13:347-68. [PMID: 17716016 DOI: 10.1162/artl.2007.13.4.347] [Citation(s) in RCA: 5] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/16/2023]
Abstract
As man-made systems become more complex and autonomous, there is a growing need for novel engineering methods that offer self-construction, adaptation to the environment, and self-repair. In a step towards developing such methods, we demonstrate how a simple model multicellular organism can assemble itself by replication from a single cell and finally express a fundamental behavior: foraging. Previous studies have employed evolutionary approaches to this problem. Instead, we aim at explicit design of self-constructing and -repairing systems by hierarchical specification of elementary intracellular mechanisms via a kind of genetic code. The interplay between individual cells and the gradually increasing self-created complexity of the local structure that surrounds them causes the serial unfolding of the final functional organism. The developed structure continuously feeds back to the development process, and so the system is also capable of self-repair.
Collapse
Affiliation(s)
- Fabian Roth
- Institute of Neuroinformatics, University/ETH Zürich, Winterthurerstrasse 190, 8057 Zürich, Switzerland.
| | | | | |
Collapse
|
85
|
Hartmann M, Haddow PC, Lehre PK. The genotypic complexity of evolved fault-tolerant and noise-robust circuits. Biosystems 2006; 87:224-32. [PMID: 17194524 DOI: 10.1016/j.biosystems.2006.09.017] [Citation(s) in RCA: 6] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/28/2005] [Revised: 07/08/2006] [Accepted: 07/15/2006] [Indexed: 11/26/2022]
Abstract
Noise and component failure is an increasingly difficult problem in modern electronic design. Bio-inspired techniques is one approach that is applied in an effort to solve such issues, motivated by the strong robustness and adaptivity often observed in nature. Circuits investigated herein are designed to be tolerant to faults or robust to noise, using an evolutionary algorithm. A major challenge is to improve the scalability of the approach. Earlier results have indicated that the evolved circuits may be suited for the application of artificial development, an approach to indirect mapping from genotype to phenotype that may improve scalability. Those observations were based on the genotypic complexity of evolved circuits. Herein, we measure the genotypic complexity of circuits evolved for tolerance to faults or noise, in order to uncover how that tolerance affects the complexity of the circuits. The complexity is analysed and discussed with regards to how it relates to the potential benefits to the evolutionary process of introducing an indirect genotype-phenotype mapping such as artificial development.
Collapse
Affiliation(s)
- Morten Hartmann
- Complex Adaptive Organically-Inspired Systems Group (CAOS), Department of Computer Science, The Norwegian University of Science and Technology (NTNU), Norway.
| | | | | |
Collapse
|
86
|
Federici D, Downing K. Evolution and development of a multicellular organism: scalability, resilience, and neutral complexification. ARTIFICIAL LIFE 2006; 12:381-409. [PMID: 16859446 DOI: 10.1162/artl.2006.12.3.381] [Citation(s) in RCA: 8] [Impact Index Per Article: 0.4] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/11/2023]
Abstract
To increase the evolvability of larger search spaces, several indirect encoding strategies have been proposed. Among these, multicellular developmental systems are believed to offer great potential for the evolution of general, scalable, and self-repairing organisms. We reinforce this view, presenting the results achieved by such a model and comparing it against direct encoding. Extra effort has been made to make this comparison both general and meaningful. Embryonal stages, a generic method showing increased evolvability and applicable to any developmental model, are introduced. Development with embryonal stages implements what we refer to as direct neutral complexification: direct genotype complexification by neutral duplication of expressed genes. The results show that, even for high-complexity evolutionary targets, the developmental model proves more scalable. The model also shows emergent self-repair, which is used to produce highly resilient organisms.
Collapse
Affiliation(s)
- Diego Federici
- Department of Computer and Information Science, Norwegian University of Science and Technology, N-7491 Trondheim, Norway.
| | | |
Collapse
|
87
|
Abstract
Due to their distributed architecture, artificial neural networks often show a graceful performance degradation to the loss of few units or connections. Living systems also display an additional source of fault-tolerance obtained through distributed processes of self-healing: defective components are actively regenerated. In this paper, we present results obtained with a model of development for spiking neural networks undergoing sustained levels of cell loss. To test their resistance to faults, networks are subjected to random faults during development and mutilated several times during operation. Results show that, evolved to control simulated Khepera robots in a simple navigation task, plastic and non-plastic networks develop fault-tolerant structures which can recover normal operation to various degrees.
Collapse
Affiliation(s)
- Diego Federici
- Complex Adaptive Organically-Inspired Systems Group (CAOS), Department of Computer and Information Science, Norwegian University of Science and Technology, N-7491 Trondheim, Norway.
| |
Collapse
|
88
|
Abstract
Biological development is a remarkably complex process. A single cell, in an appropriate environment, contains sufficient information to generate a variety of differentiated cell types, whose spatial and temporal dynamics interact to form detailed morphological patterns. While several different physical and chemical processes play an important role in the development of an organism, the locus of control is the cell's gene regulatory network. We designed a dynamic recurrent gene network (DRGN) model and evaluated its ability to control the developmental trajectories of cells during embryogenesis. Three tasks were developed to evaluate the model, inspired by cell lineage specification in C. elegans, describing the variation in gene activity required for early cell diversification, combinatorial control of cell lineages, and cell lineage termination. Three corresponding sets of simulations compared performance on the tasks for different gene network sizes, demonstrating the ability of DRGNs to perform the tasks with minimal external input. The model and task definition represent a new means of linking the fundamental properties of genetic networks with the topology of the cell lineages whose development they control.
Collapse
Affiliation(s)
- Nicholas Geard
- School of Information Technology and Electrical Engineering, The University of Queensland, St Lucia, Queensland 4072, Australia.
| | | |
Collapse
|
89
|
Biological Development of Cell Patterns: Characterizing the Space of Cell Chemistry Genetic Regulatory Networks. ADVANCES IN ARTIFICIAL LIFE 2005. [DOI: 10.1007/11553090_7] [Citation(s) in RCA: 12] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 01/11/2023]
|
90
|
Komosinski M, Ulatowski S. Genetic mappings in artificial genomes. Theory Biosci 2004; 123:125-37. [PMID: 18236096 DOI: 10.1016/j.thbio.2004.04.002] [Citation(s) in RCA: 8] [Impact Index Per Article: 0.4] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/17/2003] [Accepted: 04/01/2004] [Indexed: 11/27/2022]
Abstract
This paper concerns processing of genomes of artificial (computer-simulated) organisms. Of special interest is the process of translation of genotypes into phenotypes, and utilizing the mapping information obtained during such translation. If there exists more than one genetic encoding in a single artificial life model, then the translation may also occur between different encodings. The obtained mapping information allows to present genes-phenes relationships visually and interactively to a person, in order to increase understanding of the genotype-tophenotype translation process and genetic encoding properties. As the mapping associates parts of the source sequence with the translated destination, it may be also used to trace genes, phenes, and their relationships during simulated evolution.A mappings composition procedure is formally described, and a simple method of visual mapping presentation is established. Finally, advanced visualizations of gene-phene relationships are demonstrated as practical examples of introduced techniques. These visualizations concern genotypes expressed in various encodings, including an encoding which exhibits polygenic and pleiotropic properties.
Collapse
Affiliation(s)
- Maciej Komosinski
- Institute of Computing Science, Poznan University of Technology, Piotrowo 3A, 60-965, Poznan, Poland,
| | | |
Collapse
|
91
|
Abstract
Baldwin's classic hypothesis states that behavioral plasticity can speed evolution by (a) smoothing the fitness landscape and (b) indirect genetic assimilation of acquired characteristics. This latter phase demands a strong correlation between genotype and phenotype space. But the natural world shows signs of this correlation at only a very coarse level, since the intervening developmental process greatly complicates the mapping from genetics to physiology and ethology. Hence, development appears to preclude a strong Baldwin effect. However, by adding a simple developmental mechanism to Hinton and Nowlan's classic model of the Baldwin effect, and by allowing evolution to determine the proper balance between direct and indirect mapping of genome to phenotype, this research reveals several different effects of development on the Baldwin effect, some promoting and others inhibiting. Perhaps the most interesting result is an evolved cooperation between direct blueprints and indirect developmental recipes in searching for unstructured and partially structured target patterns in large, needle-in-the-haystack fitness landscapes.
Collapse
Affiliation(s)
- Keith L Downing
- Department of Computer Science, The Norwegian University of Science and Technology, Sem Selandsvei 7-9, 7491 Trondheim, Norway.
| |
Collapse
|
92
|
|
93
|
Multi-cellular Development: Is There Scalability and Robustness to Gain? LECTURE NOTES IN COMPUTER SCIENCE 2004. [DOI: 10.1007/978-3-540-30217-9_40] [Citation(s) in RCA: 27] [Impact Index Per Article: 1.4] [Reference Citation Analysis] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 01/07/2023]
|
94
|
The Emergence of Ontogenic Scaffolding in a Stochastic Development Environment. GENETIC AND EVOLUTIONARY COMPUTATION – GECCO 2004 2004. [DOI: 10.1007/978-3-540-24854-5_83] [Citation(s) in RCA: 9] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 01/07/2023]
|
95
|
Bluenome: A Novel Developmental Model of Artificial Morphogenesis. GENETIC AND EVOLUTIONARY COMPUTATION – GECCO 2004 2004. [DOI: 10.1007/978-3-540-24854-5_9] [Citation(s) in RCA: 12] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 01/20/2023]
|