Universidade Federal do Rio Grande do Norte: Aplicação do algoritmo de otimização por colônia de formigas sobre o problema do passeio do robô seletivo
Please use this identifier to cite or link to this item: https://repositorio.ufrn.br/jspui/handle/123456789/18048
Title: Aplicação do algoritmo de otimização por colônia de formigas sobre o problema do passeio do robô seletivo
Authors: Oliveira Júnior, Edmilson Frank Machado
Keywords: Otimização combinatória;Problemas de rotemento, Algoritmos em colônia de formiga;Algoritmos experimentais;Grasp;Vns;Metaheurísticas;Vns;Grasp;Metaheuristics
Citation: OLIVEIRA JÚNIOR, Edmilson Frank Machado. Aplicação do algoritmo de otimização por colônia de formigas sobre o problema do passeio do robô seletivo. 2012. 79 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal do Rio Grande do Norte, Natal, 2012.
Portuguese Abstract: Este trabalho tem o objetivo de propor e avaliar uma variante para o algoritmo de colônia de formigas baseando-se no resultado de experimentos executados sobre o problema do Passeio do Robô Seletivo (PRS, um novo problema, também proposto neste trabalho. São implementadas quatro metaheurísticas, GRASP, VNS, e duas versões do Otimização por Colônia de Formigas, e analisados seus resultados executando-os sobre 32 instâncias criadas no trabalho. As metaheurísticas também tem seu resultado comparado com o de um algoritmo exato. Os resultados mostram que o algoritmo implementado utilizando a metaheurística GRASP apresenta bons resultados. A versão multi-colônias do algoritmo de colônia de formigas, proposta e avaliada no trabalho, apresenta os melhores resultados
Abstract: This work seeks to propose and evaluate a change to the Ant Colony Optimization based on the results of experiments performed on the problem of Selective Ride Robot (PRS, a new problem, also proposed in this paper. Four metaheuristics are implemented, GRASP, VNS and two versions of Ant Colony Optimization, and their results are analyzed by running the algorithms over 32 instances created during this work. The metaheuristics also have their results compared to an exact approach. The results show that the algorithm implemented using the GRASP metaheuristic show good results. The version of the multicolony ant colony algorithm, proposed and evaluated in this work, shows the best results