Genetic Algorithm: O que é algoritmo genético?

Algoritmo genético (genetic algorithm) é um procedimento de otimização que imita os mecanismos da seleção natural e tem como objetivo melhorar iterativamente populações de soluções potenciais. Algoritmos genéticos são utilizados em diversas áreas, que vão desde a otimização de sistemas técnicos até o aprendizado de máquina.

O que se entende por algoritmo genético?

Algoritmo genético (GA) é uma heurística global para a resolução de problemas que envolvem a tomada de uma decisão. A decisão deve se basear em princípios da seleção natural e da genética. Algoritmos genéticos pertencem à categoria dos algoritmos evolucionários e utilizam mecanismos inspirados em processos da seleção natural para melhorar gradualmente soluções para problemas complexos. Em resumo, genetic algorithms simulam a “sobrevivência dos mais fortes” segundo as seguintes premissas:

1. Indivíduos competem por recursos e pela oportunidade de se reproduzirem.
2. Os indivíduos mais bem-sucedidos ou fortes geram mais descendentes do que os outros.
3. Os genes dos pais “mais aptos” são herdados através das gerações. Isso faz com que frequentemente gerem descendentes com sequências genéticas mais vantajosas do que as suas próprias.
4. Como os melhores genes são transmitidos a longo prazo, cada geração se adapta melhor ao seu ambiente do que a anterior.

Algoritmos genéticos geram uma população de indivíduos, sendo que cada um deles é uma solução potencial para o problema em questão. Aqueles tipos que melhor conseguem se adaptar ao seu ambiente sobrevivem e se reproduzem. Os diferentes indivíduos são representados por chamados cromossomos, que são apresentados na forma de cadeias de caracteres (letras, bits, float ou inteiros). Os cromossomos podem ser decompostos em genes, que especificam uma característica específica, como a cor do cabelo. As variações de um gene – neste caso, por exemplo, loiro, castanho ou preto – são chamadas de alelos.

Para se aproximar da solução ideal, algoritmos genéticos iniciam um processo de múltiplas etapas composto por cálculos e reprodução. Os cromossomos são alterados e combinados ao longo de várias gerações ou iterações por meio de operadores genéticos – seleção, cruzamento (recombinação) e mutação – para encontrar soluções progressivamente melhores. Isso significa que genetic algorithms se aproximam de uma boa solução global através da combinação de boas soluções parciais.

Como algoritmos genéticos funcionam?

O processo iterativo é normalmente dividido nas seguintes etapas:

1. O problema de otimização é codificado ou mapeado para um cromossomo binário.
2. O algoritmo genético gera uma população de indivíduos e a inicializa aleatoriamente. A população inicial é chamada de Geração 0.
3. A cada indivíduo é atribuído um escore de aptidão na forma de um número real.
4. Usando uma variante de seleção predefinida, o algoritmo genético seleciona os pais da população.
5. Com base nas informações genéticas de ambos os pais, são gerados descendentes.
6. As características genéticas dos descendentes (alelos) podem sofrer mutação, o que pode resultar na inversão de seus valores.
7. A população cresce com os descendentes recém-gerados. Se o tamanho da população exceder o limite estabelecido, um esquema de substituição determina quais indivíduos não farão mais parte do conjunto de soluções.
8. Enquanto nenhum critério de interrupção for atendido, o algoritmo genético repete os passos de 3 a 7 para se aproximar cada vez mais da solução ótima do problema. O critério de parada, no entanto, pode variar significativamente. Alguns algoritmos percorrem um número determinado de gerações, enquanto outros continuam ativos até não haver mais melhorias em relação à geração anterior.

Pontuação de aptidão

A aptidão é um sinônimo para a capacidade de adaptação dos indivíduos. A pontuação de aptidão de um indivíduo, portanto, indica sua competitividade. O objetivo do algoritmo genético é encontrar o indivíduo com a aptidão ideal (ou quase ideal). Os indivíduos com melhores pontuações têm maior probabilidade de serem selecionados para gerar descendentes. Isso leva a novas gerações cujas soluções parciais são, em média, melhores do que as das anteriores.

Quais operadores os algoritmos genéticos utilizam?

Genetic algorithms fazem uso de diferentes operadores para desenvolver a população inicial. Os mecanismos fundamentais que permitem a evolução são a seleção, recombinação e mutação. A seguir, os operadores do GA são apresentados em detalhes.

Seleção (selection operator)

A seleção determina quais indivíduos serão permitidos a gerar descendentes e quantos descendentes lhes serão permitidos. A escolha dos pais baseia-se na pontuação de aptidão, com o algoritmo genético preferindo indivíduos com bons valores de aptidão.

Recombinação (crossover operator)

Novos indivíduos são gerados através da recombinação. O Genetic Algorithm escolhe aleatoriamente os pontos de cruzamento. Nos pontos correspondentes, os genes são trocados, criando descendentes com novas características. A seguir, é apresentada uma visão geral de exemplos de recombinações:

• Genes do pai 1: A|B|C|D|E|F
• Genes do pai 2: G|H|I|J|K|L
• Genes da prole: A|B|I|J|K|F

Mutação (mutation operator)

A ideia fundamental das mutações é modificar aleatoriamente genes nos descendentes, ou seja, modificar a solução potencial de um problema de decisão. Isso mantém a diversidade dentro da população e evita a convergência prematura. Aqui está um exemplo de mutação:

• Genes antes da mutação: A|B|C|D|E|F
• Genes após a mutação: A|B|L|D|T|F

Em quais áreas algoritmos genéticos são utilizados?

Os algoritmos genéticos são usados principalmente em áreas onde os métodos analíticos tradicionais atingem seus limites. Isso é especialmente válido para problemas com um grande e complexo espaço de soluções. Uma área central de aplicação é o deep learning, onde os algoritmos genéticos são usados para otimizar os pesos de redes neurais.

Além disso, algoritmos genéticos são frequentemente usados no planejamento de produção, ajudando a encontrar cronogramas ideais e alocações de recursos. No setor financeiro e empresarial, os algoritmos são aplicados tanto na otimização de portfólios quanto no desenvolvimento de estratégias comerciais complexas. Outra área de aplicação é o ajuste de hiperparâmetros de modelos no campo de machine learning. Embora nem sempre sejam o método mais eficiente, os algoritmos genéticos são considerados uma técnica de otimização muito versátil devido à sua flexibilidade.

Exemplo de aplicação de algoritmos genéticos

Suponha que a tarefa de um algoritmo genético seja gerar uma string-alvo – por exemplo, “The fittest survive” – a partir de uma string aleatória de mesmo comprimento. Os caracteres individuais (A a Z, a a z, 0 a 9 e caracteres especiais) representam, neste exemplo, os genes. A string pode ser vista como o cromossomo ou solução. A pontuação de aptidão reflete o número de caracteres que diferem da string-alvo. Portanto, indivíduos com uma pontuação baixa são preferidos. A tabela a seguir mostra como a saída poderia ser nesse caso::

Vale ressaltar que a saída pode variar. Isso se deve ao fato de que o algoritmo genético começa com sequências aleatórias de caracteres.