Necessary conditions for density classification by cellular automata.

Classifying the initial configuration of a binary-state cellular automaton (CA) as to whether it contains a majority of 0s or 1s-the so-called density-classification problem-has been studied over the past decade by researchers wishing to glean an understanding of how locally interacting systems compute global properties. In this paper we prove two necessary conditions that a CA must satisfy in order to classify density: (1) the density of the initial configuration must be conserved over time, and (2) the rule table must exhibit a density of 0.5.

Evolutionary computation in medicine: an overview.

The term evolutionary computation encompasses a host of methodologies inspired by natural evolution that are used to solve hard problems. This paper provides an overview of evolutionary computation as applied to problems in the medical domains. We begin by outlining the basic workings of six types of evolutionary algorithms: genetic algorithms, genetic programming, evolution strategies, evolutionary programming, classifier systems, and hybrid systems. We then describe how evolutionary algorithms are applied to solve medical problems, including diagnosis, prognosis, imaging, signal processing, planning, and scheduling. Finally, we provide an extensive bibliography, classified both according to the medical task addressed and according to the evolutionary technique used.

A fuzzy-genetic approach to breast cancer diagnosis.

The automatic diagnosis of breast cancer is an important, real-world medical problem. In this paper we focus on the Wisconsin breast cancer diagnosis (WBCD) problem, combining two methodologies-fuzzy systems and evolutionary algorithms-so as to automatically produce diagnostic systems. We find that our fuzzy-genetic approach produces systems exhibiting two prime characteristics: first, they attain high classification performance (the best shown to date), with the possibility of attributing a confidence measure to the output diagnosis; second, the resulting systems involve a few simple rules, and are therefore (human-) interpretable.

Embryonic electronics.

Within the general domain of bio-inspired computing, a particular trend over the past few years has been that of constructing actual hardware devices that are inspired by nature. This paper describes one such project-Embryonics (embryonic electronics)-inspired in particular by the process of embryogenesis. Our ultimate objective is the construction of large-scale integrated circuits, exhibiting the properties of self-repair (healing) and self-replication, found until now only in living beings. We present the silicon-based artificial cell, followed by a description of mechanisms operating at the cellular level: cellular differentiation, cellular division, regeneration, and replication. We then present the cell's composition as an ensemble of lower-level elements, known as 'molecules'. As electronic chips grow evermore complex, the need for self-repair capabilities will become increasingly crucial. The Embryonics approach represents one possible way of confronting this pivotal problem.

A statistical study of a class of cellular evolutionary algorithms.

Parallel evolutionary algorithms, over the past few years, have proven empirically worthwhile, but there seems to be a lack of understanding of their workings. In this paper we concentrate on cellular (fine-grained) models, our objectives being: (1) to introduce a suite of statistical measures, both at the genotypic and phenotypic levels, which are useful for analyzing the workings of cellular evolutionary algorithms; and (2) to demonstrate the application and utility of these measures on a specific example-the cellular programming evolutionary algorithm. The latter is used to evolve solutions to three distinct (hard) problems in the cellular-automata domain: density, synchronization, and random number generation. Applying our statistical measures, we are able to identify a number of trends common to all three problems (which may represent intrinsic properties of the algorithm itself), as well as a host of problem-specific features. We find that the evolutionary algorithm tends to undergo a number of phases which we are able to quantitatively delimit. The results obtained lead us to believe that the measures presented herein may prove useful in the general case of analyzing fine-grained evolutionary algorithms.

Design, observation, surprise! A test of emergence.

The field of artificial life (Alife) is replete with documented instances of emergence, though debate still persists as to the meaning of this term. We contend that, in the absence of an acceptable definition, researchers in the field would be well served by adopting an emergence certification mark that would garner approval from the Alife community. Toward this end, we propose an emergence test, namely, criteria by which one can justify conferring the emergence label.

Von Neumann's quintessential message: genotype + ribotype = phenotype.

In this short article, we argue that von Neumann's quintessential message with respect to self-replicating automata is genotype + ribotype = phenotype. Self-replication occurs in analogy to nature: The description (genotype) written on the input tape is translated via a ribosome (ribotype) so as to create the offspring universal constructor (phenotype).

Fifty years of research on self-replication: an overview.

The study of self-replicating structures or machines has been taking place now for almost half a century. My goal in this article is to present an overview of research carried out in the domain of self-replication over the past 50 years, starting from von Neumann's work in the late 1940s and continuing to the most recent research efforts. I shall concentrate on computational models, that is, ones that have been studied from a computer science point of view, be it theoretical or experimental. The systems are divided into four major classes, according to the model on which they are based: cellular automata, computer programs, strings (or strands), or an altogether different approach. With the advent of new materials, such as synthetic molecules and nanomachines, it is quite possible that we shall see this somewhat theoretical domain of study producing practical, real-world applications.

Ontogenetic hardware.

Ontogeny is the process by which a single mother cell, the zygote, gives rise, through successive divisions, to a complete organism, possibly containing trillions of cells (e.g. in humans). This paper describes research whose inspiration is drawn from the process of ontogenetic development. By adopting certain features of cellular organization, and by transposing them to the world of integrated circuits on silicon, we show that certain properties unique to the living world, such as self-replication, self-repair, and growth, can also be attained in artificial objects (integrated circuits). Specifically, we identify and describe three classes of ontogenetic hardware: (1) self-replicating hardware; (2) embryonic hardware; and (3) L-systems based hardware, dubbed L-hardware. For each class we present an example of a hardware realization, along with a discussion of possible applications. Continued research on ontogenetic hardware may yield novel bio-inspired systems endowed with replicative, growth, and regenerative capabilities.

The evolution of parallel cellular machines: toward evolware.

The historical idea of evolving machines has recently resurfaced as the nascent field of bio-inspired systems and evolvable hardware. This paper describes the cellular programming approach used to evolve parallel cellular machines, presenting its application to six computational problems: density, synchronization, ordering, boundary computation, thinning and random number generation. Our results show that successful machines can be evolved to solve these tasks. The methodology described herein represents one possible approach to attaining truly evolving ware, evolware, with current implementations centering on hardware, while raising the possibility of using other forms in the future, such as bioware. The paper presents work in progress, the aim being to give an account of results obtained to date, ending with a list of several open issues for future research.

A single-iteration threshold Hamming network.

We analyze in detail the performance of a Hamming network classifying inputs that are distorted versions of one of its m stored memory patterns, each being a binary vector of length n. It is shown that the activation function of the memory neurons in the original Hamming network may be replaced by a simple threshold function. By judiciously determining the threshold value, the "winner-take-all" subnet of the Hamming network (known to be the essential factor determining the time complexity of the network's computation) may be altogether discarded. For m growing exponentially in n, the resulting threshold Hamming network correctly classifies the input pattern in a single iteration, with probability approaching 1.