Made available in DSpace on 2014-12-17T14:52:47Z (GMT). No. of bitstreams: 1 ThalesLS.pdf: 825402 bytes, checksum: 8e0d2b64fc7287a7921fa605343a8bb6 (MD5) Previous issue date: 2008-12-23 / Particle Swarm Optimization is a metaheuristic that arose in order to simulate the behavior of a number of birds in flight, with its random movement locally, but globally determined. This technique has been widely used to address non-liner continuous problems and yet little explored in discrete problems. This paper presents the operation of this metaheuristic, and propose strategies for implementation of optimization discret problems as form of execution parallel as sequential. The computational experiments were performed to instances of the TSP, selected in the library TSPLIB contenct to 3038 nodes, showing the improvement of performance of parallel methods for their sequential versions, in executation time and results / Otimiza??o por Enxame de Part?culas ou Particle Swarm Optimization (PSO) ? uma metaheur?stica que surgiu na inten??o de simular o comportamento de um conjunto de p?ssaros em v?o, com seu movimento localmente aleat?rio, mas globalmente determinado. Esta t?cnica tem sido muito utilizada na resolu??o de problemas cont?nuos n?o-lineares e ainda pouco explorada em problemas discretos. Este trabalho apresenta o funcionamento desta metaheur?stica, al?m de propor estrat?gias para sua aplica??o em problemas de otimiza??o discreta tanto na sua forma de execu??o seq?encial quanto paralela. Os experimentos computacionais foram realizados para inst?ncias do problema do caixeiro viajante, selecionados na biblioteca TSPLIB contendo at? 1002 n?s, mostrando a melhoria de desempenho dos m?todos paralelos em rela??o as suas vers?es seq?enciais, em tempo de execu??o e resultados

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

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-11-01T21:47:47Z No. of bitstreams: 1 AllysonFernandesDaCostaSilva_DISSERT.pdf: 1659813 bytes, checksum: 0de7287ef5c2c4ae621833638c04aa5f (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-11-08T00:21:06Z (GMT) No. of bitstreams: 1 AllysonFernandesDaCostaSilva_DISSERT.pdf: 1659813 bytes, checksum: 0de7287ef5c2c4ae621833638c04aa5f (MD5) / Made available in DSpace on 2017-11-08T00:21:06Z (GMT). No. of bitstreams: 1 AllysonFernandesDaCostaSilva_DISSERT.pdf: 1659813 bytes, checksum: 0de7287ef5c2c4ae621833638c04aa5f (MD5) Previous issue date: 2017-06-30 / Problemas de localiza??o buscam determinar as melhores posi??es onde devem ser instaladas facilidades de modo a atender demandas existentes. Pela vasta aplicabilidade da ?rea, diversas caracter?sticas j? foram importadas aos modelos para melhor representar situa??es pr?ticas. Uma delas generaliza os modelos cl?ssicos para situa??es em que decis?es de localiza??o devem ser tomadas periodicamente. Outra, permite que modelos tratem do dimensionamento das capacidades como uma vari?vel do problema. O Problema Din?mico de Localiza??o de Facilidades com Capacidades Modulares unifica estas e outras caracter?sticas presentes em problemas de localiza??o num ?nico e generalizado modelo. Este problema foi recentemente formulado na literatura, onde uma abordagem exata foi introduzida e aplicada a inst?ncias derivadas de um estudo de caso no contexto da explora??o de recursos florestais. Neste trabalho ser? apresentado um m?todo alternativo para resolver o mesmo problema. O m?todo escolhido utiliza a estrutura da metaheur?stica Algoritmo Gen?tico e a hibridiza com uma rotina de Descida em Vizinhan?a Vari?vel com tr?s vizinhan?as de busca adaptadas de vizinhan?as aplicadas a outros problemas de localiza??o. Experimentos atestaram a efetividade da metaheur?stica h?brida desenvolvida em compara??o ? aplica??o dos m?todos puros. Na compara??o com o m?todo exato, a heur?stica se mostrou competente ao chegar a solu??es at? 0,02% de dist?ncia do ?timo na maioria das inst?ncias testadas. / Location problems aim to determine the best positions where facilities should be installed in order to meet existing demands. Due to its wide applicability, several characteristics have already been appended to the models to better represent real situations. One of them generalizes classical models to the case that location decisions should be taken periodically. Another allows models to deal with capacity sizing as a problem variable. The Dynamic Facility Location Problem with Modular Capacities unifies these and other characteristics present in location problems in a single and generalized model. This problem was recently formulated in literature where an exact approach was introduced and applied to instances of a case study in the context of the forestry sector. We present an alternative method to solve the same problem. The method chosen uses a Genetic Algorithm metaheuristic framework and hybridizes it with a Variable Neighborhood Descent routine with three neighborhoods adapted from others applied to location problems. Experiments attested the effectiveness of the hybrid metaheuristic developed in comparison to the use of those methods purely. Compared to the exact approach, the heuristic proved to be competent by finding solutions up to a gap of 0,02% to the global optimum in the majority of the instances tested.

Made available in DSpace on 2014-12-17T15:48:00Z (GMT). No. of bitstreams: 1 GustavoAS_DISSERT.pdf: 3060399 bytes, checksum: 659289bc757f2443a1b6902094747b13 (MD5) Previous issue date: 2012-02-27 / This work approaches the Scheduling Workover Rigs Problem (SWRP) to maintain the wells of an oil field, although difficult to resolve, is extremely important economical, technical and environmental. A mathematical formulation of this problem is presented, where an algorithmic approach was developed. The problem can be considered to find the best scheduling service to the wells by the workover rigs, taking into account the minimization of the composition related to the costs of the workover rigs and the total loss of oil suffered by the wells. This problem is similar to the Vehicle Routing Problem (VRP), which is classified as belonging to the NP-hard class. The goal of this research is to develop an algorithmic approach to solve the SWRP, using the fundamentals of metaheuristics like Memetic Algorithm and GRASP. Instances are generated for the tests to analyze the computational performance of the approaches mentioned above, using data that are close to reality. Thereafter, is performed a comparison of performance and quality of the results obtained by each one of techniques used / O trabalho em quest?o aborda o Problema da Programa??o das Sondas de Produ??o (PPSP) para atender os po?os de um campo de petr?leo. Embora de dif?cil resolu??o, ele ? de extrema import?ncia econ?mica, t?cnica e ambiental. Uma formula??o matem?tica deste problema ? apresentada, assim como desenvolvida uma abordagem algor?tmica. O problema abordado pode ser considerado como o de encontrar o melhor escalonamento de atendimento aos po?os pelas sondas, levando em considera??o a minimiza??o da composi??o dos custos relativos ?s sondas e da perda total da produ??o de petr?leo associada aos po?os que est?o aguardando por atendimento. Tal problema assemelha-se ao Problema de Roteamento de Ve?culos (PRV), que ? classificado como pertencente ? classe de problemas NP-Dif?cil. O objetivo da presente pesquisa ? desenvolver uma abordagem algor?tmica para resolver o PPSP, utilizando os fundamentos de metaheur?sticas como o Algoritmo Mem?tico e o GRASP. Inst?ncias s?o geradas para a realiza??o dos testes computacionais para an?lise do desempenho das abordagens acima citadas, utilizando dados que se aproximam da realidade. A partir da?, ? realizada uma compara??o de desempenho e qualidade dos resultados obtidos por cada uma das t?cnicas utilizadas

Made available in DSpace on 2014-12-17T15:48:03Z (GMT). No. of bitstreams: 1 AntonioAFN_DISSERT.pdf: 3187796 bytes, checksum: c8d44014d0b75e991f4f3b3473a8dcd5 (MD5) Previous issue date: 2012-08-24 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / Committees of classifiers may be used to improve the accuracy of classification systems, in other words, different classifiers used to solve the same problem can be combined for creating a system of greater accuracy, called committees of classifiers. To that this to succeed is necessary that the classifiers make mistakes on different objects of the problem so that the errors of a classifier are ignored by the others correct classifiers when applying the method of combination of the committee. The characteristic of classifiers of err on different objects is called diversity. However, most measures of diversity could not describe this importance. Recently, were proposed two measures of the diversity (good and bad diversity) with the aim of helping to generate more accurate committees. This paper performs an experimental analysis of these measures applied directly on the building of the committees of classifiers. The method of construction adopted is modeled as a search problem by the set of characteristics of the databases of the problem and the best set of committee members in order to find the committee of classifiers to produce the most accurate classification. This problem is solved by metaheuristic optimization techniques, in their mono and multi-objective versions. Analyzes are performed to verify if use or add the measures of good diversity and bad diversity in the optimization objectives creates more accurate committees. Thus, the contribution of this study is to determine whether the measures of good diversity and bad diversity can be used in mono-objective and multi-objective optimization techniques as optimization objectives for building committees of classifiers more accurate than those built by the same process, but using only the accuracy classification as objective of optimization / Comit?s de classificadores podem ser empregados para melhorar a acur?cia de sistemas de classifica??o, ou seja, diferentes classificadores aplicados ? solu??o de um mesmo problema podem ser combinados gerando um sistema de maior acur?cia, denominado de comit?s de classificadores. Para que se obtenha sucesso ? necess?rio que os classificadores apresentem erros em diferentes objetos do problema para que assim os erros de um classificador sejam suprimidos pelo acerto dos demais na aplica??o do m?todo de combina??o do comit?. A caracter?stica dos classificadores de errarem em objetos diferentes ? denominada de diversidade. No entanto, as maiorias das medidas de diversidade n?o conseguiam descrever essa import?ncia. Recentemente, foram propostas duas medidas de diversidade (boa e m? diversidade) as medidas de boa e m? diversidade com o objetivo de auxiliar a gera??o de comit?s mais acurados. Este trabalho efetua uma an?lise experimental dessas medidas aplicadas diretamente na constru??o de comit?s de classificadores. O m?todo de constru??o adotado ? modelado como um problema de busca pelo melhor conjunto de caracter?sticas das bases de dados do problema e pelo melhor conjunto de membros do comit? a fim de encontrar o comit? de classificadores que apresente ? maior acur?cia de classifica??o. Esse problema ? resolvido atrav?s de t?cnicas de otimiza??o metaheur?sticas, nas vers?es mono e multiobjetivo. S?o efetuadas an?lises estat?sticas para verificar se usar ou adicionar as medidas de boa e m? diversidade como objetivos de otimiza??o resulte comit?s mais acurados. Assim, a contribui??o desse trabalho ? determinar se as medidas de boa e m? diversidade podem ser utilizadas em t?cnicas de otimiza??o mono e multiobjetivo como objetivos de otimiza??o para constru??o de comit?s de classificadores mais acurados que aqueles constru?dos pelo mesmo processo, por?m utilizando somente a acur?cia de classifica??o como objetivo de otimiza??o