The escalation of complexity is a commonly cited benefit of coevolutionary systems, but computational simulations generally fail to demonstrate this capacity to a satisfactory degree. We draw on a macroevolutionary theory of escalation to develop a set of criteria for coevolutionary systems to exhibit escalation of strategic complexity. By expanding on a previously developed model of the evolution of memory length for cooperative strategies by Kristian Lindgren, we resolve previously observed limitations on the escalation of memory length by extending operators of evolutionary variation. We present long-term coevolutionary simulations showing that larger population sizes tend to support greater escalation of complexity than smaller ones do. Additionally, we investigate the sensitivity of escalation during transitions of complexity. The Lindgren model has often been used to argue that the escalation of competitive coevolution has intrinsic limitations. Our simulations show that coevolutionary arms races can continue to escalate in computational simulations given sufficient population sizes.

To study open-ended coevolution, we define a complexity metric over interacting finite state machines playing formal language prediction games, and study the dynamics of populations under competitive and cooperative interactions. In the past purely competitive and purely cooperative interactions have been studied extensively, but neither can successfully and continuously drive an arms race. We present quantitative results using this complexity metric and analyze the causes of varying rates of complexity growth across different types of interactions. We find that while both purely competitive and purely cooperative coevolution are able to drive complexity growth above the rate of genetic drift, mixed systems with both competitive and cooperative interactions achieve significantly higher evolved complexity.

We examine the effect of cooperative and competitive interactions on the evolution of complex strategies in a prediction game. We extend previous work to the domain of noisy games, defining a new organism and mutation model, and an accompanying novel complexity metric. We find that a mix of cooperation and competition is the most effective in driving complexity growth, confirming prior results. We also compare our complexity metric with simpler metrics such as raw strategy size, and demonstrate the effectiveness of our metric in distinguishing true complexity from mere genetic bloat.

Artificial gene regulatory networks (GRNs) are biologically inspired dynamical systems used to control various kinds of agents, from the cells in developmental models to embodied robot swarms. Most recent work uses a genetic algorithm (GA) or an evolution strategy in order to optimize the network for a specific task. However, the empirical performances of these algorithms are unsatisfactory. This paper presents an algorithm that primarily exploits a network distance metric, which allows genetic similarity to be used for speciation and variation of GRNs. This algorithm, inspired by the successful neuroevolution of augmenting topologies algorithm's use in evolving neural networks and compositional pattern-producing networks, is based on a specific initialization method, a crossover operator based on gene alignment, and speciation based upon GRN structures. We demonstrate the effectiveness of this new algorithm by comparing our approach both to a standard GA and to evolutionary programming on four different experiments from three distinct problem domains, where the proposed algorithm excels on all experiments.

Evolving swarms can be used both to solve real-world problems and to study biological and ecological phenomena. We simulated an evolving swarm of birds under three different types of climate-change-related environmental variation a temperate environment becoming tropical, a temperate enviroment becoming a desert, and a tropical environment becoming a desert. We found that desertification increased expirations within the swarm and decreased population stability. The direction of the variation tropicalification or desertification had a greater impact on the dynamics of the swarm than the degree of variation when it came to these outcomes. The environmental variation also affected the genetics of the birds, with decreased food availability leading to collision avoidance genes being downplayed, and searching behavior for food being changed. High-intensity environmental variation led to less genetic stability post-change than lowerintensity environmental variation. Swarming and flocking behavior is ubiquitous throughout all scales of biological and physical systems. Swarming simulations were first developed by Reynolds (1987) using his boids, simple agents that moved according to a set of basic rules. Much later swarming behavior simulation work has focused on agent-based modeling, which is centered around the modeling of populations of individuals with rules governing their behavior (Mach and Schweitzer, 2003). Agent-based modeling has been used to study such subjects as the dynamics of mountian pine beetle infestations of forests (Perez and Dragicevic, 2010) and the dynamics of how bacteria aggregate to form microfilms (Lardon et al., 2011). Recent advances in robotics have made it possible to experiment with large-scale physical swarms of robots (Rubenstein et al., 2012). Swarm flying behavior is increasingly an area of interest, with a variety of algorithms and applications being developed. Karaboga (2005) used simulations of bee swarm flying to develop a numerical optimization method, and Su et al. (2009) modeled flocking behavior in the presence of a group leader. Optimization of heterogenous swarms of flying agents is challenging, but is potentially very useful in applications such as crop polination (Nagpal et al., 2011; Figure 1: Example of evolving swarm and environment. Berman et al., 2011). Flying swarms have also been applied in the lab to tasks such as chemical cloud detection (Kovacina et al., 2002) and dynamic communications relays (Hauert et al., 2008).

