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