On the size of computationally complete hybrid networks of evolutionary processors

A hybrid network of evolutionary processors (an HNEP) is a graph where each node is associated with an evolutionary processor (a special rewriting system), a set of words, an input filter and an output filter. Every evolutionary processor is given with a finite set of one type of point mutations (an insertion, a deletion or a substitution of a symbol) which can be applied to certain positions of a string over the domain of the set of these rewriting rules. The HNEP functions by rewriting the words that can be found at the nodes and then re-distributing the resulting strings according to a communication protocol based on a filtering mechanism. The filters are defined by certain variants of random-context conditions. HNEPs can be considered as both language generating devices (GHNEPs) and language accepting devices (AHNEPs). In this paper, by improving the previous results, we prove that any recursively enumerable language can be determined by a GHNEP and an AHNEP with 7 nodes. We also show that the families of GHNEPs and AHNEPs with 2 nodes are not computationally complete.     

Computational completeness of complete,star-like,and linear hybrid networks of evolutionary processors with a small number of processors

A hybrid network of evolutionary processors (HNEP) is a graph where each node is associated with a special rewriting system called an evolutionary processor, an input filter, and an output filter. Each evolutionary processor is given a finite set of one type of point mutations (insertion, deletion or a substitution of a symbol) which can be applied to certain positions in a string. An HNEP rewrites the strings in the nodes and then re-distributes them according to a filter-based communication protocol; the filters are defined by certain variants of random-context conditions. HNEPs can be considered both as languages generating devices (GHNEPs) and language accepting devices (AHNEPs); most previous approaches treated the accepting and generating cases separately. For both cases, in this paper we show that five nodes are sufficient to accept (AHNEPs) or generate (GHNEPs) any recursively enumerable language by showing the more general result that any partial recursive relation can be computed by an HNEP with (at most) five nodes with the underlying graph structure for the communication between the evolutionary processors being the complete or the linear graph with five nodes, whereas with a star-like communication graph we need six nodes. If the final results are defined by only taking the terminal strings out of the designated output node, then for these extended HNEPs we can prove that only four nodes are needed in all cases—for computing any partial recursive relation as well as for generating and accepting any recursively enumerable language—and the underlying communication structure can be a complete or a linear graph, but now even a star-like graph, too.     

Breaking the data encryption standard using networks of evolutionary processors with parallel string rewriting rules

In this paper we introduce a biologically inspired distributed computing model called networks of evolutionary processors with parallel string rewriting rules (NEPPS), which is a variation of the hybrid networks of evolutionary processors introduced by Martin-Vide et al. Such a network contains simple processors that are located in the nodes of a virtual graph. Each processor has strings (each string having multiple copies) and string rewriting rules. The rules are applied parallely on the strings. After the strings have been rewritten, they are communicated among the processors through filters. We show that we can theoretically break the DES (data encryption standard), which is the most widely used cryptosystem, using NEPPS. We prove that, given an arbitrary <plain-text, cipher-text> pair, one can recover the DES key in a constant number of steps.     

Accepting Networks of Evolutionary Processors with Subregular Filters

We propose a new variant of Accepting Networks of Evolutionary Processors, in which the operations are applied at arbitrary positions to the processed words (rather than at the ends of words only) and where the filters are languages from several special classes of regular sets. More precisely, we show that the use of filters from the class of non-counting, ordered, power-separating, suffix-closed regular, union-free, definite and combinational languages is as powerful as the use of arbitrary regular languages and yields networks that can accept all the recursively enumerable languages. On the other hand, by using filters that are only finite languages, monoids, nilpotent languages, commutative regular languages, or circular regular languages, one cannot generate all recursively enumerable languages. These results seem interesting as they provide both upper and lower bounds on the classes of languages that one can use as filters in an accepting network of evolutionary processors in order to obtain a complete computational model.     

Complexity-preserving simulations among three variants of accepting networks of evolutionary processors

In this paper we consider three variants of accepting networks of evolutionary processors. It is known that two of them are equivalent to Turing machines. We propose here a direct simulation of one device by the other. Each computational step in one model is simulated in a constant number of computational steps in the other one while a translation via Turing machines squares the time complexity. We also discuss the possibility of constructing simulations that preserve not only complexity, but also the shape of the simulated network.     

Networks of evolutionary processors

In this paper we consider networks of evolutionary processors as language generating and computational devices. When the filters are regular languages one gets the computational power of Turing machines with networks of size at most six, depending on the underlying graph. When the filters are defined by random context conditions, we obtain an incomparability result with the families of regular and context-free languages. Despite their simplicity, we show how the latter networks might be used for solving an NP-complete problem, namely the “3-colorability problem”, in linear time and linear resources (nodes, symbols, rules). Received: 26 September 2002 / 22 January 2003 RID="*" ID="*" Work supported by the Generalitat de Catalunya, Direcció General de Recerca (PIV2001-50).     

On the number of nodes in universal networks of evolutionary processors

