Emergence and Adaptation

I investigate the relationship between adaptation, as defined in evolutionary theory through natural selection, and the concept of emergence. I argue that there is an essential correlation between the former, and “emergence” defined in the field of algorithmic simulations. I first show that the computational concept of emergence (in terms of incompressible simulation) can be correlated with a causal criterion of emergence (in terms of the specificity of the explanation of global patterns). On this ground, I argue that emergence in general involves some sort of selective processes. Finally, I show that a second criterion, concerning novel explanatory regularities following the emergence of a pattern, captures the robustness of emergence displayed by some cases of emergence (according to the first criterion). Emergent processes fulfilling both criteria are therefore exemplified in evolutionary biology by some so-called “innovations”, and mostly by the new units of fitness or new kinds of adaptations (like sexual reproduction, multicellular organisms, cells, societies) sometimes called “major transitions in evolution”, that recent research programs (Maynard-Smith and Szathmary 1995; Michod 1999) aims at explaining.

Combating I-O bottleneck using prefetching: model,algorithms, and ramifications

Multiple memory models have been proposed to capture the effects of memory hierarchy culminating in the I-O model of Aggarwal and Vitter (Commun. ACM 31(9):1116–1127, [1988]). More than a decade of architectural advancements have led to new features that are not captured in the I-O model—most notably the prefetching capability. We propose a relatively simple Prefetch model that incorporates data prefetching in the traditional I-O models and show how to design optimal algorithms that can attain close to peak memory bandwidth. Unlike (the inverse of) memory latency, the memory bandwidth is much closer to the processing speed, thereby, intelligent use of prefetching can considerably mitigate the I-O bottleneck. For some fundamental problems, our algorithms attain running times approaching that of the idealized random access machines under reasonable assumptions. Our work also explains more precisely the significantly superior performance of the I-O efficient algorithms in systems that support prefetching compared to ones that do not.

Supporting scenario evolution

Scenarios have been shown to be very helpful in identifying and communicating requirements for computer-based systems (CBSs). However, they appear not to be applicable to the rest of the CBS development process. Making scenarios more useful for the entire software development lifecycle requires integrating scenarios to other representations used during CBS development. This integration is achieved with tracing technology. Having integrated scenarios into the entire software development lifecycle creates the necessity to maintain scenarios through the inevitable changes that they and other documents undergo and to subject them to configuration management. We have prototyped automated support for full-lifecycle scenario management and have applied it to some non-trivial systems.This paper is an amalgamation and extension of the conference papers numbered 8, 9, 10, and 11 in the bibliography of this paper.

---

Evolving strategy for a probabilistic game of imperfect information using genetic programming

We provide the complete record of methodology that let us evolve BrilliAnt, the winner of the Ant Wars contest. Ant Wars contestants are virtual ants collecting food on a grid board in the presence of a competing ant. BrilliAnt has been evolved through a competitive one-population coevolution using genetic programming and fitnessless selection. In this paper, we detail the evolutionary setup that lead to BrilliAnt’s emergence, assess its direct and indirect human-competitiveness, and describe the behavioral patterns observed in its strategy.

---

Invariant Signatures of Closed Planar Curves

We prove that any subset of ℝ² parametrized by a C ¹ periodic function and its derivative is the Euclidean invariant signature of a closed planar curve. This solves a problem posed by Calabi et al. (Int. J. Comput. Vis. 26:107–135, 1998). Based on the proof of this result, we then develop some cautionary examples concerning the application of signature curves for object recognition and symmetry detection as proposed by Calabi et al.

Numerical study on gas–liquid nano-flows with pseudo-particle modeling and soft-particle molecular dynamics simulation

We couple pseudo-particle modeling (PPM, Ge and Li in Chem Eng Sci 58(8):1565–1585, 2003), a variant of hard-particle molecular dynamics, with standard soft-particle molecular dynamics (MD) to study an idealized gas–liquid flow in nano-channels. The coupling helps to keep sharp contrast between gas and liquid behaviors and the simulations conducted provide a reference frame for exploring more complex and realistic gas–liquid nano-flows. The qualitative nature and general flow patterns of the flow under such extreme conditions are found to be consistent with its macro-scale counterpart.

Reader-based exploration of lexical cohesion

Lexical cohesion refers to the reader-perceived unity of text achieved by the author’s usage of words with related meanings (Halliday and Hasan, 1976). This article reports on an experiment with 22 readers aimed at finding lexical cohesive patterns in 10 texts. Although there was much diversity in peoples’ answers, we identified a common core of the phenomenon, using statistical analysis of agreement patterns and a validation experiment. The core data may now be used as a minimal test set for models of lexical cohesion; we present an example suggesting that models based on mutually exclusive lexical chains will not suffice. In addition, we believe that procedures for revealing and analyzing sub-group patterns of agreement described here may be applied to data collected in other studies of comparable size.

