Abstract
There are different models of evolutionary computations: genetic algorithms, genetic programming, etc. This chapter presents mathematical foundations of evolutionary computation based on the concept of evolutionary automaton. Different classes of evolutionary automata (evolutionary finite automata, evolutionary Turing machines and evolutionary inductive Turing machines) are introduced and studied. It is demonstrated that evolutionary algorithms are more expressive than conventional recursive algorithms, such as Turing machines. Universal evolutionary algorithms and automata are constructed. It is proved that classes of evolutionary finite automata, evolutionary Turing machines and evolutionary inductive Turing machines have universal automata. As in the case of conventional automata and Turing machines, universal evolutionary algorithms and automata provide means to study many important problems in the area of evolutionary computation, such as complexity, completeness, optimality and search decidability of evolutionary algorithms, as well as such natural phenomena as cooperation and competition. Expressiveness and generality of the introduced classes of evolutionary automata are investigated.
TopBackground
Evolution by natural selection is one of the most compelling themes of modern science. In evolutionary algorithms, selection operates on population of individuals represented by semiotic chromosomes, which are stored in a computer’s memory. Populations of semiotic chromosomes evolve in a computational process, using mutation and/or crossover in much the same way as natural populations do. This form of computation is called Evolutionary Computation (EC). Evolutionary Computation consists of four main areas: Genetic Algorithms (GA), Genetic Programming (GP), Evolution Strategies (ES) and Evolutionary Programming (EP). Additional areas include: Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO), co-evolution, Artificial Immune Systems (AIS), evolutionary robotics, evolvable hardware, Evolutionary Artificial Neural Networks (EANN), evolutionary multiobjective optimization, Artificial Life (A-Life), Classifier Systems, DNA-Based Computing and some fields in bioinformatics. Applications of Evolutionary Computing are vast and diverse. Evolutionary Computing is used for finding solutions of intractable (hard and NP-complete) optimization problems, machine learning, data mining, neural network training, evolution of technology, robotics, control, electronic circuit design, games, economics, network design, pattern recognition, genome and protein analysis, DNA-based computing, evolvable programming languages, reconfigurable hardware and many others (Back, Fogel and Michalewicz 1997; Fogel 2001; Michalewicz and Fogel, 2004).
Key Terms in this Chapter
Super-Turing Models of Computation: Models of computation more expressive than Turing machines.
Expressiveness of an Evolutionary Algorithm: Characterized by the class of problems solvable by an evolutionary algorithm.
Completeness of a Class of Evolutionary Algorithms: The ability to find any solution using algorithms from this class.
Subrecursive Algorithms: Classes of algorithms that cannot solve all problems (compute everything) that Turing machines can solve (compute).
Inductive Turing Machines of the Order n: Inductive Turing machines that have a memory connections in which are constructed by an inductive Turing machine of the order n - 1.
Evolutionary Inductive Turing Machine: An evolutionary automaton that consists of an infinite series of inductive Turing machines each of which computes a generation in evolution.
Decidability of an Evolutionary Algorithm: The ability to find whether the evolutionary algorithm can solve a specific problem or class of problems.
Decidability of a Class of Evolutionary Algorithms: The ability to find whether it is possible solve a specific problem or class of problems using algorithms from this class.
Evolutionary Turing Machine: An evolutionary automaton that consists of an infinite series of Turing machines each of which computes a generation in evolution.
Inductive Turing Machines of the First Order: Inductive Turing machines that have recursive memory.
Completeness of an Evolutionary Algorithm: The ability of an evolutionary algorithm to find any solution.
Recursive Algorithms: Classes of algorithms that can solve the same problems (compute the same fucntions) as Turing machines.
Evolutionary Automata: Class of abstract automata designed to model evolutionary processes.
Inductive Turing Machine: A finite-state machine associated that has an external storage or memory medium and gives its final result only when its output stops changing after a finite number of steps.
Super-Recursive Algorithms: Classes of algorithms that can solve more problems (compute more) than Turing machines.
Expressiveness of a Class of Evolutionary Algorithms: Characterized by the class of problems solvable by evolutionary algorithms from this class.