Jumping Frog Optimization e Algoritmo Genético Aplicados à Soluςão do Problema das P-Medianas

Abstract

Este artigo propõe um estudo comparativo entre aplicações das metaheurísticas Jump Frog Optimization e Algoritmo Genético Híbrido aplicados à solução do Problema das p-Medianas. O problema das p-medianas tem por objetivo determinar p nós, denominado medianas, em um grafo de n vértices, minimizando a distância total a partir de outros nós do grafo. A metodologia utilizada consiste na implementação do Algoritmo de Otimização por Saltos de Rãs (JFO) e Algoritmo Genético com a Busca Local (AG-BL) para melhoria do cromossomo gerado. A técnica utilizada para Busca Local é Descida Randômica. Após conhecidos os pontos onde serão fixados as medianas, é aplicado o algoritmo de Gillet e Johnson (G&J) para a geração das regiões de atendimento, conhecida como cluster, juntamente com a Heurística de Localização-Alocação (HLA). HLA - são métodos utilizados para melhorar a localização da mediana na sua região de atendimento. Os resultados obtidos são analisados e comparados com os encontrados na literatura e mostram que as soluções encontradas através da metaheurística JFO são superiores às encontradas pelo AG.