Spelling suggestions: "subject:"simulated annealing heuristic""
1 |
MULTIPLEX: um procedimento baseado em simulted annealing aplicado ao problema Max-Sat ponderadoTeixeira, Giovany Frossard 01 June 2006 (has links)
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.
|
2 |
How do different densities in a network affect the optimal location of service centers?Han, Mengjie, Håkansson, Johan, Rebreyend, Pascal January 2013 (has links)
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.
|
3 |
An?lise de escalabilidade de uma implementa??o paralela do simulated annealing acopladoSilva, Kayo Gon?alves e 25 March 2013 (has links)
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
|
Page generated in 0.1592 seconds