Seleção supervisionada de meta-heurísticas para o problema bipartite graph drawing
Arquivos
Data
2021-08-16
Autores
Ferrari, Bruno José Dreux 
Orientadores
Rosset, Mariá Cristina Vasconcelos Nascimento
Tipo
Trabalho de conclusão de curso
Título da Revista
ISSN da Revista
Título de Volume
Resumo
O processo de visualização da informação é um tópico relevante para o estudo em Ciência da Computação. Dados e informações, quando apresentados de maneira intuitiva, ajudam o usuário a entender relações relevantes e a extrair novas informações de dados abstratos de maneira eficiente. Neste universo de visualização da informação, os grafos são uma forma bem estabelecida e aceita para se representar diversas informações. São estruturas que modelam diversos problemas e são utilizadas em vários cenários, como representações de redes sociais, ligações entre páginas na web, planejamento de produção, dentre outras. Entretanto, como são estruturas que não possuem ordem, podem ser de difícil entendimento caso não estejam dispostos de maneira organizada. Portanto, para que as informações contidas possam ser visualizadas corretamente, é importante que suas representações sejam feitas utilizando algum critério estético. Por ser uma forma de abstração que por construção, representa objetos de natureza combinatória, o problema de encontrar uma representação que seja ótima em algum critério, se faz necessário, na maioria das vezes, a resolução de problemas da classe NP-Completo, sendo necessário a utilização de heurísticas para uma solução rápida do problema. Nesse contexto, existem diversas meta-heurísticas que resolvem esse problema, conhecido por graph drawing, cujas meta-heurísticas diferenciam-se em seu desempenho a depender das instâncias estudadas. Dessa forma, o presente trabalho apresenta um método de seleção de algoritmos para o problema de graph drawing, por uma estratégia de aprendizado supervisionado (meta-aprendizado) baseada em algoritmos de classificação. 1240 grafos e 16 classificadores foram considerados em testes computacionais, sendo que, em termos de acurácia, seleções não melhores que a incidência da melhor meta-heurística foram encontradas. Em outras palavras, o método selecionou, proporcionalmente, de forma correta, na proporção equivalente à do algoritmo com maior parcela de melhores resultados. Após a análise dos resultados, concluiu-se que fatores para tal acontecimento foram a homogeneidade tanto de soluções geradas, isto é, resultados em geral muito próximos, quanto de grafos considerados, isto é, instâncias com características similares.