Reader-based exploration of lexical cohesion

Lexical cohesion refers to the reader-perceived unity of text achieved by the author’s usage of words with related meanings (Halliday and Hasan, 1976). This article reports on an experiment with 22 readers aimed at finding lexical cohesive patterns in 10 texts. Although there was much diversity in peoples’ answers, we identified a common core of the phenomenon, using statistical analysis of agreement patterns and a validation experiment. The core data may now be used as a minimal test set for models of lexical cohesion; we present an example suggesting that models based on mutually exclusive lexical chains will not suffice. In addition, we believe that procedures for revealing and analyzing sub-group patterns of agreement described here may be applied to data collected in other studies of comparable size.

An Improved LOT Model for Image Restoration

Some second order PDE-based image restoration models such as total variation (TV) minimization or ROF model of Rudin et al. (Physica D 60, 259–268, 1992) can easily give rise to staircase effect, which may produce undesirable blocky image. LOT model proposed by Laysker, Osher and Tai (IEEE Trans. Image Process. 13(10), 1345–1357, 2004) has alleviated the staircase effect successfully, but the algorithms are complicated due to three nonlinear second-order PDEs to be computed, besides, when we have no information about the noise, the model cannot preserve edges or textures well. In this paper, we propose an improved LOT model for image restoration. First, we smooth the angle θ rather than the unit normal vector n, where n=(cos θ,sin θ). Second, we add an edge indicator function in order to preserve fine structures such as edges and textures well. And then the dual formulation of TV-norm and TV _g -norm are used in the numerical algorithms. Finally, some numerical experiments prove our proposed model and algorithms to be effective.

The 2007 IEEE CEC simulated car racing competition

This paper describes the simulated car racing competition that was arranged as part of the 2007 IEEE Congress on Evolutionary Computation. Both the game that was used as the domain for the competition, the controllers submitted as entries to the competition and its results are presented. With this paper, we hope to provide some insight into the efficacy of various computational intelligence methods on a well-defined game task, as well as an example of one way of running a competition. In the process, we provide a set of reference results for those who wish to use the simplerace game to benchmark their own algorithms. The paper is co-authored by the organizers and participants of the competition.

---

Interacting with mobile services: an evaluation of camera-phones and visual tags

We present a study of using camera-phones and visual-tags to access mobile services. Firstly, a user-experience study is described in which participants were both observed learning to interact with a prototype mobile service and interviewed about their experiences. Secondly, a pointing-device task is presented in which quantitative data was gathered regarding the speed and accuracy with which participants aimed and clicked on visual-tags using camera-phones. We found that participants’ attitudes to visual-tag-based applications were broadly positive, although they had several important reservations about camera-phone technology more generally. Data from our pointing-device task demonstrated that novice users were able to aim and click on visual-tags quickly (well under 3 s per pointing-device trial on average) and accurately (almost all meeting our defined speed/accuracy tradeoff of 6% error-rate). Based on our findings, design lessons for camera-phone and visual-tag applications are presented.

---

Ethical regulations on robotics in Europe

There are only a few ethical regulations that deal explicitly with robots, in contrast to a vast number of regulations, which may be applied. We will focus on ethical issues with regard to “responsibility and autonomous robots”, “machines as a replacement for humans”, and “tele-presence”. Furthermore we will examine examples from special fields of application (medicine and healthcare, armed forces, and entertainment). We do not claim to present a complete list of ethical issue nor of regulations in the field of robotics, but we will demonstrate that there are legal challenges with regard to these issues.

---

Approximate schemas,source-consistency and query answering

We use the Edit distance with Moves on words and trees and say that two regular (tree) languages are ε-close if every word (tree) of one language is ε-close to the other. A transducer model is introduced to compare tree languages (schemas) with different alphabets and attributes. Using the statistical embedding of Fischer et al. (Proceedings of 21st IEEE Symposium on Logic in Computer Science, pp. 421–430, 2006), we show that Source-Consistency and Approximate Query Answering are testable on words and trees, i.e. can be approximately decided within ε by only looking at a constant fraction of the input.

Discrete Dynamical System Framework for Construction of Connections between Critical Regions in Lattice Height Data

We define a new mathematical model for the topological study of lattice height data. A discrete multivalued dynamical system framework is used to establish discrete analogies of a Morse function, its gradient field, and its stable and unstable manifolds in order to interpret functions numerically given on finite sets of pixels. We present efficient algorithms detecting critical components of a height function f and displaying connections between them by means of a graph, called the Morse connections graph whose nodes represent the critical components of f and edges show the existence of connecting trajectories between nodes. This graph encodes efficiently the topological structure of the data and makes it easy to manipulate for subsequent processing.

