Crowd simulations are used extensively to study the dynamics of human collectives. Such studies are underpinned by specific movement models, which encode rules and assumptions about how people navigate a space and handle interactions with others. These models often give rise to macroscopic simulated crowd behaviours that are statistically valid, but which lack the noisy microscopic behaviours that are the signature of believable real crowds. In this article, we use an existing Turing test for crowds to identify realistic features of real crowds that are generally omitted from simulation models. Our previous study using this test established that untrained individuals have difficulty in classifying movies of crowds as real or simulated, and that such people often have an idealised view of how crowds move. In this follow-up study (with new participants) we perform a second trial, which now includes a training phase (showing participants movies of real crowds). We find that classification performance significantly improves after training, confirming the existence of features that allow participants to identify real crowds. High-performing individuals are able to identify the features of real crowds that should be incorporated into future simulations if they are to be considered realistic.

Japanese puzzle games such asSudokuandFutoshikiare familiar recreational pursuits, but they also present an interesting computational challenge. A number of algorithms exist for the automated solution of such puzzles, but, until now, these have not been compared in a unified way. Here, we present an integrated framework for the study of combinatorial black-box optimization, using Japanese puzzles as the test-bed. Importantly, our platform is extendable, allowing for the easy addition of both puzzles and solvers. We compare the performance of a number of optimization algorithms on five different puzzle games, and identify a subset of puzzle instances that could provide a challenging benchmark set for future algorithms.

In this article, we present a new algorithm for the well-known and computationally challenging Sudoku puzzle game. Our ant-colony-optimization-based method significantly outperforms the state-of-the-art algorithm on the hardest, large instances of Sudoku. We provide evidence that-compared to traditional backtracking methods-our algorithm offers a much more efficient search of the solution space, and demonstrate the utility of a novel antistagnation operator. This work lays the foundation for future work on a general-purpose puzzle solver, and establishes Japanese pencil puzzles as a suitable platform for benchmarking a wide range of algorithms.

Ant Colony Optimization (ACO) is a nature-inspired optimization metaheuristic which has been successfully applied to a wide range of different problems. However, a significant limiting factor in terms of its scalability is memory complexity; in many problems, the pheromone matrix which encodes trails left by ants grows quadratically with the instance size. For very large instances, this memory requirement is a limiting factor, making ACO an impractical technique. In this paper we propose a restricted variant of the pheromone matrix with linear memory complexity, which stores pheromone values only for members of a candidate set of next moves. We also evaluate two selection methods for moves outside the candidate set. Using a combination of these techniques we achieve, in a reasonable time, the best solution qualities recorded by ACO on the Art TSP Traveling Salesman Problem instances, and the first evaluation of a parallel implementation of MAX-MIN Ant System on instances of this scale (≥ 105 vertices). We find that, although ACO cannot yet achieve the solutions found by state-of-the-art genetic algorithms, we rapidly find approximate solutions within 1 -- 2% of the best known.

The increased availability of high-performance parallel architectures such as the Graphics Processing Unit (GPU) has led to significant interest in modified versions of metaheuristics that take advantage of their capabilities. Parallel Ant Colony Optimization (ACO) algorithms are now widely-used, but these often present a challenge in terms of maximizing the potential for parallelism. One common bottleneck for parallelization of ACO occurs during the tour construction phase, when edges are probabilistically selected. Independent Roulette (I-Roulette) is an alternative to the standard Roulette Selection method used during this phase, and this achieves significant performance improvements on the GPU. In this paper we provide the first in-depth study of how I-Roulette works. We establish that, even though I-Roulette works in a qualitatively different way to Roulette Wheel selection, its use in two popular ACO variants does not affect the quality of the solutions obtained. However, I-Roulette significantly accelerates convergence to a solution. Our theoretical analysis shows that I-Roulette possesses several interesting and non-obvious features, and is capable of a form of dynamical adaptation during the tour construction process.

