16

Pesquisando sobre o Programação Evolutiva, me deparei com a pergunta O que são algoritmos genéticos?

Em um trecho da resposta:

... Algoritmos genéticos são uma classe particular de algoritmos evolutivos ...

então, gostaria de saber:

  1. O que são algoritmos evolutivos?
  2. O que compõem os algoritmos evolutivos?

3 Respostas 3

9

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.

Exemplo de problema

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.

2
  • 2
    Só uma coisa: menor distância entre dois pontos, para arestas com distâncias não negativas, é um problema P. Prova disso? Algoritmo de Djikstra, resolve o problema com a melhor solução em tempo polinomial no número de vértices. Creio que você desejaria usar o problema do caminho hamiltoniano ou o problema do caixeira viajante... Commented 4/01/2019 às 17:21
  • Sim, considerando a correção. Muito obrigado! Commented 4/01/2019 às 17:28
7

Em Programação Evolutiva, cada indivíduo da população é representado por uma máquina de estados finitos (MEF), que processa uma seqüência de símbolos. Durante a avaliação, os indivíduos são analisados por uma função de payoff de acordo com a saída da máquina e a saída esperada para solução do problema. A reprodução é feita apenas por operadores de mutação, sendo que todos os indivíduos da população atual geram novos descendentes. Esse processo caracteriza a chamada reprodução assexuada. Na seleção de indivíduos para a próxima geração, os descendentes competem com os µ pais e somente os indivíduos com maior fitness (no caso, os de maior payoff entre os µ + λ indivíduos) sobrevivem.

A Programação Evolutiva garante que todos os indivíduos produzirão novos descendentes e, somente, os melhores indivíduos entre os atuais e os descendentes sobrevivem. O domínio total dos melhores indivíduos é chamado elitismo total (Kuri-Morales e Gutiérrez-García, 2001; Kuri-Morales, 2004). O elitismo mais utilizado garante a sobrevivência apenas dos k-melhores indivíduos, k < N, onde N é o tamanho da população. O elitismo total, no entanto, pode diminuir significativamente a diversidade de indivíduos, podendo estagnar em ótimos locais e/ou aumentar o tempo de convergência do algoritmo (De Jong, 2006).

Fonte

0
2

Bom não vou entrar em detalhes extramente técnicos pois isso até o prejudicaria neste momento e só criaria mais confusão em sua mente... Mas vamos lá!

Você já viu a teoria da evolução de Charles Darwin ou a Teoria de Lamarck? Bom vou puxar mais para o lado da teoria de Lamarck.

"um exemplo de sua teoria é que antigamente existiam girafas de pescoço pequeno. a comida no baixo tem uma competitividade extremamente alta, por isso só alguns animais conseguiam comer. o que aconteceu com as girafas de pescoço pequeno? tiveram dificuldades para se alimentar e isso forçou uma evolução."

Tá mais o que isso tem haver com algortimos geneticos? Tudo.

Como fariamos um algoritmo para criar as girafas adaptadas para o mundo de hoje?.

Imagine que temos um vetor com 8 girafas de pescoço pequeno, cada uma nasceu com o pescoço de um tamanho e que temos um mundo cheio de arvores frutiferas, arvores de diversos tamanho, claro que quanto mais alta a arvore mais frutos ela tem.

Então é comum em algoritmos geneticos criarmos um ciclo de vida para que nosso agente (girafa) consiga viver e coletar os objetivos (frutos das arvores)

Bom chegamos ao fim do ciclo de vida e das 8 girafas apenas 4 conseguiram se alimentar o suficiente sem morrer de fome, isso porque seus pescoços eram naturalmente maiores.

Então em algoritmos geneticos iniciamos um novo ciclo, passando as experiencias das girafas anteriores.

das 4 sobreviventes nasceram 8 girafas e o ciclo começa novamente...

Vai chegar um momento que as girafas sobreviventes terão os pescoços altos o suficiente para se alimentar sem morrer de fome. Basicamente aplicamos a lei do mais forte.


Bom é claro que algoritmos geneticos existem n modelos, esse que citei é o mais classico de todos, mas temos outros como " metodo torneio | roleta russa | cruzamento com mutação | cruzamento 1 para N "

Quando se deve usar esse tipo de algoritmo? Se você notou esses algoritmos aprendem atravez da tentativa e erro.

É muito comum usarem para resolver texto embaralhado, resolver a melhor rota para uma viagem e até mesmo passar fases de jogos (como mario, snake game, dinossauro do google kkk)...

Vantagens

  • Muitas Vezes solucionam o problema.
  • Sempre vai se corrigir para obter os melhores resultados.

Desvantagens

  • Pode demorar varios ciclos até alcançar a solução do problema.
  • Você nunca vai ter o mesmo resultado 2 vezes (Algoritmos Geneticos Trabalham muito com a Aletoriedade).

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .