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

Abstract

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.

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.