Category: Uncategorized

Forward

Forward
Content Type Journal ArticlePages 1-2DOI 10.1007/s11047-010-9240-yAuthors
Russell Deaton, Department of Computer Science and Computer Engineering, University of Arkansas, Fayetteville, AR 72701, USA

Journal Natural ComputingOnline ISS…

Forward

  • Content Type Journal Article
  • Pages 1-2
  • DOI 10.1007/s11047-010-9240-y
  • Authors
    • Russell Deaton, Department of Computer Science and Computer Engineering, University of Arkansas, Fayetteville, AR 72701, USA

Unwinding performance and power on Colossus, an unconventional computer

Abstract  In 1944 the computing machine known as Colossus became operational in support of British cryptanalysis and decryption of German
High Command wireless traffic. This first electronic digital and very unconventional computer was not a…

Abstract  

In 1944 the computing machine known as Colossus became operational in support of British cryptanalysis and decryption of German
High Command wireless traffic. This first electronic digital and very unconventional computer was not a stored-program general
purpose computer in today’s terms, despite printed claims to the contrary. At least one of these asserts Colossus was a Turing
machine. While an appropriate Turing machine can simulate the operation of Colossus, that is not an argument for generality
of computation. Nor does the behavior of Colossus resemble that of a Turing machine, much less a universal Turing machine
(UTM). Nonetheless, we shall see that a UTM could have been implemented on a clustering of the ten Colossus machines installed
at Bletchley Park, England, by the end of WWII in 1945. Improvements require even fewer machines. Several advances in input,
output, speed, processing, and applications—within the hardware capability of the time and respectful of the specification
of Colossus—are also offered.

  • Content Type Journal Article
  • Pages 1-23
  • DOI 10.1007/s11047-010-9225-x
  • Authors
    • Benjamin Wells, Departments of Computer Science and Mathematics, University of San Francisco, 2130 Fulton Street, San Francisco, CA 94117, USA

Computability in planar dynamical systems

