Genetic Algorithm: O que é algoritmo genético?

Algoritmo genético (genetic algorithm) é um pro­ce­di­mento de oti­mi­za­ção que imita os me­ca­nis­mos da seleção natural e tem como objetivo melhorar ite­ra­ti­va­mente po­pu­la­ções de soluções po­ten­ci­ais. Al­go­rit­mos genéticos são uti­li­za­dos em diversas áreas, que vão desde a oti­mi­za­ção de sistemas técnicos até o apren­di­zado de máquina.

O que se entende por algoritmo genético?

Algoritmo genético (GA) é uma heu­rís­tica global para a resolução de problemas que envolvem a tomada de uma decisão. A decisão deve se basear em prin­cí­pios da seleção natural e da genética. Al­go­rit­mos genéticos pertencem à categoria dos al­go­rit­mos evo­lu­ci­o­ná­rios e utilizam me­ca­nis­mos ins­pi­ra­dos em processos da seleção natural para melhorar gra­du­al­mente soluções para problemas complexos. Em resumo, genetic al­go­rithms simulam a “so­bre­vi­vên­cia dos mais fortes” segundo as seguintes premissas:

1. In­di­ví­duos competem por recursos e pela opor­tu­ni­dade de se re­pro­du­zi­rem.
2. Os in­di­ví­duos mais bem-sucedidos ou fortes geram mais des­cen­den­tes do que os outros.
3. Os genes dos pais “mais aptos” são herdados através das gerações. Isso faz com que fre­quen­te­mente gerem des­cen­den­tes com sequên­cias genéticas mais van­ta­jo­sas do que as suas próprias.
4. Como os melhores genes são trans­mi­ti­dos a longo prazo, cada geração se adapta melhor ao seu ambiente do que a anterior.

Al­go­rit­mos genéticos geram uma população de in­di­ví­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 so­bre­vi­vem e se re­pro­du­zem. Os di­fe­ren­tes in­di­ví­duos são re­pre­sen­ta­dos por chamados cro­mos­so­mos, que são apre­sen­ta­dos na forma de cadeias de ca­rac­te­res (letras, bits, float ou inteiros). Os cro­mos­so­mos podem ser de­com­pos­tos em genes, que es­pe­ci­fi­cam uma ca­rac­te­rís­tica es­pe­cí­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, al­go­rit­mos genéticos iniciam um processo de múltiplas etapas composto por cálculos e re­pro­du­ção. Os cro­mos­so­mos são alterados e com­bi­na­dos ao longo de várias gerações ou iterações por meio de ope­ra­do­res genéticos – seleção, cru­za­mento (re­com­bi­na­ção) e mutação – para encontrar soluções pro­gres­si­va­mente melhores. Isso significa que genetic al­go­rithms se aproximam de uma boa solução global através da com­bi­na­ção de boas soluções parciais.

Como al­go­rit­mos genéticos funcionam?

O processo iterativo é nor­mal­mente dividido nas seguintes etapas:

1. O problema de oti­mi­za­ção é co­di­fi­cado ou mapeado para um cro­mos­somo binário.
2. O algoritmo genético gera uma população de in­di­ví­duos e a ini­ci­a­liza ale­a­to­ri­a­mente. 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 pre­de­fi­nida, o algoritmo genético seleciona os pais da população.
5. Com base nas in­for­ma­ções genéticas de ambos os pais, são gerados des­cen­den­tes.
6. As ca­rac­te­rís­ti­cas genéticas dos des­cen­den­tes (alelos) podem sofrer mutação, o que pode resultar na inversão de seus valores.
7. A população cresce com os des­cen­den­tes recém-gerados. Se o tamanho da população exceder o limite es­ta­be­le­cido, um esquema de subs­ti­tui­ção determina quais in­di­ví­duos não farão mais parte do conjunto de soluções.
8. Enquanto nenhum critério de in­ter­rup­çã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 sig­ni­fi­ca­ti­va­mente. Alguns al­go­rit­mos percorrem um número de­ter­mi­nado 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 ca­pa­ci­dade de adaptação dos in­di­ví­duos. A pontuação de aptidão de um indivíduo, portanto, indica sua com­pe­ti­ti­vi­dade. O objetivo do algoritmo genético é encontrar o indivíduo com a aptidão ideal (ou quase ideal). Os in­di­ví­duos com melhores pon­tu­a­ções têm maior pro­ba­bi­li­dade de serem se­le­ci­o­na­dos para gerar des­cen­den­tes. Isso leva a novas gerações cujas soluções parciais são, em média, melhores do que as das an­te­ri­o­res.