Shape optimization techniques are becoming increasingly important in design and engineering. This growing significance reflects the need to exploit advances in digital fabrication technologies, and the desire to create new types of surface designs for various engineering applications. Evolutionary algorithms (EAs) offer several key advantages for shape optimization, but they can also be restricted, especially as design problems scale up in size. A key challenge for evolutionary shape optimization is to overcome these challenges in order to apply EAs to large-scale, “real-world” engineering problems. This paper presents a new evolutionary approach to shape optimization using what we call “surface-mapped compositional pattern producing networks (CPPNs).” Our method outperforms a state-of-the-art gradient-based method on a simple benchmark problem, and scales well as degrees of freedom are added to the design problem. Our results demonstrate that surface-mapped CPPNs offer practical ways of approaching large-scale, real-world engineering problems with EAs, opening up exciting new opportunities for engineering design.

We are pleased to present this special issue of Artificial Life, which is dedicated to articles arising from a workshop held on September 6, 2012, as part of the Unconventional Computation and Natural Computation (UCNC) conference in Orléans, France. UCNC is now a well-established meeting in the portfolio of conferences dedicated to nonstandard computation, dating back to 1998. The 2012 conference was hosted by the Fundamental Computer Science Laboratory of the University of Orléans, and the Second Workshop on Biological and Chemical Information Technologies (BioChemIT) was organized by the COBRA project.COBRA was a three-year initiative (2010–2013), supported by the European Commission to encourage and nurture research and training in the field of biological and chemical information technology. Fundamentally, the field seeks to harness the capabilities of natural and chemical systems. Rather than simply deriving inspiration from living systems, biological and chemical IT researchers seek to directly use or construct these systems for the purposes of engineering and computation. Over the past few years, technological advances in chemistry, molecular biology, functional materials, and engineering have brought biological and chemical information processing within our control. The ability to build, design, and grow ICT systems that can exploit these processes will lead to revolutionary advances in the future [1].The five articles in this issue represent a broad swathe of work, mainly covering alternative computational substrates (such as droplet architectures, chemical media, and microbes) and novel theory (complexity measurement).The first two articles concern chemistry-based computing. The one by Jones et al. considers how an architecture composed of interacting autonomous droplets might (in future) be applied to applications in robotics. They give their design for a single droplet (capable of rudimentary sensing of its environment, processing, and actuation), which is based on the well-known Braitenberg vehicle, before presenting preliminary experimental results on the processing and actuation phases, using multiple droplets.Although the first two articles both use the Belousov-Zhabotinsky (BZ) reaction [4] as a basic underlying mechanism, the second one (by King et al.) takes a slightly different approach from the first, in that it considers the geometry of the vessel containing the reaction, and how this might be designed in order to obtain large networks of chemical oscillators. Coupled oscillators are fundamental to the study of complex systems, and their properties have been harnessed for the purposes of nonstandard computation in a variety of domains and substrates (e.g., [2]). This article presents detailed experimental investigations into the effect of channel geometry on BZ excitability, thus laying the ground for threshold-based chemical computing implemented by the combination of reactions and specific 3D reaction vessel structure.The third article, by Ozasa et al., concerns the use of single-celled organisms; specifically, microbes from the genus Euglena, which are capable of self-directed movement. Previously, single colonies have been used to implement simply neurocomputing algorithms [3], but a useful extension, demonstrated here, would be to connect multiple colonies, for the purposes of distributed processing. Euglena cells are naturally averse to blue light, and this property is used to externally direct the swimming behavior of colonies of cells. In this way, the isolated colonies may be optically coupled, which allows studies of both cooperative and competitive control of behavior and colony distribution.The fourth article, by Beneš et al., also concerns microbial computing, but in the context of synthetic biology. The engineering of genetic circuits within bacteria (and other simple organisms) is now well established, but there are inherent difficulties with the approach, due to the unpredictable nature of the biological substrate. The notion of evolving circuits in situ is therefore appealing, and here the authors present a scheme for using plasmids (short circular strands of DNA) to drive a population towards good solutions. Importantly, they present a dual selection mechanism, and simulation results suggest that this adds robustness to the process.The final article in this issue, by Lui et al., considers issues of complexity, and introduces a new definition based on Kolmogorov complexity and Shannon entropy. The article shows some applications of this new measure, one using the familiar cellular automata classification scheme of Wolfram, and the other using the self-organization of porphyrin molecules. The utility of the method is illustrated by convincing demonstrations that the results of measuring existing well-understood structures (using the new metric) are consistent with previous theory.We thank the European Commission for supporting COBRA (grant number 270371), the UCNC organizers for hosting our workshop, the Editor-in-Chief, Mark Bedau, for the opportunity to publish the special issue, and the anonymous reviewers for their timely, clear, and helpful assessments.