Modularity, often observed in biological systems, does not easily arise in computational evolution. We explore the effect of adding a small fitness cost for each connection between neurons on the modularity of neural networks produced by the NEAT neuroevolution algorithm. We find that this connection cost does not increase the modularity of the best network produced by each run of the algorithm, but that it does lead to increased consistency in the level of modularity produced by the algorithm.

All multicellular living beings are created from a single cell. A developmental process, called embryogenesis, takes this first fertilized cell down a complex path of reproduction, migration, and specialization into a complex organism adapted to its environment. In most cases, the first steps of the embryogenesis take place in a protected environment such as in an egg or in utero. Starting from this observation, we propose a new approach to the generation of real robots, strongly inspired by living systems. Our robots are composed of tens of specialized cells, grown from a single cell using a bio-inspired virtual developmental process. Virtual cells, controlled by gene regulatory networks, divide, migrate, and specialize to produce the robot's body plan (morphology), and then the robot is manually built from this plan. Because the robot is as easy to assemble as Lego, the building process could be easily automated.

An important connection between evolution and learning was made over a century ago and is now termed as the Baldwin effect. Learning acts as a guide for an evolutionary search process. In this study reinforcement learning agents are trained to solve the robot coverage control problem. These agents are improved by evolving neuromodulatory gene regulatory networks (GRN) that influence the learning and memory of agents. Agents trained by these neuromodulatory GRNs can consistently generalize better than agents trained with fixed parameter settings. This work introduces evolutionary GRN models into the context of neuromodulation and illustrates some of the benefits that stem from neuromodulatory GRNs.

This paper proposes a new method to evaluate the complexity of a Gene Regulatory Network (GRN). It is based on the generation of pictures. In addition to being visually interesting, the pictures shows the capacity of the GRN to produce smooth and/or sudden transitions, fractal-like complexity and regularities. We also have studied the influence of the size of the GRN on the complexity of pictures generated.

In the research described here we examine the emergence of signaling from non-communicative origins, using the Sir Philip Sidney Game as a framework for our analysis. This game is known to exhibit a number of interesting dynamics. In our study, we quantify the difficulty of reaching multiple types of equilibria from initially non-communicative popula-tions with an infinite population model. We then compare the ability of finite populations with typical tournament selection to approximate the behaviors observed in infinite populations. Our findings suggest that honest signaling equilibria are diffi-cult to reach from non-communicative origins. In the second part of the paper, we show that the finite model fails to model dynamics that permit deceptive signaling under typical evolu-tionary conditions, where infinite populations exhibit spiral-ing behavior between honest and deceptive signaling.

This paper presents a new method to generate the body plans of modular robots. In this work, we use a developmental model where cells are controlled by a gene regulatory network. Instead of using morphogens as in many existing works, we evolve a more flexible "hormonal system" that controls the inputs of the regulatory network. By evolving the regulatory network and the hormonal system in parallel with a blind watchmaker, we have generated various virtual robots with interesting inherent properties such as regularity and symmetry. The prototypes of the robotic blocks that will be used to actually build the real machines are also presented in this paper.