We consider the networks of evolutionary processors (NEP) introduced by J. Castellanos, C. Martí n-Vide, V. Mitrana and J. Sempere recently. We show that every recursively enumerable (RE) language can be generated by an NEP with three nodes modulo a terminal alphabet and moreover, NEPs with four nodes can generate any RE language. Thus, we improve existing universality result from five nodes down to four nodes. For mNEPs (a variant of NEPs where operations of different kinds are allowed in the same node) we obtain optimal results: each RE language can be generated by an mNEP with one node modulo a terminal alphabet, and mNEPs with two nodes can generate any RE language; this is not possible for mNEPs with one node. Some open problems are formulated.     

Networks of evolutionary processors: computationally complete normal forms

Networks of evolutionary processors (NEPs, for short) form a bio-inspired language generating computational model that was shown to be equivalent to the model of phrase-structure grammars. In this paper, we analyse different restricted variants of NEPs that preserve the computational power of the general model. We prove that any recursively enumerable language can be generated by a NEP where the derivation rules can be applied at arbitrarily chosen positions, the control of the communication is done by finite automata with at most three states, and either the rule sets are singletons or the underlying graph is a complete graph. If one uses networks with arbitrary underlying graphs and allows the additional application of insertions and deletions only to the right-most or the to left-most position of the derived words for some nodes, then we only need automata with only one state to control the communication in the network. Clearly, this result is optimal; moreover, finite automata with two states are necessary and sufficient in order to generate all the recursively enumerable languages when the derivation rules can be applied only at arbitrarily chosen positions.     

Optimizing self-organizing overlay network using evolutionary approach

Self-organizing overlay networks are emerging as next generation networks capable of adapting to the needs of applications at runtime. Applications performance significantly depends on the structure and behaviors of the underlying self-organizing overlay networks. To achieve desired performance, not only the logical overlay topology but also the behaviors of nodes in this overlay network need to be optimized. Moreover, self-organizing overlay networks are extremely dynamic, unreliable and often large-scale. It is therefore important to design new optimizing approaches to meet these challenges. In this paper, we present an evolutionary optimization methodology for self-organizing overlay network. The optimizations of self-organizing overlay networks are modeled as dynamically evolutionary process, in which the nodes interact with each other, change their internal structures and alter their external links to improve the collective performance. To design appropriate fitness functions and rules that guides the direction of the evolution, overlay network can reach a stable state with desired global application performance eventually. Such a methodology leads to our distributed algorithms for proximity-based overlay topology maintenance and Peer-to-Peer living media streaming, in which every node in the overlay network rewires their behaviors and connectivity according to local available information and embedded rules. These algorithms are shown to perform well using simulations.     

Automated synthesis of multiple analog circuits using evolutionary computation for redundancy-based fault-tolerance

Analog circuits are one of the most important parts of modern electronic systems and the failure of electronic hardware presents a critical threat to the completion of modern aircraft, spacecraft, and robot missions. Compared to digital circuits, designing fault-tolerant analog circuits is a difficult and knowledge-intensive task. A simple but powerful method for robustness is a redundancy approach to use multiple circuits instead of single one. For example, if component failures occur, other redundant components can replace the functions of broken parts and the system can still work. However, there are several research issues to make the redundant system automatically. In this paper, we used evolutionary computation to generate multiple analog circuits automatically and then we combined the solutions to generate robust outputs. Evolutionary computation is a natural way to produce multiple redundant solutions because it is a population-based search. Experimental results on the evolution of the low-pass, high-pass and band-stop filters show that the combination of multiple evolved analog circuits produces results that are more robust than those of the best single circuit.     

An evolutionary approach to generalized biobjective traveling salesperson problem

We consider the generalized biobjective traveling salesperson problem, where there are a number of nodes to be visited and each node pair is connected by a set of edges. The final route requires finding the order in which the nodes are visited (tours) and finding edges to follow between the consecutive nodes of the tour. We exploit the characteristics of the problem to develop an evolutionary algorithm for generating an approximation of nondominated points. For this, we approximate the efficient tours using approximate representations of the efficient edges between node pairs in the objective function space. We test the algorithm on several randomly-generated problem instances and our experiments show that the evolutionary algorithm approximates the nondominated set well.     

An experimental study on the applicability of evolutionary algorithms to craniofacial superimposition in forensic identification

Photographic supra-projection is a forensic process that aims to identify a missing person from a photograph and a skull found. One of the crucial tasks throughout all this process is the craniofacial superimposition which tries to find a good fit between a 3D model of the skull and the 2D photo of the face. This photographic supra-projection stage is usually carried out manually by forensic anthropologists. It is thus very time consuming and presents several difficulties. In this paper, we aim to demonstrate that real-coded evolutionary algorithms are suitable approaches to tackle craniofacial superimposition. To do so, we first formulate this complex task in forensic identification as a numerical optimization problem. Then, we adapt three different evolutionary algorithms to solve it: two variants of a real-coded genetic algorithm and the state of the art evolution strategy CMA-ES. We also consider an existing binary-coded genetic algorithm as a baseline. Results on several superimposition problems of real-world identification cases solved by the Physical Anthropology lab at the University of Granada (Spain) are considered to test our proposals.     

