Tag: Natural Computing

A genetic algorithm for the Zen Puzzle Garden game

Abstract  In this paper we present a novel genetic algorithm (GA) solution to a simple yet challenging commercial puzzle game known
as Zen Puzzle Garden (ZPG). We describe the game in detail, before presenting a suitable encoding scheme and …

Abstract  

In this paper we present a novel genetic algorithm (GA) solution to a simple yet challenging commercial puzzle game known
as Zen Puzzle Garden (ZPG). We describe the game in detail, before presenting a suitable encoding scheme and fitness function
for candidate solutions. By constructing a simulator for the game, we compare the performance of the GA with that of the A*
algorithm. We show that the GA is competitive with informed search in terms of solution quality, and significantly out-performs
it in terms of computational resource requirements. By highlighting relevant features of the game we hope to stimulate further
work on its study, and we conclude by presenting several possible areas for future research.

  • Content Type Journal Article
  • Pages 1-7
  • DOI 10.1007/s11047-011-9284-7
  • Authors
    • Martyn Amos, School of Computing, Mathematics and Digital Technology, Manchester Metropolitan University, Manchester, M1 5GD UK
    • Jack Coldridge, School of Computing, Mathematics and Digital Technology, Manchester Metropolitan University, Manchester, M1 5GD UK

Hierarchical self assembly of patterns from the Robinson tilings: DNA tile design in an enhanced Tile Assembly Model

Abstract  We introduce a hierarchical self assembly algorithm that produces the quasiperiodic patterns found in the Robinson tilings
and suggest a practical implementation of this algorithm using DNA origami tiles. We modify the abstract Til…

Abstract  

We introduce a hierarchical self assembly algorithm that produces the quasiperiodic patterns found in the Robinson tilings
and suggest a practical implementation of this algorithm using DNA origami tiles. We modify the abstract Tile Assembly Model
(aTAM), to include active signaling and glue activation in response to signals to coordinate the hierarchical assembly of
Robinson patterns of arbitrary size from a small set of tiles according to the tile substitution algorithm that generates
them. Enabling coordinated hierarchical assembly in the aTAM makes possible the efficient encoding of the recursive process
of tile substitution.

  • Content Type Journal Article
  • Pages 1-16
  • DOI 10.1007/s11047-011-9268-7
  • Authors
    • Jennifer E. Padilla, Monrovia, CA 91016, USA
    • Wenyan Liu, Department of Chemistry, New York University, New York, NY 10003, USA
    • Nadrian C. Seeman, Department of Chemistry, New York University, New York, NY 10003, USA

Towards collaborative feature extraction for face recognition

Abstract  Principal components analysis has become a popular preprocessing method to avoid the small sample size problem for most of
the supervised graph embedding methods. Nevertheless, there is potential loss of relevant information when p…

Abstract  

Principal components analysis has become a popular preprocessing method to avoid the small sample size problem for most of
the supervised graph embedding methods. Nevertheless, there is potential loss of relevant information when projecting the
data onto the space defined by the principal Eigenfaces when the number of individuals in the gallery is large. This paper
introduces a new collaborative feature extraction method based on projection pursuit, as a robust preprocessing for supervised
embedding methods. A previously proposed projection index was adopted as a measure of interestingness, based on a weighted
sum of six state of the art indices. We compare our collaborative feature extraction technique against principal component
analysis as preprocessing stage for Laplacianfaces. For completeness, results for Eigenfaces and Fisherfaces are included.
Experimental results to demonstrate the robustness of our approach against changes in facial expression and lighting are presented.

  • Content Type Journal Article
  • Pages 1-10
  • DOI 10.1007/s11047-011-9285-6
  • Authors
    • Eduardo Rodriguez, Department of Electrical Engineering and Electronics, University of Liverpool, Liverpool, UK
    • Konstantinos Nikolaidis, Department of Electrical Engineering and Electronics, University of Liverpool, Liverpool, UK
    • Tingting Mu, School of Computing, Informatics & Media, University of Bradford, Bradford, UK
    • Jason F. Ralph, Department of Electrical Engineering and Electronics, University of Liverpool, Liverpool, UK
    • John Y. Goulermas, Department of Electrical Engineering and Electronics, University of Liverpool, Liverpool, UK

Faster synchronization in P systems

Abstract  In the field of molecular computing, in particular P systems, synchronization is an important requirement for composing or
sequentially linking together congenial P system activities. We provide a deterministic algorithm to the Fir…

Abstract  