This paper explores connections between Ficici's notion of solution concept and order theory. Ficici postulates that algorithms should ascend an order called weak preference; thus, understanding this order is important to questions of designing algorithms. We observe that the weak preference order is closely related to the pullback of the so-called lower ordering on subsets of an ordered set. The latter can, in turn, be represented as the pullback of the subset ordering of a certain powerset. Taken together, these two observations represent the weak preference ordering in a more simple and concrete form as a subset ordering. We utilize this representation to show that algorithms which ascend the weak preference ordering are vulnerable to a kind of bloating problem. Since this kind of bloat has been observed several times in practice, we hypothesize that ascending weak preference may be the cause. Finally, we show that monotonic solution concepts are convex in the order-theoretic sense. We conclude by speculating that monotonic solution concepts might be derivable from non-monotonic ones by taking convex hull. Since several intuitive solution concepts like average fitness are not monotonic, there is practical value in creating monotonic solution concepts from non-monotonic ones.

The use of genotypic populations is necessary for adaptation in Evolutionary Algorithms. We use a technique called form-invariant commutation to study the immediate effect of evolutionary operations on populations of genotypes. This technique allows us to understand compositional changes induced by evolutionary operations in terms of constraints between populations. Deep insight into the population-level effect of some evolutionary operation is possible when multiple constraints can be derived for all pairs of pre and post operative populations; for each such pair of populations the constraints between them are then said to hold simultaneously. When selection is fitness proportional we show that any coarse-graining of the genotype set can be used to systematically derive single constraints between between all pairs of pre and post selection populations. Matters are not so simple in the case of variation. We develop an abstract condition called ambivalence and show that when a coarse-graining and a variation operation satisfy this condition then a systematic derivation of single constraints between all pairs of pre and post variation populations is possible. Finally we show that it is possible to use schema partitions to systematically derive simultaneous constraints for any combination of variation operations that are commonly used in GAs.

Evolutionary computation has demonstrated the ability to design novel and interesting objects. Such objects are increasingly being assembled in the physical world, albeit with some difficultly. An obstacle to this assembly is that most evolved designs are descriptive representations: they specify what to build, but carry no information on how to build it. Inferring a corresponding assembly sequence for such an object is a complex task for any but the most trivial designs. We offer an alternative solution to this spectre of the fabrication gap, namely the direct evolution of assembly sequences. As we show, such methods not only lead to the evolution of buildable objects, but also lead to the emergence of novel means of assembly as well

When applied to optimization problems, Cooperative Coevolutionary Algorithms(CCEA) have been observed to exhibit a behavior called relative overgeneralization. Roughly, they tend to identify local optima with large basins of attraction which may or may not correspond to global optima. A question which arises is whether one can modify the algorithm to promote the discovery of global optima. We argue that a mechanism from Pareto coevolution can achieve this end. We observe that in CCEAs candidate individuals from one population are used as tests or measurements of individuals in other populations; by treating individuals as tests in this way, a finer-grained comparison can be made among candidate individuals. This finer-grained view permits an algorithm to see when two candidates are differently capable, even when one's evident value is higher than the other's. By modifying an existing CCEA to compare individuals using Pareto dominance we have produced an algorithm which reliably finds global optima. We demonstrate the algorithm on two Maximum of Two Quadratics problems and discuss why it works.

Artificial Ontogenies, which are inspired by biological development, have been used to automatically generate a wide array of novel objects, some of which have recently been manufactured in the real world. The majority of these evolved designs have been evaluated in simulation as completed objects, with no attention paid to how, or even if, they can be realistically built. As a consequence, significant human effort is required to transfer the designs to the real world. One way to reduce human involvement in this regard is to evolve how to build rather than what to build, by using prescriptive rather than descriptive representations. In the context of Artificial Ontogenies, this requires what we call Situated Development, in which an object's development occurs in the same environment as its final evaluation. Not only does this produce sufficient information on how to build evolved designs, but it also ensures that only buildable designs are evolved. In this paper we explore the consequences of Situated Development, and demonstrate how it can be incorporated into Artificial Ontogenies in order to generate buildable objects, which can be sequentially assembled in a realistic 3-D physics environment.

