Algoritmos Genéticos e sua Implementação na Prática

O que são algoritmos genéticos?

Algoritmos genéticos (AG) são uma ferramenta poderosíssima para solução de problemas de busca e otimização que consistem em tentar várias soluções e usar a informação coletada em cada tentativa para melhorar a qualidade da próxima sugestão. Os AGs são inspirados na teoria da evolução de Darwin e implementam conceitos como sobrevivência dos mais adaptados, seleção natural, mutação, entre outros. São considerados biomiméticos por se inspirarem na natureza para solucionar problemas. Inclusive, eu escrevi um artigo sobre isso! você pode acessá-lo aqui: Biomimética: Por que sair e "tocar grama" pode realmente ser a resposta para o seu problema

Nesta publicação, explicarei como funciona o algoritmo genético em como o usei para resolver um problema na prática.

Você pode acessar o repositório do projeto aqui: GeneticAlgorithm-TheTravelingThief

Como funciona o algoritmo genético?

Como dito anteriormente, o AG implementa funções da teoria da evolução de Darwin. Para que possamos ter uma base melhor antes de falar do algoritmo, é preciso entender como funciona esta teoria.

A evolução Darwiniana

Com o tempo, os seres vivos sofrem mudanças genéticas aleatórias (mutações) que podem causar vantagens adaptativas no ambiente em que vivem. Os indivíduos mais adaptados, pela seleção natural, têm mais chances de sobreviver e se reproduzirem, transferindo estas vantagens genéticas para a próxima geração.

Composição do algoritmo genético

• Gene
  Informação que será alterada pelo algoritmo genético.

• Cromossomo
  Estrutura de dados que contém a coleção de genes.

• Indivíduo
  Objeto que contenha o cromossomo e guarde o valor do fitness.

• População
  Conjunto de indivíduos.

• Mutação
  Função que alterará o gene do indivíduo. A mutação fará uma pequena alteração nos genes.

• Crossover
  Função que cruzará cromossomos de indivíduos da população. O crossover é um tipo de mutação que combina dois indivíduos.

• Fitness
  Função para pontuar o indivíduo. A função de fitness é uma das partes mais importantes do AG. É esta que define quão bem cada indivíduo performou e, portando, quão bem adaptado está.

• Seleção
  Função que decide quais indivíduos serão a população inicial da próxima geração. Esta função é a responsável por analisar o fitness de cada indivíduo e selecionar quais devem "sobreviver"

Etapas do algoritmo genético

O AG funciona da seguinte maneira:

1. É gerada uma população inicial de indivíduos. Esta população pode ser aleatória ou não, dependendo de quão otimizado você precise que o código seja.
2. À partir da população inicial, é criada a população que sofreu a mutação e a população que sofreu o crossover. Estas são somadas em uma só. Falarei melhor sobre mutação e crossover mais à frente.
3. Todos os indivíduos da população total passam pela seleção, onde aqueles com maior pontuação de fitness (os mais adaptados) "sobrevivem" e se transformam na população inicial da próxima geração.
4. Este processo é repetido até que alguma condição de parada seja atingida como erro mínimo ou gerações máximas.

Para facilitar a visualização, veja o código de um AG:

Algoritmo genético na prática

Tudo é mais fácil de entender quando é bem exemplificado. À partir deste ponto, explicarei como eu utilizei um AG para solucionar um problema!

O problema

Introdução ao problema

A AIC (Agência internacional do crime) propõe a Joana, o desafio de realizar roubos em várias cidades em apenas 72 horas. Joana deve viajar discretamente usando transporte coletivo pago e carregando os itens roubados em uma mochila de até 20 kg. Cada cidade possui um item valioso para ser roubado, mas cada roubo leva tempo para ser concluído. Além disso, as viagens entre as cidades têm um custo financeiro e levam tempo. Se ela conseguir roubar a quantidade máxima de itens, deverá retornar à sede da AIC na cidade Escondidos para receber seu prêmio.

Dados do problema

Os dados disponibilizados são:

• Uma tabela com dados dos itens:

• Tabela com os dados de custo e tempo das viagens entre cidades:

A tabela acima está incompleta pois é muito longa. A versão completa dela está disponível no repositório do projeto.

Aplicação do algoritmo genético

Tratamento dos dados

Para trabalhar com os dados, foi criada uma classe "Fábrica de Dados". Esta é responsável por tratar as tabelas e criar dicionários para que pudessem ser usados no código.

Modelagem das classes e funções

Para utilizar o AG, é necessário modelar nosso problema para ser adaptar à composição do AG. Para este problema, foi definido:

• Gene: Cada cidade em uma lista
• Cromossomo: Uma lista contendo as cidades
• Indivíduo: Um objeto de uma classe "Rota" que contenha o cromossomo e guarde o valor do fitness
• População: Um objeto de uma classe "Rotas" que contém uma lista de objetos "Rota"

