“Bicentenário da Independência: 200 anos de ciência, tecnologia e inovação no Brasil e 96 anos de contribuição da UFV”.
8 a 10 de novembro de 2022
Trabalho 16587
| ISSN | 2237-9045 |
|---|---|
| Instituição | Universidade Federal de Viçosa |
| Nível | Graduação |
| Modalidade | Pesquisa |
| Área de conhecimento | Ciências Exatas e Tecnológicas |
| Área temática | Ciência da computação |
| Setor | Instituto de Ciências Exatas e Tecnológicas - Campus Florestal |
| Bolsa | PIBIC/CNPq |
| Conclusão de bolsa | Não |
| Apoio financeiro | CAPES |
| Primeiro autor | Artur Souza Papa |
| Orientador | MARCUS HENRIQUE SOARES MENDES |
| Título | Uso da meta-heurística Border Collie Optimization na resolução do problema do caixeiro-viajante |
| Resumo | Um clássico exemplo de problema de otimização combinatória é o Problema do Caixeiro Viajante (PCV), nele tem-se a seguinte situação, um caixeiro viajante deve visitar n cidades diferentes, iniciando e encerrando sua viagem na primeira cidade. Apesar de parecer um caso simples, trata-se de um problema NP-difícil, ou seja, é um problema que possui grande dificuldade de solução exata. Assim, observa-se que devido à complexidade do PCV é interessante considerar o uso de heurísticas e meta-heurísticas para solucioná-lo. Nesse viés, dentre essas possibilidades para resolver o problema, tem-se a meta-heurística baseada em enxame Border Collie Optimization (BCO). Meta-heurísticas baseadas em enxame (swarm) são aquelas inspiradas no comportamento social de insetos ou animais. Dessa maneira, vale notar que o BCO tem como principal característica a imitação do estilo de pastoreio dos cães Border Collie para solucionar problemas, estes cães são extremamente inteligentes, atléticos e podem ser facilmente treinados, sendo o pastoreio uma habilidade inerente que eles possuem. Seguindo esse raciocínio, pode-se dizer que os Border Collie possuem, principalmente, três técnicas de pastoreio: gathering (reunião), stalking (perseguição) e eyeing (observação). No primeiro método, os cães controlam as ovelhas pelos lados e pela frente, eles tendem a reuni-las e direcioná-las para a fazenda. Para a segunda técnica, os cachorros adotam poucos movimentos parecidos com os de lobos quando eles vão controlar as ovelhas. Eles se agacham abaixando suas cabeças, colocam seus traseiros altos e seus rabos para baixo. No último artifício os Border Collie imitam o comportamento dos lobos de seleção da vítima, isso é chamado de “dar uma olhada” ou observação. Quando as ovelhas se perdem, esses cães inteligentes olham fixamente nos seus olhos, o que exerce pressão psicológica para que o grupo se mova na direção correta. Posto isso, vale citar que foi utilizada a linguagem python para programar o algoritmo e suas devidas funções. Assim, tem-se que o algoritmo proposto foi testado em 8 funções de benchmarking disponíveis na literatura. Cada experimento consistiu de 30 execuções independentes nas quais coletou-se dados estatísticos de desempenho de cada iteração, como: média, desvio padrão, melhor e pior fitness de cada execução. Observou-se que os resultados alcançados estão compatíveis com os valores esperados de desempenho nas 8 funções. Outrossim, tem-se que para utilizar o BCO para resolver o PCV é necessário adaptar o algoritmo proposto para lidar com variáveis de decisão discretas e isto pode ser feito transformando a matriz de geração dos indivíduos em uma matriz com 0’s e 1’s e, logo após, pegar as arestas com o valor 1 e multiplicar por seus respectivos valores da matriz de pesos. Na continuidade da pesquisa o resultado do BCO adaptado para variáveis discretas será comparado à heurística do vizinho mais próximo aplicado anteriormente à instância bays29.tsp do PCV. |
| Palavras-chave | otimização, problema do caixeiro viajante, meta-heurística |
| Forma de apresentação..... | Vídeo |
| Link para apresentação | Vídeo |
|---|