Herbert A. Simon's characterization of modularity in dynamical systems describes subsystems as having dynamics that are approximately independent of those of other subsystems (in the short term). This fits with the general intuition that modules must, by definition, be approximately independent. In the evolution of complex systems, such modularity may enable subsystems to be modified and adapted independently of other subsystems, whereas in a nonmodular system, modifications to one part of the system may result in deleterious side effects elsewhere in the system. But this notion of modularity and its effect on evolvability is not well quantified and is rather simplistic. In particular, modularity need not imply that intermodule dependences are weak or unimportant. In dynamical systems this is acknowledged by Simon's suggestion that, in the long term, the dynamical behaviors of subsystems do interact with one another, albeit in an "aggregate" manner--but this kind of intermodule interaction is omitted in models of modularity for evolvability. In this brief discussion we seek to unify notions of modularity in dynamical systems with notions of how modularity affects evolvability. This leads to a quantifiable measure of modularity and a different understanding of its effect on evolvability.

We use evolutionary game theory (EGT) to investigate the dynamics and equilibria of selection methods in coevolutionary algorithms. The canonical selection method used in EGT is equivalent to the standard "fitness-proportional" selection method used in evolutionary algorithms. All attractors of the EGT dynamic are Nash equilibria; we focus on simple symmetric variable-sum games that have polymorphic Nash-equilibrium attractors. Against the dynamics of proportional selection, we contrast the behaviors of truncation selection, (/spl mu/,/spl lambda/),(/spl mu/+/spl lambda/), linear ranking, Boltzmann, and tournament selection. Except for Boltzmann selection, each of the methods we test unconditionally fail to achieve polymorphic Nash equilibrium. Instead, we find point attractors that lack game-theoretic justification, cyclic dynamics, or chaos. Boltzmann selection converges onto polymorphic Nash equilibrium only when selection pressure is sufficiently low; otherwise, we obtain attracting limit-cycles or chaos. Coevolutionary algorithms are often used to search for solutions (e.g., Nash equilibria) of games of strategy; our results show that many selection methods are inappropriate for finding polymorphic Nash solutions to variable-sum games. Another application of coevolution is to model other systems; our results emphasize the degree to which the model's behavior is sensitive to implementation details regarding selection-details that we might not otherwise believe to be critical.

In many problems of interest, performance can be evaluated using tests, such as examples in concept learning, test points in function approximation, and opponents in game-playing. Evaluation on all tests is often infeasible. Identification of an accurate evaluation or fitness function is a difficult problem in itself, and approximations are likely to introduce human biases into the search process. Coevolution evolves the set of tests used for evaluation, but has so far often led to inaccurate evaluation. We show that for any set of learners, a Complete Evaluation Set can be determined that provides ideal evaluation as specified by Evolutionary Multi-Objective Optimization. This provides a principled approach to evaluation in coevolution, and thereby brings automatic ideal evaluation within reach. The Complete Evaluation Set is of manageable size, and progress towards it can be accurately measured. Based on this observation, an algorithm named DELPHI is developed. The algorithm is tested on problems likely to permit progress on only a subset of the underlying objectives. Where all comparison methods result in overspecialization, the proposed method and a variant achieve sustained progress in all underlying objectives. These findings demonstrate that ideal evaluation may be approximated by practical algorithms, and that accurate evaluation for test-based problems is possible even when the underlying objectives of a problem are unknown.

The field of evolutionary robotics has demonstrated the ability to automatically design the morphology and controller of simple physical robots through synthetic evolutionary processes. However, it is not clear if variation-based search processes can attain the complexity of design necessary for practical engineering of robots. Here, we demonstrate an automatic design system that produces complex robots by exploiting the principles of regularity, modularity, hierarchy, and reuse. These techniques are already established principles of scaling in engineering design and have been observed in nature, but have not been broadly used in artificial evolution. We gain these advantages through the use of a generative representation, which combines a programmatic representation with an algorithmic process that compiles the representation into a detailed construction plan. This approach is shown to have two benefits: it can reuse components in regular and hierarchical ways, providing a systematic way to create more complex modules from simpler ones; and the evolved representations can capture intrinsic properties of the design space, so that variations in the representations move through the design space more effectively than equivalent-sized changes in a nongenerative representation. Using this system, we demonstrate for the first time the evolution and construction of modular, three-dimensional, physically locomoting robots, comprising many more components than previous work on body-brain evolution.

