Tag: Natural Computing

Evolutionary high-dimensional QoS optimization for safety-critical utility communication networks

Abstract  This paper proposes and evaluates an evolutionary multiobjective optimization algorithm, called EVOLT, which heuristically optimizes quality of service (QoS) parameters in communication networks. EVOLT uses a population of individua…

Abstract  

This paper proposes and evaluates an evolutionary multiobjective optimization algorithm, called EVOLT, which heuristically optimizes quality of service (QoS) parameters in communication networks. EVOLT uses a population of individuals, each of which represents a set of QoS parameters, and evolves the individuals via genetic
operators such as crossover, mutation and selection for satisfying given QoS requirements. For evaluating EVOLT in real-world settings that have high-dimensional parameter and optimization objective spaces, this paper focuses on QoS
optimization in safety-critical communication networks for electric power utilities. Simulation results show that EVOLT outperforms a well-known existing evolutionary algorithm for multiobjective optimization and efficiently obtains quality
QoS parameters with acceptable computational costs. Moreover, EVOLT visualizes obtained QoS parameters in a self-organizing map in order to aid network administrators to intuitively understand
the QoS parameters and the tradeoffs among optimization objectives.

  • Content Type Journal Article
  • Pages 1-28
  • DOI 10.1007/s11047-011-9252-2
  • Authors
    • Paskorn Champrasert, Department of Computer Science, University of Massachusetts, Boston, Boston, MA, USA
    • Junichi Suzuki, Department of Computer Science, University of Massachusetts, Boston, Boston, MA, USA
    • Tetsuo Otani, Central Research Institute of Electric Power Industry, Tokyo, Japan

Design of a biomolecular device that executes process algebra

Abstract  
Process algebras are widely used for defining the formal semantics of concurrent communicating processes. This paper considers stochastic π-calculus which is a particularly expressive kind of process algebra providing a specifica…

Abstract  

Process algebras are widely used for defining the formal semantics of concurrent communicating processes. This paper considers stochastic π-calculus which is a particularly expressive kind of process algebra providing a specification of probabilities of process behavior
such as stochastic delays, communication and branching, as well as rates of execution. In this paper, we implement stochastic
π-calculus at the molecular scale, providing a design for a DNA-based biomolecular device that executes the stochastic π-calculus. Designing this device is challenging due to the requirement that a specific pair
of processes must be able to communicate repeatedly; this appears to rule out the use of many of the usual classes of DNA
computation (e.g., tiling self-assembly or hybridization chain reactions) that allow computational rule molecules to float
freely in solution within a test tube. Our design of the molecular stochastic π-calculus system makes use of a modified form
of Whiplash-PCR (WPCR) machines. In our machine which we call π-WPCR machine, we connect (via a tethering DNA nanostructure) a number of DNA strands, each of which corresponds to a π-WPCR machines.
This collection of π-WPCR machines is used to execute distinct concurrent processes, each with its own distinct program. To
implement process communication protocols, our modifications to the original design of WPCR machines include the incorporation
of additional secondary structure in the single strand (stem-loop) as well as multiple-temperature thermal cycling. The enforced locality of the collection of π-WPCR machines insures that the same pair (or any subset of the entire collection) of processes be able to repeatedly communicate with each other. Additionally, our
design of the devices include implementation of sequential execution of multiple process and limited process branching through use of restriction enzymes.

  • Content Type Journal Article
  • Pages 447-466
  • DOI 10.1007/s11047-010-9235-8
  • Authors
    • Urmi Majumder, Department of Computer Science, Duke University, Durham, NC USA
    • John H. Reif, Department of Computer Science, Duke University, Durham, NC USA

Mutual mobile membranes with objects on surface

Abstract  In this paper we study systems of mutual mobile membranes with objects on surface using pino/exo/phago rules. Their rules
are applicable whenever there is a mutual agreement between membranes expressed by appropriate objects and co…

Abstract  