In the field of molecular computing, in particular P systems, synchronization is an important requirement for composing or
sequentially linking together congenial P system activities. We provide a deterministic algorithm to the Firing Squad Synchronization Problem, for digraph-based P systems, which runs in 3e + 11 steps, where e is the eccentricity of the general. Our algorithm uses a convenient framework, called simple P modules, which embraces the
essential features of several popular types of P systems.

  • Content Type Journal Article
  • Pages 1-9
  • DOI 10.1007/s11047-011-9271-z
  • Authors
    • Michael J. Dinneen, Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand
    • Yun-Bum Kim, Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand
    • Radu Nicolescu, Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand

Parallel predator–prey interaction for evolutionary multi-objective optimization

Abstract  Over the last decade, the predator–prey model (PPM) has emerged as an alternative algorithmic approach to multi-objective
evolutionary optimization, featuring a very simple abstraction from natural species interplay and extensive…

Abstract  

Over the last decade, the predator–prey model (PPM) has emerged as an alternative algorithmic approach to multi-objective
evolutionary optimization, featuring a very simple abstraction from natural species interplay and extensive parallelization
potential. While substantial research has been done on the former, we for the first time review the PPM in the light of parallelization:
We analyze the architecture and classify its components with respect to a recent taxonomy for parallel multi-objective evolutionary
algorithms. Further, we theoretically examine benefits of simultaneous predator collaboration on a spatial population structure
and give insights into solution emergence. On the prey level, we integrate a gradient-based local search mechanism to exploit
problem independent parallelization and hybridize the model in order to achieve faster convergence and solution stability.
This way, we achieve a good approximation and unfold further parallelization potential for the model.

  • Content Type Journal Article
  • Pages 1-15
  • DOI 10.1007/s11047-011-9266-9
  • Authors
    • Christian Grimme, Robotics Research Institute, Section Information Technology, TU Dortmund University, Otto-Hahn-Strasse 8, 44227 Dortmund, Germany
    • Joachim Lepping, Robotics Research Institute, Section Information Technology, TU Dortmund University, Otto-Hahn-Strasse 8, 44227 Dortmund, Germany
    • Alexander Papaspyrou, Robotics Research Institute, Section Information Technology, TU Dortmund University, Otto-Hahn-Strasse 8, 44227 Dortmund, Germany

Digital Ecosystems: Ecosystem-Oriented Architectures

Abstract  We view Digital Ecosystems to be the digital counterparts of biological ecosystems. Here, we are concerned with the creation
of these Digital Ecosystems, exploiting the self-organising properties of biological ecosystems to evolve …

Abstract  

We view Digital Ecosystems to be the digital counterparts of biological ecosystems. Here, we are concerned with the creation
of these Digital Ecosystems, exploiting the self-organising properties of biological ecosystems to evolve high-level software
applications. Therefore, we created the Digital Ecosystem, a novel optimisation technique inspired by biological ecosystems,
where the optimisation works at two levels: a first optimisation, migration of agents which are distributed in a decentralised
peer-to-peer network, operating continuously in time; this process feeds a second optimisation based on evolutionary computing
that operates locally on single peers and is aimed at finding solutions to satisfy locally relevant constraints. The Digital
Ecosystem was then measured experimentally through simulations, with measures originating from theoretical ecology, evaluating
its likeness to biological ecosystems. This included its responsiveness to requests for applications from the user base, as
a measure of the ecological succession (ecosystem maturity). Overall, we have advanced the understanding of Digital Ecosystems,
creating Ecosystem-Oriented Architectures (EOA) where the word ecosystem is more than just a metaphor.

  • Content Type Journal Article
  • Pages 1143-1194
  • DOI 10.1007/s11047-011-9254-0
  • Authors
    • Gerard Briscoe, Department of Engineering, University of Cambridge, Cambridge, CB2 1PZ UK
    • Suzanne Sadedin, Department of Organismic and Evolutionary Biology, Harvard University, Cambridge, MA 02138, USA
    • Philippe De Wilde, Intelligent Systems Lab, Department of Computer Science, Heriot-Watt University, Edinburgh, EH14 4AS UK

Preface: Petri nets for Systems and Synthetic Biology

Preface: Petri nets for Systems and Synthetic Biology
Content Type Journal ArticlePages 987-992DOI 10.1007/s11047-011-9263-zAuthors
Monika Heiner, Brandenburg University of Technology, Cottbus, Germany

Journal Natural ComputingOnline ISSN 157…