One of the main limitations of scalability in body-brain evolution systems is the representation chosen for encoding creatures. This paper defines a class of representations called generative representations, which are identified by their ability to reuse elements of the genotype in the translation to the phenotype. This paper presents an example of a generative representation for the concurrent evolution of the morphology and neural controller of simulated robots, and also introduces GENRE, an evolutionary system for evolving designs using this representation. Applying GENRE to the task of evolving robots for locomotion and comparing it against a non-generative (direct) representation shows that the generative representation system rapidly produces robots with significantly greater fitness. Analyzing these results shows that the generative representation system achieves better performance by capturing useful bias from the design space and by allowing viable large scale mutations in the phenotype. Generative representations thereby enable the encapsulation, coordination, and reuse of assemblies of parts.

One of the applications of evolutionary algorithms is the automatic creation of designs. For evolutionary techniques to scale to the complexities necessary for actual engineering problems, it has been argued that generative systems, where the genotype is an algorithm for constructing the final design, should be used as the encoding. We describe a system for creating generative specifications by combining Lindenmayer systems with evolutionary algorithms, and we apply it to the problem of generating table designs. Designs evolved by our system reach an order of magnitude more parts than previous generative systems. Comparing it against a non-generative encoding, we find that the generative system produces designs with higher fitness and is faster than the non-generative system. Finally, we demonstrate the ability of our system to go from design to manufacture by constructing evolved table designs using rapid prototyping equipment.

Recent research has demonstrated the ability for automatic design of the morphology and control of real physical robots using techniques inspired by biological evolution. The main criticism of the evolutionary design approach, however, is that it is doubtful whether it will reach the high complexities necessary for practical engineering. Here we claim that for automatic design systems to scale in complexity the designs they produce must be made of re-used modules. Our approach is based on the use of a generative design grammar subject to an evolutionary process. Unlike a direct encoding of a design, a generative design specification can re-use components, giving it the ability to create more complex modules from simpler ones. Re-used modules are also valuable for improved efficiency in testing and construction. We describe a system for creating generative specifications capable of hierarchical modularity by combining Lindenmayer systems with evolutionary algorithms. Using this system we demonstrate for the first time a generative system for physical, modular, 2D locomoting robots and their controllers.

The difficulties associated with designing, building, and controlling robots have led their development to a stasis: Applications are limited mostly to repetitive tasks with predefined behavior. Over the last few years we have been trying to address this challenge through an alternative approach: Rather than trying to control an existing machine or create a general-purpose robot, we propose that both the morphology and the controller should evolve at the same time. This process can lead to the automatic design of special-purpose mechanisms and controllers for specific short-term objectives. Here we provide a brief review of three generations of our recent research, which underlies the robots shown on the cover of this issue: Automatically designed static structures, automatically designed and manufactured dynamic electromechanical systems, and modular robots automatically designed through a generative DNA-like encoding.

The replicator equation used in evolutionary game theory (EGT) assumes that strategies reproduce in direct proportion to their payoffs; this is akin to the use of fitness-proportionate selection in an evolutionary algorithm (EA). In this paper, we investigate how various other selection methods commonly used in EAs can affect the discrete-time dynamics of EGT. In particular, we show that the existence of evolutionary stable strategies (ESS) is sensitive to the selection method used. Rather than maintain the dynamics and equilibria of EGT, the selection methods we test either impose a fixed-point dynamic virtually unrelated to the payoffs of the game matrix, or they give limit cycles or induce chaos. These results are significant to the field of evolutionary computation because EGT can be understood as a coevolutionary algorithm operating under ideal conditions: an infinite population, noiseless payoffs and complete knowledge of the phenotype space. Thus, certain selection methods, which may operate effectively in simple evolution, are pathological in an ideal-world coevolutionary algorithm, and therefore dubious under real-world conditions.

