Life‐like self‐reproducers

In order to understand the interplay among information, genetic instructions, and phenotypic variations, self‐reproducers discovered in two‐dimensional cellular automata are considered as proto‐organisms, which undergo to mutations as they were in a real environmental situation. We realized a computational model through which we have been able to discover the genetic map of the self‐reproducers and the networks they use. Identifying in these maps sets of different functional genes, we found that mutations in the genetic sequences could affect both external shapes and behavior of the self‐reproducers, thus realizing different life‐like strategies in the evolution process. The results highlight that some strategies evolution uses in selecting organisms that are fitting with changing environmental situations maintain the self‐reproducing function, whereas other variations create new self‐reproducers. These self‐reproducers in turn realize different genetic networks, which can be very different from the basic ancestors pools. The mutations that are disruptive bring self‐reproducers to disappear, while other proto‐organisms are generated. © 2004 Wiley Periodicals, Inc. Complexity 9: 38–55, 2004     

Population structure increases the evolvability of genetic algorithms

Populations are shaped by the spatial structure of their environment: space organizes interactions between individuals locally, and gives rise to a global population structure. Both local and global population structures can have a profound influence on the evolutionary dynamics of a population. To characterize this influence, we use genetic algorithms with several distinct contact structures to evolve cellular automata, which perform a density classification task. We find that local contact structures (modeled as graphs with various topologies) that limit the number of breeding partners show greater evolvability than well‐mixed populations. Furthermore, we show that the evolvability of well‐mixed populations is enhanced in a metapopulation setting of coupled subpopulations. © 2012 Wiley Periodicals, Inc. Complexity, 2012     

The emergence of dynamical complexity: An exploration using elementary cellular automata

This work concerns the interaction between two classical problems: the forecasting of the dynamical behaviors of elementary cellular automata (ECA) from its intrinsic mathematical laws and the conditions that determine the emergence of complex dynamics. To approach these problems, and inspired by the theory of reversible logical gates, we decompose the ECA laws in a “spectrum” of dyadic Boolean gates. Emergent properties due to interactions are captured generating another spectrum of logical gates. The combined analysis of both spectra shows the existence of characteristic bias in the distribution of Boolean gates for ECA belonging to different dynamical classes. These results suggest the existence of signatures capable to indicate the propensity to develop complex dynamics. Logical gates “exclusive‐or” and “equivalence” are among these signatures of complexity. An important conclusion is that within ECA space, interactions are not capable to generate signatures of complexity in the case these signatures are absent in the intrinsic law of the automaton. © 2004 Wiley Periodicals, Inc. Complexity 9: 33–42, 2004     

How to make dull cellular automata complex by adding memory: Rule 126 case study

Using Rule 126 elementary cellular automaton (ECA), we demonstrate that a chaotic discrete system — when enriched with memory — hence exhibits complex dynamics where such space exploits on an ample universe of periodic patterns induced from original information of the ahistorical system. First, we analyze classic ECA Rule 126 to identify basic characteristics with mean field theory, basins, and de Bruijn diagrams. To derive this complex dynamics, we use a kind of memory on Rule 126; from here interactions between gliders are studied for detecting stationary patterns, glider guns, and simulating specific simple computable functions produced by glider collisions. © 2010 Wiley Periodicals, Inc. Complexity, 2010     

Classifying cellular automata automatically: Finding gliders,filtering, and relating space‐time patterns,attractor basins,and the Z parameter

Cellular automata (CA) rules can be classified automatically for a spectrum of ordered, complex, and chaotic dynamics by a measure of the variance of input‐entropy over time. Rules that support interacting gliders and related complex dynamics can be identified, giving an unlimited source for further study. The distribution of rule classes in rule‐space can be shown. A byproduct of the method allows the automatic “filtering” of CA space‐time patterns to show up gliders and related emergent configurations more clearly. The classification seems to correspond to our subjective judgment of space‐time dynamics. There are also approximate correlations with global measures on convergence in attractor basins, characterized by the distribution of in‐degree sizes in their branching structure, and to the rule parameter, Z. Based on computer experiments using the software Discrete Dynamics Lab (DDLab), this article explains the methods and presents results for 1D CA. © 1999 John Wiley & Sons, Inc.     

Some applications of propositional logic to cellular automata

In this paper we give a new proof of Richardson's theorem [31]: a global function G_?? of a cellular automaton ?? is injective if and only if the inverse of G_?? is a global function of a cellular automaton. Moreover, we show a way how to construct the inverse cellular automaton using the method of feasible interpolation from [20]. We also solve two problems regarding complexity of cellular automata formulated by Durand [12] (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Are complex systems hard to evolve?

Evolutionary complexity is measured here by the number of trials/evaluations needed for evolving a logical gate in a nonlinear medium. Behavioral complexity of the gates evolved is characterized in terms of cellular automata behavior. We speculate that hierarchies of behavioral and evolutionary complexities are isomorphic up to some degree, subject to substrate specificity of evolution, and the spectrum of evolution parameters. © 2009 Wiley Periodicals, Inc. Complexity, 2009     

