O Problema Biobjetivo da Árvore Geradora Quadrática em Adjacência de Arestas
Árvore geradora quadrática biobjetico com adjacência em arestas
Algoritmo exato
Heurística
Algoritmo evolucionário
O problema da Árvore Geradora Mínima Quadrática (AGMQ) é uma versão da Árvore Geradora Mínima na qual se considera, além dos custos lineares tradicionais, uma estrutura de custos quadrática. Tal estrutura quadrática modela efeitos de interação entre pares de arestas. Os custos lineares e quadráticos são somados para compor o custo total da árvore geradora, que deve ser minimizado. Quando as interações são restritas às arestas adjacentes, o problema é denominado Árvore Geradora Mínima Quadrática em Adjacência de Arestas (AGMQA). A AGMQA e a AGMQ são problemas NP-difíceis que modelam diversos problemas de projeto de redes de transporte e distribuição. Em geral, a AGMQA emerge como um modelo mais apropriado para modelagem de problemas reais. Embora, na literatura, os custos lineares e quadráticos sejam somados, em aplicações reais, pode ser interessante considerar os custos separadamente. Neste sentido, a Otimização Multiobjetivo provê uma modelagem mais realista para os problemas de AGMQ e da AGMQA. Uma revisão do estado da arte, até o momento, não foi capaz de encontrar trabalhos no qual a natureza inerentemente biobjetiva destes problemas é considerada. O objetivo desta tese é, pois, o desenvolvimento de algoritmos exatos e heurísticos para o problema da Árvore Geradora Quadrática Biobjetivo em Adjacência de Arestas (AGQA-bi). Para tanto, como fundamentação teórica, discutem-se outros problemas NP‑difíceis diretamente relacionados à AGQA-bi, a saber: AGMQA, Árvore Geradora Mínima Biobjetivo e Quadrático de Alocação. Algoritmos exatos backtracking, branch‑and‑bound e k-best são propostos para o problema-alvo desta investigação. Os algoritmos heurísticos desenvolvidos são: busca local Pareto Local Search, Algoritmo Transgenético, NSGA‑II, SPEA2, MOEA/D e suas respectivas hibridizações com algoritmos transgenéticos, a saber: NSTA, SPETA e MOTA/D. As abordagens evolucionárias mencionadas foram escolhidas devido aos resultados promissores em problemas relacionados à AGQA-bi. Além disso, NSGA-II, SPEA2 e MOEA/D são algoritmos evolucionários clássicos que apresentam bom desempenho para uma grande variedade de problemas. Os algoritmos propostos são comparados entre si por meio da análise de seus desempenhos em experimentos computacionais com casos de teste adaptados da literatura da AGMQ. No que se refere aos algoritmos exatos, a análise considera apenas o tempo de execução. No caso dos algoritmos heurísticos, além do tempo de execução, a qualidade do conjunto de aproximação gerado é avaliada. Indicadores de qualidade são empregados para aferir tal informação. Ferramentas estatísticas apropriadas são usadas na análise de desempenho dos algoritmos exatos e heurísticos.