Abstract  In this paper we explore the problem of computing attractors and their respective basins of attraction for continuous-time
planar dynamical systems. We consider C
1 systems and show that stability is in general necessary (but may …

Abstract  

In this paper we explore the problem of computing attractors and their respective basins of attraction for continuous-time
planar dynamical systems. We consider C
1 systems and show that stability is in general necessary (but may not be sufficient) to attain computability. In particular,
we show that (a) the problem of determining the number of attractors in a given compact set is in general undecidable, even
for analytic systems and (b) the attractors are semi-computable for stable systems. We also show that the basins of attraction
are semi-computable if and only if the system is stable.

  • Content Type Journal Article
  • Pages 1-18
  • DOI 10.1007/s11047-010-9230-0
  • Authors
    • Daniel Graça, DM/FCT, Universidade do Algarve, C. Gambelas, 8005-139 Faro, Portugal
    • Ning Zhong, DMS, University of Cincinnati, Cincinnati, OH 45221-0025, USA

Connecting Community-Grids by supporting job negotiation with coevolutionary Fuzzy-Systems

Abstract  We utilize a competitive coevolutionary algorithm (CA) in order to optimize the parameter set of a Fuzzy-System for job negotiation
between Community-Grids. In a Community-Grid, users are submitting jobs to their local High Perform…

Abstract  

We utilize a competitive coevolutionary algorithm (CA) in order to optimize the parameter set of a Fuzzy-System for job negotiation
between Community-Grids. In a Community-Grid, users are submitting jobs to their local High Performance Computing (HPC) sites
over time. Now, we assume that Community-Grids are interconnected such that the exchange of jobs becomes possible: Each Community
strives for minimizing the response time for their own members by trying to distribute workload to other communities in the
Grid environment. For negotiation purpose, a Fuzzy-System is used to steer each site’s decisions whether to distribute or
accept workload in a beneficial, yet egoistic direction. In such a system, it is essential that communities can only benefit
if the workload is equitably (not necessarily equally) portioned among all participants. That is, if one community egoistically
refuses to execute foreign jobs regularly, other HPC sites suffer from overloading. This, on the long run, deteriorates the
opportunity to utilize them for job delegation. Thus, the egoistic community will degrade its own average performance. This
scenario is particularly suited for the application of a competitive CA: the Fuzzy-Systems of the participating communities
are modeled as species, which evolve in different populations while having to compete within the commonly shared ecosystem.
Using real workload traces and Grid setups, we show that the opportunistic cooperation leads to significant improvements for
both each community and the overall system.

  • Content Type Journal Article
  • Pages 1-13
  • DOI 10.1007/s00500-010-0667-y
  • Authors
    • Alexander Fölling, Robotics Research Institute, TU Dortmund University, 44221 Dortmund, Germany
    • Christian Grimme, Robotics Research Institute, TU Dortmund University, 44221 Dortmund, Germany
    • Joachim Lepping, Robotics Research Institute, TU Dortmund University, 44221 Dortmund, Germany
    • Alexander Papaspyrou, Robotics Research Institute, TU Dortmund University, 44221 Dortmund, Germany

Influences on the formation and evolution of Physarum polycephalum inspired emergent transport networks

Abstract  The single-celled organism Physarum polycephalum efficiently constructs and minimises dynamical nutrient transport networks resembling proximity graphs in the Toussaint hierarchy.
We present a particle model which collectively appr…

Abstract  

The single-celled organism Physarum polycephalum efficiently constructs and minimises dynamical nutrient transport networks resembling proximity graphs in the Toussaint hierarchy.
We present a particle model which collectively approximates the behaviour of Physarum. We demonstrate spontaneous transport network formation and complex network evolution using the model and show that the model
collectively exhibits quasi-physical emergent properties, allowing it to be considered as a virtual computing material. This
material is used as an unconventional method to approximate spatially represented geometry problems by representing network
nodes as nutrient sources. We demonstrate three different methods for the construction, evolution and minimisation of Physarum-like transport networks which approximate Steiner trees, relative neighbourhood graphs, convex hulls and concave hulls. We
extend the model to adapt population size in response to nutrient availability and show how network evolution is dependent
on relative node position (specifically inter-node angle), sensor scaling and nutrient concentration. We track network evolution
using a real-time method to record transport network topology in response to global differences in nutrient concentration.
We show how Steiner nodes are utilised at low nutrient concentrations whereas direct connections to nutrients are favoured
when nutrient concentration is high. The results suggest that the foraging and minimising behaviour of Physarum-like transport networks reflect complex interplay between nutrient concentration, nutrient location, maximising foraging
area coverage and minimising transport distance. The properties and behaviour of the synthetic virtual plasmodium may be useful
in future physical instances of distributed unconventional computing devices, and may also provide clues to the generation
of emergent computation behaviour by Physarum.

  • Content Type Journal Article
  • Pages 1-25
  • DOI 10.1007/s11047-010-9223-z
  • Authors
    • Jeff Jones, Centre for Unconventional Computing, University of the West of England, Bristol, BS16 1QY UK

On the hierarchy of conservation laws in a cellular automaton

Abstract  Conservation laws in cellular automata (CA) are studied as an abstraction of the conservation laws observed in nature. In
addition to the usual real-valued conservation laws we also consider more general group-valued and semigroup-…

Abstract  

Conservation laws in cellular automata (CA) are studied as an abstraction of the conservation laws observed in nature. In
addition to the usual real-valued conservation laws we also consider more general group-valued and semigroup-valued conservation
laws. The (algebraic) conservation laws in a CA form a hierarchy, based on the range of the interactions they take into account.
The conservation laws with smaller interaction ranges are the homomorphic images of those with larger interaction ranges,
and for each specific range there is a most general law that incorporates all those with that range. For one-dimensional CA,
such a most general conservation law has—even in the semigroup-valued case—an effectively constructible finite presentation,
while for higher-dimensional CA such effective construction exists only in the group-valued case. It is even undecidable whether
a given two-dimensional CA conserves a given semigroup-valued energy assignment. Although the local properties of this hierarchy
are tractable in the one-dimensional case, its global properties turn out to be undecidable. In particular, we prove that
it is undecidable whether this hierarchy is trivial or unbounded. We point out some interconnections between the structure
of this hierarchy and the dynamical properties of the CA. In particular, we show that positively expansive CA do not have
non-trivial real-valued conservation laws.

  • Content Type Journal Article
  • Pages 1-20
  • DOI 10.1007/s11047-010-9222-0
  • Authors
    • Enrico Formenti, Laboratoire I3S, Université de Nice Sophia Antipolis, 2000 route des Lucioles, Les Algorithmes – Bât. Euclide B, BP 121, 06903 Sophia Antipolis Cedex, France
    • Jarkko Kari, Department of Mathematics, University of Turku, 20014 Turku, Finland
    • Siamak Taati, Laboratoire I3S, Université de Nice Sophia Antipolis, 2000 route des Lucioles, Les Algorithmes – Bât. Euclide B, BP 121, 06903 Sophia Antipolis Cedex, France

Unconventional complexity measures for unconventional computers

Abstract  Unconventional computers—which may, for example, exploit chemical/analogue/quantum phenomena in order to compute, rather than
electronically implementing discrete logic gates—are widely studied in both theoretical and practical…

Abstract  

Unconventional computers—which may, for example, exploit chemical/analogue/quantum phenomena in order to compute, rather than
electronically implementing discrete logic gates—are widely studied in both theoretical and practical contexts. One particular
motivation behind unconventional computation is the desire efficiently to solve classically difficult problems—we recall chemical-computer
attempts at solving
NP
-complete problems such as the Travelling Salesperson Problem—, with computational complexity theory offering the criteria
for judging this efficiency. However, care must be taken here; conventional (Turing-machine-style) complexity analysis is
not always appropriate for unconventional computers: new, non-standard computational resources, with correspondingly new complexity
measures, are often required. Accordingly, we discuss in the present paper various resources beyond merely time and space
(and, indeed, discuss various interpretations of the term ‘resource’ itself), advocating such resources’ consideration when
analysing the complexity of unconventional computers. We hope that this acts as a useful starting point for practitioners
of unconventional computing and computational complexity.

  • Content Type Journal Article
  • Pages 1-15
  • DOI 10.1007/s11047-010-9226-9
  • Authors
    • Ed Blakey, Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford, OX1 3QD UK

Greedy versus social: resource-competing oscillator network as a model of amoeba-based neurocomputer

Abstract  A single-celled amoeboid organism, the true slime mold Physarum polycephalum, exhibits rich spatiotemporal oscillatory behavior and sophisticated computational capabilities. The authors previously created
a biocomputer that incorpo…

Abstract  

A single-celled amoeboid organism, the true slime mold Physarum polycephalum, exhibits rich spatiotemporal oscillatory behavior and sophisticated computational capabilities. The authors previously created
a biocomputer that incorporates the organism as a computing substrate to search for solutions to combinatorial optimization
problems. With the assistance of optical feedback to implement a recurrent neural network model, the organism changes its
shape by alternately growing and withdrawing its photosensitive branches so that its body area can be maximized and the risk
of being illuminated can be minimized. In this way, the organism succeeded in finding the optimal solution to the four-city
traveling salesman problem with a high probability. However, it remains unclear how the organism collects, stores, and compares
information on light stimuli using the oscillatory dynamics. To study these points, we formulate an ordinary differential
equation model of the amoeba-based neurocomputer, considering the organism as a network of oscillators that compete for a
fixed amount of intracellular resource. The model, called the “Resource-Competing Oscillator Network (RCON) model,” reproduces
well the organism’s experimentally observed behavior, as it generates a number of spatiotemporal oscillation modes by keeping
the total sum of the resource constant. Designing the feedback rule properly, the RCON model comes to face a problem of optimizing
the allocation of the resource to its nodes. In the problem-solving process, “greedy” nodes having the highest competitiveness
are supposed to take more resource out of other nodes. However, the resource allocation pattern attained by the greedy nodes
cannot always achieve a “socially optimal” state in terms of the public cost. We prepare four test problems including a tricky
one in which the greedy pattern becomes “socially unfavorable” and investigate how the RCON model copes with these problems.
Comparing problem-solving performances of the oscillation modes, we show that there exist some modes often attain socially
favorable patterns without being trapped in the greedy one.

  • Content Type Journal Article
  • Pages 1-26
  • DOI 10.1007/s11047-010-9224-y
  • Authors
    • Masashi Aono, Flucto-Order Functions Research Team, RIKEN-HYU Collaboration Research Center, RIKEN Advanced Science Institute, 2-1 Hirosawa, Wako, Saitama 351-0198, Japan
    • Yoshito Hirata, Institute of Industrial Science, The University of Tokyo, 4-6-1 Komaba, Meguro-ku, Tokyo 153-8505, Japan
    • Masahiko Hara, Flucto-Order Functions Research Team, RIKEN-HYU Collaboration Research Center, RIKEN Advanced Science Institute, 2-1 Hirosawa, Wako, Saitama 351-0198, Japan
    • Kazuyuki Aihara, Institute of Industrial Science, The University of Tokyo, 4-6-1 Komaba, Meguro-ku, Tokyo 153-8505, Japan

Chaos-based multi-objective immune algorithm with a fine-grained selection mechanism

Abstract  In this paper, we propose a chaos-based multi-objective immune algorithm (CMIA) with a fine-grained selection mechanism based
on the clonal selection principle. Taking advantage of the ergodic and stochastic properties of chaotic s…

Abstract  

In this paper, we propose a chaos-based multi-objective immune algorithm (CMIA) with a fine-grained selection mechanism based
on the clonal selection principle. Taking advantage of the ergodic and stochastic properties of chaotic sequence, a novel
mutation operator, named as chaos-based mutation (CM) operator, is proposed. Moreover, the information of diversity estimation
is also adopted in the CM operator for nondominated solutions to adjust mutation steps adaptively, which encourages searching
less-crowded regions with relative large step sizes. When comparing with polynomial mutation operator that is used in many
state-of-the-art multi-objective optimization evolutionary algorithms, simulations show that it is effective to enhance the
search performance. On the other hand, in order to increase the population diversity, a fine-grained selection mechanism is
proposed in this paper, which seems to be remarkably effective in two-objective benchmark functions. When comparing with two
state-of-the-art multi-objective evolutionary algorithms (NSGA-II and SPEA-2) and a new multi-objective immune algorithm (NNIA),
simulation results of CMIA indicate the effectiveness of the fine-grained selection mechanism and the remarkable performance
in finding the true Pareto-optimal front, especially on some benchmark functions with many local Pareto-optimal fronts.

  • Content Type Journal Article
  • Pages 1-16
  • DOI 10.1007/s00500-010-0661-4
  • Authors
    • Jianyong Chen, Department of Computer Science and Technology, Shenzhen University, Shenzhen, 518060 People’s Republic of China
    • Qiuzhen Lin, Department of Computer Science and Technology, Shenzhen University, Shenzhen, 518060 People’s Republic of China
    • Zhen Ji, Department of Computer Science and Technology, Shenzhen University, Shenzhen, 518060 People’s Republic of China

A note on group decision-making procedure based on incomplete reciprocal relations

Abstract  In a very recent paper by Xu and Chen (Soft Comput 12:515–521, 2008), a novel procedure for group decision making with incomplete reciprocal relations was developed. In this note, we examine
the function between the fuzzy prefere…

Abstract  

In a very recent paper by Xu and Chen (Soft Comput 12:515–521, 2008), a novel procedure for group decision making with incomplete reciprocal relations was developed. In this note, we examine
the function between the fuzzy preference relation and its corresponding priority vector developed by Xu and Chen with a numerical
example and show that the function does not hold in general cases. Then, we deduce an exact function between the additive
transitivity fuzzy preference relation and its corresponding priority vector. Based on this, we develop a procedure for the
decision making with an incomplete reciprocal relation and also develop a procedure for the group decision making with incomplete
reciprocal relations. In order to compare the performances of our method with Xu and Chen’s method in fitting the reciprocal
relation, we introduce some criteria. Theoretical analysis and numerical examples have shown that the function deduced by
us is more reasonable and effective than Xu and Chen’s.

  • Content Type Journal Article
  • Pages 1-12
  • DOI 10.1007/s00500-010-0662-3
  • Authors
    • Yejun Xu, Business School, HoHai University, Nanjing, 210098 Jiangsu China
    • Qingli Da, School of Economics and Management, Southeast University, Nanjing, 210096 Jiangsu China
    • Huimin Wang, Business School, HoHai University, Nanjing, 210098 Jiangsu China