Searching for extensible Korobov rules

Extensible lattice sequences have been proposed and studied in [F.J. Hickernell, H.S. Hong, Computing multivariate normal probabilities using rank-1 lattice sequences, in: G.H. Golub, S.H. Lui, F.T. Luk, R.J. Plemmons (Eds.), Proceedings of the Workshop on Scientific Computing (Hong Kong), Singapore, Springer, Berlin, 1997, pp. 209–215; F.J. Hickernell, H.S. Hong, P. L’Ecuyer, C. Lemieux, Extensible lattice sequences for quasi-Monte Carlo quadrature, SIAM J. Sci. Comput. 22 (2001) 1117–1138; F.J. Hickernell, H.Niederreiter, The existence of good extensible rank-1 lattices, J. Complexity 19 (2003) 286–300]. For the special case of extensible Korobov sequences, parameters can be found in [F.J. Hickernell, H.S. Hong, P. L’Ecuyer, C.Lemieux, Extensible lattice sequences for quasi-Monte Carlo quadrature, SIAM J. Sci. Comput. 22 (2001) 1117–1138]. The searches made to obtain these parameters were based on quality measures that look at several projections of the lattice. Because it is often the case in practice that low-dimensional projections are very important, it is of interest to find parameters for these sequences based on measures that look more closely at these projections. In this paper, we prove the existence of “good” extensible Korobov rules with respect to a quality measure that considers two-dimensional projections. We also report results of experiments made on different problems where the newly obtained parameters compare favorably with those given in [F.J. Hickernell, H.S. Hong, P. L’Ecuyer, C. Lemieux, Extensible lattice sequences for quasi-Monte Carlo quadrature, SIAM J. Sci. Comput. 22 (2001) 1117–1138].     

The EvCA project: A brief history

This article presents a brief history of the Evolving Cellular Automata (EvCA) project. In the EvCA project, a genetic algorithm was used to evolve cellular automata to perform certain (nontrivial) computational tasks, in an effort to gain more insight into the question: “How does evolution produce sophisticated emergent computation in systems composed of simple components limited to local interactions?” Next to providing many interesting results and useful insights, the EvCA project seems to have spawned a whole research area of its own. Here, a brief overview is given of how it all started, developed, and inspired further work. © 2013 Wiley Periodicals, Inc. Complexity 18: 15–19, 2013     

Discrete threshold growth dynamics are omnivorous for box neighborhoods

In the discrete threshold model for crystal growth in the plane we begin with some set of seed crystals and observe crystal growth over time by generating a sequence of subsets of by a deterministic rule. This rule is as follows: a site crystallizes when a threshold number of crystallized points appear in the site's prescribed neighborhood. The growth dynamics generated by this model are said to be omnivorous if finite and imply . In this paper we prove that the dynamics are omnivorous when the neighborhood is a box (i.e. when, for some fixed , the neighborhood of is . This result has important implications in the study of the first passage time when is chosen randomly with a sparse Bernoulli density and in the study of the limiting shape to which converges.

     

制度下行为模拟的Agent与CA方法比较研究

在对CAS理论研究的基础上,分析了基于其理论框架下相对成熟且应用较为广泛的两种行为模拟模型或方法(即智能体和元胞自动机),并对它们的优缺点及适用领域进行了比较,对其发展趋势和前景进行了展望.     

Reversible cellular automata with memory of delay type

The effect of delay type memory of past states on reversible elementary cellular automata (CA) is examined in this study. It is assessed in simple scenarios, such as elementary CA, but the feasibility of enriching the dynamics with memory in a general reversible CA context is also outlined. © 2014 Wiley Periodicals, Inc. Complexity 20: 49–56, 2014     

The Container Transshipment Problem: Searching Representation Landscapes with Metaheuristic Algorithms

The container transshipment problem involves scheduling a fleet of lorries to collect and deliver containers of various sizes while minimizing the total distance travelled. The problem originates in the need for logistics companies to solve the problem on a regular basis as part of their daily operations. In this paper, we compare two genetic algorithms tailored to solve this problem based on permutation and bin-packing inspired encodings. Results are presented and analysed in order to evaluate the validity and robustness of the two approaches. As part of the analysis, bounds were calculated to determine how well both GAs perform in absolute terms as well as relative to each other. Of the two GA there is one clear winner, although it is not the one that would have been indicated by previous research. Whilst the winning GA is able to generate significant savings in practice, compared to the optimum there remains room for further improvement.     

Emergent behavior in two complex cellular automata rule sets

Cellular automata systems often produce complex behavior from simple rule sets. The behaviors and results of two complex combinations of cellular automata rules are analyzed. Both two‐dimensional rule sets add complexities to typical cellular automata systems by attaching attributes and rules to each cell. One of the rule sets produces gliders that reproduce upon collision, whereas the other grows into an intricate shape. Projection and entropy analysis classify the rule sets as complex for the intricate shape, but measurements indicate that the self‐reproducing gliders fall between ordered and complex classification, despite their complex appearance. © 2005 Wiley Periodicals, Inc. Complexity 10: 45–55, 2005     

