Total de visualizações de página

sábado, 3 de março de 2012

Algoritmo Genético

Neste post vamos abordar um pouco sobre IA, mais especificamente os Algoritmos Genéticos. Primeiramente, para os que não convivem muito com os termos da Ciência da Computação, IA significa Inteligência Artificial. IA pode ser conceituada como o estudo de sistemas que possuem a capacidade de aprender e interagir como o ambiente. Esse conceito, de minha autoria, procura ser abrangente, pois esse ramo da computação é bem vasto e complexo, além de envolver outras ciências. Aproveitando, já que o assunto é Algoritmos Genéticos, penso que para nivelarmos o conhecimento é necessário uma pequena revisão sobre Genética.

Genética
Resumidamente, Genética é o estudo do gene. Os genes são partes do DNA e neles estão contidos os dados necessários para a formação de um novo indivíduo (qualquer organismo vivo), como também os dados de uma determinada célula.
Como um gene é um constituinte do DNA, deve-se lembrar que o DNA é formado por bases nitrogenadas: Timina (T), Guanina (G), Citosina (C) e Adenina (A). Desse modo, um gene pode ser representado como uma sequência de bases nitrogenadas: TTAGCCTACCCGGT. Com o auxílio da figura 1 pode-se verificar as bases nitrogenadas, as quais estão representadas pelos retângulos coloridos: laranja, amarelo, verde e vermelho.

Figura 1: Estrutura do DNA
Fonte: <http://publications.nigms.nih.gov/thenewgenetics/chapter1.html>



Algoritmo Genético
Algoritmo Genético é um método de busca que visa a obtenção de soluções ótimas. Os Algoritmos Genéticos possuem algumas etapas, como: verificação da aptidão, seleção de indivíduos, cruzamento, mutação, análise dos indivíduos filhos e inserção deles na população. Para todas estas etapas pode-se utilizar um modelo binário de amostra que representa um indivíduo de uma população. Esse modelo é composto por genes, como mostra a figura 2.

Figura 2: Modelo de indivíduo
Fonte: do autor

Baseado neste modelo sugerido, a população geral poderia conter 127 indivíduos do sexo feminino e 127 do sexo masculino.
Depois de criada a população, deve-se verificar a aptidão dos indivíduos. Para o exemplo que está sendo criado neste artigo, adotar-se-á que a conversão binária, onde o 1 sugere que aquele gene é perfeito. Supondo que o terceiro gene do modelo fosse o da resistência a doenças, o indivíduo mostrado na figura 2 possuiria essa aptidão. Ainda verificando o indivíduo da figura 2, sua aptidão seria 77. Para facilitar uma análise futura, esse valor poderia ser transformado num percentual e o valor obtido, por meio de uma regra de 3 simples, seria igual a 60,63%. Quanto maior o percentual, maior o número de genes perfeitos.
Após a criação dos indivíduos e a análise de sua aptidão pode iniciar a fase de cruzamento. Como o objetivo do Algoritmo Genético é um resultado ótimo, alguns indivíduos poderiam ser selecionados aleatoriamente, uns cinco indivíduos de cada sexo, por exemplo. Em seguida, os dois indivíduos mais aptos de cada sexo seriam selecionados para reprodução. Como uma regra para a manutenção do mesmo número total de indivíduos o indivíduo mais apto selecionado do sexo masculino cruzaria com o segundo indivíduo mais apto do sexo feminino e vice-versa, como mostra a figura 3.

Figura 3: Seleção de indivíduos para o cruzamento
Fonte: do autor

Com a ajuda dos valores do exemplo da figura 3, o cruzamento ocorrerá, segundo as regras supracitadas, entre os indivíduos de valor 205 (masculino) com o de valor 82 (feminino) e, também, os indivíduos de valor 183 (masculino) com o 115 (feminino). O cruzamento consiste, no modelo adotado por este artigo, de manter-se os quatro genes mais significativos do indivíduo mais apto com os três menos significativos do segundo, além de manter-se o sexo do mais apto, como pode ser visto nas figuras 4 e 5.

Figura 4: Cruzamento de indivíduos selecionados, exemplo 1
Fonte: do autor

Figura 5: Cruzamento de indivíduos selecionados, exemplo 2
Fonte: do autor

Seguindo os exemplos da biologia (regras da evolução) após o cruzamento temos a etapa de mutação. A mutação serve para gerar variabilidade genética, isso é essencial para que uma espécie não seja dizimada por alguma doença, por exemplo. Nesta etapa foi adotado um critério de troca de posição de dois genes, o segundo pelo sétimo. Caso sejam observados os indivíduos resultantes na figura 4 e 5, observar-se-á que o indivíduo resultante não sofre alteração.
A última etapa deste modelo de Algoritmo Genético consiste da recolocação do indivíduo resultante na população de “escolhidos”. Para manutenção do número total de indivíduos e para que o aprimoramento ocorra, o indivíduo de menor valor é retirado dos indivíduos selecionados (desprezado).

Implementação
O modelo aqui descrito foi implementado em JAVA. Foi criada uma classe AMOSTRA, a qual possuía os genes (Gene 1, Gene 2, ..., Gene 8), um índice (valor decimal dos genes) e o valor de aptidão em percentual.

Figura 6: Implementação da classe AMOSTRA
Fonte: do autor

Na classe Algoritmo Genético (MAIN) foram programadas as etapas descritas neste artigo.

Este assunto é um pouco extenso e, por isso, dúvidas podem não ter sido solucionadas. Para auxiliar no aprofundamento neste assunto sugiro os seguintes livros:
- Inteligência Artificial, do Ben Coppin;
- Inteligência Artificial, do Stuart J. Russell e Peter Norvig.

Lembre-se, qualquer dúvida é só me contatar: silveira-fabio@hotmail.com. Não esquecendo de colocar no assunto que trata-se de uma dúvida do Blog.
Obrigado!