Blog do Eduardo

Tecnologia, Inovação, Negócios e muito mais...

Algoritmo Genético

Inteligência Artificial

  • 20 de Outubro de 2017 às 23:59
Capa Post
Inteligência Artificial

Se enquadra na classe de "Algoritmos Evolutivos", pois se baseia em uma gama de mecanismos da evolução biológica. Particularmente foi inspirado com o na Teoria de Genética de Mendel  e de Darwin. Tem como objetivo resolver um problema de otimização.

Um indivíduo é formado por uma cadeia de atributos definidos e finitos. Uma cadeia são definidas segundo a modelagem do problema, entretanto costuma ser valor binários (0 ou 1) ou alfanuméricos (A, B, C, ....). Os atributos são entendidos como características ou tem uma função especifica para formar um indivíduo, ou seja, representam valores para modelar o problema. Na "Figura 1" abaixo, mostra um exemplo de indivíduos:

Figura 1 - Processo do Algoritmo Genético

  1. Cria-se uma população inicial, normalmente aleatória;
  2. Escolhem-se os indivíduos de melhor valor (dado pela função de aptidão) como base para a criação de um novo conjunto de possíveis soluções, chamado de nova "geração";
  3. Aplica-se sobre os indivíduos selecionados operações que misturem suas características (chamadas "genes"), por meio de "cruzamento" ("crossover");
  4. Para garantir uma maior variabilidade, algumas das suas características (chamadas "genes") passam por uma "mutação" ("mutação");

O algoritmo inicia criando um conjunto de indivíduos aleatório com atributos aleatórios, é importante criar uma população inicial grande o suficiente para haver todos os atributos representados nos indivíduos. Isso pode várias para cada caso dependendo da regra para criação de um indivíduo, por isso o número mínimo necessário para a população inicial pode varias. Por exemplo, se formos representar a nossa cadeia com um conjunto de atributos alfanuméricos, que para simplificar um pouco as contas, correspondem as 26 letras do alfabeto, na nossa cadeia temos 8 caracteres, permitindo que os atributos repitam, utilizaremos a teoria de Arranjos com Repetição para representarmos todos os possíveis indivíduos dessa população que de 208.827.064.576 indivíduos

Formúla

Pensando se realizarmos esse esforço por força bruta, levando em conta que todo processo para gerar um novo indivíduo diferente demorasse algo próximo de 100ms, iriamos demorar aproximadamente 66.219 anos aproximadamente para gerar todos os indivíduos possíveis.

Como é obvio, não faz sentido criarmos uma população com todos os indivíduos possíveis, pois simplesmente além de ser inviável, foge do objetivo inicial que era otimizar a solução. Entretanto deve-se garantir que a população inicial disponha de indivíduos com todos os atributos, justamente para não perdermos nenhuma característica que possa ser importante. Para resolver esse problema temos que garantir que haja todos os atributos, em pelo menos uma quantidade relevante de indivíduos e também que os mesmos sejam distribuição homogênea, a fim de garantir uma maior variabilidade para os sucessores da população.  É importante entender isso agora, pois mais adiante irá fazer sentido. Porém ainda não está claro quantos indivíduos devemos ter na nossa população inicial. Vamos partir por uma abordagem mais analítica, pensando no pior caso, quantas gerações são necessárias criarmos para termos um certo grau de confiabilidade no nosso algoritmo? Para responder isso precisamos entender o próximo passo do algoritmo.

Como foi dito anteriormente, a ideia do algoritmo foi baseada na seleção natural, ou seja, precisamos selecionar (de a para b na Figura 1) os nossos indivíduos. Para isso é criada uma função de aptidão (ou fitness), que tem como objetivo classificar o seu "grau" de qualificação. Então indivíduos que sejam "melhores" para as regras do nosso problema a devem repassar os seus atributos (os genes) e os "piores" devem ser descartados. Para isso antes devemos definir uma taxa de descarte que devemos considerar. Novamente não existe regra bem definida para essa taxa, mas particularmente costumo a me basear no Princípio de Pareto, dos 80/20, onde firma-se que, para muitos eventos, aproximadamente 80% do resultado de uma amostra, tem origem de 20% das causas.

Baseado nessa informação, o total de possibilidades (208.827.064.576) os melhores indivíduos estão entre 41.765.412.916, ainda é número grande, mas já é 80% a menos. Por exemplo, se iniciarmos com uma população de 10.000 indivíduos, com aproximadamente 4.176.542 gerações depois já teremos testado pelo menos 20% dos indivíduos. Depende de cada problema fazer essa análise, porém é sempre uma boa prática faze-la, pois garante uma maior confiabilidade ao seu algoritmo. 

 Si Indivíduo Função de Aptidão f(Si) Aptidão Relativa
