No post Introdução a Algoritmos Genéticos falei um pouco sobre os AG’s e falei sobre a estrutura básica de um AG.
Neste post irei demonstrar passo-a-passo a execução de um AG através de figuras.
Neste site tem alguns applets demonstrando a execução de um AG. Foi através deste site que consegui as imagens abaixo e pedi a autorização do dono do site para que pudesse usá-las neste post. Portanto se você deseja copiar as imagens para utilizar, certifique-se de ler os termos de uso.
Algoritmo
Um AG funciona da seguinte maneira:
1. Inicialmente é gerado uma população de indivíduos chamada de geração.
2. Todos os indivíduos de cada geração são avaliados pela função objetivo e recebem uma nota de acordo com a sua adequação ao ambiente. Quanto melhor for a adequação do indivíduo, mais chances ele tem de ser selecionado.
3. Se for encontrada uma solução, ou seja, nesta geração possui uma solução ótima, então o problema está resolvido.
4. Alguns indivíduos são selecionados, de acordo com a nota de adequação adquirida no passo 2, para fazer o cruzamento e assim gerar a próxima geração.
5. Após o cruzamento é aplicada a mutação.
6. Os passos 2 a 5 são repetidos até que a solução ótima seja encontrada.
Algumas variações podem ocorrer, mas basicamente um AG funciona desta maneira.
Demonstração
Já vimos que o entendimento de um AG é muito simples. O objetivo deste post é demonstrar, através de imagens, um passo-a-passo da execução do algoritmo.
Demonstração AG 01
Na figura acima podemos ver a população atual (present population) e a população que vai ser gerada (new population). O gráfico representa o espaço de soluções, onde as linhas verticais indicam a população atual. A linha vermelha representa a melhor solução da população atual, enquanto as linhas verdes representam as outras soluções candidatas.
Assumindo que a representação do problema foi feita em forma de vetor de valores binários, então podemos dizer que os pontos em azul e vermelho representam, respectivamente, os bits 0 e 1 (ou vice-versa) de cada posição do vetor.
Podemos perceber que já temos uma população gerada e que para todos os indivíduos desta população já foi atribuído a nota pela função de aptidão (pois já temos conhecimento da melhor solução da população atual).
Demonstração AG 02
O elitismo é demonstrado neste passo, ou seja, os melhores cromossomos (indivíduos) são simplesmentes copiados para a nova população.
Demonstração AG 03
Neste passo, 2 cromossomos são escolhidos para que seja feito o cruzamento. Lembre-se que, os melhores cromossomos tem mais chances de serem escolhidos para o cruzamento (crossover). Isto não significa que eles sempre serão escolhidos.
Note que na população atual, os dois cromossomos que foram selecionados estão marcados com um ponto preto em cima e embaixo da representação.
O “Crossover point” (ou ponto de cruzamento) é o ponto que foi escolhido para que seja feita a troca de genes entre os pais. Ou seja, um filho vai ser gerado pela combinação dos genes que estão acima do ponto de cruzamento de um genitor com os genes que estão abaixo do ponto de cruzamento do outro genitor. E a geração do outro filho segue da mesma forma mas invertendo a ordem.
Demonstração AG 04
Na figura acima temos os filhos que foram gerados e podemos ver claramente como foi realizado o cruzamento.
Demonstração AG 05
Após o cruzamento é feito a mutação de alguns genes para que ocorra a diversificação da espécie e que algumas características não sejam perdidas.
Os genes que sofreram mutação estão marcados com um ponto preto ao lado. Neste caso, apenas o primeiro filho sofreu mutação.
Demonstração AG 06
Os filhos que foram gerados são adicionados à nova população.
Demonstração AG 07
Esses passos são executados até que uma nova geração inteira seja formada.
Demonstração AG 08
A nova geração que foi criada passa a ser a população atual e o algoritmo continua sua execução até que uma solução ótima seja encontrada.
Conclusão
Como podemos ver não é complicado de entender o funcionamento de um AG. Vale relembrar que existem alguns parâmetros que podem ser configurados, por exemplo, taxa de mutação, taxa de cruzamento, dentre outros, e que esta configuração influencia muito no desempenho do algoritmo.
Recomendo vocês a testarem vocês mesmo a execução de um AG neste applet.
