Dissertação

Incorporando técnicas de mineração de dados a meta-heurísticas populacionais

Vários problemas do mundo real podem ser modelados como problemas de otimização combinatória. Em geral são problemas complexos e de larga escala, não podendo ser resolvidos por métodos exatos, pois os mesmos necessitariam de tempo computacional impraticável. Desse modo, as meta-heurísticas têm si...

ver descrição completa

Autor principal: Protásio, Ivaneide Alves
Outros Autores: http://lattes.cnpq.br/0854253453556102
Grau: Dissertação
Idioma: por
Publicado em: Universidade Federal do Amazonas 2017
Assuntos:
Meta-heurísticas Populacionais
Caixeiro Viajante
Mineração de Dados
Algoritmo Genético
CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO
Acesso em linha: http://tede.ufam.edu.br/handle/tede/5471
id oai:https:--tede.ufam.edu.br-handle-:tede-5471
recordtype dspace
spelling oai:https:--tede.ufam.edu.br-handle-:tede-54712017-02-02T05:03:40Z Incorporando técnicas de mineração de dados a meta-heurísticas populacionais Protásio, Ivaneide Alves Nakamura, Fabíola Guerra http://lattes.cnpq.br/0854253453556102 http://lattes.cnpq.br/9615041048900531 Meta-heurísticas Populacionais Caixeiro Viajante Mineração de Dados Algoritmo Genético CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO Vários problemas do mundo real podem ser modelados como problemas de otimização combinatória. Em geral são problemas complexos e de larga escala, não podendo ser resolvidos por métodos exatos, pois os mesmos necessitariam de tempo computacional impraticável. Desse modo, as meta-heurísticas têm sido amplamente empregadas para a resolução de tais problemas. Duas das principais dificuldades destes métodos são escapar das regiões sub-ótimas e evitar a convergência prematura do algoritmo. Para tentar solucionar estes problema, propõe-se o uso de técnicas híbridas buscando desenvolver estratégias que sejam aplicáveis a diversos algoritmos de otimização. O presente trabalho investiga a eficiência da incorporação de técnicas de Mineração de Dados (MD) as Meta-heurísticas Populacionais Colônia de Formiga e Algoritmo Genético com o intuito de guiá-las a gerar novas e melhores soluções. Para a validação da proposta, serão utilizados o Problema do Caixeiro Viajante e diferentes versões das meta-heurísticas híbridas serão testadas e analisadas. A técnica escolhida para guiar a obtenção de novas soluções, a partir dos padrões obtidos com a Mineração de Dados, foi o de Agrupamento de soluções similares, na tentativa de reduzir o espaço de busca em problemas de otimização combinatória. O algoritmos de mineração utilizados são o K-Means e o Ward que utilizam técnicas de particionamento e hierárquico respectivamente. Experimentos Computacionais foram realizados com o objetivo de avaliar o uso de MD em Meta-heurísticas Populacionais tradicionais, atai como Algoritmo Genético e Colonia de Formiga. Estes experimentos mostraram que a utilização de padrões minerados podem auxiliar na obtenção de boas soluções em relação as técnicas tradicionais Several real-world problems can be modeled as combinatorial optimization problems. This is are usually complex and large scale problems can not be solved by exact methods , since they would require impractical computational time . Thus, meta-heuristics have been widely used for solving such problems. Two of the major difficulties of these methods are to escape from sub-optimal regions and to avoid premature convergence of the algorithm . To try to solving this problem , we use o hybrid techniques in order to develop strategies that are applicable to many optimization algorithms . This study investigates the efficiency of incorporating of data mining techniques to ant colony and genetic algorithm Population Metaheuristcs in order to guide them to generate new and better solutions. To validate the proposal, we use the Travelling Salesman Problem and the Problem Sets Cover and different versions of the hybrid meta-heuristics are tested and analyzed . The technique chosen to guide the search of new solutions , from the patterns obtained with the Data Mining , was grouping similar solutions in an attempt to reduce the search space in combinatorial optimization problems . The mining algorithms used are the K -means and Ward which use techniques of hierarchical and partitioning respectively. Computational experiments were performed in order to evaluate the use of MD in Meta-Population traditional heuristics . These experiments showed that the use of mined patterns can assist in obtaining good solutions . FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas 2017-02-01T18:21:08Z 2014-03-21 Dissertação PROTÁSIO, Ivaneide Alves. Incorporando técnicas de mineração de dados a meta-heurísticas populacionais. 2014. 73 f. Dissertação (Mestrado em Informática) - Universidade Federal do Amazonas, Manaus, 2014. http://tede.ufam.edu.br/handle/tede/5471 por Acesso Aberto http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Universidade Federal do Amazonas Instituto de Computação Brasil UFAM Programa de Pós-graduação em Informática
institution TEDE - Universidade Federal do Amazonas
collection TEDE-UFAM
language por
topic Meta-heurísticas Populacionais
Caixeiro Viajante
Mineração de Dados
Algoritmo Genético
CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO
spellingShingle Meta-heurísticas Populacionais
Caixeiro Viajante
Mineração de Dados
Algoritmo Genético
CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO
Protásio, Ivaneide Alves
Incorporando técnicas de mineração de dados a meta-heurísticas populacionais
topic_facet Meta-heurísticas Populacionais
Caixeiro Viajante
Mineração de Dados
Algoritmo Genético
CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO
description Vários problemas do mundo real podem ser modelados como problemas de otimização combinatória. Em geral são problemas complexos e de larga escala, não podendo ser resolvidos por métodos exatos, pois os mesmos necessitariam de tempo computacional impraticável. Desse modo, as meta-heurísticas têm sido amplamente empregadas para a resolução de tais problemas. Duas das principais dificuldades destes métodos são escapar das regiões sub-ótimas e evitar a convergência prematura do algoritmo. Para tentar solucionar estes problema, propõe-se o uso de técnicas híbridas buscando desenvolver estratégias que sejam aplicáveis a diversos algoritmos de otimização. O presente trabalho investiga a eficiência da incorporação de técnicas de Mineração de Dados (MD) as Meta-heurísticas Populacionais Colônia de Formiga e Algoritmo Genético com o intuito de guiá-las a gerar novas e melhores soluções. Para a validação da proposta, serão utilizados o Problema do Caixeiro Viajante e diferentes versões das meta-heurísticas híbridas serão testadas e analisadas. A técnica escolhida para guiar a obtenção de novas soluções, a partir dos padrões obtidos com a Mineração de Dados, foi o de Agrupamento de soluções similares, na tentativa de reduzir o espaço de busca em problemas de otimização combinatória. O algoritmos de mineração utilizados são o K-Means e o Ward que utilizam técnicas de particionamento e hierárquico respectivamente. Experimentos Computacionais foram realizados com o objetivo de avaliar o uso de MD em Meta-heurísticas Populacionais tradicionais, atai como Algoritmo Genético e Colonia de Formiga. Estes experimentos mostraram que a utilização de padrões minerados podem auxiliar na obtenção de boas soluções em relação as técnicas tradicionais
author_additional Nakamura, Fabíola Guerra
author_additionalStr Nakamura, Fabíola Guerra
format Dissertação
author Protásio, Ivaneide Alves
author2 http://lattes.cnpq.br/0854253453556102
author2Str http://lattes.cnpq.br/0854253453556102
title Incorporando técnicas de mineração de dados a meta-heurísticas populacionais
title_short Incorporando técnicas de mineração de dados a meta-heurísticas populacionais
title_full Incorporando técnicas de mineração de dados a meta-heurísticas populacionais
title_fullStr Incorporando técnicas de mineração de dados a meta-heurísticas populacionais
title_full_unstemmed Incorporando técnicas de mineração de dados a meta-heurísticas populacionais
title_sort incorporando técnicas de mineração de dados a meta-heurísticas populacionais
publisher Universidade Federal do Amazonas
publishDate 2017
url http://tede.ufam.edu.br/handle/tede/5471
_version_ 1831969465487589376
score 11.753735

Registros relacionados