S1 ABCDEFGH f(S1) = 8,80577688405317  0,303153343395305
S2 GDBEHCFA f(S2) = 9,00562822831897  0,310033554419723
S3 ECGBAFDH f(S3) = 7,36243144935013  0,253463804361337
S4 DCHGAEFB f(S4) = 3,87343299971095  0,133349297823634

A tabela a cima mostra o cálculo da função de aptidão para uma população de 4 indivíduos.

Como a função de aptidão será criada depende de cada problema, inclusive é realmente uma das partes mais difíceis de se definir nesse algoritmo. Entretanto não vamos aborda-lo aqui, pois depende muito de cada problema.  

Processo Iterativo

Para que o processo ocorra precisamos definir a nossa taxa de mutação e taxa de crossover, que normalmente varia no intervalo de 0% as 100% da geração será afetada. No caso do crossover podemos definir o corte que será realizado nos atributos, mas normalmente isso é feito de forma aleatória. O ideal é que seja um valor pequeno, justamente para evitar problemas que irei mencionar logo mais. 

Uma vez definidos esses parâmetros de seleção inicias, já podemos dar início a geração dos nossos indivíduos. Isto é feito através de processos iterativos, onde cada iteração é chamada de geração. Na Figura 1 mostra um exemplo dos processos realizados para criar uma nova geração de indivíduos. Na abordagem mais comum para selecionar os indivíduos, o algoritmo escolhe "aleatória", porém utiliza a função adaptação para realizar a distribuição, ou seja, quem tem um valor maior para a função adaptação, tem mais chances de ser escolhido. Uma vez selecionados devemos nos atentar a alguns pontos.

Convergência Prematura

Existem algumas características indesejada do algoritmo de AG que podem causar a convergência prematura, são elas:

  • Excessivo número de filhos de um mesmo indivíduo (o super indivíduo);
  • Perda de diversidade da população;
  • Deriva Genética (Genetic Drift), onde um atributo acaba tranando-se mais frequente na população;
  • Desaparecimento de genes na população devido puramente ao acaso;
  • Alta pressão de seleção;

Algumas dessas causas podem ser previstas, outras somente devemos observar se estão ocorrendo enquanto o algoritmo está executando. Por esse motivo é importante termos dados em tempo real para "ajustarmos" a nossa população em tempo de execução. Podemos eliminar essas consequências da seguinte forma:

  • Evitando cromossomos duplicados na mesma população.
  • Aumentar a taxa de mutação;
  • Diminuindo a pressão da seleção, suavizando a nossa função adaptação.
Conclusão

Não há garantias de que chegamos nos melhores indivíduos para a nossa solução, porém é uma técnica muito poderosa quando não existe nenhum algoritmo que resolva a solução em tempo polinomial, somente em tempo exponencial. Porém devemos usá-lo sempre tomando cuidado para evitar comportamentos indesejados.

 

Referências:

Algoritmos Genéticos - ICMS USP

COMPUTAÇÃO EVOLUTIVA - Grupo d e Pesquisas em Computação Evolutiva

Cover Image
Livro: Artificial Intelligence: A Modern Approach

3rd Prentice Hall Press Upper Saddle River, NJ, USA ©2009

ISBN-10: 0136042597

ISBN-13: 9780136042594

Algoritmo Inteligência Artificial Programação
  • COMENTÁRIOS: 1

  • Guilherme 7 de Março de 2018 às 15:17


    Boa tarde, você saberia me dizer como ficaria o algoritmo genético em pseudocódigo ou portugol?

    • RESPOSTAS: 1

    • Eduardo Martins 9 de Março de 2018 às 13:06


      Olá Guilherme, tudo bem? No link de referência (http://conteudo.icmc.usp.br/pessoas/andre/research/genetic/) possui um pseudocódigo genérico. Mas como eu explico no artigo, o mais difícil é criar a função aptidão. Abraços

Você tem o permissão de:

Compartilhar: copiar e redistribuir o material em qualquer suporte ou formato.

Adaptar: remixar, transformar, e criar a partir do material para qualquer fim, mesmo que comercial.

Esta licença é aceitável para Trabalhos Culturais Livres. O licenciante não pode revogar estes direitos desde que você respeite os termos da licença.


Blog do Eduardo - Todos os direitos reservados © 2020 Licença Creative Commons