Made available in DSpace on 2016-12-23T14:33:34Z (GMT). No. of bitstreams: 1 dissertacao.pdf: 412800 bytes, checksum: 479ec97937646fdcffeadd81d19f1b7a (MD5) Previous issue date: 2006-06-01 / Computar a solução ótima para uma unidade de problema MAX-SAT Ponderado (weighted maximum satisfiability) é difícil mesmo se cada cláusula contiver apenas dois literais. Neste trabalho, será descrita a implementação de uma nova heurística aplicada a instâncias de problema do tipo MAX-SAT Ponderado, mas perfeitamente extensível a outros problemas. Para comparação, serão geradas soluções para uma quantidade significativa de problemas e seus resultados serão comparados com os de outras heurísticas já desenvolvidas para esse tipo de problema, dentre elas as heurísticas consideradas "estado da arte", ou seja, heurísticas que têm obtido os melhores resultados no universo das heurísticas existentes.

The p-median problem is often used to locate p service centers by minimizing their distances to a geographically distributed demand (n). The optimal locations are sensitive to geographical context such as road network and demand points especially when they are asymmetrically distributed in the plane. Most studies focus on evaluating performances of the p-median model when p and n vary. To our knowledge this is not a very well-studied problem when the road network is alternated especially when it is applied in a real world context. The aim in this study is to analyze how the optimal location solutions vary, using the p-median model, when the density in the road network is alternated. The investigation is conducted by the means of a case study in a region in Sweden with an asymmetrically distributed population (15,000 weighted demand points), Dalecarlia. To locate 5 to 50 service centers we use the national transport administrations official road network (NVDB). The road network consists of 1.5 million nodes. To find the optimal location we start with 500 candidate nodes in the network and increase the number of candidate nodes in steps up to 67,000. To find the optimal solution we use a simulated annealing algorithm with adaptive tuning of the temperature. The results show that there is a limited improvement in the optimal solutions when nodes in the road network increase and p is low. When p is high the improvements are larger. The results also show that choice of the best network depends on p. The larger p the larger density of the network is needed.

Made available in DSpace on 2014-12-17T14:56:13Z (GMT). No. of bitstreams: 1 KayoGS_DISSERT.pdf: 4975392 bytes, checksum: 5d113169a6356e5e7704aec116237caf (MD5) Previous issue date: 2013-03-25 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / This paper analyzes the performance of a parallel implementation of Coupled Simulated Annealing (CSA) for the unconstrained optimization of continuous variables problems. Parallel processing is an efficient form of information processing with emphasis on exploration of simultaneous events in the execution of software. It arises primarily due to high computational performance demands, and the difficulty in increasing the speed of a single processing core. Despite multicore processors being easily found nowadays, several algorithms are not yet suitable for running on parallel architectures. The algorithm is characterized by a group of Simulated Annealing (SA) optimizers working together on refining the solution. Each SA optimizer runs on a single thread executed by different processors. In the analysis of parallel performance and scalability, these metrics were investigated: the execution time; the speedup of the algorithm with respect to increasing the number of processors; and the efficient use of processing elements with respect to the increasing size of the treated problem. Furthermore, the quality of the final solution was verified. For the study, this paper proposes a parallel version of CSA and its equivalent serial version. Both algorithms were analysed on 14 benchmark functions. For each of these functions, the CSA is evaluated using 2-24 optimizers. The results obtained are shown and discussed observing the analysis of the metrics. The conclusions of the paper characterize the CSA as a good parallel algorithm, both in the quality of the solutions and the parallel scalability and parallel efficiency / O presente trabalho analisa o desempenho paralelo de uma implementa??o do Simulated Annealing Acoplado (CSA, do ingl?s Coupled Simulated Annealing) para otimiza??o de vari?veis cont?nuas sem restri??es. O processamento paralelo ? uma forma eficiente de processamento de informa??o com ?nfase na explora??o de eventos simult?neos na execu??o de um software. Ele surge principalmente devido ?s elevadas exig?ncias de desempenho computacional e ? dificuldade em aumentar a velocidade de um ?nico n?cleo de processamento. Apesar das CPUs multiprocessadas, ou processadores multicore, serem facilmente encontrados atualmente, diversos algoritmos ainda n?o s?o adequados para executar em arquiteturas paralelas. O algoritmo do CSA ? caracterizado por um grupo de otimizadores Simulated Annealing (SA) trabalhando em conjunto no refinamento da solu??o. Cada otimizador SA ? executado em uma ?nica thread, e essas executadas por diferentes processadores. Na an?lise de desempenho e escalabilidade paralela, as m?tricas investigadas foram: o tempo de execu??o; o speedup do algoritmo com respeito ao aumento do n?mero de processadores; e a efici?ncia na utiliza??o de elementos de processamento com rela??o ao aumento da inst?ncia do problema tratado. Al?m disso, foi verificada a qualidade da solu??o final. Para o estudo, esse trabalho analisa uma vers?o paralela do CSA e sua vers?o serial equivalente. Ambos algoritmos foram analisados sobre 14 fun??es de refer?ncia. Para cada uma dessas fun??es, o CSA ? avaliado utilizando de 2 a 24 otimizadores. Os resultados obtidos s?o exibidos e comentados observando-se as m?tricas de an?lise. As conclus?es do trabalho caracterizam o CSA como um bom algoritmo paralelo, seja na qualidade das solu??es como na escalabilidade e efici?ncia paralela