Preface: Petri nets for Systems and Synthetic Biology

  • Content Type Journal Article
  • Pages 987-992
  • DOI 10.1007/s11047-011-9263-z
  • Authors
    • Monika Heiner, Brandenburg University of Technology, Cottbus, Germany

Topological active volume 3D segmentation model optimized with genetic approaches

Abstract  The topological active volumes is an active model focused on 3D segmentation tasks. It is based on the 2D Topological Active
Nets model and provides information about the surfaces and the inside of the detected objects in the scene…

Abstract  

The topological active volumes is an active model focused on 3D segmentation tasks. It is based on the 2D Topological Active
Nets model and provides information about the surfaces and the inside of the detected objects in the scene. This paper proposes
new optimization approaches based on genetic algorithms that improve the results of the 3D segmentations and overcome some
drawbacks of the model related to parameter tuning or noise conditions. The hybridization of the genetic algorithm with a
greedy local search allows the treatment of topological changes in the model, with the possibility of an automatic subdivision
of the topological active volume. This combination integrates the advantages of the global and local search procedures in
the segmentation process.

  • Content Type Journal Article
  • Pages 1-18
  • DOI 10.1007/s11047-011-9261-1
  • Authors
    • Jorge Novo, Department of Computer Science, University of A Coruña, Campus de Elviña s/n, 15071 A Coruña, Spain
    • Noelia Barreira, Department of Computer Science, University of A Coruña, Campus de Elviña s/n, 15071 A Coruña, Spain
    • Manuel González Penedo, Department of Computer Science, University of A Coruña, Campus de Elviña s/n, 15071 A Coruña, Spain
    • José Santos, Department of Computer Science, University of A Coruña, Campus de Elviña s/n, 15071 A Coruña, Spain

Approximating Mexican highways with slime mould

Abstract  Plasmodium of Physarum polycephalum is a single cell visible by unaided eye. During its foraging behavior the cell spans spatially distributed sources of nutrients
with a protoplasmic network. The geometrical structure of the proto…

Abstract  

Plasmodium of Physarum polycephalum is a single cell visible by unaided eye. During its foraging behavior the cell spans spatially distributed sources of nutrients
with a protoplasmic network. The geometrical structure of the protoplasmic networks allows the plasmodium to optimize transport
of nutrients between remote parts of its body. Assuming major Mexican cities are sources of nutrients that need to be distributed
across Mexico, how much does the structure of the Physarum protoplasmic network correspond to the structure of Mexican Federal highway network? To address the issue we undertook a
series of laboratory experiments with living P. polycephalum. We represent geographical locations of major cities (19 locations) by oat flakes, place a piece of plasmodium in the area
corresponding to Mexico city, record the plasmodium’s foraging behavior and extract topology of the resulting nutrient transport
networks. Results of our experiments show that the protoplasmic network formed by Physarum is isomorphic, subject to limitations imposed, to a network of principal highways. Ideas and results in the paper may contribute
towards future developments in bio-inspired road planning.

  • Content Type Journal Article
  • Pages 1195-1214
  • DOI 10.1007/s11047-011-9255-z
  • Authors
    • Andrew Adamatzky, Unconventional Computing Centre, University of the West of England, Bristol, BS16 1QY UK
    • Genaro J. Martínez, Unconventional Computing Centre, University of the West of England, Bristol, BS16 1QY UK
    • Sergio V. Chapa-Vergara, Ingeniería Eléctrica, Departamento de Computación, Centro de Investigación y de Estudios Avanzados del Instituto Politécnico Nacional, Mexico, Mexico
    • René Asomoza-Palacio, Ingeniería Eléctrica, Departamento de Computación, Centro de Investigación y de Estudios Avanzados del Instituto Politécnico Nacional, Mexico, Mexico
    • Christopher R. Stephens, Instituto de Ciencias Nucleares and Centro de Ciencias de la Complejidad, Universidad Nacional Autónoma de México, Mexico, Mexico

Preface: Petri nets for Systems and Synthetic Biology

Preface: Petri nets for Systems and Synthetic Biology
Content Type Journal ArticlePages 633-638DOI 10.1007/s11047-011-9253-1Authors
Monika Heiner, Brandenburg University of Technology at Cottbus, Cottbus, Germany

Journal Natural ComputingOnli…

Preface: Petri nets for Systems and Synthetic Biology

  • Content Type Journal Article
  • Pages 633-638
  • DOI 10.1007/s11047-011-9253-1
  • Authors
    • Monika Heiner, Brandenburg University of Technology at Cottbus, Cottbus, Germany