Quais ope­ra­do­res os al­go­rit­mos genéticos utilizam?

Genetic al­go­rithms fazem uso de di­fe­ren­tes ope­ra­do­res para de­sen­vol­ver a população inicial. Os me­ca­nis­mos fun­da­men­tais que permitem a evolução são a seleção, re­com­bi­na­ção e mutação. A seguir, os ope­ra­do­res do GA são apre­sen­ta­dos em detalhes.

Seleção (selection operator)

A seleção determina quais in­di­ví­duos serão per­mi­ti­dos a gerar des­cen­den­tes e quantos des­cen­den­tes lhes serão per­mi­ti­dos. A escolha dos pais baseia-se na pontuação de aptidão, com o algoritmo genético pre­fe­rindo in­di­ví­duos com bons valores de aptidão.

Re­com­bi­na­ção (crossover operator)

Novos in­di­ví­duos são gerados através da re­com­bi­na­ção. O Genetic Algorithm escolhe ale­a­to­ri­a­mente os pontos de cru­za­mento. Nos pontos cor­res­pon­den­tes, os genes são trocados, criando des­cen­den­tes com novas ca­rac­te­rís­ti­cas. A seguir, é apre­sen­tada uma visão geral de exemplos de re­com­bi­na­çõ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 fun­da­men­tal das mutações é modificar ale­a­to­ri­a­mente genes nos des­cen­den­tes, ou seja, modificar a solução potencial de um problema de decisão. Isso mantém a di­ver­si­dade dentro da população e evita a con­ver­gên­cia 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 al­go­rit­mos genéticos são uti­li­za­dos?

Os al­go­rit­mos genéticos são usados prin­ci­pal­mente em áreas onde os métodos ana­lí­ti­cos tra­di­ci­o­nais atingem seus limites. Isso é es­pe­ci­al­mente 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 al­go­rit­mos genéticos são usados para otimizar os pesos de redes neurais.

Além disso, al­go­rit­mos genéticos são fre­quen­te­mente usados no pla­ne­ja­mento de produção, ajudando a encontrar cro­no­gra­mas ideais e alocações de recursos. No setor fi­nan­ceiro e em­pre­sa­rial, os al­go­rit­mos são aplicados tanto na oti­mi­za­ção de port­fó­lios quanto no de­sen­vol­vi­mento de es­tra­té­gias co­mer­ci­ais complexas. Outra área de aplicação é o ajuste de hi­per­pa­râ­me­tros de modelos no campo de machine learning. Embora nem sempre sejam o método mais eficiente, os al­go­rit­mos genéticos são con­si­de­ra­dos uma técnica de oti­mi­za­ção muito versátil devido à sua fle­xi­bi­li­dade.

Exemplo de aplicação de al­go­rit­mos 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 com­pri­mento. Os ca­rac­te­res in­di­vi­du­ais (A a Z, a a z, 0 a 9 e ca­rac­te­res especiais) re­pre­sen­tam, neste exemplo, os genes. A string pode ser vista como o cro­mos­somo ou solução. A pontuação de aptidão reflete o número de ca­rac­te­res que diferem da string-alvo. Portanto, in­di­ví­duos com uma pontuação baixa são pre­fe­ri­dos. 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ên­cias ale­a­tó­rias de ca­rac­te­res.