Evolution provides a creative fount of complex and subtle adaptations that often surprise the scientists who discover them. However, the creativity of evolution is not limited to the natural world: Artificial organisms evolving in computational environments have also elicited surprise and wonder from the researchers studying them. The process of evolution is an algorithmic process that transcends the substrate in which it occurs. Indeed, many researchers in the field of digital evolution can provide examples of how their evolving algorithms and organisms have creatively subverted their expectations or intentions, exposed unrecognized bugs in their code, produced unexpectedly adaptations, or engaged in behaviors and outcomes, uncannily convergent with ones found in nature. Such stories routinely reveal surprise and creativity by evolution in these digital worlds, but they rarely fit into the standard scientific narrative. Instead they are often treated as mere obstacles to be overcome, rather than results that warrant study in their own right. Bugs are fixed, experiments are refocused, and one-off surprises are collapsed into a single data point. The stories themselves are traded among researchers through oral tradition, but that mode of information transmission is inefficient and prone to error and outright loss. Moreover, the fact that these stories tend to be shared only among practitioners means that many natural scientists do not realize how interesting and lifelike digital organisms are and how natural their evolution can be. To our knowledge, no collection of such anecdotes has been published before. This article is the crowd-sourced product of researchers in the fields of artificial life and evolutionary computation who have provided first-hand accounts of such cases. It thus serves as a written, fact-checked collection of scientifically important and even entertaining stories. In doing so we also present here substantial evidence that the existence and importance of evolutionary surprises extends beyond the natural world, and may indeed be a universal property of all complex evolving systems.

This paper proposes a new sensor control algorithm to adapt the operation parameters of the sensors in order to optimize temporal coverage. Traditional sensor control algorithms rely on non-probabilistic sensor coverage models and simple target trajectory prediction methods, while the new algorithm overcomes all these limitations. The proposed approach make an optimization of one sensor at the time, processed in a random order. The performance of the proposed algorithm is compared with a state-of-the-art general purpose optimization method (i.e., CMA-ES). Results show that our algorithm produces the results in a much shorter time in all the cases considered, while the final coverage of the network was superior in a smaller map and competitive in larger maps. Therefore, the new algorithm can be used in scenarios where response within some time limit is of great importance (e.g., real-time control of the sensors).

This paper proposes the use of a kernel density estimation to measure similarities between trajectories. The similarities are then used to predict the future locations of a target. For a given environment with a history of previous target trajectories, the goal is to establish a probabilistic framework to predict the future trajectory of currently observed targets based on their recent moves. Instead of clustering trajectories into groups, we calculate the similarity between a given test trajectory and the set of all past trajectories in a dataset. Next, we use a weighted mechanism for prediction, that can be used in target tracking and collision avoidance applications. The proposed method is compared with two other commonly used similarity models (PCA and LCSS) over a dataset of simulated trajectories, and two datasets of real observations. Results show that the proposed method significantly outperforms the existing models for those datasets and experimental settings.

Learning from non-stationary data requires methods that are able to deal with a continuous stream of data instances, possibly of infinite size, where the class distributions are potentially drifting over time. For handling such datasets, we are proposing a new method that incrementally creates and adapts a network of prototypes for classifying complex data received in an online fashion. The algorithm includes both an accuracy-based and time-based forgetting mechanisms that ensure that the model size does not grow indefinitely with large datasets. We have performed tests on seven benchmarking datasets for comparing our proposal with several approaches found in the literature, including ensemble algorithms associated to two different base classifiers. Performances obtained show that our algorithm is comparable to the best of the ensemble classifiers in terms of accuracy/time trade-off. Moreover, our approach appears to have significant advantages for dealing with data that has a complex, non-linearly separable topology.

This paper generalizes the "Improved Run-Time Complexity Algorithm for Non-Dominated Sorting" by Jensen, removing its limitation that no two solutions can share identical values for any of the problem's objectives. This constraint is especially limiting for discrete combinatorial problems, but can also lead the Jensen algorithm to produce incorrect results even for problems that appear to have a continuous nature, but for which identical objective values are nevertheless possible. Moreover, even when values are not meant to be identical, the limited precision of floating point numbers can sometimes make them equal anyway. Thus a fast and correct algorithm is needed for the general case. The paper shows that generalizing the Jensen algorithm can be achieved without affecting its time complexity, and experimental results are provided to demonstrate speedups of up to two orders of magnitude for common problem sizes, when compared with the correct baseline algorithm from Deb.

