Search

We consider the absolute worst case time complexity for Hopcroft΄s minimization algorithm applied to unary languages (or a modification of this algorithm for cover automata minimization). We show that in this setting the worst case is reached only for deterministic automata or cover automata following the structure of the de Bruijn words. We refine a previous result by showing that the Berstel/Carton example reported before is actually the absolute worst case time complexity in the case of unary languages for deterministic automata. We show that the same result is valid also when considering the setting of cover automata and an algorithm based on the Hopcroft΄s method used for minimization of cover automata. We also show that a LIFO implementation for the splitting list is desirable for the case of unary languages in the setting of deterministic finite automata. [ABSTRACT FROM AUTHOR]

Recently, the idea of spiking neurons and thus of computing by spiking was incorporated into membrane computing, and so-called spiking neural P systems (abbreviated SN P systems) were introduced. Very shortly, in these systems neurons linked by synapses communicate by exchanging identical signals (spikes), with the information encoded in the distance between consecutive spikes. Several ways of using such devices for computing were considered in a series of papers, with universality results obtained in the case of computing numbers, both in the generating and the accepting mode; generating, accepting, or processing strings or infinite sequences was also proved to be of interest. In the present paper, after a short survey of central notions and results related to spiking neural P systems (including the case when SN P systems are used as string generators), we contribute to this area with two (types of) results: (i) we produce small universal spiking neural P systems (84 neurons are sufficient in the basic definition, but this number is decreased to 49 neurons if a slight generalization of spiking rules is adopted), and (ii) we investigate the possibility of generating a language by following the trace of a designated spike in its way through the neurons. [ABSTRACT FROM AUTHOR]

We consider symport/antiport P systems using the time as the support for the output of a computation. We describe and study the properties of "timed symport/antiport systems", showing that this new model of membrane systems based on time has more power/flexibility, and thus allows us to improve previous universality results. We were able to improve or match the best results concerning the symport/antiport systems which consider the output as originally defined as the number of molecules found in a pre-defined elementary membrane in the halting configuration of the system. [ABSTRACT FROM AUTHOR]

Cellular signalling pathways are fundamental to the control and regulation of cell behavior. Understanding of biosignalling network functions is crucial to the study of different diseases and to the design of effective therapies. In this paper we present P systems as a feasible computational modeling tool for cellular signalling pathways that takes into consideration the discrete character of the components of the system and the key role played by membranes in their functioning. We illustrate these cellular models simulating the epidermal growth factor receptor (EGFR) signalling cascade and the FAS-induced apoptosis using a deterministic strategy for the evolution of P systems. [ABSTRACT FROM AUTHOR]

A k-output spiking neural P system (SNP) with output neurons, O1..., Ok, generates a tuple (n1..., nk) of positive integers if, starting from the initial configuration, there is a sequence of steps such that during the computation, each Oi generates exactly two spikes a a (the times the pair a a are generated may be different for different output neurons) and the time interval between the first a and the second a is ni. After the output neurons generate their pairs of spikes, the system eventually halts. We give characterizations of sets definable by partially blind multicounter machines in terms of k-output SNPs operating in a sequential mode. Slight variations of the models make them universal. [ABSTRACT FROM AUTHOR]

We consider P systems with active membranes, but without polarizations, yet with using membrane division and membrane generation, but as the result of a halting computation we do not take the terminal string generated in a designated output membrane, instead we consider the resulting tree representing the membrane structure of the final configuration as its result. We show that each recursively enumerable tree language can be obtained in that way generated by P systems with active membranes working on strings. [ABSTRACT FROM AUTHOR]

P systems with proteins on membranes are inspired closely by switching protein channels. This model of membrane computing using membrane division has been previously shown to solve an NP-complete problem in polynomial time. In this paper we characterize the class of problems solvable by these P systems in polynomial time and we show that it equals PSPACE. Therefore, these P systems are computationally equivalent (up to a polynomial time reduction) to the alternating Turing machine or the PRAM computer. The proof technique we employ reveals also some interesting trade-offs between certain P system properties, as antiport rules, membrane labeling by polarization or the presence of proteins. [ABSTRACT FROM AUTHOR]

The spiking neural P systems are a class of computing devices recently introduced as a bridge between spiking neural nets and membrane computing. In this paper we consider sequential SNP systems where the sequentiality of the system is induced by a simple choice: the neuron with the maximum number of spikes out of the neurons that can spike at one step will fire. This corresponds to a global view of the whole network that makes the system sequential. We study the properties of this restriction. [ABSTRACT FROM AUTHOR]

