Algoritmos Experimentais para o Problema Biobjetivo da Árvore Geradora Quadrática em Adjacência de Arestas
Algoritmos Experimentais, Algoritmos exatos, Metaheurísticas, Otimização Multiobjetivo, Árvore Geradora Quadrática em Adjacência de Arestas Biobjetivo.
O problema da Árvore Geradora Mínima Quadrática (AGMQ) é uma generalização do problema da Árvore Geradora Mínima onde, além dos custos lineares das arestas, custos quadráticos associados a cada par de arestas são considerados. Os custos quadráticos são devidos à custos de interação entre as arestas. No caso das interações ocorrerem somente entre arestas adjacentes, o problema é denominado Árvore Geradora Mínima Quadrática em Adjacência de Arestas (AGMQA). Tanto a AGMQ quanto a AGMQA são NP-difíceis e modelam diversos problemas reais envolvendo projeto de redes de infraestrutura. Os custos lineares e quadráticos são somados nas versões mono-objetivo destes problemas. Frequentemente, aplicações reais lidam com objetivos conflitantes. Nestes casos a consideração dos custos lineares e quadráticos separadamente é mais adequada e a otimização multiobjetivo provê modelos mais realistas. Algoritmos exatos e heurísticos são investigados neste trabalho para a versão biobjetivo da AGMQA. As seguintes técnicas são propostas: backtracking, branch-and-bound, busca local de Pareto, Greedy Randomized Adaptive Search Procedure, Simulated Annealing, NSGAII, MOEA-D, Algoritmo Transgenético, Otimização por Nuvem de Partículas e uma hibridização entre o MOEA-D e o Algoritmo Transgenético. São utilizados indicadores de qualidade Pareto concordantes para comparar os algoritmos em um conjunto de instâncias de bases de dado da literatura.