Networks of evolutionary processors: the power of subregular filters

In this paper, we propose a hierarchy of families of languages generated by networks of evolutionary processors where the filters belong to several special classes of regular sets. More precisely, we show that the use of filters from the class of ordered, non-counting, power-separating, circular, suffix-closed regular, union-free, definite, and combinational languages is as powerful as the use of arbitrary regular languages and yields networks that can generate all the recursively enumerable languages. On the other hand, the use of filters that are only finite languages allows only the generation of regular languages, but not every regular language can be generated. If we use filters that are monoids, nilpotent languages, or commutative regular languages, we obtain one and the same family of languages which contains non-context-free languages but not all regular languages. These results seem to be of interest because they provide both upper and lower bounds on the families of languages that one can use as filters in a network of evolutionary processors in order to obtain a complete computational model.     

On-the-fly calibrating strategies for evolutionary algorithms

The issue of controlling values of various parameters of an evolutionary algorithm is one of the most important and interesting areas of research in evolutionary computation. In this paper we propose two new parameter control strategies for evolutionary algorithms based on the ideas of reinforcement learning. These strategies provide efficient and low-cost adaptive techniques for parameter control and they preserve the original design of the evolutionary algorithm, as they can be included without changing either the structure of the algorithm nor its operators design.     

Comparing evolutionary algorithms and particle filters for Markerless Human Motion Capture

Markerless Human Motion Capture is the problem of determining the joints’ angles of a three-dimensional articulated body model that best matches current and past observations acquired by video cameras. The problem of Markerless Human Motion Capture is high-dimensional and requires the use of models with a considerable number of degrees of freedom to appropriately adapt to the human anatomy.Particle filters have become the most popular approach for Markerless Human Motion Capture, despite their difficulty to cope with high-dimensional problems. Although several solutions have been proposed to improve their performance, they still suffer from the curse of dimensionality. As a consequence, it is normally required to impose mobility limitations in the body models employed, or to exploit the hierarchical nature of the human skeleton by partitioning the problem into smaller ones.Evolutionary algorithms, though, are powerful methods for solving continuous optimization problems, specially the high-dimensional ones. Yet, few works have tackled Markerless Human Motion Capture using them. This paper evaluates the performance of three of the most competitive algorithms in continuous optimization – Covariance Matrix Adaptation Evolutionary Strategy, Differential Evolution and Particle Swarm Optimization – with two of the most relevant particle filters proposed in the literature, namely the Annealed Particle Filter and the Partitioned Sampling Annealed Particle Filter.The algorithms have been experimentally compared in the public dataset HumanEva-I by employing two body models with different complexities. Our work also analyzes the performance of the algorithms in hierarchical and holistic approaches, i.e., with and without partitioning the search space. Non-parametric tests run on the results have shown that: (i) the evolutionary algorithms employed outperform their particle filter counterparts in all the cases tested; (ii) they can deal with high-dimensional models thus leading to better accuracy; and (iii) the hierarchical strategy surpasses the holistic one.     

遗传算法采用进化方向算子的几种策略

提出了采用实数编码情况下应用进化方向算子的几种策略，包括单亲进化方向算子、双亲进化方向算子以及无轮盘赌选择的双亲进化方向算子策略，并进行了数值仿真。仿真结果表明，灵活使用方向进化算子以及遗传操作可大大提高遗传算法的全局搜索能力。     

A Universal Accepting Hybrid Network of Evolutionary Processors

We propose a construction of an accepting hybrid network of evolutionary processors (AHNEP) which behaves as a universal device in the class of all these devices. We first construct a Turing machine which can simulate any AHNEP and then an AHNEP which simulates the Turing machine. We think that this approach can be applied to other bio-inspired computing models which are computationally complete.     

An evolutionary approach towards contact plan design for disruption-tolerant satellite networks

Delay and disruption tolerant networks (DTNs) are becoming an appealing solution for satellite networks where nodes can temporarily store and carry in-transit data until a link with a suitable next-hop becomes available. Since satellite trajectories and orientation can be predicted, on-board routing schemes can base these forwarding decisions on a contact plan comprising all forthcoming communication opportunities. In general, contact plans are previously calculated on ground where their design can be optimized to consider not only available spacecraft resources but also the expected traffic which is largely foreseeable in space applications. Despite optimal contact plan design procedures exist, their computation complexity might result prohibitive even for medium-sized satellite networks. In this work, we propose an evolutionary algorithm to provide sub-optimal yet efficient and implementable contact plans in bounded time. In particular, we depict specific strategies such as encoding and repairing techniques to later evaluate the algorithm performance in a typical scenario demonstrating its usefulness for planning future DTN-based satellite networks.