We propose a new process for continuously reconfigurable robotics. Given a task, a robot evolves a suitable morphology and control, then prints the assembled 3D structure, downloads into it and performs the task, and then recycles into a different form for the next task. This approach relinquishes the need to adhere to discrete or fixed components as well as manually designed configurations. Although the technology for fully realizing the proposed concept is not entirely available, we have demonstrated a first case: Given the task of locomotion, various robots with different mechanics and control are evolved automatically. The design space is comprised of only linear actuators and sigmoidal control neurons embodied in an arbitrary thermoplastic body. The robots then print pre-assembled using rapid prototyping technology, and perform the task in reality. The robots are then recycled. This paper described one implementation and provides examples of successful physical robots generated by the proposed process.

With its ability to represent variable sized trees in fixed width patterns, recursive auto-associative memory (RAAM) is a bridge between connectionist and symbolic systems. In the past, due to limitations in our understanding, its development plateaued. By examining RAAM from a dynamical systems perspective we overcome most of the problems that previously plagued it. In fact, using a dynamical systems analysis we can now prove that not only is RAAM capable of generating parts of a context free language (a/sup n/b/sup n/) but is capable of expressing the whole language.

We present a method to extract qualitative information from any classification model that uses decision regions, independent on the dimensionality of the data and model. The qualitative information can be directly used to analyze the classification strategies employed by a model, and also to directly compare strategies across different models. We apply the method to compare between two types of classifiers using real-world high-dimensional data.

We present an algorithm to extract representations from multiple hidden layer, multiple output feedforward perceptron threshold networks. The representation is based on polytopic decision regions in the input space and is exact not an approximation like most other network analysis methods. Multiple examples show some of the knowledge that can be extracted from networks by using this algorithm, including the geometrical form of artifacts and bad generalization. We compare threshold and sigmoidal networks with respect to the expressiveness of their decision regions, and also prove lower bounds for any algorithm which extracts decision regions from arbitrary neural networks.

The paper studies the effect of noise on co-evolutionary learning, using Backgammon as a typical noisy task. It might seem that co-evolutionary learning would be ill-suited to noisy tasks: genetic drift causes convergence to a population of similar individuals, and on noisy tasks it would seem to require many samples (i.e., many evaluations and long computation time) to discern small differences between similar population members. Surprisingly, the paper learns otherwise: for small population sizes, the number of evaluations does have an effect on learning; but for sufficiently large populations, more evaluations do not improve learning at all-population size is the dominant variable. This is because a large population maintains more diversity, so that the larger differences in ability can be discerned with a modest number of evaluations. This counter-intuitive result means that co-evolutionary learning is a feasible method for noisy tasks, such as military situations and investment management.

We introduce Embodied Evolution (EE) as a methodology for the automatic design of robotic controllers. EE is an evolutionary robotics (ER) technique that avoids the pitfalls of the simulate-and-transfer method, allows the speed-up of evaluation time by utilizing parallelism, and is particularly suited to future work on multi-agent behaviors. In EE, an evolutionary algorithm is distributed amongst and embodied within a population of physical robots that reproduce with one another while situated in the task environment. We have built a population of eight robots and successfully implemented our first experiments. The controllers evolved by EE compare favorably to hand-designed solutions for a simple task. We detail our methodology, report our initial results, and discuss the application of EE to more advanced and distributed robotics tasks.

The building-block hypothesis suggests that the genetic algorithm (GA) will perform well when it is able to identify above-average-fitness low-order schemata and recombine them to produce higher-order schemata of higher fitness. We suppose that the recombinative process continues recursively, combining schemata of successively higher orders as search progresses. Historically, attempts to illustrate this intuitively straight-forward process on abstract test problems, most notably the Royal Road problems, have been somewhat perplexing. More recent building-block test problems have abandoned the multi-level hierarchical structure of the Royal Roads, and thus departed from the original recursive aspects of the hypothesis. This paper defines the concept of hierarchical consistency, which captures the recursive nature of problems implied by the building-block hypothesis. We introduce several variants of problems that are hierarchically consistent and begin to explore aspects of problem difficulty with respect to these models.

