As primeiras versões de algoritmos genéticos foram propostas primeiramente nos anos 1950, mas sua versão mais popular foi publicada em 1975 por John Henry Holland. Esses algoritmos são métodos computacionais que têm como finalidade encontrar soluções satisfatórias para problemas de busca e otimização. Esses algoritmos são inspirados na teoria da evolução de Darwin e são utilizados em problemas que possuem diversas variáveis e diferentes soluções possíveis. Isso porque eles funcionam de maneira distinta de algoritmos “tradicionais” que são determinísticos. Os algoritmos genéticos trabalham com probabilidades e várias soluções possíveis para a resolução de um problema. Esses algoritmos atendem a diversos tipos de problemas com aplicações práticas em educação, medicina, varejo e transporte. Alguns desses exemplos serão tratados ao longo do texto. Então, o que são algoritmos genéticos e para que servem?

Conceitos básicos e como funcionam os algorítimos genéticos

Para entendermos as aplicações e como operam os algoritmos genéticos, é necessário conhecer alguns conceitos básicos que são baseados na genética natural. Como na evolução de Darwin, uma população de indivíduos inseridas em um determinado ambiente buscam sempre adaptar-se da melhor forma, certo? Nessa população, os indivíduos reproduzem-se e geram outros indivíduos, criando uma nova geração. E, a cada nova geração, os processos biológicos vão selecionando os mais adaptados ao ambiente e a espécie vai tornando-se cada vez mais apta a viver nesse ambiente.

Na computação, o processo é parecido. É gerada uma população inicial que contém n indivíduos e que cada indivíduo é equivalente à um cromossomo com uma quantidade x de genes. Depois esses indivíduos são submetidos a chamada função de avaliação ou função de aptidão. Essa função representa o ambiente em que os indivíduos estão inseridos e, portanto, devem se adaptar a ele. O papel da avaliação é analisar os genes dos indivíduos e atribui-los uma nota de aptidão para identificar os mais adaptados. Depois que a nota de aptidão é atribuída aos indivíduos, o próximo passo do algoritmo é fazer a seleção de apenas uma parte da população inicial para que aconteça a reprodução. Essa seleção é feita, na maioria das vezes, por sorteio. Nesse sorteio, os indivíduos possuem chances de serem selecionados proporcionalmente à sua nota de aptidão atribuída pela função de avaliação. Então, quanto mais adaptado, mais chances de se reproduzir. Depois da seleção desses indivíduos, é feito o processo de reprodução onde são aplicados os chamados operadores genéticos, que são:

  • Recombinação genética (crossover): Nesse operador, é escolhido dois indivíduos e há a troca de trechos do cromosso entre eles para gerar os filhos. Nesse processo os filhos herdam partes das características de seus pais e as próximas gerações (netos) também podem herdar estas características através dos genes.
  • Mutação: Esse operador troca aleatoriamente um ou mais genes de um cromossomo específico. Cada indivíduo possui uma probabilidade x de sofrer mutação. A mutação é importante para a manutenção da variabilidade genética (diversidade) da população. Quanto mais variabilidade, mais possíveis soluções para o problema.
  • Elitismo: Nesse operador, o indivíduo com a maior nota de aptidão é automaticamente selecionado e não são permitidas modificações nesse indivíduo para garantir que as melhores características não desapareçam da população.

Depois da aplicação desses operadores genéticos na etapa de reprodução, a população inicial é atualizada com novos indivíduos mais adaptados, gerando uma nova população. Todo esse processo (avaliação, seleção e reprodução) é chamado de uma geração. Após cada geração, o processo é feito outra vez com a nova população e, dessa forma, o algoritmo vai repetindo o processo até o algoritmo atingir um número x de gerações ou um indivíduo (solução) considerado ideal para o ambiente (função de avaliação). Portanto, os algoritmos genéticos são estocásticos em que o resultado é observado ao longo do tempo depois de diversas gerações.

Representação do funcionamento em loop do algoritmo genético.

Aplicações práticas

As aplicações práticas dos algoritmos genéticos são multidisciplinares e englobam diversas áreas. Como explicitado anteriormente, os algoritmos genéticos funcionam bem com problemas em que envolvem uma grande quantidade de variáveis e diversas soluções possíveis.

Um exemplo de aplicação que deixa isso mais claro é o AGHORA, criado na UNAMA (Universidade da Amazônia). Esse sistema busca resolver um grande problema das intituições de ensino: montar o horário de aulas. Esse problema tem diversas variáveis que envolvem questões como: disponibilidade dos professores (alguns trabalham em mais de uma instituição de ensino), carga horária da disciplina semanal e semestral, o uso de laboratórios, calendário letivo, etc. Esse horário pode ser montado de diversas formas levando em consideração todas essas variáveis. O que essa aplicação faz é tentar montar o melhor horário ao longo das gerações e da sua função de avaliação.

Outro exemplo na área da educação é a aplicação EducaTrans, criado na Escola Politécnica da Universidade de São Paulo. A finalidade dessa aplicação é a educação no trânsito e seu objetivo consiste no motorista competindo com a inteligência artificial para chegar a determinado ponto do mapa seguindo todas as regras de trânsito. Os algoritmos genéticos são usados para a criação da população, dos carros e ciclistas autônomos que estão presentes na cidade simulada. Nesse caso as variáveis são as regras do trânsito e função de avaliação é o quanto o indivíduo está adaptado à chegar ao destino no mapa.

Por último, temos uma aplicação na medicina que busca otimizar a segmentação de imagens e auxiliar médicos em exames. A aplicação envolve outros métodos como a lógica fuzzy e aprendizado de máquina. A parte dos algoritmos genéticos está em conseguir uma segmentação de forma versátil por conseguir gerar soluções (indivíduos) confiáveis e com baixo poder de processamento, pois algoritmos genéticos são considerados simples em questão de complexidade algoritmíca.

 Conclusão

Os algoritmos genéticos são uma subárea da computação inspirada pela natureza, como explicado no meu último texto. Isso porque esses algoritmos são inspirados na teoria da evolução de Darwin e na genética que são processos naturais. Durante o texto foi citada algumas das diversas aplicações desse tipo de algoritmo. Eles podem resolver problemas que envolvem varejo, entrega de produtos (problema do Caixeiro Viajante), entre outros. Por isso, esses algoritmos mostram-se úteis à problemas que não são resolvidos de forma satisfatória por algoritmos tradicionais porque eles conseguem trabalhar com uma grande quantidade de variáveis e propor diversas soluções possíveis. A natureza é uma grande ‘solucionadora’ de problemas, então devemos observá-la e extrair o máximo de conhecimento que pode nos ajudar com problemas práticos da vida cotidiana. Seja auxiliando profissionais ou resolvendo problemas por inteiro.