What are evolutionary algorithms?

Question

Researching on Evolutionary Programming, I came across the question What are genetic algorithms?

In an excerpt from the answer:

... Genetic algorithms are a particular class of algorithms evolutive ...

so I’d like to know:

1. What are evolutionary algorithms?
2. What make up the evolutionary algorithms?

Answer 1

They are algorithms applied to NP (complexity) problems. They are in the class of nondeterministic algorithms that better to say, has a search not necessarily for an optimal solution, but rather a good solution based on stochastic actions with less time than deterministic search algorithms. Examples for such problems that these try to solve are those that have a combinatorial characteristic that testing all possible combinations would take centuries.

To put it bluntly, I’ll use the classic problem. If we consider any graph with nodes and edges, where each edge connects one or more nodes, let us consider that the goal is to get out of any node and go to another with the shortest possible distance.

Considering an illustrative example, in the Graph above, one wants to leave the point D and go to E performing the lowest possible cost. Although the image graph is possible to test all possible combinations, it is very difficult when considering huge graph problems.

In this context comes these algorithms, considered metaheuristic searches. As I said before, the solution that these models seek are not necessarily optimal solutions, but that in the search space among all possible combinations it manages to go in the direction of the best choice. For a well-defined evolutionary algorithm structure we have:

• Fitness Function: Assesses the cost of your solution.
• Item Pool: Loads a complete solution.
• Search Engine: Model that combines or induces individuals stochastically to the best places in the search space.

Previously, evolutionary algorithms are subsets of intelligent algorithms, and contain some proposed models of evolutionary algorithms, which in general share the above structure.

To illustrate, a classical model for solving the proposed routing model in the graph would be a genetic algorithm. So to build the model, we consider a fitness function that costs the size of the edges, and the pool of "individuals" are made up of a vector of items to be considered. To make it more understandable, an individual can be described as {D, A, B, E} and another {D, F, G, E}, the first has a cost of 5+7+7=19 and the second 6+11+9=26, where the former has a better fitness function and therefore a better individual than the latter. In the mechanism of action for these individuals to be updated, we can describe something very simple as a mutation that uses two of the individuals in the pool to generate a third. Noting that in the graph problem there are constraints in which the algorithm you are modeling needs to respect.

• Do not connect disconnected edges.
• That the individual has D at the beginning and E at the end.

That is, evolutionary algorithms are most often modeled to solve specific problems, with specific construction to contain restrictions and in a stochastic way change, at the level of individuals (Solution carriers) to improve your solution in the search space, however much you have an idea behind, are built according to the problem to be solved.

In general, I advise you to look for information on how to solve NP-Hard problems, these algorithms belong to the discipline of computational intelligence and are most likely quick ways to find good solutions. Also look for optimizers that are the core of Artificial Intelligence models.

Considerations and Corrections.

The problem I mentioned is of the minimum path, with easy solution. The inverse of the problem is the longer path. The shortest path problem in a directed or undirected graph with non-negative-weight edges is solved in computational time by Dijkstra’s algorithm.

Answer 2

In evolutionary programming, each individual in the population is represented by a finite state machine (MEF) which processes a sequence of symbols. During the evaluation, individuals are analyzed by a payoff function according to the machine output and the expected output to solution of the problem. Reproduction is done only by mutation operators, all of which individuals of the current population generate new descendants. This process characterizes the so-called asexual reproduction. In selecting individuals for the next generation, the descendants compete with the µ parents and only the individuals with the highest fitness (in this case, the greater payoff among µ + λ individuals) survive.

Evolutionary Programming ensures that all individuals will produce new offspring and only the best individuals between the present and the descendants survive. Total mastery of the best individuals are called total elitism (Kuri-Morales and Gutiérrez-García, 2001; Kuri-Morales, 2004). The most widely used elitism ensures the survival of only the best individuals, k < N, where N is the population size. Total elitism, however, can decrease significantly the diversity of individuals, which may stagnate in optimal locations and/or increase the convergence time of the algorithm (De Jong, 2006).

Source

Answer 3

Well I won’t go into extra technical details because that would even harm you right now and would only create more confusion in your mind... But come on!

Have you seen Charles Darwin’s theory of evolution or Lamarck’s theory? Well I’m going to pull more to the side of Lamarck’s theory.

"An example of his theory is that once there were giraffes with small necks. the food on the bottom has an extremely high competitiveness, so only a few animals could eat. what happened to the small-necked giraffes? they had difficulties feeding and this forced an evolution."

Is this more about genetic algorithms? Everything.

How we would make an algorithm to create giraffes adapted to today’s world?.

Imagine that we have a vector with 8 small-necked giraffes, each one born with a neck of one size and that we have a world full of fruit trees, trees of several sizes, of course that the higher the tree more fruits it has.

So it is common in genetic algorithms to create a life cycle so that our agent (giraffe) can live and collect the goals (fruits of trees)

Well we reached the end of the life cycle and the 8 giraffes only 4 managed to feed enough without dying of hunger, this because their necks were naturally larger.

So in genetic algorithms we start a new cycle, passing the experiences of the previous giraffes.

of the 4 survivors born 8 giraffes and the cycle begins again...

There will come a time when the surviving giraffes will have their necks high enough to feed without starving to death. Basically we apply the law of the strongest.

---

Well of course genetic algorithms exist n models, the one I mentioned is the most classic of all, but we have others like " method tournament | Russian roulette | crossing with mutation | crossing 1 to N "

When should one use this type of algorithm? If you have noticed these algorithms learn through trial and error.

It is very common to use to solve scrambled text, solve the best route for a trip and even pass stages of games (such as mario, Snake game, google kkk dinosaur)...

Perks

• Often they solve the problem.
• You will always correct yourself for the best results.

Disadvantages

• It can take several cycles to reach the solution of the problem.
• You will never get the same result 2 times (Genetic Algorithms Work Hard with Allergy).