IA: Algorítmos Genéticos

Algorítmos genéticos (e estratégias evolutivas, eu não vou usar dois nomes não) têm atraido bastante atenção ultimamente, de gente que sabe o que faz e de gente que não sabe. O resultado é que o cada vez mais, eles são implementados de forma errada, o que é impressionante, já que são tão símples. Assim, na esperança de ajudar quem está começando a não cair nas mesmas armadilhas decidi escrever este texto.

Para começar, para que servem esses algorítmos genéticos? Algorítmos genéticos são úteis para resolver problemas de otimização. Problemas em que você tem alguma coisa com alguns parâmetros e precisa encontrar os melhores valores para estes parâmetros. Isso parece restritivo, mas não é, nao se sabe de nenhum problema na computação que não possa ser visto como um problema de otimização. Algorítmos genéticos são mais úteis se o problema tiver vários parâmetros e você tiver poucas informações a respeito dele.

Os algorítmos genéticos funcionam todos de forma bastante semelhante, os parâmetros a serem otimizados são concatenados em uma população de cromossomos (na prática, um pedaço da memória, normalmente vetores), cada cromossomo é avaliado segundo sua utilidade, os melhores são copiados por cima dos piores e os genes (parâmetros) de alguns cromossomos são embaralhados dois a dois. Cada iteração destas é denominada uma geração. Após diversas gerações você provavelmente terá cromossomos bem próximos do ótimo na sua população. Pode-se fazer algumas coisas diferentes, como mutações (aleatórias ou não) nos genes e preservar os melhores cromossomos para as gerações seguintes, mas no geral as diferenças são em como se faz cada uma destas etapas.

Vale notar que a única etapa que depende do problema é o cálculo da utilidade dos cromossomos. Esta utilidade é um número que é maior quão mais desejável seja o cromossomo. Normalmente ela também é positiva, o que facilita a implementação.

A embaralhada dos genes é chamada de cross-over, e é a etapa mais importante do algorítmo. (Se você acha que é a mutação, já começou errado.) Sem o cross-over, tem-se que se procurar o cromossomo ótimo em todas as combinações possíveis dos genes, pois o fato de um cromossomo ser ruim não significa que um certo gene dele é ruim, todos os outros que estão junto com ele também influenciam. Assim, não podemos avaliar os genes, somente os indivíduos. Quando os genes são embaralhados, porém, eles passam a ocorrer independentemente dos outros, se todos os indivíduos com um gene forem ruins, o gene deve ser ruim. Ou seja, agora podemos avaliar os genes separadamente, quanto mais indivíduos forem analizados, mais certeza teremos da avaliação.

Para entender porque o cross-over é tão importante, imagine um problema em que queremos otimizar 2 características, cada uma com 10 possibilidades. Esta é uma tarefa trivial para um computador, pois só temos 100 possíveis indivíduos, mesmo assim, o número de genes é bem menor, só há 20 possíveis genes. Se tivessemos, porém 3 características, teriamos mil indivíduos e 30 genes, com 6 características, teriamos um milhão de indivíduos, e só 60 genes. É fácil ver que o número de indivíduos cresce muito mais rápido do que o de genes. De fato, ele cresce exponencialmente mais rápido, tornando muito mais eficiente avaliar os genes do que os indivíduos.

Agora vamos aos detalhes. A primeira coisa que o algorítmo faz é criar a população inicial. E esta é a primeira das preocupações do programador. Idealmente, essa população tem que reúnir todos os genes possíveis, em diversas combinações. Na maior parte das vezes, porém, isso não é possível, já que os genes são muitos. Nestes casos, tenta-se obter a maior variedade possível já nesta população, normalmente escolhendo-a de forma aleatória, e utilizam-se mutações para introduzir os outros genes depois. A mutação mais comum é, em cada geração, escolher aleatóriamente alguns cromossomos e mudar o valor de um de seus genes de forma também aleatória.

O tamaho (número de indivíduos) da população também é importante. Normalmente todas as gerações têm o mesmo tamanho, o que permite a implementação com vetores de tamanho fixo, sem alocação dinâmica. A população tem que ser tão maior quanto maior for o número de genes em cada cromossomo, pois quanto mais genes interferirem na utilidade do cromossomo, mais cromossomos devem ser medidos para se ter certeza do resultado. O número de gerações é outro parâmetro que deve ser ajustado. Quanto mais valores diferentes cada gene de um cromossomo puder adquirir, mais gerações são necessárias para testar estes valores.

Até agora não tem muito o que ir errado. O erro mais comum nos parâmetros acima é colocar uma taxa de mutação muito alta. Em cada geração não se costuma escolher mais de 10% dos cromossomos para a mutação, na maior parte das vezes, se utiliza um valor bem mais baixo, como 2% ou 5%. Como já disse, se a população inicial for boa, a mutação não é nem mesmo nescessaria. Mas a maior parte dos erros acontece mesmo é ao se definir o cross-over. A principal função do cross-over é fazer com que os genes occorram independentemente na população, e é muito importante lembrar disso ao se definir esta operação. O cross-over deve embaralhar os genes da melhor forma possível, fazendo com que dois genes não costumem passar sempre juntos de um cromossomo para o outro.

O operador de cross-over mais utilizado escolhe aleatóriamente dois cromossomos e um ponto nestes cromossomos, depois disso, ele troca todos os genes de um dos cromossomos até este ponto aleatório com os do outro cromossomo. Este operador é razoável, não é o ideal, mas funciona até bem. Algumas pessoas, porém, resolvem simplificar a implementação e destroem este operador. Algumas vezes, estas pessoas escolhem sempre uma parte específica dos cromossomos para trocar os genes, outras vezes, resolvem agrupar os genes antes da troca, fazendo com que vários deles sempre sejam trocados juntos, o resultado é que o algorítmo pára de funcionar. É claro que aumentando a taxa de mutação, o tamanho da população e o número de gerações, o algorítmo resultante vai gerar vários indivíduos aleatórios, e alguma hora deve chegar em um bom. É claro também que isso vai precisar de muito mais tempo e sorte do que um algorimo genético precisaria.

Para finalizar, queria apresentar um operador de cross-over que torna os genes completamente independentes. Alguém já deve ter proposto este operador, mas nunca encontrei um operador ideal na literatura. Como eu disse, o operador que normalmente é utilizado não é ideal, apesar de conseguir resolver a maior parte dos problemas. Para fazer um cross-over ideal em um par de cromossomos com n genes, basta gerar um número aleatório de n bits - onde cada bit tem uma probabilidade de ser 1 ou 0 que não precisa ser necessáriamente 50%, mas um bit não pode interferir nos outros - e trocar os genes das posições em que se obtiver um 1, mantendo os das que se obtem 0.