São algoritmos aplicados em problemas NP (complexidade). Estão na classe de algoritmos não determinísticos que melhor dizendo, possui uma busca não necessariamente por uma solução ótima, mas sim uma boa solução baseado em ações estocásticas com menor tempo do que algoritmos de busca determinísticos. Exemplos pra tais problemas que esses tentam resolver são aqueles que tem uma característica combinatória que testar todas as combinações possíveis levaria séculos.
Explicando melhor, usarei o problema clássico. Se considerarmos um grafo qualquer com nós e arestas, aonde cada aresta conecta um ou mais nós, consideremos que o objetivo seja sair de um nó qualquer e ir para outro com a menor distancia possível.
Considerando um exemplo ilustrativo, no Grafo acima, deseja-se sair do ponto D
e ir para E
realizando o menor custo possível. Embora o grafo da imagem seja possível testar todas as combinações possíveis, é muito difícil quando considerado problemas de Grafos enormes.
Nesse contexto entra esses algoritmos, consideradas buscas meta-heurísticas. Como disse antes, a solução que esses modelos buscam não são necessariamente soluções ótimas, mas que no espaço de busca entre todas as combinações possíveis ele consiga ir em direção a melhor escolha. Para uma estrutura de algoritmo evolutivo bem definido temos:
- Função Fitness: Avalia o custo da sua solução.
- Pool de Itens: Carrega uma solução completa.
- Mecanismo de Busca: Modelo que combina ou induz de forma estocástica os indivíduos para os melhores lugares no espaço de busca.
A priore, algoritmos evolutivos são subconjuntos de algoritmos inteligentes, e contem alguns modelos propostos de algoritmos evolutivos, que no geral compartilham da estrutura acima.
Para exemplificar, um modelo clássico para resolver o modelo proposto de roteamento no grafo seria um algoritmo genético. Então para construir o modelo, consideramos uma função fitness que o custo é o tamanho das arestas, e o pool de "indivíduos" são constituídos de um vetor de itens a serem considerados. Para ficar mais compreensível, um individuo pode ser descrito como {D, A, B, E}
e outro {D, F, G, E}
, o primeiro tem um custo de 5+7+7=19
e o segundo 6+11+9=26
, aonde o primeiro tem uma função fitness melhor e portanto, um melhor individuo que o segundo. Já no mecanismo de ação para que esses indivíduos sejam atualizados, podemos descrever algo bem simples como mutação que usa dois dos indivíduos do pool para gerar um terceiro. Observando que no problema do grafo existem restrições nas quais o algoritmo que você esta modelando precisa respeitar.
- Não conectar arestas desconectas.
- Que o indivíduo tenha D no início e E no final.
Ou seja, algoritmos evolutivos na grande maioria das vezes são modelados para resolver problemas específicos, com construção especifica para que contenham restrições e de forma estocástica se alterem, a nível de indivíduos (Portadores de soluções) para melhorar sua solução no espaço de busca, por mais que tenha uma ideia por trás, são construído de acordo com o problema a se resolver.
Em geral, eu aconselho que busque informações sobre como resolver problemas NP-Hard, esses algoritmos pertencem a disciplina de inteligência computacional e muito provavelmente são formas rápidas para encontrar soluções boas. Procure também sobre otimizadores que são o Core de modelos de Inteligência Artificial.
Considerações e Correções.
O problema que eu citei é do caminho mínimo, com solução fácil. O inverso do problema é o de caminho mais longo. O problema do caminho mais curto num grafo dirigido ou não dirigido com arestas de peso não negativo é solucionado, em tempo computacional, pelo algoritmo de Dijkstra.