Compartilhamento |
|
Use este identificador para citar ou linkar para este item:
https://tedebc.ufma.br/jspui/handle/tede/tede/2063
Tipo do documento: | Dissertação |
Título: | Meta-aprendizagem aplicada a problemas de máxima satisfabilidade |
Título(s) alternativo(s): | Meta-learnging applied to problems of maximum satisfiability |
Autor: | MIRANDA, Enrico Silva |
Primeiro orientador: | OLIVEIRA, Alexandre César Muniz de |
Resumo: | Meta-aprendizado tem sido aplicado com sucesso em problemas de otimização, como o problema do Caixeiro Viajante (PCV) e Máxima Satisfabilidade (MaxSAT). Este último é um problema NP-Difícil, relevante para o estudo de problemas acadêmicos e industriais. No entanto, a maior parte da pesquisa atual no problema MaxSAT foca em métodos de solução exata. Devido à necessidade de soluções boas em um período de tempo reduzido, a utilização de meta-heurísticas é considerada neste trabalho. Além disso, propõe-se um framework de meta-aprendizagem para seleção de meta-heurísticas para o problema MaxSAT, o que inclui nova representação abstrata baseada em grafos, derivação de um novo conjunto de meta-características e definição de mecanismos de aprendizagem baseados em experiência obtida a priori. Experimentos comprovam que o arcabouço é eficaz para seleção de meta-heurística e de seus parâmetros para instâncias MaxSAT. As novas metacaracterísticas derivadas da representação baseada em grafo podem ser consideradas tão boas quanto o estado da arte atual. As medidas propostas de características de grafos podem ser aplicadas em trabalhos futuros a outras classes de problemas |
Abstract: | Meta-learning has been used with success in optimization problems, like the Traveling Salesman Problem (TSP) and the Maximum Satisfability Problem (MaxSAT). The latter is considered NP-Hard while also being relevant for academic and industrial problems. However, most of the research on the MaxSAT problem focuses of exact solution methods. Due to the need of generating good solutions on a limited time frame, this work considers the use of meta-heuristics. A meta-learning framework for meta-heuristic selection is also proposed for the MaxSAT problem, including a new representation based on graphs, new meta-features derived from this representation, the definition of machine learning mechanisms based on previous experience. Experiments show that the proposed outline is effective for selection of meta-heuristics and parameters for MaxSAT. The new metafeatures derived are shown to be as good as the current state of the art. The graph meta-features proposed can be applied to other problems on the near future. |
Palavras-chave: | Meta aprendizagem Meta heurístcas Máxima Satisfabilidade Meta-learning Meta-heuristics Maximum satisfiability |
Área(s) do CNPq: | Engenharia de Software |
Idioma: | por |
País: | Brasil |
Instituição: | Universidade Federal do Maranhão |
Sigla da instituição: | UFMA |
Departamento: | DEPARTAMENTO DE INFORMÁTICA/CCET |
Programa: | PROGRAMA DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO/CCET |
Citação: | MIRANDA, Enrico Silva. Meta-aprendizagem aplicada a problemas de máxima satisfabilidade. 2017. 69 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal do Maranhão, São Luís, 2017. |
Tipo de acesso: | Acesso Aberto |
URI: | https://tedebc.ufma.br/jspui/handle/tede/tede/2063 |
Data de defesa: | 24-Jul-2017 |
Aparece nas coleções: | DISSERTAÇÃO DE MESTRADO - PROGRAMA DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
EnricoSilvaMiranda.pdf | Dissertação | 1,01 MB | Adobe PDF | Baixar/Abrir Pré-Visualizar |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.