A software tool for verification of Spiking Neural P Systems

The formal verification of a Spiking Neural P System (SN P Systems, for short) designed for solving a given problem is usually a hard task. Basically, the verification process consists of the search of invariant formulae such that, once proved their validity, show the right answer to the problem. Even though there does not exist a general methodology for verifying SN P Systems, in (Păun et al., Int J Found Comput Sci 17(4):975–1002, 2006) a new tool based on the transition diagram of the P system has been developed for helping the researcher in the search of invariant formulae. In this paper we show a software tool which allows to generate the transition diagram of an SN P System in an automatic way, so it can be considered as an assistant for the formal verification of such computational devices.

Inverse multi-objective robust evolutionary design

In this paper, we present an Inverse Multi-Objective Robust Evolutionary (IMORE) design methodology that handles the presence of uncertainty without making assumptions about the uncertainty structure. We model the clustering of uncertain events in families of nested sets using a multi-level optimization search. To reduce the high computational costs of the proposed methodology we proposed schemes for (1) adapting the step-size in estimating the uncertainty, and (2) trimming down the number of calls to the objective function in the nested search. Both offline and online adaptation strategies are considered in conjunction with the IMORE design algorithm. Design of Experiments (DOE) approaches further reduce the number of objective function calls in the online adaptive IMORE algorithm. Empirical studies conducted on a series of test functions having diverse complexities show that the proposed algorithms converge to a set of Pareto-optimal design solutions with non-dominated nominal and robustness performances efficiently.

---

Comparative analysis of simple facial features extractors

In the article a certain class of feature extractors for face recognition is presented. The extraction is based on simple approaches: image scaling with pixel concatenation into a feature vector, selection of a small number of points from the face area, face image’s spectrum, and finally pixel intensities histogram. The experiments performed on several facial image databases (BioID [4], ORL face database [27], FERET [30]) show that face recognition using this class of extractors is particularly efficient and fast, and can have straightforward implementations in software and hardware systems. They can also be used in fast face recognition system involving feature-integration, as well as a tool for similar faces retrieval in 2-tier systems (as initial processing, before exact face recognition).

Zero-Automatic Networks

We continue the study of zero-automatic queues first introduced in Dao-Thi and Mairesse (Adv Appl Probab 39(2):429–461, 2007). These queues are characterized by a special buffering mechanism evolving like a random walk on some infinite group or monoid. The simple M/M/1 queue and Gelenbe’s G-queue with positive and negative customers are the two simplest 0-automatic queues. All stable 0-automatic queues have an explicit “multiplicative” stationary distribution and a Poisson departure process (Dao-Thi and Mairesse, Adv Appl Probab 39(2):429–461, 2007). In this paper, we introduce and study networks of 0-automatic queues. We consider two types of networks, with either a Jackson-like or a Kelly-like routing mechanism. In both cases, and under the stability condition, we prove that the stationary distribution of the buffer contents has a “product-form” and can be explicitly determined. Furthermore, the departure process out of the network is Poisson.

Uniqueness of the Perfect Fusion Grid on ℤ d

Region merging methods consist of improving an initial segmentation by merging some pairs of neighboring regions. In a graph, merging two regions, separated by a set of vertices, is not straightforward. The perfect fusion graphs defined in J. Cousty et al. (J. Math. Imaging Vis. 30:(1):87–104, 2008) verify all the basic properties required by region merging algorithms as used in image segmentation. Unfortunately, the graphs which are the most frequently used in image analysis (namely, those induced by the direct and the indirect adjacency relations) are not perfect fusion graphs. The perfect fusion grid, introduced in the above mentioned reference, is an adjacency relation on ℤ ^d which can be used in image analysis, which indeed induces perfect fusion graphs and which is “between” the graphs induced by the direct and the indirect adjacencies. One of the main results of this paper is that the perfect fusion grid is the only such graph whatever the dimension d.

Partial Partitions,Partial Connections and Connective Segmentation

In connective segmentation (Serra in J. Math. Imaging Vis. 24(1):83–130, [2006]), each image determines subsets of the space on which it is “homogeneous”, in such a way that this family of subsets always constitutes a connection (connectivity class); then the segmentation of the image is the partition of space into its connected components according to that connection. Several concrete examples of connective segmentations or of connections on sets, indicate that the space covering requirement of the partition should be relaxed. Furthermore, morphological operations on partitions require the consideration of wider framework. We study thus partial partitions (families of mutually disjoint non-void subsets of the space) and partial connections (where connected components of a set are mutually disjoint but do not necessarily cover the set). We describe some methods for generating partial connections. We investigate the links between the two lattices of partial connections and of partial partitions. We generalize Serra’s characterization of connective segmentation and discuss its relevance. Finally we give some ideas on how the theory of partial connections could lead to improved segmentation algorithms.