▷ Inteligência Artificial – Técnica Algoritmo Genético HX no Excel

Olá pessoal! Bem vindo ao meu novo artigo! Se você não sabe ou conhece, há um problema logístico chamado Caixeiro Viajante. Ele é considerado de alta complexidade se formos analisá-lo com os algorítimos lineares.

Se tomarmos o cálculo nesse método teremos a "maldição da multidimensionalidade". É inviável processarmos e aguardarmos o tempo necessário para a análise da menor distância a ser percorrida.

Mas, o que é o problema do Caixeiro Viajante?

Imagine um carteiro que deve entrar cartas em cinco cidades próximas, percorrer cada casa e voltar para sua origem. Agora imagine uma ligação entre as cidades.

O objetivo do problema é fazer a entrega das correspondências percorrendo todas as cidades, minimizando a distância percorrida utilizando o menor caminho entre os destinos informados.

Dentro dos retângulos, o número informado é a distância entre os destinos.

Podemos resolver esse problema de várias maneiras, uma é a do método linear onde executando no MS Excel será necessário a utilização do suplemento Solver, e devido ao problema da maldição da multidimensionalidade poderá realizar com até 8 destinos, pois se necessitar de mais destinos o Solver irá emitir uma mensagem de erro em que ultrapassamos os limites de variáveis a serem calculadas dentro do Excel.

Com esse problema e realizando a aula de Mineração de Dados, no curso de Gestão da Informação na UFPR com a Prof.a Dra Denise Tsunoda ela me apresentou o seguinte método, chamado Algoritmo Genético HX. O princípio do algoritmo é muito simples, não vou escrever aqui toda a teoria, pois acredito que a prática conseguiremos desenvolver melhor. Este algoritmo (Genético HX) está inserido dentro do "guarda-chuva" das técnicas de Inteligência Artificial. Vamos aos passos:

1° Passo

Escolher um destino aleatóriamente, neste caso foi o destino "3"

2° Passo

Realizar duas sequências de destinos aleatórios, segue um exemplo

1° Sequência - 3 - 1 - 5 - 2 - 4

2° Sequência - 3 - 2 - 1 - 4 - 5

3° Passo

Escolher primeiro destino, achar as distâncias entre os próximos destinos e escolher a menor distância entre eles, repetir essa estratégia até a última distância, vamos ao exemplo abaixo:

Analisando esta técnica, muito provável que ela irá te resultar um mínimo local, com pouca probabilidade de ser um mínimo global. O que se utiliza muito é uma mescla entre os algoritmos, iniciando com as heurísticas e depois continuando com os algoritmos lineares para reduzir significativamente o tempo de processamento e consequentemente resultando o mínimo global.

Segue o exemplo que fiz no MS Excel onde segue essa técnica aplicada para a quantidade de destinos desejados.

Analisando o algoritmo acima, podemos verificar que é possível melhorar (e muito!) esta técnica, segue alguns pontos de melhorias que identifiquei:

1° Escolher o primeiro destino, sendo ele fixo. Pois sempre sabemos onde a nossa rota irá se iniciar;

2° Adicionar mais sequências de maneiras aleatórias onde não poderá se repetir com as sequências anteriores;

3° Adicionar um loop para que a probabilidade aumente para a solução do mínimo global.

Com essas três melhorias irei criar um novo post chamado de Algoritmo Genético "Super" HX e nesta irei colocar todo o código VBA.

Espero que tenham gostado e se inspirado desse artigo! Caso tenha alguma sugestão de melhorias ou de mais pontos que você identificou, ou de outra técnica mais eficiente, poste aqui conosco nos comentários.

Se gostou, curtam e compartilhem para que todos saibam o que é possível fazer dentro do Excel.

E ja conhece o meu novo curso online de Excel?

Abraços a todos e até o próximo artigo!

Fabio BALDINI

Frase do dia: "Se a caminhada está difícil, então você está no caminho certo!" Autor: Desconhecido

 OBS: Obrigado sempre grande amigão e Mestre Alessandro Trovato, pelas inúmeras contribuições.