Natural Computing (eBook)

4th International Workshop on Natural Computing, Himeji, Japan, September 2009, Proceedings

Ferdinand Peper, Hiroshi Umeo, Nobuyuki Matsui, Teijiro Isokawa (Herausgeber)

eBook Download: PDF

2010 | 2010
XII, 390 Seiten
Springer Tokyo (Verlag)
978-4-431-53868-4 (ISBN)

Infos

This book is the refereed proceedings of the Fourth International Workshop on Natural Computing, IWNC 2009, held in Himeji International Exchange Center, HIMEJI, JAPAN on September 2009. IWNC aims to bring together computer scientists, biologists, mathematicians, electronic engineers, physicists, and humanitarians, to critically assess present findings in the field, and to outline future developments in nature-inspired computing.

---

Most natural and artificial systems transform information in a predictable or programmable way; such transformation can be interpreted as harnessing nature for computing. Recently we have witnessed a burst of research in unconventional computing, resulting in the development of experimental prototypes of natural computers, plasmodium computers, reaction-diffusion processors, and DNA computers as well as theoretical paradigms of natural computation such as cellular automata, artificial chemistry, evolutionary computing, and neural networks. The International Workshop on Natural Computing (IWNC) brings together computer scientists, biologists, mathematicians, electronic engineers, physicists, and others to critically assess present findings in the field, and to outline future developments in nature-inspired computing. This compilation of papers presented at the most recent workshop, held in Nagoya, Japan, makes a valuable contribution to the understanding of natural computing.

Inhalt

