Uma Introdução aos Algoritmos Genéticos – Parte 1

Introdução aos Algoritmos Genéticos

Na área de Inteligência Artificial, há uma grande diversidade de abordagens existentes: simbólica, evolutiva, conexionista, híbrida e distribuída.
Para cumprir o nosso objetivo de formar sólidos conhecimentos em computação inteligente, estudaremos agora a abordagem evolutiva.
A abordagem evolutiva inspira-se na forma como seres vivos sobrevivem e passam seu material genético geração após geração, ou seja, por meio da evolução das espécies.
Enquanto que as espécies sofrem seleção natural segundo suas capacidades (expressas por meio de seus comportamentos – fenótipo – e genomas – genótipo) a fim de determinar quais são mais aptas a sobreviver e, conseqüentemente, ter maiores chances de reproduzir novos seres, de forma similar ocorre naquilo que chamamos de Inteligência Artificial Evolutiva, que se baseia principalmente na evolução das espécies como forma de alcançar a solução para um problema. Em outras palavras, a abordagem evolutiva baseia-se na “lei do mais forte”, onde aqueles que são mais aptos à sobrevivência permanecem, repassando, assim, a sua combinação genética para seus herdeiros.

Os algoritmos que se utilizam dos princípios da abordagem evolutiva são conhecidos como algoritmos genéticos.

Sendo assim, neste (e em artigos posteriores), discutiremos sobre algoritmos genéticos e como melhor empregá-los.

Algoritmos genéticos e a evolução genética dos seres vivos

Conforme enunciamos anteriormente, os algoritmos genéticos inspiram-se na evolução genética dos seres vivos a fim de melhor compreender como a natureza competitiva em que se encontram ajuda-os a buscarem ser o “mais forte”, que não significa somente força, mas um conjunto de informações que, quando processadas no meio em que se encontram, trazem melhores resultados que outras combinações daquelas informações.
Tomemos como exemplo uma população de tigres. A vida de um tigre não é fácil, pois precisa correr bastante para garantir cada refeição. Eis que, dentre os membros de uma comunidade de tigres, alguns deles melhor se sobressaem em relação aos outros. O que acontecerá?
Bem, segundo a teoria da “sobrevivência do mais forte”, esses membros com melhor desempenho terão maiores chances de sobrevivência no meio em que se encontram. Sendo assim, é provável que muitos dos membros dessa comunidade da próxima geração sejam seus herdeiros.
Vale lembrar também que os herdeiros carregam características de seus pais. Isso se dá pelo fato de ter recebido uma combinação feita a partir de seus cromossomos, sendo, portanto os cromossomos responsáveis por manter as informações sobre as características daquele ser.
Perceba que, nesta nossa história, tivemos alguns elementos importantes: uma população de seres a ser testada (pode ser a observação da rotina daquela população), a estrutura onde armazenaremos a informação (no caso, os cromossomos), a seleção dos seres com melhor desempenho e, então, a sua reprodução (combinando, assim, seus cromossomos).
Algoritmos genéticos trabalham de forma bem similar a este processo, usando uma população inicialmente configurada com parâmetros escolhidos aleatoriamente para os seus cromossomos, simulação e testes da mesma a fim de dar alguma pontuação a cada indivíduo, seleção dos mais aptos e, então, a reprodução destes.
Perceba com isso que, ao final do processo, geramos uma nova população. Se conseguirmos encontrar seres um pouco melhores, mais “inteligentes”, com uma iteração, por que não aplicar várias outras?
Sendo assim, a nova população gerada serve como população para novos testes, onde selecionaremos novamente os melhores para reproduzi-los, criando assim um ciclo de busca progressiva de seres com comportamentos ideais.
Os algoritmos genéticos baseiam-se assim na combinação da estratégia “gerar-e-testar” combinada com a teoria darwiniana da evolução e com a genética.
Desta forma, podemos dizer que um algoritmo genético executa os seguintes passos:

  • (1) Cria uma população de seres inicialmente atribuindo valores aleatórios aos seus cromossomos;
  • (2) Executa-se um teste / simulação com a atual população visando pontuar cada um de seus membros;
  • (3) Selecionam-se os membros com melhor desempenho (pontuação);
  • (4) Se condição de parada foi atingida (um número máximo de gerações, por exemplo), encerre algoritmo e retorne os membros encontrados em (3) como sendo a solução;
  • (5) Executa-se a reprodução de uma nova população, onde os pais serão os melhores membros encontrados em (3). Durante a reprodução, podem-se aplicar técnicas a fim de garantir que a diversidade de cromossomos não será perdida. Diversidade esta que pode ser conquistada por meio de crossover e mutações, por exemplo;
  • (6) Retornar ao passo (2).

Antes de começarmos a descrever cada etapa apontada, precisamos compreender a estrutura de um cromossomo.

O Cromossomo

Um cromossomo trata-se de uma estrutura que irá armazenar todas as informações que nós desejamos que possam sofrer alterações durante a evolução de nossos “seres”, desta forma, para cada tipo de problema que queiramos resolver, teremos um determinado conjunto de parâmetros (genes) a serem inseridos em nosso cromossomo.
Suponhamos que estejamos trabalhando em um jogo de RPG com combate em que os personagens possuam cinco características primárias: força, poder de fogo, habilidade, armadura e resistência (sim, estas são as cinco características primárias existentes no sistema de RPG chamado 3D&T).
Desta forma, se quisermos simular partidas entre NPCs (personagens não jogáveis) a fim de descobrir qual a melhor combinação destas habilidades, podemos criar um cromossomo que contenha estas cinco informações e iterar por várias gerações, tendo então um cromossomo mais ou menos da seguinte forma:

Exemplo de características para um cromossomo em um algoritmo genético

Exemplo de características para um cromossomo em um algoritmo genético

Perceba que os dados foram todos agrupados em uma única estrutura e cada uma das características é agora um gene (ou um conjunto de genes).
Vamos supor que criemos um personagem aleatoriamente com:
•    Força = 4;
•    Poder de Fogo = 3;
•    Habilidade = 2;
•    Resistência = 1;
•    Armadura = 2.
O cromossomo deste personagem teria, então, estes valores:

Exemplo de cromossomo para um algoritmo genético

Exemplo de cromossomo para um algoritmo genético

Levando-se em consideração que cada atributo pode ter um valor máximo de 15, poderíamos representar esse mesmo cromossomo como uma cadeia de bits (armazenada em uma string ou em uma variável numérica), onde cada um dos genes ocuparia 4 bits, assim: 0100.0011.0010.0001.0010 (os pontos aqui somente são usados para facilitar a compreensão de quais bits estão representando qual gene, pois na verdade armazenaríamos somente a cadeia em si.
Sendo assim, alguns problemas podem ter uma melhor solução quando usando a cadeia de bits, enquanto que outros podem ser mais facilmente compreensíveis usando uma cadeia de números inteiros ou reais ou até mesmo strings.
Em nosso próximo artigo, falaremos sobre cada um dos passos necessários em um algoritmo genético.

[Conteúdo pertencente ao Material do curso de Inteligência Artificial]

Share and Enjoy

  • Facebook
  • Twitter
  • Delicious
  • LinkedIn
  • StumbleUpon
  • Add to favorites
  • Email
  • RSS
 

One comment

  1. […] Uma Introdução aos Algoritmos Genéticos – Parte 1 […]

Leave a Reply

Your email address will not be published. Required fields are marked *

Email
Print