In this paper we study systems of mutual mobile membranes with objects on surface using pino/exo/phago rules. Their rules
are applicable whenever there is a mutual agreement between membranes expressed by appropriate objects and co-objects on their
surfaces. We investigate the computational power of these systems, and also relate them to brane calculi by encoding the PEP
fragment of brane calculus into the systems of mutual mobile membranes with objects on surface.

  • Content Type Journal Article
  • Pages 777-793
  • DOI 10.1007/s11047-011-9249-x
  • Authors
    • Bogdan Aman, A. I. Cuza University, Blvd. Carol I no. 11, 700506 Iasi, Romania
    • Gabriel Ciobanu, Romanian Academy, Institute of Computer Science, Iasi, Romania

Editorial: Computing with biomolecules

Editorial: Computing with biomolecules
Content Type Journal ArticlePages 775-776DOI 10.1007/s11047-011-9251-3Authors
Erzsébet Csuhaj-Varjú, Hungarian Academy of Sciences, Budapest, HungaryKai Salomaa, Queen’s University, Kingston, ON, Canada

…

Editorial: Computing with biomolecules

  • Content Type Journal Article
  • Pages 775-776
  • DOI 10.1007/s11047-011-9251-3
  • Authors
    • Erzsébet Csuhaj-Varjú, Hungarian Academy of Sciences, Budapest, Hungary
    • Kai Salomaa, Queen’s University, Kingston, ON, Canada

Improving convergence of evolutionary multi-objective optimization with local search: a concurrent-hybrid algorithm

Abstract  A local search method is often introduced in an evolutionary optimization algorithm, to enhance its speed and accuracy of
convergence to optimal solutions. In multi-objective optimization problems, the implementation of local searc…

Abstract  

A local search method is often introduced in an evolutionary optimization algorithm, to enhance its speed and accuracy of
convergence to optimal solutions. In multi-objective optimization problems, the implementation of local search is a non-trivial
task, as determining a goal for local search in presence of multiple conflicting objectives becomes a difficult task. In this
paper, we borrow a multiple criteria decision making concept of employing a reference point based approach of minimizing an
achievement scalarizing function and integrate it as a search operator with a concurrent approach in an evolutionary multi-objective
algorithm. Simulation results of the new concurrent-hybrid algorithm on several two to four-objective problems compared to
a serial approach, clearly show the importance of local search in aiding a computationally faster and accurate convergence
to the Pareto optimal front.

  • Content Type Journal Article
  • Pages 1-24
  • DOI 10.1007/s11047-011-9250-4
  • Authors
    • Karthik Sindhya, Department of Mathematical Information Technology, P.O. Box 35 (Agora), 40014 University of Jyväskylä, Finland
    • Kalyanmoy Deb, Aalto University School of Economics, Department of Business Technology, P.O. Box 21220, 00076 Aalto, Finland
    • Kaisa Miettinen, Department of Mathematical Information Technology, P.O. Box 35 (Agora), 40014 University of Jyväskylä, Finland

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

Abstract  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 computa…

Abstract  

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.

  • Content Type Journal Article
  • Pages 429-445
  • DOI 10.1007/s11047-010-9238-5
  • Authors
    • Paolo Bottoni, Department of Computer Science, “Sapienza” University of Rome, Via Salaria 113, 00198 Rome, Italy
    • Anna Labella, Department of Computer Science, “Sapienza” University of Rome, Via Salaria 113, 00198 Rome, Italy
    • Florin Manea, Faculty of Computer Science, Otto-von-Guericke University, P.O. Box 41 20, 39016 Magdeburg, Germany
    • Victor Mitrana, Faculty of Mathematics, University of Bucharest, Str. Academiei 14, 010014 Bucharest, Romania
    • Ion Petre, Department of Information Technologies, Åbo Akademi University, ICT-building, Joukahaisenkatu 3-5 A, 20520 Turku, Finland
    • Jose M. Sempere, Department of Information Systems and Computation, Technical University of Valencia, Camino de Vera s/n., 46022 Valencia, Spain

Introduction

Introduction
Content Type Journal ArticlePages 1-3DOI 10.1007/s11047-011-9247-zAuthors
José Félix Costa, Department of Mathematics, Instituto Superior Técnico Universidade Técnica de Lisboa, Lisboa, PortugalNachum Dershowitz, School of Computer …

