Algoritmos Genéticos

Um algoritmo genético é um método evolutivo de aprendizado de máquina que se baseia nos princípios da seleção natural observados por Darwin, para descobrir soluções ótimas (ou que tentam se aproximar do ótimo) em problemas diversos.

As soluções (inicialmente aleatórias) são tratadas como uma população de indivíduos (genomas) que lutam para sobreviver e evoluem ao longo de muitas gerações. A solução buscada é tratada como um problema de otimização, onde a cada iteração do processo de evolução, a população de soluções se aproxima da solução ótima.
As soluções geralmente são representadas por um conjunto de variáveis (genes), normalmente um conjunto de números.

A primeira geração é formada por soluções aleatórias. Daí em diante, por N gerações repete-se o seguinte processo:

- cruzamento: as soluções são combinadas de alguma forma representando o processo de reprodução, recebendo assim uma porção das características (valores de variáveis) do pai, e uma outra porção da mãe.
- mutação: os valores das variáveis sofrem uma leve (ou média) perturbação,  simulando o processo de "erro de cópia" genética e assim inserindo diversidade.
- seleção: uma parte das soluções é jogada fora, e a outra é selecionada para "viver" a partir de sua medida de performance (fitness), de modo que quanto maior o fitness, maior probabilidade de uma solução sobreviver, uma vez que significa que se adaptou melhor em cumprir seu objetivo (encontrar a solução ótima).

O fitness é a medida que define o conceito de sucesso da solução buscada. Representa o conceito máximo de sobrevivência, e considerando que a sobrevivência depende de um conjunto de fatores (correlacionados ou não) este deve ser medido por uma equação que leve em consideração todos os fatores de sucesso. Essa equação deve ser definida de acordo com o problema inerente à solução buscada. Por exemplo, se o algoritmo está sendo aplicado em um jogo onde tomar um tiro significa morrer, o fitness deve ser marcado com valor baixo neste tipo de situação onde se morre. No ambiente natural, muitas vezes os fatores determinantes estão associadas à obtenção de alimentos, condições de proteção e capacidade de ataque. Em jogos que simulam ambientes naturais os problemas podem ser os mesmos. Todavia, com a mesma lógica pode-se resolver problemas diversos como problemas de minimização de rotas, redução de custos, ou até mesmo modelagem preditiva (discutido em posts anteriores).

Ao final do processo, o melhor indivíduo (melhor fitness) de todas as gerações é selecionado como solução final, pois é o que mais se aproxima do ótimo, para o problema analisado.


Abraços mining noobs!