We present a new model for simulating Fas-induced apoptosis in HIV-1-infected CD4+ T cells. Moreover, the reactivation of latently infected cells is explored. The work, an extension of our previous modeling efforts, is the first attempt in systems biology for modeling the Fas pathway in the latently infected cells. These enigmatic cells are considered the last barrier in the elimination of HIV infection. In building the model, we gathered what reaction rates and initial conditions are available from the literature. For the unknown constants, we fit the model to the available information on the observed effects of HIV-1 proteins in activated CD4+ T cells. We provide results, using the Nondeterministic Waiting Time (NWT) algorithm, from the model, simulating the infection of activated CD4+ T cells as well as the reactivation of a latently infected cells. These two model versions are distinct with respect to the initial conditions – multiplicities and locations of proteins at the beginning of the simulation. [ABSTRACT FROM AUTHOR]

We present an enhancement of the Nondeterministic Waiting Time algorithm. This work is a continuation of our group΄s previous modeling efforts. We have improved our algorithm with a ˵memory enhancement″. Previously, we have used our algorithm to explore the Fas-mediated apoptotic pathway in cells with a particular focus on cancerous or HIV-1-infected T cells. In this paper, we will describe the memory enhancement and give a simple three reaction model to illustrate the differences between our technique and a continuous, concentration-based approach using a system of ordinary differential equations. Furthermore, we provide our results from the modeling of two well-known models: the Lotka-Volterra predator-prey and a circadian rhythm model. For these models, we provide the results of our simulation technique in comparison to results from ordinary differential equations and the Gillespie Algorithm. We show that our algorithm, while being faster than Gillespie΄s approach, is capable of generating oscillatory behavior where ordinary differential equations do not. [ABSTRACT FROM AUTHOR]

Dimensionality reduction methods are used routinely in statistics, pattern recognition, data mining, and machine learning to cope with high-dimensional spaces. Also in the case of high-dimensional multiobjective optimization problems, a reduction of the objective space can be beneficial both for search and decision making. New questions arise in this context, e.g., how to select a subset of objectives while preserving most of the problem structure. In this chapter, two different approaches to the task of objective reduction are developed, one based on assessing explicit conflicts, the other based on principal component analysis (PCA). Although both methods use different principles and preserve different properties of the underlying optimization problems, they can be effectively utilized either in an a posteriori scenario or during search. Here, we demonstrate the usability of the conflict-based approach in a decision-making scenario after the search and show how the principal-component-based approach can be integrated into an evolutionary multicriterion optimization (EMO) procedure. [ABSTRACT FROM AUTHOR]

We consider a class of optimization problems wherein the quality of candidate solutions is estimated by their performance on a number of tests. Classifier induction, function regression, and certain types of reinforcement learning, including problems often attacked with coevolutionary algorithms, can all be seen as members of this class. Traditional approaches to such test-based problems use a single objective function that aggregates the scores obtained on the tests. Recent work, by contrast, argues that useful finer-grained distinctions between candidate solutions are obtained when each test is treated as a separate objective, and that algorithms employing such multiobjective comparisons show favourable behaviour relative to those which do not. Unfortunately, the number of tests can be very large. Since it is well-known that high-dimensional multiobjective optimization problems are difficult to handle in practice, the question arises whether the multiobjective treatment of test-based problems is feasible. To begin addressing this question, we examine a method for reducing the number of dimensions without sacrificing the favorable properties of the multiobjective approach. Our method, which is a form of dimension extraction, finds underlying objectives implicit in test-based problems. Essentially, the method proceeds by placing the tests along the minimal number of coordinate axes that still preserve ordering information among the candidate solutions. Application of the method to the strategy set for several instances of the game of Nim suggest the technique has significant practical benefits: a type of compression of the set of objectives is observed in all tested instances. Surprisingly, we also find that the information contained in the arrangement of tests on the coordinate axes reveals important information about the structure of the underlying problem. [ABSTRACT FROM AUTHOR]

Model-based multiobjective optimization is one class of metaheuristics for solving multiobjective optimization problems, where a probabilistic model is built from the current distribution of the solutions and new candidate solutions are generated from the model. One main difficulty in model-based optimization is constructing a probabilistic model that is able to effectively capture the structure of the problems to enable efficient search. This chapter advocates a new type of probabilistic model that takes the regularity in the distribution of Pareto-optimal solutions into account. We compare our model to two other model-based multiobjective algorithms on a number of test problems to demonstrate that it is scalable to high-dimensional optimization problems with or without linkage linkage among the design variables. [ABSTRACT FROM AUTHOR]

