Algoritmos Genéticos em problemas de otimização

por Neuller Alves

No dia a dia de um profissional de engenharia, os problemas de otimização estão sempre presentes. Estes profissionais, ao longo de sua graduação têm uma sólida formação teórica em cálculo diferencial e integral, estatística e álgebra linear, adquirindo ferramentas muito poderosas que podem ser aplicadas na solução desse tipo de problema. Esses conhecimentos, quando conciliados com ferramentas computacionais, podem agregar grande valor para os processos de uma empresa.

Dentre os diversos algoritmos utilizados atualmente para solucionar problemas de otimização, o algoritmo genético, método desenvolvido por John Henry Holland em 1975, está entre os mais empregados. Este método utiliza os princípios da evolução propostos por Charles Darwin, segundo os quais indivíduos que possuem características mais vantajosas em um determinado ambiente são selecionados e possuem maior possibilidade de passar suas características genéticas para frente. Nos algoritmos genéticos, essa teoria é aplicada na seleção de soluções (que são os indivíduos) que otimizam a função objetivo do problema de otimização.

Antes de apresentar o funcionamento dessa classe de algoritmos, conhecer alguns conceitos é muito importante. Para exemplificar, pensemos em um problema onde queremos minimizar o custo de produção de um adubo que precisa de uma determinada proporção de Nitrogênio, Fósforo e Potássio. O produtor de adubo tem à sua disponibilidade diversas fontes de cada um desses nutrientes, sendo que cada fonte tem uma concentração e um preço específicos. Nesse caso, podemos fazer as seguintes definições:

Indivíduo: Uma solução viável para o problema que se deseja otimizar. No exemplo apresentado, um indivíduo seria um conjunto de n fontes em proporções específicas, de forma a atender as quantidades de N-P-K desejadas no adubo.

Cromossomo: cada um dos fatores que formam um indivíduo. No exemplo apresentado, cada fonte de nutrientes associada com a sua proporção é um cromossomo.

População: Um conjunto formado por uma quantidade pré-definida de indivíduos.

Mutação: Processo onde um determinado indivíduo, a um dado nível de probabilidade p, pode ou não ter cada um de seus cromossomos modificados. No exemplo apresentado, uma mutação poderia gerar uma modificação na proporção de uma ou mais fontes de N-P-K utilizadas.

Combinação: Processo onde um indivíduo é criado a partir do cruzamento de outros. No exemplo apresentado, uma combinação geraria um indivíduo que possui proporções de fontes de nutrientes herdadas de outros dois indivíduos.

Geração: Conjunto formado por uma população original, uma população gerada a partir da mutação de todos os indivíduos da população original, e uma população gerada através da combinação de indivíduos da população original.

Função Fitness: Função que, para cada indivíduo, calcula o valor da métrica que se deseja otimizar. No exemplo anterior, a função fitness calcula qual é o custo do adubo para cada formulação.

Funcionamento do Algoritmo Genético

Inicialmente, uma população com uma quantidade de indivíduos definida pelo usuário do algoritmo é gerada de forma aleatória. Outras duas são geradas a partir dessa, uma através do processo de mutação e outra através do processo de combinação. Essas três populações passam pela função fitness que calcula o valor da métrica que se deseja maximizar ou minimizar. Com base no valor da métrica, são selecionados os indivíduos com melhor desempenho de acordo com a função objetivo do problema. Esses indivíduos selecionados formarão a nova população, que também passará por mutação e combinação. Esse último processo se repete por uma quantidade de vezes especificada na entrada do algoritmo, ou até que as condições de parada tenham sido alcançadas.

Pode-se observar que os algoritmos genéticos são conceitualmente muito simples e fáceis de serem implementados. O formato aqui apresentado traz uma versão básica desses algoritmos, entretanto existem diversas variações que foram desenvolvidas ao longo do tempo. O fato é que, mesmo em suas formas mais simples, esses algoritmos têm se mostrado muito eficientes na solução de uma ampla variedade de problemas.

Referência: https://www.dm.ufscar.br/~sadao/download/?file=article/algoritmos-geneticos.pdf