Algoritmos Genéticos

 Algoritmos Genéticos

Atividades de busca e otimização são sempre necessárias nos mais diversos ambientes, essas atividades possuem vários componentes, entre eles: o espaço de busca, onde são consideradas todas as possibilidades de solução de um determinado problema e a função de avaliação (ou função de custo), que é função que avalia a qualidade dos membros do espaço de busca. Existem muitos métodos de busca e funções de avaliação. 

Nesse sentido a utilização dos algoritmos Genéticos mostra-se eficiente na busca de soluções ótimas, ou aproximadamente ótimas em uma grande variedade de problemas, pois não impõem muitas das limitações encontradas nos métodos de busca tradicionais.  

Para mais detalhes teóricos sobre o funcionamento dos algoritmos genéticos, leia nosso primeiro post sobre esse tema. Esse post possui carácter mais prático.

Os passos para construção dos algoritmos genéticos são descritos na sequencia e na imagem a seguir.

• [Início] Geração aleatória de uma população de n cromossomos. 
• [Adaptação] Verificar a função objetivo f(x) de cada cromossomo. 
• População] Cria-se uma nova população pela repetição 
• [Seleção] Selecione um par de cromossomos da população de acordo com a adaptação de cada um (os mais bem adaptados  tem maior chance de serem escolhidos) 
• [Crossover] Produza dois descendentes (filhos) realizando cruzamento com os cromossomos dos pais. O ponto para a realização do cruzamento deve ser aleatório. 
• [Mutação] Com uma certa probabilidade, o descendente  sofre mutação em cada posição no cromossomo.  
• Aceitação] Coloque os descendentes em uma nova população, juntamente com a melhor solução da geração velha.

 

 Abaixo é mostrado um exemplo de algoritmo genético. 


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çao de parada for atingida
 retorna o melhor indivíduo da população de acordo com a função-objetivo  

Agora se você quer um exemplo mais complexo e em Java, acesse aqui.
 

Por,

Gleyser Guimarães - Integrante do PET Computação