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.
Link permanente
Tenho interesse em estudar algorítimos , no seu caso, aplicados no excel, como ponto de partida. Quais os requisitos meus, necessários para inicial seu curso. Falo de conhecimento.
Link permanente
Olá Water tudo bom, acredito que inicialmente você vai necessitar conhecer o VBA que é a logica de programação do MS Excel para depois realizar esses códigos de maneira otimizada. Abraços