O algoritmo genético (GA) | Computação Inteligente
O algoritmo genético (do inglês genetic algorithm – GA) é um método evolutivo de otimização introduzido por John Holland em 1975 [1] e mais tarde foi popularizado por David Goldberg [2]. O GA se inspira nos princípios da teoria da seleção natural, proposta por Charles Darwin, na qual somente os indivíduos mais aptos sobrevivem para uma próxima geração. Como o GA é um algoritmo de otimização, é necessário entender o que é um problema de otimização, clique no link e leia nosso post. Caso você já domine este assunto, siga em frente.
Assim como o PSO e o DE, já apresentados neste site, o GA também utiliza uma população de indivíduos (também chamada de cromossomos). Essa população será submetida a 3 operadores: seleção, crossover (ou cruzamento) e mutação. Aplicando estes operadores de maneira iterativa, ao fim de um critério de parada pré-estabelecido, o algoritmo entrega a otimização desejada (ou algo próximo dela). Neste ponto, se você leu o post na qual discutimos sobre o DE, já deve ter percebido que ambos os algoritmos são muito semelhantes.
Para entender a ideia por trás do GA, vamos fazer uma analogia com a teoria da seleção natural, de onde o algoritmo foi inspirado. Imagine uma família com pai, mãe e filho. O filho é gerado a partir da combinação dos genes de seus pais. Agora imagine milhares de pessoas se relacionando, gerando filhos (ou seja, uma população) e transmitindo seus genes (essas seriam as etapas de cruzamento e mutação do algoritmo). De acordo com Darwin, somente os indivíduos mais aptos sobrevivem para perpetuar a espécie. Isso ocorre por conta de uma seleção, que neste caso, é natural. Da população de filhos, os genes mais aptos serão transmitidos para as próximas gerações de população. Porém, a seleção natural leva muito tempo para evoluir nossa espécie (não entrarei nas discussões biológicas, filosóficas e afins). A ideia do GA é simular esse procedimento para otimizar algum problema. Um dos vídeos mais legais relacionados a seleção natural é da série quer que desenhe. Caso tenha interesse, sugiro fortemente que assista, vale a pena.
Bom, dodo a breve introdução, vamos ao algoritmo de fato. O GA pode ser implementado para números binários ou contínuos. A versão apresentada aqui, será a contínua, todavia vamos apenas ilustrar a ideia binária, pois a mesma é bem interessante quando comparada com o processo da evolução natural. Na Figura 1a é apresentada uma população de indivíduos ou cromossomos. Perceba que cada indivíduo é formado por uma cadeia de bits. Neste caso é interessante a nomenclatura cromossomos, pois cada cromossomo é formado por uma cadeia de genes, ou seja, cada gene é representado por 1 bit. Na Figura 1b é representada outra população, agora por números reais, na qual cada gene é uma dimensão. Obviamente trabalhar com a combinação de bits é mais trabalhoso do que com números reais.
Agora vamos as etapas do algoritmo para valores reais. O primeiro passo a ser tomado é gerar uma população aleatória de tamanho . Chamaremos essa população de (população principal). Se o tamanho do espaço de busca for conhecido, gere os valores por meio de uma distribuição de probabilidade uniforme. Caso contrário, gere de uma distribuição normal. O tamanho da população utilizado é escolhido de maneira empírica. Normalmente se utiliza igual a 10 vezes a dimensão do problema a ser otimizado, ou seja, se for uma função , estamos otimizando um problema de 3 dimensões. Gerada a população, o primeiro operador a ser utilizado é a seleção. Nesta etapa é gerada uma população intermediária , também de tamanho , a partir da , da seguinte forma:
São sorteados dois indivíduos pertencentes a e são comparados por meio da função objetivo previamente determinada (neste ponto, se você não sabe o que é uma função objetivo você precisa entender o problema de otimização). O individuo mais apto, ou seja, com maior valor na função objetivo segue adiante para a .
Primeiramente é determinada uma taxa de crossover. Essa taxa indica a probabilidade de dois indivíduos serem cruzados, portanto nem todos os indivíduos serão cruzados. Normalmente, valores em torno de 70% são boas escolhas. Essa taxa ajuda na diversidade da população.
onde é uma constante gerada a partir de uma distribuição normal com média 1 e desvio padrão 0. Os indivíduos e serão alocados em uma nova população intermediária .
Realizado o crossover, o próximo operador é a mutação. Este operador também auxilia na diversidade e nada mais é do que a inserção de um ruído alguns indivíduos da população . Na versão binária, seria nada mais nada menos do que alterar o valor de 1 ou 2 bits. Portanto, assim como no crossover, teremos uma taxa de mutação. Aqui, um valor de 10% já suficiente. Com isso, apenas uma pequena parcela da população vai ser mutada. Sendo um indivíduo pertencente ao conjunto de 10% a ser mutado, fazemos:
onde é um ruído obtido por uma distribuição normal de média 0 e desvio padrão 1.
Bom, realizado todos os operadores, neste ponto temos a , que é a nossa primeira geração, a e a . Agora o algoritmo é iniciado novamente com o operador de seleção entre a e a . Com isso, cada iteração do algoritmo vai selecionar os indivíduos mais aptos para seguir para as próximas gerações como mostra o fluxograma da Figura 2. O algoritmo só para quando um critério de parada for alcançado. Esse critério pode ser o número de iterações, erro mínimo ou convergência do erro, você escolhe de acordo com o problema que esta trabalhando.
Figura 2: fluxograma GA
Como de praxe, deixo uma implementação da versão discutida neste post. Antes de encerrar, deixo claro que existem diversas outras versões e alterações no GA e a mostrada aqui é apenas uma delas, mas que também funciona. Perceba que as constantes a ser definidas, como taxa de aprendizagem e de mutação, interferem na convergência do seu algoritmo. Esses valores podem variar de problema para problema e por conta disso existem outras abordagem para se realizar crossover e mutação. Como todo método heurístico, ele não soluciona todos os problemas e seus parâmetros afetam no desempenho final. Mas nessa altura já apresentamos 3 algoritmos evolutivos bastante utilizados atualmente, PSO, DE e o GA. Você tem opção de escolher aquele que se dá melhor no seu problema. Em um próximo post podemos debater sobre uma outra heurística inspirada na natureza, a colônia de formigas.
Para mais conceitos relacionados ao GA, como por exemplo o elitismo, sugiro a leitura deste capítulo de livro em português e muito bem explicado