Evolutionary Computation
Evolution is produced as a result of natural selection and sexual reproduction. Charles Darwin published in 1859 his book "The origin of species” which caused many controversies in the world of science for the theories that argue that species evolve according to the environment to adapt to it. It was a discussion between those who thought that the world was a static and perfect creation of God against theories about how individuals were in constant competition and evolution to be able to perpetuate their species through time. Species are created, evolve and disappear if they cannot adapt, so that only the fittest, that is, those that best adapt to the environment, survive and manage to perpetuate their abilities.
According to this point of view of evolution, computing sees in this framework a clear process of optimization: Individuals who have adapted themselves better, the best temporary solutions, intersect and / or mix generating new individuals or new solutions are taken which will contain part of the genetic code or information of their predecessors, and the average of adaptation of the whole population is improved.
Evolutionary computing has become a general concept that is adapted for problem solving, specifically for optimization problems, because it adds flexibility and adaptability in the resolution, combinable with the robustness and advantages of global search.
What is Evolutionary Computation?
Evolutionary computation (EC) is a branch of artificial intelligence that focuses on techniques that simulate natural evolution, and is an alternative approach to address complex problems of search and learning through computational models of evolutionary processes and involves problems of combinatorial optimization. The EC was based on the mechanisms of biological evolution that were proposed by Darwin, Lamark and Medel; being Darwin who proposed the "natural selection of the most adapted”, Medel proposed the "corpuscular theory of inheritance" and Lamark proposed the "inheritance of acquired characters".
The EC tries to solve problems of combinatorial optimization in order to find the best solution to a problem, that is, just as in nature only the strongest and best adapted to the environment are able to survive, reproduce and perpetuate their species through time.
EC encompasses different strategies for solving optimization problems, which are:
- Evolutionary search processes: This was proposed by Alan Turing in 1948.
- Evolutionary Strategies: This represents individuals through real vectors. It was proposed by Rechenberg in 1964.
- Evolutionary Programming: This uses finite state machines. It was proposed by Fogel in the year 1965.
- Genetic Algorithms: This represents individuals as binary chains and was proposed by Holland in 1975.
- Genetic Programming: It uses LISP trees and was proposed by Koza in 1992.
Evolutionary Algorithms
This term is used to describe system for solving optimization problems or searches that are based on a computer and computational models are used of some mechanism of evolution known as a key element in its design and implementation.
The evolutionary algorithms take as inspiration the evolution in different biological systems and their main idea is to maintain a set of individuals which represent a possible solution to a problem. Individuals mix and compete among themselves where only the ones that adapt best will survive. As you can notice, these algorithms mimic the principle of "natural selection" that was proposed by Charles Darwin.
Main components:
- Population of individuals, which are a representation of possible solutions.
- Selection procedure based on the aptitude of the individuals to solve the problem.
- Transformation procedure to build new individuals from the previous ones.
BEGIN
INICIALIZAR de forma aleatoria una población con soluciones candidatas
EVALUATE each candidate
REPEAT UNTIL (TERMINATION CONDITION == true)
1. SELECT parents
2. RECOMMEND selected parents obtaining offspring
3. MUTATE offspring
4. EVALUATE new candidates
5. SELECT individuals for the next generation
END REPEAT
ENDCharacteristics:
- Evolutionary Strategies:Developed by Rechenberg and Schwefel and extended by Herdy, Kursawe, Ostermeier, Rudolph, and others, was designed with the purpose of solving discrete and continuous optimization problems. It works with vectors of real numbers that code the possible solutions of numerical problems. This uses recombination or crossing (arithmetic crossover), mutation and the selection operation, which may be deterministic or probabilistic, eliminates the worst solutions of the population and does not generate a copy of those individuals with an aptitude below the average aptitude.
- Evolutionary Programming:It was introduced by Fogel and extended by Burguin, at first it was designed with the purpose of creating artificial intelligence. The representation of the problem is done through real numbers and employs mutation and selection mechanisms.
- Genetic Algorithms: They work with binary chains for the representation of the problem and the space of the solutions that are possible is explored by applying transformations to these candidate solutions as well as we can observe it in living organisms: crossing, inversion and mutation.
- Genetic Programming:Developed by Koza, individuals are programs or automatons of variable length, are described through LISP-S expressions and are represented as trees, and as variation operators it uses crossover and modification, in addition to selection mechanisms.
How are individuals represented?
We can say that each person has a unique genetic information which is in the DNA. DNA is composed of four types of elements: "Adenine" (A), "Thymine" (T), "Cytosine" (C) y "Guanine" (G), we can say that human beings are represented by means of an ARRAY ( composed of any of these 4 "elements" and with this we have a way to represent the individuals. Passing this to a problem of combinatorial optimization, it means that a possible result to the problem we can pass it to an array that could be full of zeros or ones (binary), to which we will give a certain meaning and this array that represents the individual is he calls it Chromosome.
How are individuals reproduced and mutated?
We can define the process of reproduction as the creation of a new individual from two given individuals, that is, making a combination of two arrays that represent two individuals. Here is an example of what this process would be like:
This is how human reproduction works, because at birth the individual inherits characteristics of the mother and others of the father. It is not necessary to inherit in equal parts the characteristics of the two parents.
In reference to the generation of new individuals, there is the possibility of a mutation in some gene; that is to say, that without any "logic" a specific element of the chromosome changes its value, for example:
Genetic algorithms
Genetic algorithms work on a set of potential solutions, which is called population. This population is composed of a series of solutions that are called individuals and an individual is made up of a series of positions that represent each of the variables involved in optimization processes called chromosomes. Chromosomes are composed of a chain of symbols that in most cases is represented in binary numbers. In a genetic algorithm, each individual is defined as a data structure that represents a possible solution to the search space of the problem. Evolution strategies work on individuals, which evolve through generations. Within the population each of the individuals is differentiated by their fitness value, which they obtain using some measures according to the problem that is going to be solved. In order to obtain the next generations, new individuals are created, which are called children, using two basic evolution strategies such as the crossover operator and the mutation operator, which are generally used in a random manner.
- Book: Artificial Intelligence a modern approach, second edition. Stuart J. Russell & Peter Norvig.
Hola @merlinrosales96, upv0t3
Este es un servicio gratuito para nuevos usuarios de steemit, para apoyarlos y motivarlos a seguir generando contenido de valor para la comunidad.
<3 Este es un corazón, o un helado, tu eliges .
: )
N0. R4ND0M:
1583 8047 6725 8634
2725 6859 6440 7146
1348 4987 4060 7706
8692 5322 4639 6697