Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-02-01T18:20:32Z
No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Dissertação - Ivaneide Alves Protásio.pdf: 1710443 bytes, checksum: 890976db270d6fb66cc3f04a13cabf51 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-02-01T18:20:47Z (GMT) No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Dissertação - Ivaneide Alves Protásio.pdf: 1710443 bytes, checksum: 890976db270d6fb66cc3f04a13cabf51 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-02-01T18:21:08Z (GMT) No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Dissertação - Ivaneide Alves Protásio.pdf: 1710443 bytes, checksum: 890976db270d6fb66cc3f04a13cabf51 (MD5) / Made available in DSpace on 2017-02-01T18:21:08Z (GMT). No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Dissertação - Ivaneide Alves Protásio.pdf: 1710443 bytes, checksum: 890976db270d6fb66cc3f04a13cabf51 (MD5)
Previous issue date: 2014-03-21 / FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas / 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 . / 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
| Identifer | oai:union.ndltd.org:IBICT/oai:http://localhost:tede/5471 |
| Date | 21 March 2014 |
| Creators | Protásio, Ivaneide Alves |
| Contributors | Nakamura, Fabíola Guerra |
| Publisher | Universidade Federal do Amazonas, Programa de Pós-graduação em Informática, UFAM, Brasil, Instituto de Computação |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFAM, instname:Universidade Federal do Amazonas, instacron:UFAM |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -312656415484870643, 600, 500, 4163267508810754609 |
Page generated in 0.0089 seconds