Natural computing,G.Rozenberg, T.Back, J.Kok, Editors, Handbook of Natural Computing, Springer Verlag, 2012A.Brabazon, M.O'Neill, S.McGarraghy. Natural Computing Algorithms, Springer Verlag, 2015 also called natural computation, is a terminology introduced to encompass three classes of methods: 1) those that take inspiration from nature for the development of novel problem-solving techniques; 2) those that are based on the use of computers to synthesize natural phenomena; and 3) those that employ natural materials (e.g., molecules) to compute. The main fields of research that compose these three branches are artificial neural networks, evolutionary algorithms, swarm intelligence, artificial immune systems, fractal geometry, artificial life, DNA computing, and quantum computing, among others. However, the field is more related to biological computation.
Computational paradigms studied by natural computing are abstracted from natural phenomena as diverse as self-replication, the functioning of the brain, Darwinian evolution, group behavior, the immune system, the defining properties of life forms, cell membranes, and morphogenesis. Besides traditional electronic hardware, these computational paradigms can be implemented on alternative physical media such as biomolecules (DNA, RNA), or trapped-ion quantum computing devices.
Dually, one can view processes occurring in nature as information processing. Such processes include self-assembly, developmental processes, gene regulation networks, protein–protein interaction networks, biological transport (active transport, passive transport) networks, and gene assembly in unicellular organisms. Efforts to understand biological systems also include engineering of semi-synthetic organisms, and understanding the universe itself from the point of view of information processing. Indeed, the idea was even advanced that information is more fundamental than matter or energy. The Zuse-Fredkin thesis, dating back to the 1960s, states that the entire universe is a huge cellular automaton which continuously updates its rules.Fredkin, F. Digital mechanics: An informational process based on reversible universal CA. Physica D 45 (1990) 254–270Zuse, K. Rechnender Raum. Elektronische Datenverarbeitung 8 (1967) 336–344 Recently it has been suggested that the whole universe is a quantum computer that computes its own behaviour.Lloyd, S. Programming the Universe: A Quantum Computer Scientist Takes on the Cosmos. Knopf, 2006 The universe/nature as computational mechanism is addressed by exploring nature with the help of the idea of computabilityZenil, H. A Computable Universe: Understanding and Exploring Nature as Computation. World Scientific Publishing Company, 2012 and studying natural processes as computations (information processing).Dodig-Crnkovic, G. and Giovagnoli, R. COMPUTING NATURE. Springer, 2013
Nature-inspired models of computation The most established "classical" nature-inspired models of computation are cellular automata, neural computation, and evolutionary computation. More recent computational systems abstracted from natural processes include swarm intelligence, artificial immune systems, membrane computing, and amorphous computing. Detailed reviews can be found in many books .Olarius S., Zomaya A. Y., Handbook of Bioinspired Algorithms and Applications, Chapman & Hall/CRC, 2005.de Castro, L. N., Fundamentals of Natural Computing: Basic Concepts, Algorithms, and Applications, CRC Press, 2006.
Cellular automata
A cellular automaton is a dynamical system consisting of an array of cells. Space and time are discrete and each of the cells can be in a finite number of states. The cellular automaton updates the states of its cells synchronously according to the transition rules given a priori. The next state of a cell is computed by a transition rule and it depends only on its current state and the states of its neighbors.
Conway's Game of Life is one of the best-known examples of cellular automata, shown to be computationally universal. Cellular automata have been applied to modelling a variety of phenomena such as communication, growth, reproduction, competition, evolution and other physical and biological processes.
Neural computation
Neural computation is the field of research that emerged from the comparison between computing machines and the human nervous system.von Neumann, J. The Computer and the Brain. Yale University Press, 1958 This field aims both to understand how the brain of living organisms works (brain theory or computational neuroscience), and to design efficient algorithms based on the principles of how the human brain processes information (Artificial Neural Networks, ANNArbib, M., editor. The Handbook of Brain Theory and Neural Networks. MIT Press, 2003.).
An artificial neural network is a network of artificial neurons.Rojas, R. Neural Networks: A Systematic Introduction. Springer, 1996 An artificial neuron A is equipped with a function , receives n real-valued inputs with respective weights , and it outputs . Some neurons are selected to be the output neurons, and the network function is the vectorial function that associates to the n input values, the outputs of the m selected output neurons. Note that different choices of weights produce different network functions for the same inputs. Back-propagation is a supervised learning method by which the weights of the connections in the network are repeatedly adjusted so as to minimize the difference between the vector of actual outputs and that of desired outputs. Learning algorithms based on backwards propagation of errors can be used to find optimal weights for given topology of the network and input-output pairs.
Evolutionary computation
Evolutionary computationBäck, T., Fogel, D., Michalewicz, Z., editors. Handbook of Evolutionary Computation. IOP Publishing, U.K., 1997 is a computational paradigm inspired by Darwinian evolution.
An artificial evolutionary system is a computational system based on the notion of simulated evolution. It comprises a constant- or variable-size population of individuals, a fitness criterion, and genetically inspired operators that produce the next generation from the current one. The initial population is typically generated randomly or heuristically, and typical operators are mutation and recombination. At each step, the individuals are evaluated according to the given fitness function (survival of the fittest). The next generation is obtained from selected individuals (parents) by using genetically inspired operators. The choice of parents can be guided by a selection operator which reflects the biological principle of mate selection. This process of simulated evolution eventually converges towards a nearly optimal population of individuals, from the point of view of the fitness function.
The study of evolutionary systems has historically evolved along three main branches: Evolution strategies provide a solution to parameter optimization problems for real-valued as well as discrete and mixed types of parameters. Evolutionary programming originally aimed at creating optimal "intelligent agents" modelled, e.g., as finite state machines. Genetic algorithmsKoza, J. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, 1992 applied the idea of evolutionary computation to the problem of finding a (nearly-)optimal solution to a given problem. Genetic algorithms initially consisted of an input population of individuals encoded as fixed-length bit strings, the genetic operators mutation (bit flips) and recombination (combination of a prefix of a parent with the suffix of the other), and a problem-dependent fitness function. Genetic algorithms have been used to optimize computer programs, called genetic programming, and today they are also applied to real-valued parameter optimization problems as well as to many types of combinatorial tasks.
Estimation of Distribution Algorithm (EDA), on the other hand, are evolutionary algorithms that substitute traditional reproduction operators by model-guided ones. Such models are learned from the population by employing machine learning techniques and represented as Probabilistic Graphical Models, from which new solutions can be sampled or generated from guided-crossover.
Swarm intelligence Swarm intelligence,Engelbrecht, A. Fundamentals of Computational Swarm Intelligence. Wiley and Sons, 2005. sometimes referred to as collective intelligence, is defined as the problem solving behavior that emerges from the interaction of individual agents (e.g., bacteria, ants, termites, bees, spiders, fish, birds) which communicate with other agents by acting on their local environments.
Particle swarm optimization applies this idea to the problem of finding an optimal solution to a given problem by a search through a (multi-dimensional) solution space. The initial set-up is a swarm of particles, each representing a possible solution to the problem. Each particle has its own velocity which depends on its previous velocity (the inertia component), the tendency towards the past personal best position (the nostalgia component), and its tendency towards a global neighborhood optimum or local neighborhood optimum (the social component). Particles thus move through a multidimensional space and eventually converge towards a point between the global best and their personal best. Particle swarm optimization algorithms have been applied to various optimization problems, and to unsupervised learning, game learning, and scheduling applications.
In the same vein, ant algorithms model the foraging behaviour of ant colonies. To find the best path between the nest and a source of food, ants rely on indirect communication by laying a pheromone trail on the way back to the nest if they found food, respectively following the concentration of pheromones if they are looking for food. Ant algorithms have been successfully applied to a variety of combinatorial optimization problems over discrete search spaces.
Artificial immune systems Artificial immune systems (a.k.a. immunological computation or immunocomputing) are computational systems inspired by the natural immune systems of biological organisms.
Viewed as an information processing system, the natural immune system of organisms performs many complex tasks in parallel and distributed computing fashion.Dasgupta, D. editor. Artificial Immune Systems and Their Applications. Springer, 1998 These include distinguishing between self and nonself,de Castro, L., Timmis, J. Artificial Immune Systems: A New Computational Intelligence Approach. Springer, 2002. neutralization of nonself pathogens (viruses, bacteria, fungi, and parasites), learning, memory, associative retrieval, self-regulation, and fault-tolerance. Artificial immune systems are abstractions of the natural immune system, emphasizing these computational aspects. Their applications include computer virus detection, anomaly detection in a time series of data, fault diagnosis, pattern recognition, machine learning, bioinformatics, optimization, robotics and control.
Membrane computing Membrane computing investigates computing models abstracted from the compartmentalized structure of living cells affected by membranes.Paun, G. Membrane Computing: An Introduction. Springer, 2002 A generic membrane system (P-system) consists of cell-like compartments (regions) delimited by membranes, that are placed in a nested hierarchical structure. Each membrane-enveloped region contains objects, transformation rules which modify these objects, as well as transfer rules, which specify whether the objects will be transferred outside or stay inside the region. Regions communicate with each other via the transfer of objects.