Algoritmos Genéticos

Para começar o período letivo 2008.2, o 1º post será sobre o assunto que deve ser também o primeiro da disciplina de ICA: Algoritmos Genéticos.

O princípio dos algoritmos genéticos (ag's) é baseado na Teoria da Evolução (biologia).

A idéia é a seguinte: primeiro deve-se analisar qual o problema e desenvolver uma solução representada por um vetor de numéros, preferencialmente binários. Depois disto, criam-se várias soluções (vetores de números binários) aleatoriamente (o conjunto de soluções denomina-se população e cada solução é denominada indivíduo), cada um destes indivíduos é então testado e atribui-se um grau de "adaptabilidade", que corresponde a quanto esta solução (indivíduo) satisfaz o problema. A partir da adaptabilidade, o indivíduo terá uma probabilidade de "cruzar" com outro indivíduo, quanto maior a adaptabilidade maior a probabilidade do indivíduo "cruzar".
O cruzamento entre indivíduos ocorre da seguinte forma: como cada indivíduo corresponde a um vetor (de números binários), toma-se um ponto aleatório neste vetor e faz-se um crossing-over, em que serão gerados 2 novos indivíduos sendo um com o começo dos "genes" de um indivíduo anterior e o final dos "genes" do outro indivíduo.

Para ilustra o problema, tomemos o seguinte problema:
Tem-se uma sala que tem N lâmpadas e deseja-se determinar quais devem ficar acesas para melhor iluminar o ambiente com o menor gasto de energia (ag's são muito usados em problemas de otimização, como este).

{Fazendo N = 10}

Cada solução corresponde a um vetor de 10 posições: s = [l0 l1 l2 l3 l4 l5 l6 l7 l8 l9] em que cada posição representa o status de uma lâmpada (0 -> apagada e 1 -> acesa).

Cria-se agora uma população de soluções, por exemplo:
s1 = [0 1 1 0 0 0 1 1 1 1]
s2 = [0 1 0 0 1 1 0 1 1 0]
s3 = [1 1 0 1 1 0 0 0 1 0]
s4 = [0 0 0 0 1 1 1 1 1 0]

Para cada solução, avalia-se quão bem o ambiente é iluminado e quanto de energia é gasto de modo a determinar a adaptabilidade de cada indivíduo. Suponto que chegue em:

adapt(s1) = 30%
adapt(s2) = 60%
adapt(s3) = 70%
adapt(s4) = 10%

Então cada indivíduo terá a probabilidade de "cruzar".

Fazendo o cruzamento dos indivíduos s1 e s3:
s1= [0 1 1 0 0 0 1 1 1 1] e s3 = [1 1 0 1 1 0 0 0 1 0]

Determina-se um ponto aleatoriamente para ocorrer o crossing-over, por exemplo 6.
s1' = [s1[0] s1[1] s1[2] s1[3] s1[4] s1[5] s3[6] s3[7] s3[8] s3[9]]
s1' = [0 1 1 0 0 0 0 0 1 0]
s2' = [s3[0] s3[1] s3[2] s3[3] s3[4] s3[5] s1[6] s1[7] s1[8] s1[9]]
s2' = [1 1 0 1 1 0 1 1 1 1]

São calculadas as adaptabilidades dos novos indivíduos e o processo é repetido até encontrar-se um indivíduo que satisfaça uma "adaptabilidade mínima".

A forma abordada é a mais simples, porém o algoritmo pode ficar complexo se forem definidos vários pontos de crossing-over, se o problema não tiver solução de natureza binária, se forem inseridas técnicas de mutação caso o algoritmo não esteja fornecendo bons resultados, enfim: pode-se complicar do jeito que quiser.