The advantage of complexity in two 2 × 2 games

Competing populations of finite automata co‐evolve in an evolutionary algorithm to play two player games. Populations endowed with greater complexity do better against their less complex opponents in a strictly competitive constant sum game. In contrast, complexity determines efficiency levels, but not relative earnings, in a Prisoner's Dilemma game; greater levels of complexity result in mutually higher earnings. With reporting noise, advantages to complexity are lost and efficiency levels are reduced as relatively less complex strategies are selected. © 2004 Wiley Periodicals, Inc. Complexity 9: 71–78, 2004     

Selecting informative rules with parallel genetic algorithm in classification problem

The classification system is very important for making decision and it has been attracted much attention of many researchers. Usually, the traditional classifiers are either domain specific or produce unsatisfactory results over classification problems with larger size and imbalanced data. Hence, genetic algorithms (GA) are recently being combined with traditional classifiers to find useful knowledge for making decision. Although, the main concerns of such GA-based system are the coverage of less search space and increase of computational cost with the growth of population. In this paper, a rule-based knowledge discovery model, combining C4.5 (a Decision Tree based rule inductive algorithm) and a new parallel genetic algorithm based on the idea of massive parallelism, is introduced. The prime goal of the model is to produce a compact set of informative rules from any kind of classification problem. More specifically, the proposed model receives a base method C4.5 to generate rules which are then refined by our proposed parallel GA. The strength of the developed system has been compared with pure C4.5 as well as the hybrid system (C4.5 + sequential genetic algorithm) on six real world benchmark data sets collected from UCI (University of California at Irvine) machine learning repository. Experiments on data sets validate the effectiveness of the new model. The presented results especially indicate that the model is powerful for volumetric data set.     

Further Algebraic Results in the Theory of Balance

In an article published in 1970 in the French journal Mathématiques et Sciences Humaines , Flament described a number of mathematical results pertaining to an algebraic formulation of the theory of balance in signed graphs. This paper describes some additional results based on those discussed by Flament. These newer results are especially useful for the development of algorithms for calculating the line index of balance in the study of specific networks arising in psychological and sociological research.     

A Cellular Genetic Algorithm with Disturbances: Optimisation Using Dynamic Spatial Interactions

This paper describes a novel evolutionary algorithm inspired by the nature of spatial interactions in ecological systems. The Cellular Genetic Algorithm with Disturbances (CGAD) can be seen as a hybrid between a fine-grained and a coarse-grained parallel genetic algorithm. The introduction of a disturbance-colonisation cycle provides a mechanism for maintaining flexible subpopulation sizes and self-adaptive controls on migration. Experiments conducted, using a range of stationary and non-stationary optimisation problems, show how changes in the structure of the environment can lead to changes in selective pressure, population diversity and subsequently solution quality. The significance of the disturbance events lies in the new ecological patterns that arise during the recovery phase.     

Decentralized Interaction and Co-Adaptation in the Repeated Prisoner&2018;s Dilemma

A Prisoner&2018;s dilemma that is repeated indefinitely has many equilibria; the problem of selecting among these is often approached using evolutionary models. The background of this paper is a number of earlier studies in which a specific type of evolutionary model, a genetic algorithm (GA), was used to investigate which behavior survives under selective pressure. However, that normative instrument searches for equilibria that may never be attainable. Furthermore, it aims for optimization and, accordingly, says what people should do to be successful in repeated prisoner&2018;s dilemma (RPD) type situations. In the current paper, I employ simulation to find out what people would do, whether this makes them successful or not. Using a replication of Miller&2018;s (1988) GA study for comparison, a model is simulated in which the population is spatially distributed across a torus. The agents only interact with their neighbors and locally adapt their strategy to what they perceive to be successful behavior among those neighbors. Although centralized GA-evolution may lead to somewhat better performance, this goes at the cost of a large increase in required computations while a population with decentralized interactions and co-adaptation is almost as successful and, additionally, endogenously learns a more efficient scheme for adaptation. Finally, when the agents&2018; perceptive capabilities are limited even further, so that they can only perceive how their neighbors are doing against themselves, rather than against all those neighbors&2018; opponents&2014;which essentially removes reputation as a source of information&2014;cooperation breaks down.     

Complex genetic evolution of artificial self‐replicators in cellular automata

It is widely believed that evolutionary dynamics of artificial self‐replicators realized in cellular automata (CA) are limited in diversity and adaptation. Contrary to this view, we show that complex genetic evolution may occur within simple CA. The evolving self‐replicating loops (“evoloops”) we investigate exhibit significant diversity in macro‐scale morphologies and mutational biases, undergoing nontrivial genetic adaptation by maximizing colony density and enhancing sustainability against other species. Nonmutable subsequences enable genetic operations that alter fitness differentials and promote long‐term evolutionary exploration. These results demonstrate a unique example of genetic evolution hierarchically emerging from local interactions between elements much smaller than individual replicators. © 2004 Wiley Periodicals, Inc. Complexity 10: 33–39, 2004