Evolutionary Learning Algorithm
An Evolutionary Learning Algorithm is an iterative online learning algorithm that consisting of random variation (Reproduction, Mutation, Recombination) followed by selection.
- AKA: Evolutionary Computing, EC.
- Context:
- It can be a Multiobjective Evolutionary Algorithm.
- It can use a Gene-based Representation.
- …
- Example(s):
- Counter-Example(s):
- See: Metaheuristic, Ensemble Learning Algorithm, Reproduction, Mutation, Genetic Recombination, Natural Selection, Candidate Solution, Fitness Function; Coevolution Learning; Compositional Coevolution; Evolutionary Clustering; Evolutionary Computation in Economics; Evolutionary Computation in Finance; Evolutionary Computational Techniques in Marketing; Evolutionary Feature Selection and Construction; Evolutionary Fuzzy Systems; Evolutionary Games; Evolutionary Kernel Learning; Evolutionary Robotics; Neuroevolution; Nonstandard Criteria in Evolutionary Learning; Test-Based Coevolution.
References
2017a
- (Sammut & Webb, 2017) ⇒ (2017) "Evolutionary Algorithms". In: Sammut, C., Webb, G.I. (eds) Encyclopedia of Machine Learning and Data Mining. Springer, Boston, MA
- QUOTE: Generic term subsuming all machine learning and optimization methods inspired by neo-Darwinian evolution theory.
2017b
- (Sammut, 2017) ⇒ Claude Sammut.(2017). "Genetic and Evolutionary Algorithms". In: Sammut, C., Webb, G.I. (eds) Encyclopedia of Machine Learning and Data Mining. Springer, Boston, MA
- QUOTE: There are many variations of genetic algorithms (GA). Here, wedescribe a simple scheme to introduce some of the key terms in genetic and evolutionary algorithms. See the main entry on Evolutionary Algorithms for references to specific methods.
In genetic learning, we assume that there is a population of individuals, each of which represents a candidate problem solver for a given task. GAs can be thought of as a family of general purpose search methods that are capable of solving a broad range of problems from optimization and scheduling to robot control. Like evolution, genetic algorithms test each individual from the population and only the fittest survive to reproduce for the next generation. The algorithm creates new generations until at least one individual is found that can solve the problem adequately.
- QUOTE: There are many variations of genetic algorithms (GA). Here, wedescribe a simple scheme to introduce some of the key terms in genetic and evolutionary algorithms. See the main entry on Evolutionary Algorithms for references to specific methods.
2017c
- (Sebag, 2017) ⇒ Sebag M. (2017). Nonstandard Criteria in Evolutionary Learning. In: Sammut, C., Webb, G.I. (eds) Encyclopedia of Machine Learning and Data Mining. Springer, Boston, MA
- QUOTE: Machine learning (ML), primarily concerned with extracting models or hypotheses from data, comes into three main flavors: supervised learning also known as classification or regression (Bishop 2006; Duda et al. 2001; Han and Kamber 2000), unsupervised learning also known as clustering (Ben-David et al. 2005), and reinforcement learning (Sutton and Barto 1998).
All three types of problems can be viewed as optimization problems. The ML core task is to define a learning criterion (i.e., the function to be optimized) such that it enforces (i) the statistical relevance of the solution; (ii) the well-posedness of the underlying optimization problem. Since evolutionary computation (see Evolutionary Algorithms) makes it possible to handle ill-posed optimization problems, the field of evolutionary learning (Holland 1986) has investigated quite a few nonstandard learning criteria and search spaces. Only supervised ML will be considered in the following. Unsupervised learning has hardly been touched upon in the evolutionary computation (EC) literature; regarding reinforcement learning, the interested reader is referred to the entries related to evolutionary robotics and control.
The entry will first briefly summarize the formal background of supervised ML and its two mainstream approaches for the last decade, namely support vector machines (SVMs) (Cristianini and Shawe-Taylor 2000; Schölkopf et al. 1998; Vapnik 1995) and ensemble learning (Breiman 1998; Dietterich 2000; Schapire 1990). Thereafter and without pretending to exhaustivity, this entry will illustrate some innovative variants of these approaches in the literature, building upon the evolutionary freedom of setting and tackling optimization problems.
- QUOTE: Machine learning (ML), primarily concerned with extracting models or hypotheses from data, comes into three main flavors: supervised learning also known as classification or regression (Bishop 2006; Duda et al. 2001; Han and Kamber 2000), unsupervised learning also known as clustering (Ben-David et al. 2005), and reinforcement learning (Sutton and Barto 1998).
2014
- (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/evolutionary_algorithm Retrieved:2014-11-20.
- In artificial intelligence, an 'evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses mechanisms inspired by biological evolution, such as reproduction, mutation, recombination, and selection. Candidate solutions to the optimization problem play the role of individuals in a population, and the fitness function determines the quality of the solutions (see also loss function). Evolution of the population then takes place after the repeated application of the above operators. Artificial evolution (AE) describes a process involving individual evolutionary algorithms; EAs are individual components that participate in an AE.
Evolutionary algorithms often perform well approximating solutions to all types of problems because they ideally do not make any assumption about the underlying fitness landscape; this generality is shown by successes in fields as diverse as engineering, art, biology, economics, marketing, genetics, operations research, robotics, social sciences, physics, politics and chemistry.
Techniques from evolutionary algorithms applied to the modeling of biological evolution are generally limited to explorations of microevolutionary processes and planning models based upon cellular processes. The computer simulations Tierra and Avida attempt to model macroevolutionary dynamics.
In most real applications of EAs, computational complexity is a prohibiting factor. In fact, this computational complexity is due to fitness function evaluation. Fitness approximation is one of the solutions to overcome this difficulty. However, seemingly simple EA can solve often complex problems; therefore, there may be no direct link between algorithm complexity and problem complexity.
A possible limitation of many evolutionary algorithms is their lack of a clear genotype-phenotype distinction. In nature, the fertilized egg cell undergoes a complex process known as embryogenesis to become a mature phenotype. This indirect encoding is believed to make the genetic search more robust (i.e. reduce the probability of fatal mutations), and also may improve the evolvability of the organism. [1] [2] Such indirect (aka generative or developmental) encodings also enable evolution to exploit the regularity in the environment. [3] Recent work in the field of artificial embryogeny, or artificial developmental systems, seeks to address these concerns. And gene expression programming successfully explores a genotype-phenotype system, where the genotype consists of linear multigenic chromosomes of fixed length and the phenotype consists of multiple expression trees or computer programs of different sizes and shapes. [4]
- In artificial intelligence, an 'evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses mechanisms inspired by biological evolution, such as reproduction, mutation, recombination, and selection. Candidate solutions to the optimization problem play the role of individuals in a population, and the fitness function determines the quality of the solutions (see also loss function). Evolution of the population then takes place after the repeated application of the above operators. Artificial evolution (AE) describes a process involving individual evolutionary algorithms; EAs are individual components that participate in an AE.
- ↑ G.S. Hornby and J.B. Pollack. Creating high-level components with a generative representation for body-brain evolution. Artificial Life, 8(3):223–246, 2002.
- ↑ Jeff Clune, Benjamin Beckmann, Charles Ofria, and Robert Pennock. "Evolving Coordinated Quadruped Gaits with the HyperNEAT Generative Encoding". Proceedings of the IEEE Congress on Evolutionary Computing Special Section on Evolutionary Robotics, 2009. Trondheim, Norway.
- ↑ J. Clune, C. Ofria, and R. T. Pennock, “How a generative encoding fares as problem-regularity decreases,” in PPSN (G. Rudolph, T. Jansen, S. M. Lucas, C. Poloni, and N. Beume, eds.), vol. 5199 of Lecture Notes in Computer Science, pp. 358–367, Springer, 2008.
- ↑ Ferreira, C., 2001. Gene Expression Programming: A New Adaptive Algorithm for Solving Problems. Complex Systems, Vol. 13, issue 2: 87-129.
2009
- http://en.wikipedia.org/wiki/Evolutionary_algorithm
- In artificial intelligence, an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses some mechanisms inspired by biological evolution: reproduction, mutation, recombination, and selection. Candidate solutions to the optimization problem play the role of individuals in a population, and the fitness function determines the environment within which the solutions "live" (see also cost function). Evolution of the population then takes place after the repeated application of the above operators. Artificial evolution (AE) describes a process involving individual evolutionary algorithms; EAs are individual components that participate in an AE.
- Similar techniques differ in the implementation details and the nature of the particular applied problem.
- Genetic algorithm - This is the most popular type of EA. One seeks the solution of a problem in the form of strings of numbers (traditionally binary, although the best representations are usually those that reflect something about the problem being solved), by applying operators such as recombination and mutation (sometimes one, sometimes both). This type of EA is often used in optimization problems;
- Genetic programming - Here the solutions are in the form of computer programs, and their fitness is determined by their ability to solve a computational problem.
- Evolutionary programming - Like genetic programming, only the structure of the program is fixed and its numerical parameters are allowed to evolve;
- Evolution strategy - Works with vectors of real numbers as representations of solutions, and typically uses self-adaptive mutation rates;
2000
- (Fogel et al., 2000) ⇒ David B. Fogel, Thomas Bäck, and Zbigniew Michalewicz. (2000). “Evolutionary Computation: Basic algorithms and operators." CRC Press
- QUOTE: Convergence reliability: Informally, the convergence reliability of an evolutionary algorithm means its capability to yield reasonable good solution in the case of highly multimodal topologies of the objective function.
- (Fogel, 2000) ⇒ David B. Fogel. (2000). “What is Evolutionary Computation?.” In: IEEE Spectrum, 37(2).
- QUOTE: In the most general terms, evolution can be described as a two-step iterative process, consisting of random variation followed by selection. The link between this description of evolution and the optimizing algorithms that are the hallmark of evolutionary computation is conceptually simple.