Recent advances in fabrication technologies open up exciting opportunities to manufacture entirely new types of physical materials and structures. These have varied and specific mechanical properties, which can be exploited in a number of engineering applications, and a growing area of research concerns the generation of two- and three-dimensional designs using these materials. However, the computational tools required to explore large spaces of possible 2-D and 3-D morphologies remain underdeveloped. State-of-the-art evolutionary approaches such as CPPN-NEAT and HyperNEAT-LEO are often used to explore possible 2-D and 3-D designs, but their ability to construct efficient solutions for practical use in engineering domains remains in question. In this paper, we present an extension of CPPN-NEAT, in which nodes grow connections across a dynamic substrate, and illustrate this by creating efficient 2-D truss structures. Using four benchmark problems, we then demonstrate that our extended CPPN-NEAT model outperforms similar HyperNEAT methods for approximating specific connectivity patterns, and suggests important clues regarding how to best harness generative and developmental representations to build scalable and high-performance physical morphologies.

We present a developmental genotype-phenotype growth process, or embryogeny, which is used to evolve, in silico, efficient three-dimensional structures that exhibit real-world architectural performance. The embryogeny defines a sequential assembly of architectural components within a three-dimensional volume, and indirectly establishes a regulatory network of components based on the principles of gene regulation. The implicitly regulated phenotypes suggest advances for the automatic design of physical structures, by improving scalability of the genotype encoding and embedding real-world constraints. We demonstrate that our model can evolve novel, yet efficient, architectural structures which exhibit emergent shape, topology and material distribution. Finally, we compare evolved structures against a "hand-coded" solution to illustrate that our model produces competitive results without prior knowledge of the design solution or direct human guidance.

We present an ant-based algorithm for spatially sorting objects into an annular structure. The model is minimal, as it requires only stochastic ant behaviour coupled with a pheromone-inspired “attraction-repulsion” mechanism. This is the first annular sorting algorithm to consider the problem of objects with non-uniform size, as well as the situation where objects are pre-sorted. The algorithm consistently generates high-quality annular structures, and is particularly powerful in situations where the initial configuration of objects is similar to those observed in nature. We suggest that this model provides a powerful algorithmic framework, as well as a contribution to the study of “attraction-repulsion” models of animal behaviour.

In this paper we present a new algorithm for the Layout Optimization Problem: this concerns the placement of circular, weighted objects inside a circular container, the two objectives being to minimize imbalance of mass and to minimize the radius of the container. This problem carries real practical significance in industrial applications (such as the design of satellites), as well as being of significant theoretical interest. We present a genetic algorithm solution and compare it with two existing nature-inspired methods, one of which is the best published algorithm for this problem. Experimental results show that our approach out-performs these existing methods in terms of both solution quality and execution time.

Complex natural processes may often be expressed in terms of networks of computational components, such as Boolean logic gates or artificial neurons. The interaction of biological molecules and the flow of information controlling the development and behaviour of organisms is particularly amenable to this approach, and these models are well established in the biological community. However, only relatively recently have papers appeared proposing the use of such systems to perform useful, human-defined tasks. Rather than merely using the network analogy as a convenient technique for clarifying our understanding of complex systems, it may now be possible to harness the power of such systems for the purposes of computation. We review several such proposals, focusing on the molecular implementation of fundamental computational elements.