This paper improves upon the reference NSGA-II procedure by removing an instability in its crowding distance operator. This instability stems from the cases where two or more individuals on a Pareto front share identical fitnesses. In those cases, the instability causes their crowding distance to either become null, or to depend on the individual's position within the Pareto front sequence. Experiments conducted on nine different benchmark problems show that, by computing the crowding distance on unique fitnesses instead of individuals, both the convergence and diversity of NSGA-II can be significantly improved.

This paper presents experiments of Nearest Neighbor (NN) classifier design using different evolutionary computation methods. Through multiobjective and coevolution techniques, it combines genetic algorithms and genetic programming to both select NN prototypes and design a neighborhood proximity measure, in order to produce a more efficient and robust classifier. The proposed approach is compared with the standard NN classifier, with and without the use of classic prototype selection methods, and classic data normalization. Results on both synthetic and real data sets show that the proposed methodology performs as well or better than other methods on all tested data sets.

This paper introduces a new mathematical model of the master-slave architecture for distributed evolutionary computations (EC). This model is validated using a concrete implementation based on the Distributed BEAGLE C++ framework. Results show that contrary to (current) popular belief, master-slave architectures are able to scale well over local area networks of workstations using off-the-shelf networking equipment. The main properties of the master-slave are also compared with those of the more mainstream island-model.

This paper addresses the fundamental problem of automatically discovering an unknown moving deformable object in a monocular video sequence. No prior model of the object is used; it is only assumed that the object is composed of a set of apparently rigid parts that are not necessarily visible simultaneously, making it possible to circumvent the typical constraint of model initialization. A set of rigid parts describing the object is incrementally extracted in a modeling-tracking loop with reinforced memory. In this framework, low-level segmentation is considered as a necessary but non reliable process that helps initiating hypotheses. Motion-based layer segmentation from feature points and edges is applied only when and where no modeled parts can be tracked. Using the quantity of motion measure, it is further shown how to deal with temporal scale. The interest for this approach in applications such as human tracking is demonstrated for a set of various sequences including a rapidly evolving shape

This paper presents experiments that compare the performances of several versions of a regional-fuzzy representation (RFR) developed for cursive handwriting recognition (CHR). These experiments are conducted using a common neural network classifier namely a multilayer perceptron (MLP) trained with backpropagation. Results are given for isolated digits, isolated lower-case letters and lower-case letters extracted from phrases, from the Unipen database. Data set Train-R01/V07 is used for training while DevTest-R01/V02 is used for testing. The best overall representation yields recognition rates of respectively 97.0% and 85.6% for isolated digits and lower case, and 84.4% for lower-case extracted from phrases.

This paper discusses logical labeling in documents, which is one basic step in logical structure recognition. Logical labels have to be attributed to text blocks composing the layout structure. Our study is based on physical characteristics having a visual aspect: typographic, geometric and/or topologic attributes. Our objective is to map a low level logical structure, which consists of a set of logical labels, on the extracted layout structure components. We have to build a model that allows this mapping. However, the documents we consider have various layout and logical structures, thus, we chose to perform this task by supervised learning on the basis of a set of training documents. This allows us to define a generic method to solve this problem, without imposing any constraint on document structure. We propose a probabilistic model represented by a Bayesian Network (BN), which is a graphical model used in our problem as a classifier. A prototype has been implemented, and applied to tables of contents in periodicals.

Hidden Markov models (HMM) are stochastic models capable of statistical learning and classification. They have been applied in speech recognition and handwriting recognition because of their great adaptability and versatility in handling sequential signals. On the other hand, as these models have a complex structure and also because the involved data sets usually contain uncertainty, it is difficult to analyze the multiple observation training problem without certain assumptions. For many years researchers have used the training equations of Levinson (1983) in speech and handwriting applications, simply assuming that all observations are independent of each other. This paper presents a formal treatment of HMM multiple observation training without imposing the above assumption. In this treatment, the multiple observation probability is expressed as a combination of individual observation probabilities without losing generality. This combinatorial method gives one more freedom in making different dependence-independence assumptions. By generalizing Baum's auxiliary function into this framework and building up an associated objective function using the Lagrange multiplier method, it is proven that the derived training equations guarantee the maximization of the objective function. Furthermore, we show that Levinson's training equations can be easily derived as a special case in this treatment.

