Author: Community

Distributed differential evolution with explorative–exploitative population families

Abstract  This paper proposes a novel distributed differential evolution algorithm, namely Distributed Differential Evolution with Explorative–Exploitative
Population Families (DDE-EEPF). In DDE-EEPF the sub-populations are grouped into tw…

Abstract  This paper proposes a novel distributed differential evolution algorithm, namely Distributed Differential Evolution with Explorative–Exploitative
Population Families (DDE-EEPF). In DDE-EEPF the sub-populations are grouped into two families. Sub-populations belonging to
the first family have constant population size, are arranged according to a ring topology and employ a migration mechanism
acting on the individuals with the best performance. This first family of sub-populations has the role of exploring the decision
space and constituting an external evolutionary framework. The second family is composed of sub-populations with a dynamic
population size: the size is progressively reduced. The sub-populations belonging to the second family are highly exploitative
and are supposed to quickly detect solutions with a high performance. The solutions generated by the second family then migrate
to the first family. In order to verify its viability and effectiveness, the DDE-EEPF has been run on a set of various test
problems and compared to four distributed differential evolution algorithms. Numerical results show that the proposed algorithm
is efficient for most of the analyzed problems, and outperforms, on average, all the other algorithms considered in this study.

  • Content Type Journal Article
  • Pages 343-371
  • DOI 10.1007/s10710-009-9089-y
  • Authors
    • Matthieu Weber, University of Jyväskylä Department of Mathematical Information Technology P.O. Box 35 (Agora) 40014 Jyväskylä Finland
    • Ferrante Neri, University of Jyväskylä Department of Mathematical Information Technology P.O. Box 35 (Agora) 40014 Jyväskylä Finland
    • Ville Tirronen, University of Jyväskylä Department of Mathematical Information Technology P.O. Box 35 (Agora) 40014 Jyväskylä Finland

Trace monoids with idempotent generators and measure-only quantum automata

Abstract  In this paper, we analyze a model of 1-way quantum automaton where only measurements are allowed (
MON
-1qfa). The automaton works on a compatibility alphabet

(S, E)
of observables and its probabilistic behavior is a formal ser…

Abstract  

In this paper, we analyze a model of 1-way quantum automaton where only measurements are allowed (
MON
-1qfa). The automaton works on a compatibility alphabet

(S, E)

of observables and its probabilistic behavior is a formal series on the free partially commutative monoid

FI(S, E)

with idempotent generators. We prove some properties of this class of formal series and we apply the results to analyze the
class

LMO(S, E)

of languages recognized by
MON
-1qfa’s with isolated cut point. In particular, we prove that

LMO(S, E)

is a boolean algebra of recognizable languages with finite variation, and that

LMO(S, E)

is properly contained in the recognizable languages, with the exception of the trivial case of complete commutativity.

  • Content Type Journal Article
  • DOI 10.1007/s11047-009-9154-8
  • Authors
    • Alberto Bertoni, Università degli Studi di Milano Dipartimento di Scienze dell’Informazione via Comelico 39 20135 Milano Italy
    • Carlo Mereghetti, Università degli Studi di Milano Dipartimento di Scienze dell’Informazione via Comelico 39 20135 Milano Italy
    • Beatrice Palano, Università degli Studi di Milano Dipartimento di Scienze dell’Informazione via Comelico 39 20135 Milano Italy

Deterministic and stochastic P systems for modelling cellular processes

Abstract  This paper presents two approaches based on metabolic and stochastic P systems, together with their associated analysis methods,
for modelling biological systems and illustrates their use through two case studies.

Content Type…

Abstract  

This paper presents two approaches based on metabolic and stochastic P systems, together with their associated analysis methods,
for modelling biological systems and illustrates their use through two case studies.

  • Content Type Journal Article
  • DOI 10.1007/s11047-009-9158-4
  • Authors
    • Marian Gheorghe, The University of Sheffield Department of Computer Science Regent Court, Portobello Street Sheffield S1 4DP UK
    • Vincenzo Manca, The University of Verona Department of Computer Science Strada Le Grazie 15 37134 Verona Italy
    • Francisco J. Romero-Campero, The University of Nottingham School of Computer Science Jubilee Campus Nottingham NG8 1BB UK

Robust self-assembly of graphs

