What are evolutionary algorithms?
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 evolutionary ...
So I would like to know:
- What are evolutionary algorithms?
- what make up evolutionary algorithms?
3 answers
Are algorithms applied in NP (complexity) problems. They are in the class of non-deterministic algorithms that better 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 they try to solve are those that have a combinatorial characteristic that testing all possible combinations would take centuries.
Explaining better, I'll use the classic problem. If we consider any graph with nodes and edges, where each edge connects one or more nodes, consider that the goal is to leave one node and go to another with the shortest possible distance.
Considering an illustrative example, in the graph above, you want to exit the point D and go to E at the lowest possible cost. Although the graph of the image is possible to test all possible combinations, it is very difficult when considering huge graph problems.
In this context enter these algorithms, considered meta-heuristic searches. As I said before, the solution that these models seek are not necessarily optimal solutions, but that in the search space between all possible combinations he can go towards the best choice. For a well-defined evolutionary algorithm structure we have:
- Fitness function: evaluates the cost of your solution.
- item Pool: Loads a complete solution.
- Search Engine: a model that combines or stochastically induces individuals to the best places in the search space.
A priore, evolutionary algorithms are subsets of intelligent algorithms, and contains some proposed models of evolutionary algorithms, which generally share the above structure.
For example, a classic model for solving the proposed routing model on the graph would be an algorithm genetic. So to build the model, we consider a fitness function that cost is the size of the edges, and the pool of "individuals" are made up of a vector of items to be considered. To be more understandable, an individual can be described as {D, A, B, E} and another {D, F, G, E}, the former has a cost of 5+7+7=19 and the latter 6+11+9=26, where the former has a better fitness function and therefore a better individual than the latter. Already in the mechanism of action for these individuals to be updated, we can describe something quite simple as a mutation that uses two of the individuals in the pool to generate a third. Note 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 in the vast majority of times are modeled to solve specific problems, with specific construction for that contain restrictions and stochastically change, at the level of individuals (solution carriers) to improve their solution in the search space, no matter how 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. Look also about optimizers that are the Core of Artificial Intelligence models.
Considerations and Corrections.
The problem I cited is of the minimum path, with easy solution. The inverse of the problem is the longer way. The shortest path problem in a directed or undirected graph with edges of non-negative weight is solved, in computational time, by Dijkstra's algorithm.
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 output of the machine and the expected output for solution of the problem. Reproduction is done only by mutation operators, and all individuals of the current population generate new offspring. This process characterizes the call asexual reproduction. In the selection of individuals for the next generation, the offspring they compete with the µ parents and only the individuals with greater fitness (in the case, those of higher 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. The total mastery of the best individuals is called total elitism (Kuri-Morales and Gutiérrez-García, 2001; Kuri-Morales, 2004). The most widely used elitism guarantees the survival of only the K-best individuals, k
Well I'm not going to go into extremely technical details because it would even harm you at this point and 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'll pull more to the side of Lamarck's theory.
"an example of his theory is that in the old days there were small-necked giraffes. the food in the Bass has an extremely high competitiveness, so only some animals they could eat. what happened to the small-necked giraffes? they had difficulty feeding and this forced an evolution."
What else does this have to do with genetic algorithms? Everything.
How would we make an algorithm to create giraffes adapted to today's world?.
Imagine that we have a vector with 8 small-necked giraffes, each born with a neck of one size and that we have a world full of fruit trees, trees of several size, of course the taller the tree the 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 the trees)
Well we reached the end of the life cycle and of the 8 giraffes only 4 were able to feed enough without starving, that's because their necks were naturally larger.
Then in genetic algorithms we start a new cycle, passing the experiences of previous giraffes.
Of the 4 survivors were 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. We basically apply the law of the strongest.
Good it is clear that genetic algorithms exist n models, the one I cited is the most classic of all, but we have others like " tournament method / Russian roulette / crossing with mutation / cross 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 them to solve scrambled text, solve the best route for a trip and even pass game stages (like mario, snake game, google kkk dinosaur)...
Advantages
- often solve the problem.
- will always correct to get the better results.
Disadvantages
- it may take several cycles to solve the problem.
- you will never get the same result 2 times (genetic algorithms work a lot with Aletoriousness).