What are genetic algorithms?

Darwinism

Starting the answer with the classic phrase of Charles Darwin, which can be found in his book "The Origin Of Species" (1859):

The better an individual adapts to their environment, the Greater it will be your chance to survive and spawn offspring.

When we hear about Darwinism , we already associate evolution, natural selection, among others. The characteristic that most distinguishes Darwinism from all other theories are that evolution is seen as a function of the change of the population and not of the change of the individual and it is there that the genetic algorithm enters, since as its development, biologists, physicists, mathematicians and scientist can describe evolutionary processes similar to the evolution of life.

Thinking about the conditions that a Darwinist process requires:

• reproduction: agents must be able to produce copies of themselves and such copies must also have the ability to reproduce;
• heredity: copies must inherit the characteristics of the originals;
• variation: occasionally copies have to be imperfect (diversity within the population);
• Natural Selection: individuals are selected by the environment. Natural selection destroys, and does not create. The problem of the existence of a goal does not arise from the elimination of the unfit, but from the origin of the able.

In any system where they occur these characteristics should occur evolution.

Having these concepts in mind, we can talk a little about the genetic algorithm itself.

Genetic algorithm

Definition:

A genetic algorithm (AG) is a search technique used in science to find approximate solutions to problems of optimization and search, mainly based on the American John Henry Holland. Genetic algorithms are a particular class of evolutionary algorithms using techniques inspired by biology evolution as heredity, mutation, natural selection and recombination (or crossing over).

Source: Wikipedia

And what does that mean?

Think of the" laws of nature", individuals from the same population compete with each other, primarily seeking survival, whether in the search for food or reproduction. The fittest individuals will have a larger number of offspring. O genetic algorithms simulate these processes of survival and reproduction of populations.

Genetic algorithms are methods of optimization and search, which were inspired by the mechanisms of evolution of populations of living beings. They follow the principle of natural selection and survival of the fittest.

Optimization is the search for the best solution to a given problem, consisting of trying several solutions and using the information obtained in this process in order to find better and better solutions.

Genetic algorithms differ from traditional search and optimization methods, mainly in four aspects:

1. They work with a parameter set encoding and not with the parameters themselves.

2. They work with a population and not with a single point.

3. They use cost or reward information and not derived or other ancillary knowledge.

4. Use rules of probabilistic and non-deterministic transition.

função AlgoritmoGenético(população, função-objetivo) saídas: indivíduo
  entradas: população→ uma lista de indivíduos
            função-objetivo→ uma função que recebe um indivíduo e retorna um número real.
  repetir
     lista de pais := seleção(população, função-objetivo)
     população := reprodução(lista de pais)
  enquanto nenhuma condição de parada for atingida
  retorna o melhor indivíduo da população de acordo com a função-objetivo

Code of the Wikipedia.

Genetic algorithms are very efficient for finding optimal, or roughly optimal, solutions to a wide variety of problems, as they do not impose many of the limitations found in traditional search methods.

Operation

In 1975, HOLLAND , decomposed the functioning of genetic algorithms into the following steps: initialization, evaluation, selection, crossing, mutation, update and finalization.

Basically, what a genetic algorithm does is create a population of possible answers to the problem to be treated ( initialization ) and then submit it to the process of evolution, consisting of the following steps:

• Evaluation : the aptitude of the solutions (individuals of the population) is evaluated, an analysis is made to establish how well they they respond to the proposed problem.

• Selection : individuals are selected for breeding. The probability that a given solution i will be selected is proportional to its suitability. Can be used roulette method, elitism, etc..

• Crossing : characteristics of the chosen solutions are recombined, generating new individuals.

• Mutation : characteristics of individuals resulting from the reproduction process are changed, thereby adding variety to the population.

• Update : individuals created in this generation are inserted into the population.

• Completion : verifies that the conditions for ending the evolution have been reached, returning to the evaluation stage in a negative case and ending the execution in a positive case.

Because it is quite a technique widespread and generally offer good results, genetic algorithms are used to solve several types of problems, among them: classification systems, scheduling and time grid.

References:

• Genetic Algorithms
• evolutionary computation
• Apostille Genetic Algorithms