Creating artificial life forms through evolutionary robotics faces a "chicken and egg" problem: Learning to control a complex body is dominated by problems specific to its sensors and effectors, while building a body that is controllable assumes the pre-existence of a brain. The idea of coevolution of bodies and brains is becoming popular, but little work has been done in evolution of physical structure because of the lack of a general framework for doing it. Evolution of creatures in simulation has usually resulted in virtual entities that are not buildable, while embodied evolution in actual robotics is constrained by the slow pace of real time. The work we present takes a step in addressing the problem of body evolution by applying evolutionary techniques to the design of structures assembled out of elementary components that stick together. Evolution takes place in a simulator that computes forces and stresses and predicts stability of three-dimensional brick structures. The final printout of our program is a schematic assembly, which is then built physically. We demonstrate the functionality of this approach to robot body building with many evolved artifacts.

Following Tesauro's work on TD-Gammon, we used a 4,000 parameter feedforward neural network to develop a competitive backgammon evaluation function. Play proceeds by a roll of the dice, application of the network to all legal moves, and selection of the position with the highest evaluation. However, no backpropagation, reinforcement or temporal difference learning methods were employed. Instead we apply simple hillclimbing in a relative fitness environment. We start with an initial champion of all zero weights and proceed simply by playing the current champion network against a slightly mutated challenger and changing weights if the challenger wins. Surprisingly, this worked rather well. We investigate how the peculiar dynamics of this domain enabled a previously discarded weak method to succeed, by preventing suboptimal equilibria in a “meta-game” of self-learning.

Pollack (1991) demonstrated that second-order recurrent neural networks can act as dynamical recognizers for formal languages when trained on positive and negative examples, and observed both phase transitions in learning and interacted function system-like fractal state sets. Follow on work focused mainly on the extraction and minimization of a finite state automaton (FSA) from the trained network. However, such networks are capable of inducing languages that are not regular and therefore not equivalent to any FSA. Indeed, it may be simpler for a small network to fit its training data by inducing such a nonregular language. But when is the network's language not regular? In this article, using a low-dimensional network capable of learning all the Tomita data sets, we present an empirical method for testing whether the language induced by the network is regular. We also provide a detailed "-machine analysis of trained networks for both regular and nonregular languages.

Many researchers in AI and cognitive science believe that the complexity of a behavioural description reflects the underlying information processing complexity of the mechanism producing the behaviour. This paper explores the foundations of this complexity assumption. We first distinguish two types of complexity judgements that can be applied to these descriptions and then argue that neither type can be an intrinsic property of the underlying physical system. In short, we demonstrate how changes in the method of observation can radically alter both the number of apparent states and the apparent generative class of a system's behavioural description. From these examples we conclude that the act of observation can suggest frivolous computational explanations of physical phenomena, up to and including cognition.

Achilles cannot overtake a fleeing tortoise because in the interval of time that he takes to get to where the tortoise was, it can move away. But even if it should wait for him Achilles must first reach the half-way mark between them and he cannot do this unless he first reaches the half-way mark to that mark, and so on indefinitely. Against such an infinite conceptual regression he cannot even make a start, and so motion is impossible (Zeno, according to Zippin 1962, p. 10).

Standard methods for simultaneously inducing the structure and weights of recurrent neural networks limit every task to an assumed class of architectures. Such a simplification is necessary since the interactions between network structure and function are not well understood. Evolutionary computations, which include genetic algorithms and evolutionary programming, are population-based search methods that have shown promise in many similarly complex tasks. This paper argues that genetic algorithms are inappropriate for network acquisition and describes an evolutionary program, called GNARL, that simultaneously acquires both the structure and weights for recurrent networks. GNARL's empirical acquisition method allows for the emergence of complex behaviors and topologies that are potentially excluded by the artificial architectural constraints imposed in standard network induction methods.