ALGORITMO EVOLUCIONÁRIO (EA)

Fonte: iStock/Nobi_Prizue

Já ouviu falar sobre Algoritmo Evolucionário, Evolutivo ou Genético ? Sabia que ele pode te apoiar em tarefas de otimização, mineração de dados, robótica, sistema de controle, modelagem financeira e muito mais?

O algoritmo evolutivo é uma ferramenta poderosa que através de uma abordagem heurística, resolve problemas que não poderiam ser facilmente resolvido com tempo polinomial. Vamos entender melhor!

O algoritmo evolucionário – ou genético – é uma técnica de aprendizado de máquina aplicável a problemas de otimização. EA é particularmente adequado para resolver problemas computacionais que não são facilmente resolvidos usando algoritmos tradicionais em uma abordagem polinomial, como traveling salesman problem (problema do caixeiro viajante).

A técnica é baseada na evolução genética de seres vivos, dividida em fases distintas: Inicialização, Seleção, Operações Genéticas e Finalização.

A premissa do método é que os melhores indivíduos de uma população – de acordo com o objetivo do algoritmo e alguns critérios de aptidão – irão se reproduzir e gerar descendentes, enquanto os piores irão morrer. Em outras palavras, o algoritmo realiza uma seleção natural com os indivíduos de uma população.

Na fase de inicialização, uma população é criada no ambiente. Os indivíduos dessa população são caracterizados por um conjunto de parâmetros chamados genes. A coleção de genes – tipicamente representada por letras de um alfabeto – gera o cromossomo de um indivíduo. Para o sucesso do EA, os genes dos indivíduos devem ser tão aleatórios quanto possível, uma vez que representam a amplitude genética do problema. Quanto maior a variedade, melhor para o algoritmo.

Na fase de seleção, a viabilidade do candidato como soluções para o problema é avaliada por meio de alguma medição — ou Fitness Function (Função de aptidão) — que quantifica numericamente a qualidade dos indivíduos. Essa avaliação representa o quão bons esses indivíduos são como soluções para o problema. No final desta fase, os melhores indivíduos são selecionados para reprodução. Na fase de operação genética, os melhores indivíduos, ou seja, as melhores soluções encontradas (pais) gerarão seus descendentes (filhos). Os filhos são gerados a partir da mistura genética dos pais, isso é chamado de crossover.

Na fase de mutação é definada como o mecanismo em que novo material genético é aleatoriamente introduzido na solução, evitando que o algoritmo fique preso em extremos locais.

Finalmente, a etapa de finalização é responsável por interromper o algoritmo com uma definição de critério de parada. Os critérios usuais são o tempo de execução ou o alcance do algoritmo de desempenho satisfatório.

Exemplo Prático

Problema:

Você deve definir o melhor trajeto de uma aeronave na entrega de suprimentos, admitindo que existem 6 bases. Nesse cenário, a aeronave deve percorrer todas as bases pelo melhor caminho possível, sendo que o menor caminho é o mais viável.

A definição do melhor caminho pode ser realizada através do algoritmo genético, o diagrama de blocos a seguir ilustra essa execução.

Figura 1 Diagrama de Blocos. Fonte: Autoria Própria

Inicialmente o algoritmo requisita a posição das 6 bases, representadas geograficamente. Com as coordenadas de cada base, o algoritmo entra na etapa de Inicialização, onde é gerado caminhos aleatórios que a aeronave poderá percorrer, e para cada nova execução do algoritmo um novo percurso é sugerido.

É necessário então, calcular a Aptidão de cada trajeto gerado, entrando assim na etapa Fitness, isso pode ser feito calculando a distância total percorrida para cada trajeto, esse resultado é tabelado e classificado de forma crescente.

Na etapa de Seleção, o algoritmo seleciona os 4 menores percursos encontrados, denominados Pais. O próximo passo é escolher os caminhos que farão a reprodução, essa etapa é chamada de Crossover. Nesse problema, o 1º selecionado irá reproduzir com o 2º e o 3º selecionado com o 4º, desse modo, o critério utilizado para definição do ponto de crossover pode ser feita de forma randômica, ou seja, aplicado uma variação [2,6] o valor sorteado será o ponto / indice escolhido, sendo esse o ponto de comutação entre pares.

Admita que a figura Figura 2 (a) represente 2 (dois) trajetos Pais classificados pelo algoritmo, o próximo passo é definir o ponto de crossover, no exemplo o valor sorteado é 4. Dessa forma, a Figura 2 (b) ilustra o ponto que deve ser comutado entre os 2 trajetos selecionados. O resultado dessa comutação pode ser vista na Figura 2 (c).

Analisando atentamente o resultado encontrado, pode ser observado a ausência de algumas bases e a duplicata de outras no mesmo trajeto, isso é um erro que deve ser corrigido.

Figura 2 Crossover. Fonte: Autoria Própria

Existem algumas formas de contornar o problema, nesse problema a opção escolhida é excluir o último valor duplicado e adicionar as bases que faltam no trajeto.

A Figura 3 ilustra esse procedimento, os valores duplicados foram destacados em vermelho na Figura 3 (a), em seguida é feita a exclusão dos últimos valores, Figura 3 (b), e por fim é adicionado as bases que faltariam no trajeto, Figura 3 (c). Esse procedimento é feito para os 4 trajetos escolhidos.

Figura 3 Crossover Duplicatas. Fonte: Autoria Própria

A próxima fase é a etapa de Mutação, nela é sorteado randomicamente 2 valores, esses valores representam bases que serão comutadas no mesmo trajeto. Um exemplo pode ser visto na Figura 4, observe que a Figura 4 (a) é o resultado final encontrado na etapa de crossover, na Figura 4 (b) é destacados os pontos sorteados para mutação, nesse exemplo são os pontos [3] e [5], em seguida a Figura 4 (c) apresenta o resultado final do novo trajeto definido, ou seja, ao final dessa etapas o algoritmo chega em 4 novos caminhos possíveis para a aeronave, esses novos caminhos serão chamado de Filhos.

Figura 4 Mutação. Fonte: Autoria Própria

Com isso, o algoritmo percorreu todas as etapas da técnica de aprendizado - Inicialização, Cálculo de aptidão (fitness), Seleção, Crossover e Mutação - contudo, para que a técnica gere o resultado esperado, os novos percursos gerados devem ser realimentados no algoritmo de forma que seja calculado a aptidão Fitness dos novos percursos, sendo assim possível comparar com os anteriores, questionando se os percursos Filhos gerados são melhores que os percursos Pais definidos anteriormente.

Dessa forma, serão considerados trajetos viáveis os 4 caminhos Filhos gerados e os 2 melhores Pais classificados anteriormente. Em vista disso, o algoritmo será realimentado com 6 (seis) novos percursos, essa realimentação é feita na etapa do cálculo de aptidão (fitness), criando assim uma estrutura de repetição que deverá ser quebrada em algum momento seguindo algum tipo de critério de parada, definido pelo programador.

Espero que tenham gostado =D.

Comente aqui embaixo o que achou, teria aplicação para você?

Até a próxima !

Autor: Adson Nogueira Alves

Pesquisador de Inteligência Artificial