IV. Algoritmos Genéticos


Descrição Básica

Algoritmos Genéticos são inspirados na teoria da evolução de Darwin. Solução de um problema através de algoritmos genéticos utiliza um processo evolucionário (a solução é desenvolvida).

O algoritmo começa um um conjunto de soluções (representadas por cromossomas) chamados população. Soluções de uma população são utilizadas para formar uma nova população. Isto é motivado pela esperança que a nova população será melhor do que a primeira. Soluções que são selecionadas para formar novas gerações de soluções são selecionadas de acordo com sua adequação - quanto melhores, mais chances de reprodução terão.

Esse processo é repetido até que alguma condição é satisfeita (por exemplo o número de populações ou o aperfeiçoamento da melhor solução).

Exemplo
Como você já sabe se viu o capítulo sobre espaço de soluções, a solução de problemas pode freqüentemente ser expressa como a procura pelo extremo de uma função. Nós resolveremos aqui exatamente esse problema - dada uma função o algoritmo genético tenta achar o mínimo dessa função.
Experimente rodar o algoritmo genético no applet a seguir apertando o botão "Start". O gráfico representa o espaço de soluções e as linhas verticais representam soluções (pontos no espaço de soluções). A linha vermelha é a melhor solução e as verdes são as outras.
O botão "Start" inicia o algoritmo, o botão "Step" executa um passo (isto é, produz uma nova geração), o botão "Stop" pára o algoritmo e o botão "Reset" reinicia a população.


Isto é um applet, mas seu navegador não suporta Java. Se você quer ver os applets, por favor verifique requisitos do navegador.






Esboço Básico do Algoritmo Genético

  1. [Início] Gere uma população aleatória de n cromossomas (soluções adequadas para o problema)
  2. [Adequação] Avalie a adequação f(x) de cada cromossoma x da população
  3. [Nova população] Crie uma nova população repetindo os passos seguintes até que a nova população esteja completa
    1. [Seleção] Selecione de acordo com sua adequação (melhor adequação, mais chances de ser selecionado) dois cromossomas para serem os pais
    2. [Cruzamento] Com a probabilidade de cruzamento cruze os pais para formar a nova geração. Se não realizar cruzamento, a nova geração será uma cópia exata dos pais.
    3. [Mutação] Com a probabilidade de mutação, altere os cromossomas da nova geração nos locus (posição nos cromossomas).
    4. [Aceitação] Coloque a nova descendência na nova população
  4. [Substitua] Utilize a nova população gerada para a próxima rodada do algoritmo
  5. [Teste] Se a condição final foi atingida, pare, e retorne a melhor solução da população atual
  6. [Repita] Vá para o passo 2





Alguns comentários

Como você viu, a estrutura deste Algoritmo Genético Básico é bastante geral. Há muitos parâmetros e ajustes que podem ser implementados de forma diferente em variados problemas.

A primeira questão a ocorrer é como criar cromossomas e que tipo de codificação escolher. Nós veremos então Cruzamento e Mutação, os dois operadores básicos dos Algoritmos Genéticos. A codificação do cruzamento e da mutação serão introduzidos no próximo capítulo.

A próxima questão é: como selecionar os pais para o cruzamento? Isso pode ser feito de muitas formas, mas a idéia principal é selecionar os melhores pais (os melhores sobreviventes), na suposição que os melhores pais produzirão as melhores descendências.

Você pode achar que gerando as populações apenas de dois pais, pode fazer com que se perca os melhores cromossomas da última população. Isto é verdade, e portanto, o elitismo é usado com freqüência. Isto significa que pelo menos uma cópia sem alterações da melhor solução da geração é passada para a nova população, de forma que a melhor solução possa sobreviver às sucessivas gerações.

Você deve estar querendo saber por que os Algoritmos Genéticos funcionam. Isso pode ser explicado parcialmente pelo Teorema do Esquema de Holland, entretanto, esse Teorema tem sido criticado ultimamente. Se você deseja saber mais, veja outras fontes.



prev             next


(c) Marek Obitko, 1998
Versão em Português do Brasil (c) Hermelindo Pinheiro Manoel
- Terms of use