2009 Amy K. Hoover and Kenneth O. StanleyTo appear in: Connection Science Special Issue on Music, Brain, and Cognition. Abington, UK: Taylor & Francis, 2009 (33 pages)Abstract The ability of gifted composers such as Mozart to create complex multipart musical compositions with relative ease suggests a highly efficient mechanism for generating multiple parts simultaneously. Computational models of human music composition can potentially shed light on how such rapid creativity is possible. This paper proposes such a model based on the idea that the multiple threads of a song are temporal patterns that are functionally related, which means that one instrument's sequence is a function of another's. This idea is implemented in a program called NEAT Drummer that interactively evolves a type of artificial neural network (ANN) called a Compositional Pattern Producing Network (CPPN), which represents the functional relationship between the instruments and drums. The main result is that richly textured drum tracks that tightly follow the structure of the original song are easily generated because of their functional relationship to it.
Kenneth O. Stanley, David B. D'Ambrosio, and Jason Gauci To appear in: Artificial Life journal. Cambridge, MA: MIT Press, 2009 (Manuscript 39 pages)Abstract Research in neuroevolution, i.e. evolving artificial neural networks (ANNs) through evolutionary algorithms, is inspired by the evolution of biological brains. Because natural evolution discovered intelligent brains with billions of neurons and trillions of connections, perhaps neuroevolution can do the same. Yet while neuroevolution has produced successful results in a variety of domains, the scale of natural brains remains far beyond reach. This paper 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 (connective 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. The advantage of this approach is that it 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 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.
2008
Joel Lehman and Kenneth O. StanleyNote: This paper is accompanied with version 1.0 of the Novelty Search C++ software found here. To appear in: Proceedings of the Eleventh International Conference on Artificial Life (ALIFE XI). Cambridge, MA: MIT Press, 2008 (8 pages)Abstract
This paper establishes a link between the challenge of solving highly ambitious problems in machine learning and the goal of reproducing the dynamics of open-ended evolution in artificial life. A major problem with the objective function in machine learning is that through deception it may actually prevent the objective from being reached. In a similar way, selection in evolution may sometimes act to discourage increasing complexity. This paper proposes a single idea that both overcomes the obstacle of deception and suggests a simple new approach to open-ended evolution: Instead of either explicitly seeking an objective or modeling a domain to capture the open-endedness of natural evolution, the idea is to simply search for novelty. Even in an objective-based problem, such novelty search ignores the objective and searches for behavioral novelty. Yet because many points in the search space collapse to the same point in behavior space, it turns out that the search for novelty is computationally feasible. Furthermore, because there are only so many simple behaviors, the search for novelty leads to increasing complexity. In fact, on the way up the ladder of complexity, the search is likely to encounter at least one solution. In this way, by decoupling the idea of open-ended search from only artificial life worlds, the raw search for novelty can be applied to real world problems. Counterintuitively, in the deceptive maze navigation task in this paper, novelty search significantly outperforms objective-based search, suggesting a surprising new approach to machine learning.
David B. D'Ambrosio and Kenneth O. StanleyIn: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2008). New York, NY: ACM, 2008 (8 pages)Winner of the Best Paper Award in Generative and Developmental Systems at GECCO-2008 Abstract
This paper argues that multiagent learning is a potential "killer application" for generative and developmental systems (GDS) because key challenges in learning to coordinate a team of agents are naturally addressed through indirect encodings and information reuse. For example, a significant problem for multiagent learning is that policies learned separately for different agent roles may nevertheless need to share a basic skill set, forcing the learning algorithm to reinvent the wheel for each agent. GDS is a good match for this kind of problem because it specializes in ways to encode patterns of related yet varying motifs. In this paper, to establish the promise of this capability, the Hypercube-based NeuroEvolution of Augmenting Topologies (HyperNEAT) generative approach to evolving neurocontrollers learns a set of coordinated policies encoded by a single genome representing a team of predator agents that work together to capture prey. Experimental results show that it is not only possible, but beneficial to encode a heterogeneous team of agents with an indirect encoding. The main contribution is thus to open up a significant new application domain for GDS.
Jason Gauci and Kenneth O. StanleyNote: This paper is accompanied with version 2.0 of the HyperNEAT software found here. To appear in: Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence (AAAI-2008). Menlo Park, CA: AAAI Press, 2008 (6 pages)
Abstract
An important feature of many problem domains in machine learning is their geometry. For example, adjacency relationships, symmetries, and Cartesian coordinates are essential to any complete description of board games, visual recognition, or vehicle control. Yet many approaches to learning ignore such information in their representations, instead inputting flat parameter vectors with no indication of how those parameters are situated geometrically. This paper argues that such geometric information is critical to the ability of any machine learning approach to effectively generalize; even a small shift in the configuration of the task in space from what was experienced in training can go wholly unrecognized unless the algorithm is able to learn the regularities in decision-making across the problem geometry. To demonstrate the importance of learning from geometry, three variants of the same evolutionary learning algorithm (NeuroEvolution of Augmenting Topologies), whose representations vary in their capacity to encode geometry, are compared in checkers. The result is that the variant that can learn geometric regularities produces a significantly more general solution. The conclusion is that it is important to enable machine learning to detect and thereby learn from the geometry of its problems.
Jimmy Secretan, Nicholas Beato, David B. D'Ambrosio, Adelein Rodriguez, Adam Campbell and Kenneth O. StanleyIn: Proceedings of the Computer Human Interaction Conference (CHI 2008). New York, NY: ACM, 2008 (10 pages)Abstract
Picbreeder is an online service that allows users to collaborativelyevolve images. Like in other Interactive Evolutionary Computation (IEC) programs, users evolve images in Picbreeder by selecting ones that appeal to them to produce a new generation. However, Picbreeder also offers an online community in which to share these images, and most importantly, the ability to continue evolving others’ images. Through this process of branching from other images, and through continually increasing image complexity made possible by the NeuroEvolution of Augmenting Topologies (NEAT) algorithm, evolved images proliferate unlike in any other current IEC systems. Picbreeder enables all users, regardless of talent, to participate in a creative, exploratory process. This paper details how Picbreeder encourages innovation, featuring images that were collaboratively evolved.
Amy K. Hoover, Michael P. Rosario, and Kenneth O. StanleyIn: Proceedings of the Sixth European Workshop on Evolutionary and Biologically Inspired Music, Sound, Art and Design (EvoMUSART 2008). New York, NY: Springer, 2008 (10 pages)Winner of the Best Paper Award at EvoMUSART 2008
Abstract
A major challenge in computer-generated music is to produce music that sounds natural. This paper introduces NEAT Drummer, which takes steps toward natural creativity. NEAT Drummer evolves a kind of artificial neural network called a Compositional Pattern Producing Network (CPPN) with the NeuroEvolution of Augmenting Topologies (NEAT) method to produce drum patterns. An important motivation for this work is that instrument tracks can be generated as a function of other song parts, which, if written by humans, thereby provide a scaffold for the remaining auto-generated parts. Thus, NEAT Drummer is initialized with inputs from an existing MIDI song and through interactive evolution allows the user to evolve increasingly appealing rhythms for that song. This paper explains how NEAT Drummer processes MIDI inputs and outputs drum patterns. The net effect is that a compelling drum track can be automatically generated and evolved for any song.
2007Jimmy Secretan, Nicholas Beato, David B. D'Ambrosio, Adelein Rodriguez, Adam Campbell and Kenneth O. StanleyIn: Leonardo (Transactions Section) Vol. 41, No. 1. Cambridge, MA: MIT Press, 2008. (2 pages)Abstract
Picbreeder is a new website that is open to the public for collaborative interactive evolution of images. A unique feature of Picbreeder is that users can continue evolving other users’ images by branching. The continual process of evolving and branching means that images can continue to improve and increase in complexity indefinitely, yielding a proliferation of artistic novelty that requires no explicit artistic talent to produce.
Jason J. Gauci and Kenneth O. StanleyIn: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2007). New York, NY: ACM, 2007 (8 pages)Abstract
Connectivity patterns in biological brains exhibit many repeating motifs. This repetition mirrors inherent geometric regularities in the physical world. For example, stimuli that excite adjacent locations on the retina map to neurons that are similarly adjacent in the visual cortex. That way, neural connectivity can exploit geometric locality in the outside world by employing local connections in the brain. If such regularities could be discovered by methods that evolve artificial neural networks (ANNs), then they could be similarly exploited to solve problems that would otherwise require optimizing too many dimensions to solve. This paper introduces such a method, called Hypercube-based Neuroevolution of Augmenting Topologies (HyperNEAT), which evolves a novel generative encoding called connective Compositional Pattern Producing Networks (connective CPPNs) to discover geometric regularities in the task domain. Connective CPPNs encode connectivity patterns as concepts that are independent of the number of inputs or outputs, allowing functional large-scale neural networks to be evolved. In this paper, this approach is tested in a simple visual task for which it effectively discovers the correct underlying regularity, allowing the solution to both generalize and scale without loss of function to an ANN of over eight million connections.
David B. D'Ambrosio and Kenneth O. StanleyIn: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2007). New York, NY: ACM, 2007 (8 pages)Nominated for Best Paper Award in Generative and Developmental Systems at GECCO-2007 Abstract
A significant problem for evolving artificial neural networks is that the physical arrangement of sensors and effectors is invisible to the evolutionary algorithm. For example, in this paper, directional sensors and effectors are placed around the circumference of a robot in analogous arrangements. This configuration ensures that there is a useful geometric correspondence between sensors and effectors. However, if sensors are mapped to a single input layer and the effectors to a single output layer (as is typical), evolution has no means to exploit this fortuitous arrangement. To address this problem, this paper presents a novel generative encoding called connective Compositional Pattern Producing Networks (connective CPPNs) that can effectively detect and capitalize on geometric relationships among sensors and effectors. The key insight is that sensors and effectors with consistent geometric relationships can be exploited by a repeating motif in the neural architecture. Thus, by employing an encoding that can discover such motifs as a function of network geometry, it becomes possible to exploit it. In this paper, a method for evolving connective CPPNs called Hypercube-based Neuroevolution of Augmenting Topologies (HyperNEAT) discovers sensible repeating motifs that take advantage of two different placement schemes, demonstrating the utility of such an approach.
Kenneth O. StanleyIn: Genetic Programming and Evolvable Machines Special Issue on Developmental Systems 8(2): 131-162. New York, NY: Springer, 2007 (36 pages)Springer link to article in publication format (requires subscription to Springer): http://www.springerlink.com/content/804411v3703ph210/ Abstract
Natural DNA can encode complexity on an enormous scale. Researchers are attempting to achieve the same representational efficiency in computers by implementing developmental encodings, i.e. encodings that map the genotype to the phenotype through a process of growth from a small starting point to a mature form. A major challenge in in this effort is to find the right level of abstraction of biological development to capture its essential properties without introducing unnecessary inefficiencies. In this paper, a novel abstraction of natural development, called Compositional Pattern Producing Networks (CPPNs), is proposed. Unlike currently accepted abstractions such as iterative rewrite systems and cellular growth simulations, CPPNs map to the phenotype without local interaction, that is, each individual component of the phenotype is determined independently of every other component. Results produced with CPPNs through interactive evolution of two-dimensional images show that such an encoding can nevertheless produce structural motifs often attributed to more conventional developmental abstractions, suggesting that local interaction may not be essential to the desirable properties of natural encoding in the way that is usually assumed.
Erin Hastings, Ratan Guha, and Kenneth O. StanleyIn: Proceedings of the IEEE Symposium on Computational Intelligence and Games (CIG'07). Piscataway, NJ: IEEE, 2007 (7 pages)Abstract
Particle systems are a representation, computation, and rendering method for special effects such as fire, smoke, explosions, electricity, water, magic, and many other phenomena. This paper presents NEAT Particles, a new design, representation, and animation method for particle systems tailored to real-time effects in video games and simulations. In NEAT Particles, the NeuroEvolution of Augmenting Topologies (NEAT) method evolves artificial neural networks (ANN) that control the appearance and motion of particles. NEAT Particles affords three primary advantages over traditional particle effect development methods. First, it decouples the creation of new particle effects from mathematics and programming, enabling users with little knowledge of either to produce complex effects. Second, it allows content designers to evolve a broader range of effects than typical development tools through a form of Interactive Evolutionary Computation (IEC). And finally, it acts as a concept generator, allowing users to interactively explore the space of possible effects. In the future such a system may allow content to be evolved in the game itself, as it is played.
2006Patterns Without DevelopmentKenneth O. StanleyUniversity of Central Florida Dept. of EECS Technical Report CS-TR-06-01 (40 pages)Abstract
Natural DNA can encode complexity on an enormous scale. Researchers are attempting to achieve the same representational efficiency in computers by implementing developmental encodings, i.e. encodings that map the genotype to the phenotype through a process of growth from a small starting point to a mature form. A major challenge in this effort is to find the right level of abstraction of biological development to capture its essential properties without introducing unnecessary inefficiencies. In this paper, a novel abstraction of natural development, called Compositional Pattern Producing Networks (CPPNs), is proposed. Unlike most computational abstractions of natural development, CPPNs do not include a developmental phase, differentiating them from developmental encodings. Instead of development, CPPNs employ compositions of functions derived from gradient patterns present in developing natural organisms. In this paper, a variant of the NeuroEvolution of Augmenting Topologies (NEAT), method called CPPN-NEAT, evolves increasingly complex CPPNs. This novel approach promises greater efficiency than developmental encoding and also evolves patterns with strikingly natural characteristics.
Kenneth O. StanleyIn: Proceedings of the AAAI Fall Symposium on Developmental Systems. Menlo Park, CA: AAAI Press, 2006 (8 pages)Abstract
A major challenge in evolutionary computation is to find the right level of abstraction of biological development to capture its essential properties without introducing unnecessary inefficiencies. In this paper, a novel abstraction of natural development, called Compositional Pattern Producing Networks (CPPNs), is proposed. Unlike most computational abstractions of natural development, CPPNs do not include a developmental phase, differentiating them from developmental encodings. Instead of development, CPPNs employ compositions of functions derived from gradient patterns present in developing natural organisms. In this paper, a variant of the NeuroEvolution of Augmenting Topologies (NEAT) method, called CPPN-NEAT, evolves increasingly complex CPPNs, producing patterns with strikingly natural characteristics.
Kenneth O. StanleyProceedings of the Genetic and Evolutionary Computation Conference (GECCO) Workshop Program. New York, NY: ACM Press, 2006 (2 pages)Abstract
As an aid in assessing artificial developmental encodings, this paper presents several common and uncommon features of patterns observed in biological organisms. Evolved phenotypes can be compared with both lists in order to assess the viability of the encoding that generates them.
|