Title Page 2
Preface 5
Organization 7
Table of Contents 9
Invited Talks 9
Investigating Universal Computability of Conventional Cellular Automata Problems on an Organic Molecular Matrix 13
Introduction 13
Universality and Computability 14
Molecular Cellular Automaton Rules 15
Dirichlet Tessellation (DT) or Voronoi Decomposition 16
Directed Propagation of Information 17
Information Writing, Storage and Retrieval 17
Logic Gate 19
Coalescence and Giant Explosion 19
Density Classification Task (DCT) 20
Multi-agent Robotics 21
Phase Ordering 22
Ant Colony 22
Chemotaxis 23
References 24
Noise-Based Logic and Computing: From Boolean Logic Gates to Brain Circuitry and Its Possible Hardware Realization 25
Models and Mechanisms for Artificial Morphogenesis 35
Background 35
Embodied Computation 35
Artificial Morphogenesis 37
Requirements for a Formalism 38
Approach 39
Example 43
References 44
Biologically–Inspired Network Architecture for Future Networks 46
Introduction 46
Why Bio-inspired Approaches? 47
Attractor Selection Principle and Its Application to Networking Problems 50
Concluding Remarks 52
References 53
Foraging Behaviors and Potential Computational Ability of Problem-Solving in an Amoeba 54
Introduction 54
Foraging Behaviors in the Case of Spatially Distributed FSs 56
Accumulation of Mass of Organism to FS in Relation to Amount of Nutrient at FS 56
Time Course of Two Connections between Two FSs in Relation to Food Amount at FS 56
Order of Tube Collapse in Five Connections with Different Length between Two FSs 57
Maze-Solving 57
Risk-Minimum Path in the Inhomogeneous Field of Risk 59
Networking of Three and More FSs 59
Not Only the Final Answer But Also Transient 59
Mathematical Modeling for the Foraging Behaviors to Connect the Spatially Distributed FSs through a Smart Network 60
Mathematical Formulation of Network Dynamics Adaptable to Streaming 60
Physarum Solver: A Biologically Inspired Method for Path-Finding 62
Risk-Minimum Path in an Inhomogeneous Field 62
Effect of Food Amount on Tube Selection between Two FSs 63
Concluding Remarks: Possibility of Physarum Computing 64
References 65
Two Molecular Information Processing Systems Based on Catalytic Nucleic Acids 67
Introduction 67
Systems Based on Deoxyribozyme-Based Logic Gates 67
Spider-Based System 72
Conclusions 74
References 74
Invited Papers 9
The Effect of Community on Distributed Bio-inspired Service Composition 76
Introduction 76
Bio-inspired Service Management 77
Distributed Service Composition 77
Community 78
Community Structure and Formation 79
Simulation and Results 80
Conclusion 82
References 83
Efficient Computation in Brownian Cellular Automata 84
Introduction 84
A Brownian Cellular Automaton Model 85
Embedding Delay-Insensitive Circuits into Brownian Cellular Automaton 89
Implementing Ratchets with Various Configurations 91
Conclusions 92
References 92
A Molecular Communication System 94
Introduction 94
Overview of a Molecular Communication System 94
System Design and Initial Experimental Results 96
Molecular Communication Interface 96
Molecular Propagation System 97
Sender and Receiver 99
Conclusions 100
References 100
Properties of Threshold Coupled Chaotic Neuronal Maps 102
Introduction 102
The Model System: Neuronal Maps 103
Relaxation Time 104
Nonlocal Coupling 105
Asynchronous Updating 106
Dynamic Logic Cell 107
Conclusion 108
References 109
Contributed Papers 10
Implementation of Rotary Element with Quantum Cellular Automata 111
Introduction 111
RotaryElement 112
Quantum Cellular Automata 113
Implementation of Rotary Element 113
Delay Element and C-JOIN 116
Concluding Remarks 117
References 118
Universal 2-State Asynchronous Cellular Automaton with Inner-Independent Transitions 119
Introduction 119
On Delay Insensitive Circuits 120
Implementing DI-Circuits on Asynchronous CA 121
Conclusions and Discussion 126
References 126
Effect of Population Size in Extended Parameter-Free Genetic Algorithm 129
Introduction 129
Parameter-Free Genetic Algorithm 130
Mutation Rate Coding 131
Extended Selection Rule 132
Experiments 133
Conclusion and Discussion 135
References 136
Temperature Effects on Olive Fruit Fly Infestation in the FlySim Cellular Automata Model 137
Introduction 137
Description of the Model 138
Elementary Processes and Transition Function 139
Temperature 139
Growth and Death Rate of Olive Fruit Flies 140
Diffusion of Adult Olive Fruit Flies 141
Results 141
Conclusions 143
References 143
Computing by Observing Changes 145
Computing by Observing 145
Preliminaries 147
Computing by Observing Changes 148
The Power of Change-Observing Acceptors 150
Conclusion 151
References 152
Robustness of the Critical Behaviour in a Discrete Stochastic Reaction-Diffusion Medium 153
Introduction 153
Model and Methods 154
The Model 154
Effect of Noise 155
Robustness Studies 156
Robustness to Variations of the Excitation Level 156
Holes and Missing Links 156
Changing the Topology 157
The Inverse Proportionality Law 158
Conclusion 160
References 160
Quantifying the Severity of the Permutation Problem in Neuroevolution 161
Introduction 161
The Permutation Problem 162
Calculating the Probability of Genotypic Permutations 163
Calculating the Probability of Phenotypic Permutations 165
Discussion 166
Conclusions and Future Work 167
References 168
Extending the Geometrical Design of DNA Nanostructures 169
Introduction 169
Interconnected Single-Duplex Junction (T-Junction) 170
Structural Description 170
Abstraction 171
Designing Shapes and Patterns 171
Experiments 175
Conclusion 175
References 176
An Optical Solution for the Subset Sum Problem 177
Introduction 177
The Device 178
The Modified Device 179
Finding the Solution Subset 183
Conclusion and Future Work 184
References 184
Design of True Random One-Time Pads in DNA XOR Cryptosystem 186
Introduction 186
DNA XOR One-Time-Pad Cryptosystem with Random Hybridization 187
Message Encryption 188
Random Tiling Operation 189
Extraction of Cipher Strings and Key Strings 190
Analysis on Error Tolerance 193
Conclusion 194
References 194
On Designing Gliders in Three-Dimensional Larger than Life Cellular Automata 196
Introduction 196
Larger than Life Cellular Automata 197
Bugs in Three-Dimensional Larger than Life 197
Period 1 Bugs 197
Bugs with Longer Period 199
Experimental Results of Collisions of Bugs 200
Conclusion 201
References 201
Instability of Collective Flow in Two-Dimensional Optimal Velocity Model 203
Introduction 203
Two-DimensionalOVModel 203
Linear Analysis 204
Longitudinal Mode along the x-Axis 206
Transverse Mode along the x-Axis 206
Transverse Mode along the y-Axis 207
Longitudinal Mode along the y-Axis 207
Elliptically Polarized Mode 208
Phase Diagrams 209
Summary 210
References 210
A New Differential Evolution for Multiobjective Optimization by Uniform Design and Minimum Reduce Hypervolume 211
Introduction 211
UniformDesign 213
Minimum Reduce Hypervolume 213
Differential Evolution for MOPs by Uniform Design and Minimum Reduce Hypervolume 214
Experiment Results 215
Conclusion and Further Research 219
References 219
Noise Effects on Chaos in Chaotic Neuron Model 221
Introduction 221
Chaotic Neuron Model 222
Noise-Induced Order in Chaotic Neuron Model 223
Summary 227
References 228
Application of Improved Grammatical Evolution to Santa Fe Trail Problems 230
Introduction 230
Original Grammatical Evolution 231
Function Identification Problem 231
Problem Settings 231
Syntax and Parameters 232
Result 232
Improved Schemes of Grammatical Evolution 233
Difficulties of Original GE 233
Improvement of GE 234
Santa Fe Trail Problem 234
Problem Setting 234
Syntax and Parameters 235
Result 236
Conclusion 236
References 237
Limit Theorem for a Time-Dependent Coined Quantum Walk on the Line 238
Introduction 238
Time-Dependent QW 239
Two-PeriodQW 241
Special Cases in Time-Dependent QWs 243
Case 1 243
Case 2 245
Conclusion and Discussion 246
References 246
Top-Predator Survivor Region Is Affected by Bottom-Prey Mortality Rate on the Monte-Carlo Simulation in Lattice Model 248
Introduction 248
Model and Method 249
Model 249
Simulation Method 250
Mean-Field Theory 250
Simulation Results 251
Steady-State Density 251
Results of Simulation Experiment 252
Discussions and Conclusion 253
References 255
Simulation and Theoretical Comparison between “Zipper” and “Non-Zipper” Merging 256
Introduction 256
Modeling 257
Simulations and Theoretical Calculation 258
Conclusive Discussion 263
References 263
Universality of 2-State 3-Symbol Reversible Logic Elements — A Direct Simulation Method of a Rotary Element 264
Introduction 264
Preliminaries 265
Direct Simulation of an RE by 3-Symbol RLEMs 267
Concluding Remarks 271
References 271
Pump Current as a Signal Transformation 272
Introduction: Pump Current 272
Stochastic Model 274
Simple Model for the Pumping Phenomenon 274
Counting Statistics 275
Mathematical Structure Behind the Pumping Phenomenon 276
Interpretation as a Shr¨odinger-Like Equation 276
Geometrical Phase Interpretation 277
Discussion: Pump Current as a Signal Transformation 278
Concluding Remarks 279
References 279
Evaluation of Generation Alternation Models in Evolutionary Robotics 280
Introduction 280
Generation Alternation Models 281
Evaluation of Generation Alternation Models by Experiment 283
Experimental Settings 283
Experimental Results 284
Discussion 285
Conclusions 287
References 287
Photonic Switching of DNA’s Position That Represents the Internal State in Photonic DNA Automaton 288
Introduction 288
Photonic DNA Automaton 290
A Method for Controlling Position of DNA 292
Experiments 295
Conclusions 299
References 299
Fluctuation Induced Structure in Chemical Reaction with Small Number of Molecules 302
Parallel Retrieval of Nanometer-Scale Light-Matter Interactions for Nanophotonic Systems 310
Introduction 310
Nanometric Optical Processing Based on Nanophotonics 312
Nanophotonic Matching Utilizing Macro-scale Observation of Optical Near-Field Interactions 312
Transcription Based on Photoinduced Phase Transition 316
Conclusions 318
References 318
A Compressible Fluid Model for Traffic Flow and Nonlinear Saturation of Perturbation Growth 320
Introduction 320
New Compressible Fluid Model Based on Experimental Data 322
Linear Stability Analysis 324
Reductive Perturbation Analysis 324
Conclusion 327
References 327
Functional Sized Population Magnetic Optimization Algorithm 328
Introduction 328
Functional Sized Population MOA (FSMOA) 329
Finding the Best Parameters 333
Experimental Results 334
Conclusion 335
References 336
Emergence and Collapse of Order in Ad Hoc Cellular Automata 337
Introduction 337
Ad Hoc Cellular Automata with Intra-agent Dynamics 337
Results 339
Emergence and Collapse of Complex/Periodic Patterns 339
Emergence and Collapse of Clusters in Rule-Entry Space 341
Classifying ACA 342
Power Law in Stationary State Distribution 343
Discussion and Conclusion 343
References 344
A Transition Rule Set for the First 2-D Optimum-Time Synchronization Algorithm 345
Introduction 345
Firing Squad Synchronization Problem 346
FSSP on Two-Dimensional Cellular Arrays 346
Overview of Shinahr’s Time-Optimum Algorithm 346
Constructionof Real-Coded Transition Rule Set for ABS 348
Discussions 352
References 352
A Two-Dimensional Optimum-Time Firing Squad Synchronization Algorithm and Its Implementation 354
Introduction 354
Firing Squad Synchronization Problem on Two-Dimensional Arrays 354
Delayed Synchronization Scheme for One-Dimensional Arrays 355
New Optimum-Time Synchronization Algorithm 357
Segmentation of Rectangular Array of Size m× n 357
Starting Synchronization Process 357
Synchronization of Lm 359
Synchronization of Li 359
Synchronization of Rectangle Longer Than Wide 360
Conclusions 362
References 363
Quaternion Based Thermal Condition Monitoring System 364
Introduction 364
Machine Condition Monitoring System Model 365
Log-Polar Mapping 366
Quaternion Based Thermal Image Correlator 366
Max-Product Fuzzy Neural Network Classifier 368
Experimental Results 370
Conclusion 373
References 374
Firing Correlation in Spiking Neurons with Watts–Strogatz Rewiring 375
Introduction 375
Izhikevich’s Neuron Model and Network Structure 376
Izhikevich’s Spiking Neuron Model 376
Network Structure and Neuron Ensembles 376
Simulation Experiment with a WS Network Structure 379
Summary 381
References 383
Methods for Shortening Waiting Time in Walking-Distance Introduced Queueing Systems 384
Introduction 384
Walking-Distance Introduced Queueing Theory 385
Distance Introduced Fork-Type Queueing System: D-Fork 385
Update Rules 386
Stationary Equations 387
Methods for Shortening Mean Waiting Time in D-Fork 388
Set the Head of the Queue at the Center: D-Fork-Center 388
Keep One Person Waiting at the Window: D-Fork-Wait 388
Theoretical Analysis and Simulation 389
Experiments 390
Conclusion 391
References 391
Effect of Mutation to Distribution of Optimum Solution in Genetic Algorithm 392
Introduction 392
Mathematical Model 393
Representations 393
Linkage Equilibrium 393
Stochastic Models 394
Wright-FisherModel 394
With Mutation 394
Calculation of Success Probability 395
Results 396
Summary and Discussion 398
References 399
Author Index 400

Produkt-Details

• Erscheint lt. Verlag: 18.2.2010
• Reihe/Serie: Proceedings in Information and Communications Technology
• Reihe/Serie: Proceedings in Information and Communications Technology
• Zusatzinfo: XII, 390 p.
• Verlagsort: Tokyo
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Netzwerke
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Informatik ► Weitere Themen ► Hardware
• Themenwelt: Mathematik / Informatik ► Mathematik
• Themenwelt: Naturwissenschaften ► Physik / Astronomie ► Quantenphysik
• Themenwelt: Naturwissenschaften ► Physik / Astronomie ► Theoretische Physik
• Themenwelt: Technik
• Schlagworte: artificial neurons • Automata • Biomolecular computing • bionanotechnology • BZ-reaaction • Chaos • Evolution • Monte-Carlo Simulation • nanomachine communication • Natur • Optimization • Robotics • Simulation
• ISBN-10: 4-431-53868-2 / 4431538682
• ISBN-13: 978-4-431-53868-4 / 9784431538684