This paper describes a new hybrid architecture for an artificial neural network classifier that enables incremental learning. The learning algorithm of the proposed architecture detects the occurrence of unknown data and automatically adapts the structure of the network to learn these new data, without degrading previous knowledge. The architecture combines an unsupervised self-organizing map with a supervised perceptron network to form the hybrid self-organizing perceptron (SOP) network. Recognition experiments conducted on isolated characters taken in the context of cursive words show the promising incremental capabilities of this SOP network.

This paper describes a new hybrid architecture for an artificial neural network classifier that enables incremental learning. The learning algorithm of the proposed architecture detects the occurrence of unknown data and automatically adapts the structure of the network to learn these new data, without degrading previous knowledge. The architecture combines an unsupervised self-organizing map with a supervised perceptron network to form the self-organizing perceptron network.

Presents a hidden Markov model (HMM) based approach to online handwritten digit recognition using stroke sequences. In this approach, a character instance is represented by a sequence of symbolic strokes, and the representation is obtained by component segmentation and stroke classification. The component segmentation is based on the delta lognormal model of handwriting generation. The symbolic strokes are used for HMM multiple observation training or recognition. A training and recognition experiment has been conducted using the above techniques.

Introduces a fuzzy representation for isolated character description. This representation maps a character from its original sequence of 2D coordinates into a fuzzy vector space that can thereafter serve as input to any artificial neural network classifier. Recognition experiments on isolated digits extracted from the UNIPEN database are their conducted to evaluate the performances of the proposed representation using a hybrid Kohonen-perceptron (KP) neural network.

This paper presents an original method for creating allograph models and recognizing them within cursive handwriting. This method concentrates on the morphological aspect of cursive script recognition. It uses fuzzy-shape grammars to define the morphological characteristics of conventional allographs which can be viewed as basic knowledge for developing a writer independent recognition system. The system uses no linguistic knowledge to output character sequences that possibly correspond to an unknown cursive word input. The recognition method is tested using multi-writer cursive random letter sequences. For a test dataset containing a handwritten cursive text 600 characters in length written by ten different writers, average character recognition rates of 84.4% to 91.6% are obtained, depending on whether only the best character sequence output of the system is considered or if the best of the top 10 is accepted. These results are achieved without any writer-dependent tuning. The same dataset is used to evaluate the performance of human readers. An average recognition rate of 96.0% was reached, using ten different readers, presented with randomized samples of each writer. The worst reader-writer performance was 78.3%. Moreover, results show that system performances are highly correlated with human performances.>

This paper presents an overview of a dynamic cursive script recognition approach that uses no linguistic constraints. This approach seeks to recognize in cursive script, morphologically and pragmatically coherent sequences of character hypotheses. As performance is compared with the performance of the best available cursive script recognizers-humans-in a reading experiment where linguistic knowledge is useless. The recognition method uses fuzzy-shape grammars to model the morphological characteristics of conventional letters. These models, called allographs, can be viewed as basic (a priori) knowledge for developing a multi-writer recognition system. Character hypotheses are segmented within a cursive word using a parser for these grammars. Character sequences are then constructed from these segmentation hypotheses using local adjacency constraints also modeled by fuzzy-shape grammars. Two experiments are conducted on a test database containing a handwritten cursive test 600 characters in length written by ten different writers. Results show that the system performances are highly correlated with human performance.

Defines an operational handwriting model for online syntactic recognition of cursive script. To represent handwriting, it uses characteristic points linked together by segments of uniform curvature. The model acts as a guide for the extraction of attributed primitives used in shape grammars that model allographs and their adjacency rules. The handwriting model is evaluated by human readers in a comparative analysis of original cursive letter sequences versus their reconstructed traces. Also, its performance is measured in terms of mean reconstruction error and data compression rate.>

A report is presented on a comparative study of three different signal matching algorithms in the context of signature verification: regional correlation, dynamic time warping, and skeletal tree matching. The algorithm performances are compared in a single experimental protocol over the same database. Algorithm performance is analyzed in terms of verification error rates, execution time, and number and sensitivity of algorithm parameters. Three different script types (normal signatures, handwritten passwords, and initials) and three different signal representation spaces (position, velocity, and acceleration) are considered. Verification errors show that no algorithm consistently outperforms the others in all circumstances.>

The performance of position, velocity, and acceleration signals for automatic signature verification is compared. Three types of signal comparison algorithms (dynamic time warping, regional correlation and tree matching) are used on a single database. Variance analysis shows that significant differences exist among the three signal representation spaces. Among other things, it is shown that the most discriminant are signals which reflect the vertical activity of the signing process and that the best representation space for a 2-D signature verification system is the velocity domain.>