Existem inúmeros recursos na Internet que fornecem a descrição da teoria dos Algoritmos Genéticos e a explicação teórica dos mesmos. Eu, entretanto, não encontrei nenhum exemplo real (eu posso não ter procurado direito, é verdade!). Por isso, decidi tentar e implementar a teoria em um exemplo vivo. Embora existam milhares de áreas onde os algoritmos genéticos podem ser aplicados, eu decidi escolher o processo de solução da equação trivial quadrática por uma questão de simplicidade na implementação. A equação é y = 13x ^ 2 – 5x – 12. Ela possui duas raízes (pontos onde o gráfico intercepta o eixo X) em x = -0,7875184 e em x = 1,17213378. Embora, esta implementação particularmente não tenha aplicação na vida real (você pode resolver essa equação no papel em alguns segundos), ela demonstra o AG no seu melhor.
Codificação de dados
A implementação clássica do AG implica na codificação de dados como cadeias de bits (cromossomos, onde cada gene é representado por um ou mais bits). No entanto, eu decidi mudar um pouco (o que não é proibido) e usar números reais ao invés das strings de bits. Cada cromossomo inclui dois genes e duas soluções possíveis – uma para cada raíz da equação.
typedef struct _CHROMO_ { double value1, value2; double fitness; }chromo_t;
O terceiro membro do cromossomo é a aptidão e ela é usada apenas para armazenar a aptidão da solução representada por este cromossomo. Os genes (valores) são iniciados por valores aleatórios quando a população inicial é criada:
#define POPULATION 2000 chromot_t population[POPULATION]; for(int i = 0; i < POPULATION; i++) { population[i].value1 = (double)(rand() % 10) + 5.0; population[i].value2 = -(double)(rand() % 10) - 5.0; }
Função Fitness
A função Fitness é utilizada para estimar a adequação da solução atual. Neste caso particular, a função de adequação é a soma dos valores produzidos pela equação quando alimentadas com valores do cromossomo. Isso significa que, quanto menor o valor devolvido pela função fitness, mais perto chegaros à solução adequada.
double fitness(chromo_t* ch) { return fabs(13.0 * pow(ch->value1, 2.0) - 5.0 * ch->value1 - 12.0) + fabs(13.0 * pow(ch->value2, 2.0) - 5.0 * ch->value2 - 12.0); }
Enquanto você iterar na população calculando o fitness para cada fenótipo, você deve salvar os índices de duas soluções (a quantidade pode variar de caso para caso), como os que seriam usados para produzir a próxima geração.
Crossover
O operador de crossover é a parte crucial de qualquer implementação de AG. É uma função que recebe os dois (ou mais) melhores fenótipos e os utiliza para produzir uma nova geração. Minha sugestão é fazer um crossover desse par para fazer um (ou mais – depende da aplicação) descendente e, então, faça o crossover do melhor fenótipo com o restante da população; assim, substituindo inteiramente a geração antiga pela nova. Neste caso, a função do cruzamento é trivial:
void cross(chromo_t* chMom, chromo_t* chDad, chromo_t* chChild) { static int mutation = 0; // Which operation to use for crossover switch(mutation) { case 0: chChild->value1 = chMom->value1 + chDad->value1 * MUTATION_RATE; chChild->value2 = chMom->value2 + chDad->value2 * MUTATION_RATE; break; case 1: chChild->value1 = chMom->value1 + chDad->value1 * MUTATION_RATE; chChild->value2 = chMom->value2 - chDad->value2 * MUTATION_RATE; break; case 3: chChild->value1 = chMom->value1 - chDad->value1 * MUTATION_RATE; chChild->value2 = chMom->value2 + chDad->value2 * MUTATION_RATE; break; case 4: chChild->value1 = chMom->value1 - chDad->value1 * MUTATION_RATE; chChild->value2 = chMom->value2 - chDad->value2 * MUTATION_RATE; break; case 5: chChild->value1 = chDad->value1 - chMom->value1 * MUTATION_RATE; chChild->value2 = chDad->value2 - chMom->value2 * MUTATION_RATE; break; case 6: chChild->value1 = chDad->value1 + chMom->value1 * MUTATION_RATE; chChild->value2 = chDad->value2 - chMom->value2 * MUTATION_RATE; break; case 7: chChild->value1 = chDad->value1 - chMom->value1 * MUTATION_RATE; chChild->value2 = chDad->value2 + chMom->value2 * MUTATION_RATE; break; } mutation++; if(mutation > 7) mutation = 0; }
MUTATION_RATE é a velocidade na qual as soluções evoluem (neste exemplo, definir a 0,0001). Quanto maior for a MUTATION_RATE, mais depressa pode-se chegar à solução adequada – no entanto, elas podem ser menos exatas. O melhor seria reduzi-las ao se aproximar da solução.
Como você deve ter notado, o crossover e a mutação são combinados em uma única função, enquanto a maior parte do tempo você gostaria para separá-los e usar a mutação apenas em caso de estagnação (incapacidade dos fenótipos de evoluir para uma solução adequada).
Condição de parada
Não ha muito que possa ser dito aqui. Você deve parar a execução assim que alcançar a precisão desejada ou quando você perceber que não há solução, uma vez que é totalmente possível que certas equações quadráticas não possuam raízes, e ao invés disso terem o seu mínimo ou máximo. É importante mencionar que a precisão e rapidez das implementações de AG dependem da taxa da mutação e da quantidade de fenótipos na população. Na verdade, você pode implementar outra AG, a fim de encontrar os valores ideais para a atual.
Testando o algoritmo implementado
Esta implementação específica aproxima as raízes da equação quadrática acima mencionada com um pouco menos de 23 segundos. As soluções geradas são precisas o suficiente para a maioria das necessidades.
Vamos dar uma olhada na evolução das soluções geradas pela implementação descrita de AG.
A curva fitness é muito semelhante:
Curva de fitness
Como você pode ver, a AG é capaz de encontrar a direção certa de maneira muito rápida.
Conclusão
Embora esta aplicação específica seja trivial e, para ser honesto, muito superficial, espero que demonstre que as AGs são uma ferramenta muito poderosa. É sábio dizer que resolver uma equação quadrática é uma das tarefas mais simples, onde a AG pode ser aplicada com sucesso. Os algoritmos genéticos de diferentes tipos podem ser utilizados para a seleção da topologia de rede neural artificial, otimizações de algoritmos diferentes, etc. O sucesso de determinada AG só depende da exatidão das implementações do cromossomo e do crossover. Gostaria de reiterar que é sempre possível implementar outra AG, a fim de obter a aplicação adequada da atual.
Espero que este artigo tenha sido útil. Vejo você no próximo!
***
Artigo original disponível em: http://syprog.blogspot.com.br/2013/01/genetic-algorithms-lame-example-solving.html