Repositório Digital

A- A A+

Paralelização do algoritmo de geração de redes aleatórias contínuas por Simulated Annealing

.

Paralelização do algoritmo de geração de redes aleatórias contínuas por Simulated Annealing

Mostrar registro completo

Estatísticas

Título Paralelização do algoritmo de geração de redes aleatórias contínuas por Simulated Annealing
Outro título Paralelization of the algorithm to generate continuous random network using Simulated Annealing
Autor Romano, Gustavo
Orientador Maillard, Nicolas Bruno
Data 2008
Nível Mestrado
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Programa de Pós-Graduação em Computação.
Assunto Algoritmos paralelos
Análise numérica
[en] Continuous random network
[en] Paralelization
[en] Simulated Annealing
Resumo Esse trabalho tem dois objetivos principais: o primeiro deles consiste em apresentar o estado da arte sobre processos de otimização combinatorial dando uma ênfase especial ao método Simulated Annealing (SA). São apresentados seu histórico, funcionalidades, algoritmo genérico e propostas de paralelização presentes na literatura. Além disso, é apresentado o algoritmo de geração de redes aleatórias contínuas, algoritmo, esse, projetado por pesquisadores do Instituto de Física da UFRGS que utiliza o método SA para gerar redes que atendam certas restrições. O segundo objetivo consiste empropor a paralelização desse algoritmo visando diminuir significativamente o tempo de geração de cada rede, que com o algoritmo seqüencial chega a demorar mais de um mês. Nessa etapa foi utilizada uma adaptação de um dos métodos propostos pela literatura juntamente com a técnica de divisão de domínio. Os resultados obtidos mostraram-se satisfatórios tanto em relação à qualidade numérica quanto à diminuição do tempo de processamento. Além disso, discute-se no trabalho a genericidade da proposta de paralelização a outros problemas baseados em SA.
Abstract This work has two main goals: the first one is to present the state of the art on combinatorial optimization processes, with a special emphasis to the Simulated Annealing (SA) method. The work presents its history, features, generic algorithm and proposed parallelization present in the literature. Moreover, the algorithm to generate random networks continued is presented. This algorithm was designed by researchers of the UFRGS Physics Institute and it uses the SA method. The second goal of this work is to propose a parallelization for this algorithm in order to decrease significantly the generation time of each network, that with the sequential algorithm reaches more than months. To do that was used an adaptation of one of the methods proposed by literature together with the domain partitioning technical. The results were satisfactory in terms of the numerical quality and in the decrease of the processing time. In addition, this work discusses the genericity of the proposed parallelization to other problems based on SA.
Tipo Dissertação
URI http://hdl.handle.net/10183/14707
Arquivos Descrição Formato
000665916.pdf (2.360Mb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.