Advances in Complex Systems

This special journal issue of Advances in Complex Systems presents a collection of papers describing current research delivered by recognized researchers actively working in various corners of the field of modeling of complex systems by cellular automata and related methods. All included papers are self-contained and present the latest developments in the areas where the authors work. Hence, all papers can be read independently, but it is strongly recommended to study the issue as a whole to get a general overview of the various methods and techniques from the field. The main aim of this special issue is to provide researchers from neighboring fields with sufficient information and vital examples of how to design models in complex systems. The whole issue is organized in such a way that common features occurring repeatedly in most models of complex systems are highlighted.

Drawing inspiration from social interactions in nature, the field of swarm intelligence has presented a promising approach to the design of complex systems consisting of numerous, usually homogeneous, simple parts, to solve a wide variety of problems. Like cellular automata, swarm-intelligence systems involve highly parallel computations across space, based heavily on self-organization, the emergence of global behavior through local interactions of components, and the absence of centralized or global control. However, this has a disadvantage as the desired behavior of a system becomes hard to predict or design based on its local interaction rules. In our ongoing research, we propose to provide greater control over a system, and potentially more useful, goal-oriented behavior, by introducing layered, hierarchical controllers in the particles or components. The layered controllers allow each particle to extend their reactive behavior in a more goal-oriented style, while keeping the locality of the interactions and the general simplicity of the system. In this paper, we present three systems designed using this approach: a competitive foraging system, a system for the collective transport and distribution of goods, and a self-assembly system capable of creating complex structures in a 3D world. Our simulation results show that in all three cases it was possible to guide the self-organization process at different levels of the designated task, suggesting that the self-organizing behavior of swarm-intelligence systems may be extendable to support problem solving in various contexts, such as coordinated robotic teams.

We examine a strong chess-endgame player, previously developed by us through genetic programming, focusing on the player's emergent capabilities and tactics in the context of a chess match. First, we provide a detailed description of the evolutionary approach by which our player was developed. Then, using a number of methods we analyze the evolved player's building blocks and their effect on play level. We conclude that evolution has found combinations of building blocks that are far from trivial and cannot be explained through simple combination — thereby indicating the possible emergence of complex strategies.

We recently formulated an approach to representing structures in cellular automata (CA) spaces, and the rules that govern cell state changes, that is amenable to manipulation by genetic programming (GP). Using this approach, it is possible to efficiently generate self-replicating configurations for fairly arbitrary initial structures. Here, we investigate the properties of self-replicating systems produced using GP in this fashion as the initial configuration's size, shape, symmetry, allowable states, and other factors are systematically varied. We find that the number of GP generations, computation time, and number of resulting rules required by an arbitrary structure to self-replicate are positively and jointly correlated with the number of components, configuration shape, and allowable states in the initial configuration, but inversely correlated with the presence of repeated components, repeated sub-structures, and/or symmetric sub-structures. We conclude that GP can be used as a "replicator factory" to produce a wide range of self-replicating CA configurations, and that the properties of the resulting replicators can be predicted in part a priori. The rules controlling self-replication that are created by GP generally differ from those created manually in past CA studies.

We investigate the performances of collective task-solving capabilities and the robustness of complex networks of automata using the density and synchronization problems as typical cases. We show by computer simulations that evolved Watts–Strogatz small-world networks have superior performance with respect to several kinds of scale-free graphs. In addition, we show that Watts–Strogatz networks are as robust in the face of random perturbations, both transient and permanent, as configuration scale-free networks, while being widely superior to Barabási–Albert networks. This result differs from information diffusion on scale-free networks, where random faults are highly tolerated by similar topologies.

This paper deals with a special kind of complex systems which depend on an arbitrary (and usually large) number n of random Boolean variables. The so-called complex stochastic Boolean systems often appear in many different scientific, technical or social areas. Clearly, there are 2ⁿ binary states associated to such a complex system. Each one of them is given by a binary string u = (u₁,…,u_n) ∈ {0, 1}ⁿ of n bits, which has a certain occurrence probability Pr{u}. The behavior of a complex stochastic Boolean system is determined by the current values of its 2ⁿ binary n-tuple probabilities Pr{u} and by the ordering between pairs of them. Hence, the intrinsic order graph provides a useful representation of these systems by displaying (scaling) the 2ⁿ binary n-tuples which are ordered in decreasing probability of occurrence. The intrinsic order reduces the complexity of the problem from exponential (2ⁿ binary n-tuples) to linear (n Boolean variables). For any fixed binary n-tuple u, this paper presents a new, simple algorithm enabling rapid, elegant determination of all the binary n-tuples v with occurrence probabilities less than or equal to (greater than or equal to) Pr{u}. This algorithm is closely related to the lexicographic (truth-table) order in {0, 1}ⁿ, and this is illustrated through the connections (paths) in the intrinsic order graph.

This paper studies asynchronously-updated linear voter cellular automata models, with local and global interactions. In the locally-interacting model, sites copy the states of randomly-chosen sites in the local neighborhood; in the globally-interacting model, sites copy the states of sites chosen at random from the entire lattice. A multiscale model is also considered, mixing the two types of interactions. Such models can be used to model simple genetic drift, or the spread of opinions or ideas. The pair approximation moment-closure method is used to develop systems of differential equations describing the dynamics of the models with k states per site; stochastic spatially explicit simulations are also used. In simulations on large lattices, state frequencies among sites remain relatively constant at their initial values, while autocorrelations between adjacent sites move toward quasiequilibrium distributions and then remain constant with minor stochastic fluctuations. Full analytical solutions for the transient dynamics of the local autocorrelation (clustering) among adjacent sites are obtained with k = 2 states, and compared with simulations. Both show that increasing global interactions decreases spatial autocorrelation, and that even in the absence of long-distance interaction, there will still be mixing among the states. That is, the lattice will not converge to a quasiequilibrium configuration where regions in different states are maximally isolated from each other (completely segregated), but instead sites will have a strictly positive probability of being adjacent to sites in different states.

Firstly, the application of a cellular automata (CA) model to simulate the dynamics of lasers is reviewed. With this kind of model, the macroscopic properties of the laser system emerge as a cooperative phenomenon from elementary components locally interacting under simple rules. Secondly, a parallel implementation of this kind of model for distributed-memory parallel computers is presented. Performance and scalability of this parallel implementation running on a computer cluster are analyzed, giving very satisfactory results. This confirms the feasibility of running large 3D simulations — unaffordable on an individual machine — on computer clusters, in order to simulate specific real laser systems.

The particle swarm algorithm uses principles derived from social psychology to find optimal points in a search space. The present paper decomposes and reinterprets the particle swarm in order to discover new ways of implementing the algorithm. Some essential characteristics of the method are illuminated, and some inessential features are discarded. Various new forms are tested and found to perform well on a suite of test functions. In particular, it is shown that the traditional trajectory formulas can be replaced with random number generators sampling from various symmetrical probability distributions. The excellent performance of these new versions demonstrates that the strength of the algorithm is in the interactions of the particles, rather than in their behavior as individuals.