Introduction

  • Content Type Journal Article
  • Pages 1-3
  • DOI 10.1007/s11047-011-9247-z
  • Authors
    • José Félix Costa, Department of Mathematics, Instituto Superior Técnico Universidade Técnica de Lisboa, Lisboa, Portugal
    • Nachum Dershowitz, School of Computer Science, Tel Aviv University, Ramat Aviv, Israel

Graph multiset transformation: a new framework for massively parallel computation inspired by DNA computing

Abstract  In this paper, graph multiset transformation is introduced and studied as a novel type of parallel graph transformation. The
basic idea is that graph transformation rules may be applied to all or at least some members of a multiset…

Abstract  

In this paper, graph multiset transformation is introduced and studied as a novel type of parallel graph transformation. The
basic idea is that graph transformation rules may be applied to all or at least some members of a multiset of graphs simultaneously
providing a computational step with the possibility of massive parallelism in this way. As a consequence, graph problems in
the class NP can be solved by a single computation of polynomial length for each input graph.

  • Content Type Journal Article
  • Pages 961-986
  • DOI 10.1007/s11047-010-9245-6
  • Authors
    • Hans-Jörg Kreowski, Department of Computer Science, University of Bremen, P.O. Box 330440, 28334 Bremen, Germany
    • Sabine Kuske, Department of Computer Science, University of Bremen, P.O. Box 330440, 28334 Bremen, Germany

The computational power of membrane systems under tight uniformity conditions

Abstract  We apply techniques from complexity theory to a model of biological cellular membranes known as membrane systems or P-systems.
Like Boolean circuits, membrane systems are defined as uniform families of computational devices. To dat…

Abstract  

We apply techniques from complexity theory to a model of biological cellular membranes known as membrane systems or P-systems.
Like Boolean circuits, membrane systems are defined as uniform families of computational devices. To date, polynomial time
uniformity has been the accepted uniformity notion for membrane systems. Here, we introduce the idea of using AC
0-uniformity and investigate the computational power of membrane systems under these tighter conditions. It turns out that
the computational power of some systems is lowered from P to NL when using AC
0-semi-uniformity, so we argue that this is a more reasonable uniformity notion for these systems as well as others. Interestingly,
other P-semi-uniform systems that are known to be lower-bounded by P are shown to retain their P lower-bound under the new tighter semi-uniformity condition. Similarly, a number of membrane systems that are known to solve
PSPACE-complete problems retain their computational power under tighter uniformity conditions.

  • Content Type Journal Article
  • Pages 613-632
  • DOI 10.1007/s11047-010-9244-7
  • Authors
    • Niall Murphy, Department of Computer Science, National University of Ireland Maynooth, Co. Kildare, Ireland
    • Damien Woods, California Institute of Technology, Pasadena, CA 91125, USA

Evolutionary computation approaches to the Curriculum Sequencing problem

Abstract  Within the field of e-Learning, a learning path represents a match between a learner profile and his preferences from one
side, and the learning content presentation and the pedagogical requirements from the other side. The Curricu…

Abstract  

Within the field of e-Learning, a learning path represents a match between a learner profile and his preferences from one
side, and the learning content presentation and the pedagogical requirements from the other side. The Curriculum Sequencing
problem (CS) concerns the dynamic generation of a personal optimal learning path for a learner. This problem has gained an
increased research interest in the last decade, as it is not possible to have a single learning path that suits every learner
in the widely heterogeneous e-Learning environment. Since this problem is NP-hard, heuristics and meta-heuristics are usually
used to approximate its solutions, in particular Evolutionary Computation approaches (EC). In this paper, a review of recent
developments in the application of EC approaches to the CS problem is presented. A classification of these approaches is provided
with emphasis on the tools necessary for facilitating learning content reusability and automated sequencing.

  • Content Type Journal Article
  • Pages 891-920
  • DOI 10.1007/s11047-010-9246-5
  • Authors
    • Sarab Al-Muhaideb, Department of Computer and Information Sciences, College for Women, Prince Sultan University, P.O. Box 53073, Riyadh, 11586 Saudi Arabia
    • Mohamed El Bachir Menai, Department of Computer Science, College of Computer and Information Sciences, King Saud University, P.O. Box 51178, Riyadh, 11543 Saudi Arabia