Abstract  Self-assembly is a process in which small building blocks interact autonomously to form larger structures. A recently studied
model of self-assembly is the Accretive Graph Assembly Model whereby an edge-weighted graph is assembled …

Abstract  

Self-assembly is a process in which small building blocks interact autonomously to form larger structures. A recently studied
model of self-assembly is the Accretive Graph Assembly Model whereby an edge-weighted graph is assembled one vertex at a time
starting from a designated seed vertex. The weight of an edge specifies the magnitude of attraction (positive weight) or repulsion
(negative weight) between adjacent vertices. It is feasible to add a vertex to the assembly if the total attraction minus repulsion of the already built neighbors exceeds a certain threshold,
called the assembly temperature. This model naturally generalizes the extensively studied Tile Assembly Model. A natural question
in graph self-assembly is to determine whether or not there exists a sequence of feasible vertex additions to realize the
entire graph. However, even when it is feasible to realize the assembly, not much can be inferred about its likelihood of
realization in practice due to the uncontrolled nature of the self-assembly process. Motivated by this, we introduce the robust self-assembly problem where the goal is to determine if every possible sequence of feasible vertex additions leads to the
completion of the assembly. We show that the robust self-assembly problem is co-NP-complete even on planar graphs with two
distinct edge weights. We then examine the tractability of the robust self-assembly problem on a natural subclass of planar
graphs, namely grid graphs. We identify structural conditions that determine whether or not a grid graph can be robustly self-assembled,
and give poly-time algorithms to determine this for several interesting cases of the problem. Finally, we also show that the
problem of counting the number of feasible orderings that lead to the completion of an assembly is #P-complete.

  • Content Type Journal Article
  • DOI 10.1007/s11047-009-9149-5
  • Authors
    • Stanislav Angelov, Google, Inc. New York NY 10011 USA
    • Sanjeev Khanna, University of Pennsylvania Department of Computer and Information Science, School of Engineering and Applied Sciences Philadelphia PA 19104 USA
    • Mirkó Visontai, University of Pennsylvania Department of Mathematics, School of Arts and Sciences Philadelphia PA 19104 USA

Deadline extended for Tenth Anniversary Special Issue on Progress in Genetic Programming and Evolvable Machines

The deadline has been extended for submissions to the Tenth Anniversary Special Issue on Progress in Genetic Programming and Evolvable Machines; see the call for papers for details.

The deadline has been extended for submissions to the Tenth Anniversary Special Issue on Progress in Genetic Programming and Evolvable Machines; see the call for papers for details.

On spiking neural P systems

Abstract  This work deals with several aspects concerning the formal verification of SN P systems and the computing power of some variants.
A methodology based on the information given by the transition diagram associated with an SN P system…

Abstract  

This work deals with several aspects concerning the formal verification of SN P systems and the computing power of some variants.
A methodology based on the information given by the transition diagram associated with an SN P system is presented. The analysis
of the diagram cycles codifies invariants formulae which enable us to establish the soundness and completeness of the system
with respect to the problem it tries to resolve. We also study the universality of asynchronous and sequential SN P systems
and the capability these models have to generate certain classes of languages. Further, by making a slight modification to
the standard SN P systems, we introduce a new variant of SN P systems with a special I/O mode, called SN P modules, and study their computing power. It is demonstrated that, as string language acceptors and transducers, SN P modules can
simulate several types of computing devices such as finite automata, a-finite transducers, and systolic trellis automata.

  • Content Type Journal Article
  • DOI 10.1007/s11047-009-9159-3
  • Authors
    • Oscar H. Ibarra, University of California Department of Computer Science Santa Barbara CA 93106 USA
    • Mario J. Pérez-Jiménez, University of Seville Department of Computer Science and AI Sevilla Spain
    • Takashi Yokomori, Waseda University Department of Mathematics, Faculty of Education and Integrated Arts and Sciences 1-6-1 Nishi-waseda, Shinjuku-ku Tokyo 169-8050 Japan

Computing with energy and chemical reactions

Abstract  Taking inspiration from some laws of Nature—energy transformation and chemical reactions—we consider two different paradigms
of computation in the framework of Membrane Computing. We first study the computational power of energ…

Abstract  

