Design configuration for MMAS algorithm applied for the travelling salesman problem with dynamic demands

Página do item simplificado
dc.contributor.advisorSouza, Sérgio Ricardo de
dc.contributor.advisor-coWanner, Elizabeth Fialho
dc.contributor.advisor-coBezerra, Leonardo César Teonácio
dc.contributor.advisor-coLatteshttp://lattes.cnpq.br/2243256075052322
dc.contributor.advisor-coLatteshttp://lattes.cnpq.br/0664132257054306
dc.contributor.advisorLatteshttp://lattes.cnpq.br/3677015295211434
dc.contributor.authorOliveira, Sabrina Moreira de
dc.contributor.authorLatteshttp://lattes.cnpq.br/9822253950704581
dc.contributor.refereeSouza, Sérgio Ricardo de
dc.contributor.refereeWanner, Elizabeth Fialho
dc.contributor.refereeBezerra, Leonardo César Teonácio
dc.contributor.refereeMarcelino, Carolina Gil
dc.contributor.refereeStüzle, Thomas
dc.contributor.refereeSá, Elisângela Martins de
dc.contributor.refereeMartins, Flávio Vinícius Cruzeiro
dc.date.accessioned2025-04-03T23:45:53Z
dc.date.available2025-04-03T23:45:53Z
dc.date.issued2022-06-24
dc.descriptionCorpo do texto em inglês
dc.description.abstractOs 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.
dc.description.abstractotherAnt colony optimization (ACO) algorithms were originally designed for static optimization problems where the input data is known a priori and is not allowed to undergo any change during their execution. Later, ACO memory proved to be effective in dealing with problems in which the benchmark is allowed to change in real-time without any prediction, that is, to solve Dynamic Combinatorial Optimization Problems (DCOPs). Among the main proposals of this kind, several adaptations of ACO procedures to improve information reuse can be identified in the Literature. In addition, the Population-Based ACO Algorithm (P-ACO) was designed specifically for DCOPs. Indeed, P-ACO drew the attention of the research community due to its ability to process faster pheromone information but the few studies that assessed the effectiveness of the procedures of ACO and specially P-ACO were not sufficient to achieve conclusions about the state of the art in ACO for Dynamic Optimization. In this work, we carried out an extensive experimental campaign to evaluate the most common adaptations of ACO main procedures identified in the literature, using the state-of-the-art ACO for static optimization as underlying algorithms, that is, the MAX -MIN Ant System ( MMAS) and the most relevant ACO algorithm proposed for dynamic optimization, P-ACO. A variant of the traveling salesman problem, the TSP with dynamic demands (TSPDDs) was used as a test benchmark, similar to most investigations on ACO for combinatorial optimization. More importantly, a carefully designed experimental setup was adopted, which represented significant contributions to literature as follows. This is the first work that acknowledged that DCOPs required custom-configured parameter settings and also the first that used an automatic configuration tool for this task. In addition, we also showed how the hypervolume indicator could be used to evaluate the anytime behavior of algorithms for DCOPs. This new way of configuring and comparing the algorithm’s performance was then applied between MMAS and P-ACO. Comparing the performance of both algorithms showed that the first was able to consistently outperform the latter when a local search was adopted. Finally, we conducted an experimental investigation on the DCOP-specific components proposed for ACO, isolating local search, which is one of the most relevant procedures presented in some ACO algorithms, like MMAS. Results showed that those components contributed very little to performance when algorithms were allowed to use local search but were remarkably effective in its absence. In fact, the used local search was not only feasible to be applied when dealing with dynamic components but also a must-use procedure, even for the TSPDDs where runtime was an issue to be coupled with. When a local search was applied, MMAS was able to outperform P-ACO for a large part of the experimental setup we adopted.
dc.identifier.urihttps://repositorio.cefetmg.br//handle/123456789/1101
dc.language.isopt
dc.publisherCentro Federal de Educação Tecnológica de Minas Gerais
dc.publisher.countryBrasil
dc.publisher.initialsCEFET-MG
dc.publisher.programPrograma de Pós-Graduação em Modelagem Matemática e Computacional
dc.subjectAlgoritmos
dc.subjectOtimização
dc.subjectAutomação
dc.titleDesign configuration for MMAS algorithm applied for the travelling salesman problem with dynamic demands
dc.typeTese

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Design configuration for MMAS algorithm applied for the travelling salesman problem with dynamic demands.pdf
Tamanho:
4.76 MB
Formato:
Adobe Portable Document Format
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.39 KB
Formato:
Item-specific license agreed to upon submission
Descrição:
Baixar

Coleções

Doutorado em Modelagem Matemática e Computacional