Design configuration for MMAS algorithm applied for the travelling salesman problem with dynamic demands
Nenhuma Miniatura disponível
Data
2022-06-24
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Centro Federal de Educação Tecnológica de Minas Gerais
Resumo
Os algoritmos Ant Colony Optimization (ACO) foram inicialmente desenvolvidos para problemas de otimização estática, em que os dados do problema são conhecidos a priori e não sofrem alterações durante a execução. No entanto, sua estrutura baseada em memória mostrou-se eficaz também em Problemas de Otimização Combinatória Dinâmicos (POCD), nos quais os dados podem mudar em tempo real, sem previsibilidade. A partir de uma revisão da literatura, identificaram-se adaptações para melhorar o desempenho do ACO em POCD, incluindo o algoritmo Population-Based ACO (P-ACO), projetado especificamente para essa classe de problemas. Embora o P-ACO tenha se destacado por seu processamento rápido, faltam estudos conclusivos sobre a eficácia dos métodos ACO em cenários dinâmicos. Neste trabalho, realiza-se uma extensiva campanha experimental para avaliar as principais versões do ACO aplicáveis a POCD: o MAX-MIN Ant System (MMAS) e o P-ACO. Utilizou-se como estudo de caso uma variação dinâmica do Problema do Caixeiro-Viajante (PCVDD), amplamente adotado na literatura. As principais contribuições incluem: (i) a proposta de um setup experimental pioneiro, com configuração automática de parâmetros para POCD; (ii) a introdução da métrica de hipervolume para avaliação de desempenho em horizontes temporais variáveis; e (iii) a comparação entre MMAS e P-ACO, demonstrando que o MMAS supera o P-ACO quando combinado com busca local, enquanto o inverso ocorre sem essa técnica. Os resultados também indicam que procedimentos adaptativos têm impacto significativo apenas quando a busca local é desativada.
Descrição
Corpo do texto em inglês
Palavras-chave
Algoritmos, Otimização, Automação