Indivíduo

O indivíduo foi definido como um objeto da classe Rota. O indivíduo pode ser instanciado com uma rota aleatória ou pré-definida. Isso é útil para ser usado na população inicial ou nas funções de mutação e crossover. O indivíduo também guarda o seu valor do fitness.

A geração de rotas garante que a primeira cidade sempre é "Escondidos", já que é de onde Joana sai. Como também é o lugar para qual Joana deve retornar ao finalizar os roubos, "Escondidos" é a única cidade que aparece mais de uma vez na rota.

Como as funções de fitness e de mutação são específicas para cada indivíduo, elas foram definidas na classe Rota também.

Fitness

O fitness é uma das funções mais importantes do AG. Esta é responsável por avaliar quão bom é aquele indivíduo.

É como se o fitness define quais indivíduos sobrevivem e quais não. Caso um indivíduo tenha, por exemplo, 23kg no total, o fitness dirá que ele não é apto e o avaliará negativamente. Isso faz com que não seja necessário elaborar funções de mutação e crossover super complexas pois, caso o indivíduo gerado seja ruim, cabe ao fitness dizer.

Como este problema define que queremos maximizar o lucro, ele se torna um ótimo retorno da função de fitness pois quanto maior, melhor.

Porém, antes do cálculo do lucro, é verificado se a rota é válida e se a rota não ultrapassa os limites de peso e tempo.

Para calcular tudo isso, a rota é considerada da primeira até a segunda ocorrência de "Escondidos". Tudo depois da segunda é desconsiderado. Isso faz com que nossa rota tenha sempre um tamanho fixo e facilita muito no crossover e na mutação.

Mutação

A mutação faz uma pequena alteração no cromossomo do indivíduo. Como defini o cromossomo como uma lista de cidades, a mutação faz uma troca aleatória na posição de duas cidades (com exceção da primeira)

No código do AG, é gerada uma nova população de indivíduos mutados que é somada aos indivíduos originais. Por este motivo a função de mutação gera um novo indivíduo. Outro motivo para isso é que, sempre que um novo indivíduo é gerado, seu fitness é calculado automaticamente.

População

A população é um objeto de uma classe Rotas.

Sempre que instanciada, a classe gera uma quantidade pré-definida de indivíduos aleatórios.

A classe da população é responsável por implementar o crossover a seleção dos indivíduos.

Crossover

A função de crossover escolhe quais indivíduos das 10 populações serão cruzados.
Neste caso, a população é dividida ao meio e cada indivíduo combinado com seu equivalente da outra metade.

Para cruzar os indivíduos, criei uma função que combina os cromossomos conforme a imagem abaixo:



Resultado:

Assim como a mutação, o crossover retorna uma lista de novos indivíduos.

Seleção

A seleção é responsável por determinar quais serão os indivíduos que passarão para a próxima geração. Ela faz isso ordenando a lista da população total e definindo a nova população como os 10 melhores.

Com isso, o AG está pronto para rodar!

Resultados, problemas e limitações

Problemas e limitações

Apesar de fascinantes, os AGs não são perfeitos. Durante a implementação, percebi dois dos problemas comumente relatados sobre os AGs

Convergência prematura

Um dos grandes problemas do AG é a convergência prematura. Quando um indivíduo razoavelmente bom aparece muito cedo, o algoritmo tende a usar este como modelo para geração de novos indivíduos. Isso é um problema pois impede a criação de indivíduos melhores. Para entender melhor, a imagem abaixo exemplifica máximas e mínimas globais e locais:

Há alguns métodos para mitigar este problema como melhores funções de crossover e mutação ou eliminar indivíduos idênticos, mas ainda é um problema sem solução definida.

Falta de garantia de otimalidade

Os AGs são algoritmos heurísticos e não garantem a obtenção da solução ótima em todos os casos. Embora possam convergir para soluções de alta qualidade, não há garantia de que a solução encontrada seja a melhor possível. Isso foi percebido quando o algoritmo é executado várias vezes e as respostas foram diferentes. Isso seria mitigado aumentando a quantidade de gerações mas o custo disso é a necessidade de mais tempo e processamento.

Resultado

O indivíduo mais adaptado do AG foi:

Conclusão

Pessoalmente, os AG me fascinam. Foi um prazer enorme trabalhar neste projeto e poder compartilhá-lo. Aprendi muito no processo e isso me motiva a buscar mais conhecimento na área. Durante o desenvolvimento, tive contato com a tese de doutorado de Estefane George Macedo de Lacerda "Model Selection of RBF Networks via Genetic Algorithms", o que foi de grande ajuda na compreensão do funcionamento dos AGs e gostaria de parabenizá-la abertamente pela fantástica pesquisa.

Você pode acessar o meu repositório aqui