This chapter considers a number of alternative methods for fitness assignment in evolutionary algorithms for multiobjective optimization. Most of the fitness assignment methods in the literature were designed to work for any number of objectives, in principle; but, in practice, some of the more popular methods (e.g. those in NSGA-II, IBEA and SPEA) do not perform well on problems with four or more objectives. We investigate why this is the case, considering two aspects of performance: convergence towards the Pareto front and drive towards a set of well spread solutions. The visualization of induced fitness surfaces is used to understand the effects of the different fitness assignment methods, and both Pareto- and non-Pareto-based methods are analysed. [ABSTRACT FROM AUTHOR]

This chapter provides a comparative discussion on natural and artificial systems. It focuses on multiobjective problems as related to the evolution of systems either naturally or artificially; yet, it should be viewed as relevant to other forms of adaptation. Research developments in areas such as evolutionary design, plant biology, robotics, A-life, biotechnology, and game theory are used to support the comparative discussion. A unified approach, namely multi-competence cybernetics (MCC) is suggested. This is followed by a discussion on the relevance of a Pareto approach to the study of nature. One outcome of the current MCC study is a suggested analogy between species and design concepts. Another resulting suggestion is that multi-fitness dynamic visualization of natural systems should be of a scientific value, and in particular for the pursuit of understanding of natural evolution by way of ∈dexthought experimentthought experiments. It is hoped, at best, that MCC would direct thinking into fruitful new observations on the multi-fitness aspects of natural adaptation. Alternatively, it is expected that such studies would allow a better understanding of the similarities and dissimilarities between the creation of natural and artificial systems by adaptive processes. [ABSTRACT FROM AUTHOR]

This chapter centres around the use of interactive evolutionary computation as a search and exploration tool for open-ended contexts in design. Such contexts are characterized by poor initial definition and uncertainty in terms of objectives, constraints and defining variable parameters. The objective of the research presented is the realization of ‘user-centric' intelligent systems, i.e., systems which can overcome initial lack of understanding and associated uncertainty, whilst also stimulating innovation and creativity through a high degree of human / machine interaction. Two application areas are used to illustrate how, through the adoption of bespoke visualization techniques, flexible representations, and machine learning agents that ‘observe' the evolutionary process, this objective can be achieved. [ABSTRACT FROM AUTHOR]

In optimization studies, often researchers are interested in finding one or more optimal or near-optimal solutions. In this chapter, we describe a systematic optimization-cum-analysis procedure which performs a task beyond simply finding optimal solutions, but first finds a set of near-Pareto-optimal solutions and then analyses them to unveil salient knowledge about properties which make a solution optimal. The proposed ‘innovization' task is explained and its working procedure is illustrated on a number of engineering design tasks. The variety of problems chosen in the chapter and the resulting innovations obtained for each problem amply demonstrate the usefulness of the proposed innovization task. The procedure is a by-product of performing a routine multiobjective optimization for a design task and in our opinion portrays an important process of knowledge discovery which may not be possible to achieve by other means. [ABSTRACT FROM AUTHOR]

In this chapter, we discuss the application of evolutionary multiobjective optimization (EMO) to association rule mining. Especially, we focus our attention on classification rule mining in a continuous feature space where the antecedent and consequent parts of each rule are an interval vector and a class label, respectively. First we explain evolutionary multiobjective classification rule mining techniques. Those techniques are roughly categorized into two approaches. In one approach, each classification rule is handled as an individual. An EMO algorithm is used to search for Pareto-optimal rules with respect to some rule evaluation criteria such as support and confidence. In the other approach, each rule set is handled as an individual. An EMO algorithm is used to search for Pareto-optimal rule sets with respect to some rule set evaluation criteria such as accuracy and complexity. Next we explain evolutionary multiobjective rule selection as a post-processing procedure in classification rule mining. Pareto-optimal rule sets are found from a large number of candidate classification rules, which are extracted from a database using an association rule mining technique. Then we examine the effectiveness of evolutionary multiobjective rule selection through computational experiments on some benchmark classification problems. Finally we examine the use of Pareto-optimal and near Pareto-optimal rules as candidate rules in evolutionary multiobjective rule selection. [ABSTRACT FROM AUTHOR]

The work presented in this chapter is concerned with the identification and modelling of nonlinear dynamical systems using multiobjective evolutionary algorithms (MOEAs). This problem involves the processes of structure selection, parameter estimation, model performance and model validation and defines a complex solution space. Evolutionary algorithms (EAs), in particular genetic programming (GP), are found to provide a way of evolving models to solve this identification and modelling problem, and their use is extended to encompass multiobjective functions. Multiobjective genetic programming (MOGP) is then applied to multiple conflicting objectives in order to yield a set of simple and valid human-understandable models which can reproduce the behaviour of a given unknown system. [ABSTRACT FROM AUTHOR]