Título: Análise do Espaço de Instâncias - Um estudo sobre a ferramenta MATILDA
Título alternativo: Instance Space Analysis - A Study on the MATILDA Toolkit
Autoria de: Kali Nunes Ferreira
Orientação de: Mayron Cesar de Oliveira Moreira
Presidente da banca: Mayron César de Oliveira Moreira
Primeiro membro da banca: Janderson Rodrigo de Oliveira
Segundo membro da banca: Paulo Henrique Sales Guimaraes
Palavras-chaves: Otimização, Espaço de instância, Heurística, Problema da Mochila, Pesquisa operational
Data da defesa: 25/07/2023
Semestre letivo da defesa: 2023-1
Data da versão final: 02/08/2023
Data da publicação: 02/08/2023
Referência: Ferreira, K. N. Análise do Espaço de Instâncias - Um estudo sobre a ferramenta MATILDA. 2023. 43 p. Trabalho de Conclusão de Curso (Graduação em Ciência da Computação Bacharelado)-Universidade Federal de Lavras, Lavras, 2023.
Resumo: A avaliação objetiva de heurísticas é um problema há décadas na computação, pela dificuldade de escolher um conjunto de instâncias de teste que explore todas as fraquezas e virtudes de um algoritmo livre de viés, e também a dificuldade de determinar o que faz uma instância ser fácil ou difícil. Afim de avançar o entendimento sobre o comportamento desses programas, foi desenvolvido o método de Análise de Espaço de Instância, que seleciona as características de maior impacto na performance de algoritmos para resolver as instâncias testadas, e permite uma visualização clara de um plano em que projeta estas instâncias. Esse método também oferece um sistema que prevê o melhor algoritmo para resolver uma dada instância baseado na posição projetada a partir de suas características. Este trabalho explica o funcionamento desse método, e o aplica utilizando software MATILDA, desenvolvido para facilitar o acesso ao método. É demonstrada a aplicação da MATILDA, tanto para analisar as instâncias existentes quanto para gerar novas instâncias, ao problema da mochila, um problema clássico de otimização na literatura de computação.
Abstract: The objective avaliation of heuristics has been a problem for decades in the computer science field, due to the difficulty both of choosing a test instance set that explores all weakness and strengths of an algorithm without bias, and of what makes an instance be easy or hard to solve. The Instance Space Analysis method was developed with the goal of advancing the understanding of these programs behaviours, a method that selects the features of the tested instance that had the most impact over given algorithms performances and allows clear visualization of a 2d plane where all these instances are projected. This method also offers a program that antecipates the best algorithm to solve a given instance based on its projected position from its features. This work explains this methods inner working, and applies it using the MATILDA software, developed with the goal to facilitate access to the method. MATILDAs application is demonstrated both for analysing existing instances of and for guiding the generation of new instances of the knapsack problem, a classic optimization problem in computer science literature.
URI: sip.prg.ufla.br/publico/trabalhos_conclusao_curso/acessar_tcc_por_curso/
ciencia_da_computacao/20231201811357
URI alternaviva: sem URI do Repositório Institucional da UFLA até o momento.
Curso: G010 - CIÊNCIA DA COMPUTAÇÃO (BACHARELADO)
Nome da editora: Universidade Federal de Lavras
Sigla da editora: UFLA
País da editora: Brasil
Gênero textual: Trabalho de Conclusão de Curso
Nome da língua do conteúdo: Português
Código da língua do conteúdo: por
Licença de acesso: Acesso aberto
Nome da licença: Licença do Repositório Institucional da Universidade Federal de Lavras
URI da licença: repositorio.ufla.br
Termos da licença: Acesso aos termos da licença em repositorio.ufla.br
Detentores dos direitos autorais: Kali Nunes Ferreira e Universidade Federal de Lavras
Baixar arquivo