Taking inspiration from some laws of Nature—energy transformation and chemical reactions—we consider two different paradigms
of computation in the framework of Membrane Computing. We first study the computational power of energy-based P systems, a
model of membrane systems where a fixed amount of energy is associated with each object and the rules transform objects by
manipulating their energy. We show that if we assign local priorities to the rules, then energy-based P systems are as powerful
as Turing machines; otherwise, they can be simulated by vector addition systems, and hence are not universal. Then, we consider
stochastic membrane systems where computations are performed through chemical networks. We show how molecular species and
chemical reactions can be used to describe and simulate the functioning of Fredkin gates and circuits. We conclude the paper
with some research topics related to computing with energy-based P systems and with chemical reactions.

  • Content Type Journal Article
  • DOI 10.1007/s11047-009-9160-x
  • Authors
    • Alberto Leporati, Università degli Studi di Milano – Bicocca Dipartimento di Informatica, Sistemistica e Comunicazione Viale Sarca 336 20126 Milano Italy
    • Daniela Besozzi, Università degli Studi di Milano Dipartimento di Informatica e Comunicazione Via Comelico 39 20135 Milano Italy
    • Paolo Cazzaniga, Università degli Studi di Milano – Bicocca Dipartimento di Informatica, Sistemistica e Comunicazione Viale Sarca 336 20126 Milano Italy
    • Dario Pescini, Università degli Studi di Milano – Bicocca Dipartimento di Informatica, Sistemistica e Comunicazione Viale Sarca 336 20126 Milano Italy
    • Claudio Ferretti, Università degli Studi di Milano – Bicocca Dipartimento di Informatica, Sistemistica e Comunicazione Viale Sarca 336 20126 Milano Italy

CIG-2009 proceedings available online

Pier Luca Lanzi just sent a note saying saying that the proceedings of the 2009 Symposium on Computational Intelligence and Games (CIG-2009) are now available on-line at
http://www.ieee-cig.org/cig-2009/Proceedings/
Related Posts

Pier Luca Lanzi just sent a note saying saying that the proceedings of the 2009 Symposium on Computational Intelligence and Games (CIG-2009) are now available on-line at

http://www.ieee-cig.org/cig-2009/Proceedings/

Related Posts

    GP challenge: evolving energy function for protein structure prediction

    Abstract  One of the key elements in protein structure prediction is the ability to distinguish between good and bad candidate structures.
    This distinction is made by estimation of the structure energy. The energy function used in the best s…

    Abstract  One of the key elements in protein structure prediction is the ability to distinguish between good and bad candidate structures.
    This distinction is made by estimation of the structure energy. The energy function used in the best state-of-the-art automatic
    predictors competing in the most recent CASP (Critical Assessment of Techniques for Protein Structure Prediction) experiment
    is defined as a weighted sum of a set of energy terms designed by experts. We hypothesised that combining these terms more
    freely will improve the prediction quality. To test this hypothesis, we designed a genetic programming algorithm to evolve
    the protein energy function. We compared the predictive power of the best evolved function and a linear combination of energy
    terms featuring weights optimised by the Nelder–Mead algorithm. The GP based optimisation outperformed the optimised linear
    function. We have made the data used in our experiments publicly available in order to encourage others to further investigate
    this challenging problem by using GP and other methods, and to attempt to improve on the results presented here.

    • Content Type Journal Article
    • Category Original Paper
    • DOI 10.1007/s10710-009-9087-0
    • Authors
      • Paweł Widera, University of Nottingham School of Computer Science Nottingham NG8 1BB UK
      • Jonathan M. Garibaldi, University of Nottingham School of Computer Science Nottingham NG8 1BB UK
      • Natalio Krasnogor, University of Nottingham School of Computer Science Nottingham NG8 1BB UK

    Preface

    Preface
    Content Type Journal ArticleDOI 10.1007/s11047-009-9161-9Authors
    Paola Bonizzoni, Milan ItalyGheorghe Paun, Bucharest RomaniaGrzegorz Rozenberg, Leiden The NetherlandsClaudio Zandron, Milan Italy

    Journal Natural ComputingOnline ISSN 1…

    Preface

    • Content Type Journal Article
    • DOI 10.1007/s11047-009-9161-9
    • Authors
      • Paola Bonizzoni, Milan Italy
      • Gheorghe Paun, Bucharest Romania
      • Grzegorz Rozenberg, Leiden The Netherlands
      • Claudio Zandron, Milan Italy