Made available in DSpace on 2016-06-02T19:52:00Z (GMT). No. of bitstreams: 1 DissRH.pdf: 983555 bytes, checksum: 2f6efc30e82bc4d5f60bb2893dd0bb3f (MD5) Previous issue date: 2004-12-16 / This research consists of the development of algorithms to solve the Periodic Vehicle Routing Problem (PVRP), wich has not received a great deal of attention in the O.R. literature. The objective of the PVRP is to elaborate a set of routes to attend to customers demand along a planning horizon. Each customer roquests that the visits occur in a combination predefined of days. Two heuristics were developed for the PVRP. In the first heuristic, three types of initial solution construction are used to attribute the customers to days. After that, visiting day combinations are changed in order to improvr the solution. The search process is controlled by an adaptative tabu heuristic from the literature which determines intensification and diversification actions, applied for each day in the period. The second heuristic incorporates a similar approach for the period as a whole. Computacional results show that this approach leads to good solution. / Esta pesquisa consiste no desenvolvimento de algoritmos para resolver o Problema de Roteamento de Veículos Periódico (PRPV), o qual tem sido pouco abordado na literatura de Pesquisa Operacional. O objetivo do PRVP é elaborar um conjunto de rotas para atender à demanda de cliente ao longo de um horizonte de planejamento. Cada cliente requer que as visitas aconteçam em uma combinação predefinida de dias. Foram desenvolvidas duas heurísticas para o PRPV, chamadas de VERSÃO 1 e VERSÃO 2. Na VERSÃO 1 são utilizados três tipos de construções iniciais para atribuir os clientes aos dias. Em seguida, são realizadas mudanças de combinações de dias de visitas na tentativa de melhorar a solução. O processo de busca por soluções é controlado por heurísitca tabu adaptativa da literatura que determina as ações de intensificação e diversificação, aplicado a cada dia do período. A VERSÃO 2 incorpora uma abordagem similar para o período como um todo. Resultados computacionais indicam que esta abordagem leva a soluções de boa qualidade.

Made available in DSpace on 2015-05-07T15:08:20Z (GMT). No. of bitstreams: 1 parte1.pdf: 2773821 bytes, checksum: fb76fff21676798c65b8f19a1378b235 (MD5) Previous issue date: 2011-10-31 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work presents a strategy for teaching mathematics in a meaningful learning perspective, concerning the content of high school called Combinatorial Analysis, to understand the processes of counting from the understanding of the concepts involved. For the development of research, we used the assumptions of a teaching methodology based on the theory of David Ausubel and strategies of concept maps by Joseph Novak and Bob Gowin, as a mechanism for structuring the knowledge of students in the teaching and learning of the content mentioned. Ausubel tells us that knowledge is acquired and retained if the learner able to associate the relevant ideas in our pre-existing cognitive structure with the new information being offered. In this sense, Novak uses the concept maps for this relationship between existing and acquired knowledge is meaningful to the learner. Our study was an experiment, exposing Combinatorial Analysis content through the use of concept maps constructed and systematized by Bloom's Revised Taxonomy, so that we find meaningful learning in the apprentice. To check this, we apply a test before and after exposure of the content, using concept maps in the experimental class and without the use of concept maps in class Control. The results were evaluated on a quantitative and a qualitative analysis, proving that the use of concept maps in the study of mathematics, specifically in the content worked, favored meaningful learning. / Este trabalho apresenta uma estratégia de ensino de matemática numa perspectiva de aprendizagem significativa, referente ao conteúdo do Ensino Médio intitulado Análise Combinatória, a fim de que possamos entender os processos de contagem a partir da compreensão dos conceitos envolvidos. Para o desenvolvimento da pesquisa, utilizaram-se pressupostos de uma metodologia de ensino baseada na teoria de David Ausubel e nas estratégias dos mapas conceituais de Joseph Novak e Bob Gowin, como mecanismo de estruturação do conhecimento dos alunos no processo de ensino e aprendizagem do conteúdo mencionado. Ausubel nos fala que o conhecimento será adquirido e retido se o aprendiz conseguir associar as ideias relevantes pré existentes em sua estrutura cognitiva com as novas informações que estão sendo oferecidas. Nesta direção, Novak utiliza-se dos mapas conceituais para que essa relação entre o conhecimento existente e o adquirido tenha sentido para o aprendiz. Nosso trabalho foi de caráter experimental, expondo o conteúdo Análise Combinatória através do uso de mapas conceituais construídos e sistematizados pela Taxonomia de Bloom-Modificada, de maneira que verificamos a aprendizagem significativa no aprendiz. Para essa verificação, aplicamos um teste antes e depois da exposição do conteúdo, com uso de mapas conceituais na turma experimental e sem o uso de mapas conceituais na turma controle. Os resultados foram avaliados sobre um aspecto quantitativo e uma análise qualitativa, comprovando que o uso de mapas conceituais no estudo de matemática, especificamente no conteúdo trabalhado, favoreceu a aprendizagem significativa.

Pesquisas recentes mostram que abordagens baseadas em sistemas multiagentes (SMA) e mecanismos de mercado como leilões são eficazes para encontrar soluções factíveis para problemas de planejamento em cadeias de suprimento. Esta dissertação aborda a utilização do paradigma de SMA baseado em Leilões Combinatoriais e o uso de estratégias de participação em leilões na resolução do problema de transporte de derivados de petróleo em uma rede multimodal da PETROBRAS – Petróleo Brasileiro S/A, denominado Problema de Transporte de Derivados de Petróleo Simplificado (PTDPS), que se caracteriza como um problema de planejamento em cadeias de suprimento. Em leilões combinatoriais, a determinação do vencedor é um problema NP-Completo sem algoritmos de aproximação, cujo custo computacional aumenta com o número de ofertas recebidas pelo leiloeiro. Este trabalho tem por objetivo aumentar o escopo de aplicação de leilões combinatoriais em problemas de planejamento pelo uso de uma estratégia heurística de participação em leilões, além de servir como uma ferramenta de apoio à tomada de decisão por especialistas da indústria petrolífera. Os resultados obtidos a partir da aplicação do SMA desenvolvido em uma série de cenários para a estratégia proposta (avaliação da necessidade global) e outras de referência (geral - todos os leilões possíveis - e gulosa – somente um leilão) foram comparados entre si e demonstram que a utilização da estratégia proposta reduz o tempo de processamento em relação à estratégia geral e sem perda da qualidade da solução em comparação com as estratégias geral e gulosa. Outras contribuições deste trabalho são um SMA para realizar o planejamento do transporte de derivados de petróleo tendo como modelo de negociação o mecanismo de leilões combinatoriais e a proposição de um modelo descentralizado onde diversos leilões combinatoriais podem ser executados simultaneamente. / Recent researches have shown that approaches based on multi-agent systems (MAS) and market mechanisms like auctions are efficient on the resolution of planning problems in supply chains. This work uses the combinatorial auction-based MAS paradigm and participation strategies in auctions for solving the problem of transporting oil derivatives of PETROBRAS - Petroleo Brasileiro S/A, called Simplified Problem of Transporting Oil Derivatives (SPTOD), which is characterized as a planning problem in supply chains. In combinatorial auctions, the winner determination is a NP-Complete problem without approximation algorithms, whose computational cost increases with the number of bids received by the auctioneer. In this context, this work aims at enlarging the scope of application of combinatorial-auction mechanisms in planning problems by using a heuristic strategy for participation in auctions, besides serving as a support tool for decision-making process by specialists of industrial oil. The results were drawn from several scenarios where the MAS was used with the proposed strategy (global evaluation of needs) and with other strategies for comparison (general – all possible auctions – and greedy – only one auction). The results show that the use of the proposed strategy reduces the processing time when compared to the general strategy and that the quality of the solution is preserved in comparison with the general and greedy strategies. Other contributions of this work are the development of a MAS to realize the planning of transporting oil derivatives between producing and consuming basis having as negotiation model the combinatorial auction-based mechanism and a proposition of a decentralized model where several combinatorial auctions can be run simultaneously.

A otimização de uma rede de transporte de derivados de petróleo é um problema complexo e abordado na literatura atual. A modelagem matemática deste problema proposta neste trabalho cria um problema de otimização combinatorial. Métodos de resolução deste problema através da programação linear inteira mista e de algoritmos heurísticos de evolução diferencial (Evolução Diferencial Binária e Evolução Diferencial Discretizada) são propostos utilizando variáveis binárias. Os resultados encontrados com a programação linear apresentam valores ótimos para os benchmarks com pequenos espaços de busca e valores sub-ótimos para grandes. Resultados utilizando a evolução diferencial também são apresentados como uma alternativa de baixo esforço computacional. A aplicação destes métodos proporciona alternativas para o transporte de diferentes produtos em um horizonte de tempo definido e compara os métodos heurísticos com codificações binárias e contínuas. Tais resultados incentivam a utilização de algoritmos heurísticos com codificação contínua e apontam os métodos de discretização como alternativas eficazes para a resolução de problemas discretos. / The optimization of an pipeline network is a complex problem and addressed in the current literature. The mathematical modeling of this problem proposed in this paper creates a problem of combinatorial optimization. Methods for solving this problem using linear mixed integer programming and heuristic algorithms of differential evolution (Binary Differential Evolution and Discretized Differential Evolution) are proposed using binary variables. The results obtained with the linear programming have optimal values for the benchmarks with small search spaces and sub-optimal for large values. Results using the differential evolution are also presented as an alternative low computational effort. The application of these methods provides alternatives for transporting different products in a defined time horizon and compare heuristic methods with continuous and binary encodings. Such results encourage the use of heuristic algorithms with continuous coding and the point discretization methods as effective for solving problems discrete alternatives.

CAPES / Este trabalho propõe uma modificação da meta-heurística Busca Harmônica (HS) a partir de uma nova abordagem baseada em população, empregando, também, algumas estratégias inspiradas em outras meta-heurísticas. Este novo modelo foi implementado utilizando a arquitetura de programação paralela CUDA em uma GPU. O uso de placas de processamento gráficas (GPU) para processamento de propósito geral está crescendo, e estas têm sido utilizadas por muitos pesquisadores para processamento científico. Seu uso se mostra interessante para meta-heurísticas populacionais, podendo realizar muitas operações simultaneamente. A HS é uma meta-heurística inspirada no objetivo de um músico em buscar uma harmonia perfeita. modelo proposto incluiu-se uma população de harmonias temporárias que são geradas a cada nova iteração, permitindo a realização simultânea de diversas avaliações de função. Assim aumenta-se o grau de paralelismo da HS, possibilitando maiores ganhos de velocidade com o uso de arquiteturas paralelas. O novo modelo proposto executado em GPU foi denominado Mega Harmony Search (MHS). Na implementação em GPU cada passo do algoritmo é tratado individualmente em forma de kernels com configurações particulares para cada um. Para demonstrar a eficácia do modelo proposto foram selecionados alguns problemas de benchmark, como a otimização de estruturas de proteínas, a otimização de treliças e problemas matemáticos. Através de experimentos fatoriais foi identificado um conjunto de parâmetros padrão, o qual foi utilizado nos outros experimentos. As análises realizadas sobre resultados experimentais mostram que o MHS apresentou solução de qualidade equivalente à HS e ganhos de velocidade, com a sua execução em GPU, superiores a 60x quando comparado a implementação em CPU. Em trabalhos futuros poderão ser estudadas novas modificações ao algoritmo, como a implementação de nichos e estudos de estratégias de interação entre eles. / This work propose a new approach for the metaheuristic Harmonic Search (HS), by using a population of solutiona and other strategies inspired in another metaheuristics. This new model was implemented using a parallel architecture of a graphical processing unity (GPU). The use of GPU for general-purpose processing is growing, specially for scientific processing. Its use is particularly interesting for populational metaheuristics, where multiple operations are executed simultaneously. The HS is a metaheuristic inspired by the way jazz musicians search for a perfect harmony. In the proposed model a population of temporary harmonies was included. Such population was generated at each iteration, enabling simultaneous evaluation of the objective function being optimized, and thus, increasing the level of parallelism of HS. The new approach implemented in GPU was named Mega Harmony Search (MHS), and each step of the algorithm is handled in the form of kernels with particular configurations for each one. To show the efficiency of MHS some benchmark problems were selected for testing, including mathematical optimization problems, protein structure prediction, and truss structure optimization. Factorial experiments were done so as to find the best set of parameters for the MHS. The analyzes carried out on the experimental results show that the solutions provided by MHS have comparable quality to those of the simple Harmony Search. However, by using GPU, MHS achieved a speedup of 60x, compared with the implementation in regular CPU. Future work will focus other improvements in the algorithm, such as the use of niches and species, as well a study of the interactions between them.

CNPq / A Transgenética Computacional é uma metáfora para o desenvolvimento de algoritmos evolucionários com base na teoria de evolução endossimbiótica e em outras interações do fluxo intracelular. Diversos algoritmos foram desenvolvidos com base nesta metáfora para problemas de Otimização Combinatória, em sua maioria com um único objetivo, obtendo bons resultados. Uma vez que a consideração de mais de um objetivo leva, em geral, a representações mais realistas de problemas práticos complexos, neste trabalho investiga-se o desenvolvimento de Algoritmos Transgenéticos para problemas multiobjetivo. Tais algoritmos são examinados em versões que utilizam elementos de outros algoritmos evolucionários multiobjetivo sendo eles o NSGA-II (Non-Dominated Sorting Genetic Algorithm-II) e o MOEA/D (Multi-objective Evolutionary Algorithm based on Decomposition). Diante disso, este trabalho propõe duas novas metodologias utilizando a Transgenética Computacional acoplada ao NSGA-II e ao MOEA/D, denominadas NSTA (Non-Dominated Sorting Transgenetic Algorithm) e MOTA/D (Multi-objective Transgenetic Algorithm based on Decomposition), respectivamente. Para avaliar o desempenho das técnicas propostas, os algoritmos desenvolvidos foram aplicados a dois problemas de Otimização Combinatória, NP-difíceis,em versões com mais de um objetivo. O primeiro problema é o Caixeiro Comprador Biobjetivo e o segundo o Quadrático de Alocação multiobjetivo. Foram realizados experimentos com casos de teste disponíveis em bancos utilizados comumente por outros trabalhos da literatura. Os resultados dos algoritmos propostos foram comparados com os resultados obtidos com os algoritmos evolucionários multiobjetivo que os inspiraram. A análise dos dados obtidos com os experimentos computacionais mostram que a versão MOTA/D é a mais eficiente dentre os algoritmos do experimento com relação a qualidade da aproximação da fronteira de Pareto. / The Computational Transgenetic is a metaphor for the development of evolutionary algorithms based on the theory of evolution endosymbiotic and other intracellular interactions flow. Several algorithms have been developed based on this metaphor for combinatorial optimization problems, mostly with a single objective, obtaining good results. Once the account of more than one objective provides, in general, more realistic representations of complex practical problems, this work investigates the development of Transgenetic Algorithms for multiobjective problems. Such algorithms are examined in versions that use elements of other multiobjective evolutionary algorithms such as the NSGA-II (Non-Dominated Sorting Genetic Algorithm-II) and the MOEA/D (Multi-objective Evolutionary Algorithm based on Decomposition). Therefore, this work proposes two new methods using Computational Transgenetic attached to NSGA-II and MOEA/D, named NSTA (Non-Dominated Sorting Transgenetic Algorithm) and MOTA/D (Multi-objective Transgenetic Algorithm based on Decomposition), respectively. To evaluate the proposed techniques performance, the experiments consider two NP-hard combinatorial optimization problems, in versions with more than one objective. The first problem is the Traveling Purchaser Problem and the second the Quadratic Assignment Problem. Experiments were performed with test cases available in benchmarks commonly used by other studies in the literature. The proposed algorithms' results were compared with those obtained by the multiobjetive evolutionary algorithms that inspired them. The analysis of data obtained by the computational experiment shows that the version MOTA/D is among the most efficient algorithms of the experiment with respect to the quality of the Pareto front approximation.

CAPES / O presente trabalho tem dois objetivos: o primeiro está relacionado ao ensino da análise combinatória nas séries do ensino fundamental 2 e ensino médio. O segundo objetivo e buscar aprofundar meus conhecimentos relacionados aos conceitos combinatoriais. Com relação ao primeiro objetivo, o ensino da análise combinatória, na minha trajetória como docente, tem sido uma das tarefas mais árduas que o professor de matemática da educação básica enfrenta. Diante disso, surgem algumas perguntas. Por que um assunto totalmente aplicável ao cotidiano tem gerado tanta dificuldade de compreensão? Um dos objetivos desse trabalho e buscar respostas para essa pergunta e propor sugestões que possam melhorar o entendimento desse conceito. Como segundo objetivo proposto, busquei compreender conceitos que até então, por mim, não dominados, aprofundando meu conhecimento combinatorial. Para tanto, esse trabalho possui uma parte dedicada ao estudo de conceitos combinatorias mais complexos, não o abordados junto aos alunos de ensino médio mas que permitem compreender situações combinatoriais mais complexas. / The present work has two major goals. The first one is related to the teaching of combinatorics in elementary school and high school. The second one is to seek further knowledge related to combinatorial concepts. Regarding the first goal, the teaching of combinatorics, in my trajectory as a teacher, has been one of the most arduous tasks that the math teacher of basic education faces. Therefore, some questions arise. Why a subject fully applicable to everyday, has generated so much trouble understanding? One of the goals of this work is to seek answers to this question and propose suggestions that can improve the understanding of this concept. As a second proposed goal, I sought to understand concepts that hitherto were not dominated, deepening my combinatorial knowledge. Therefore, this work has section devoted to the study of more complex combinatory concepts, not addressed to the students of high school but they allow us to understand more complex combinatorial situations.

A otimização de uma rede de transporte de derivados de petróleo é um problema complexo e abordado na literatura atual. A modelagem matemática deste problema proposta neste trabalho cria um problema de otimização combinatorial. Métodos de resolução deste problema através da programação linear inteira mista e de algoritmos heurísticos de evolução diferencial (Evolução Diferencial Binária e Evolução Diferencial Discretizada) são propostos utilizando variáveis binárias. Os resultados encontrados com a programação linear apresentam valores ótimos para os benchmarks com pequenos espaços de busca e valores sub-ótimos para grandes. Resultados utilizando a evolução diferencial também são apresentados como uma alternativa de baixo esforço computacional. A aplicação destes métodos proporciona alternativas para o transporte de diferentes produtos em um horizonte de tempo definido e compara os métodos heurísticos com codificações binárias e contínuas. Tais resultados incentivam a utilização de algoritmos heurísticos com codificação contínua e apontam os métodos de discretização como alternativas eficazes para a resolução de problemas discretos. / The optimization of an pipeline network is a complex problem and addressed in the current literature. The mathematical modeling of this problem proposed in this paper creates a problem of combinatorial optimization. Methods for solving this problem using linear mixed integer programming and heuristic algorithms of differential evolution (Binary Differential Evolution and Discretized Differential Evolution) are proposed using binary variables. The results obtained with the linear programming have optimal values for the benchmarks with small search spaces and sub-optimal for large values. Results using the differential evolution are also presented as an alternative low computational effort. The application of these methods provides alternatives for transporting different products in a defined time horizon and compare heuristic methods with continuous and binary encodings. Such results encourage the use of heuristic algorithms with continuous coding and the point discretization methods as effective for solving problems discrete alternatives.

CAPES / Este trabalho propõe uma modificação da meta-heurística Busca Harmônica (HS) a partir de uma nova abordagem baseada em população, empregando, também, algumas estratégias inspiradas em outras meta-heurísticas. Este novo modelo foi implementado utilizando a arquitetura de programação paralela CUDA em uma GPU. O uso de placas de processamento gráficas (GPU) para processamento de propósito geral está crescendo, e estas têm sido utilizadas por muitos pesquisadores para processamento científico. Seu uso se mostra interessante para meta-heurísticas populacionais, podendo realizar muitas operações simultaneamente. A HS é uma meta-heurística inspirada no objetivo de um músico em buscar uma harmonia perfeita. modelo proposto incluiu-se uma população de harmonias temporárias que são geradas a cada nova iteração, permitindo a realização simultânea de diversas avaliações de função. Assim aumenta-se o grau de paralelismo da HS, possibilitando maiores ganhos de velocidade com o uso de arquiteturas paralelas. O novo modelo proposto executado em GPU foi denominado Mega Harmony Search (MHS). Na implementação em GPU cada passo do algoritmo é tratado individualmente em forma de kernels com configurações particulares para cada um. Para demonstrar a eficácia do modelo proposto foram selecionados alguns problemas de benchmark, como a otimização de estruturas de proteínas, a otimização de treliças e problemas matemáticos. Através de experimentos fatoriais foi identificado um conjunto de parâmetros padrão, o qual foi utilizado nos outros experimentos. As análises realizadas sobre resultados experimentais mostram que o MHS apresentou solução de qualidade equivalente à HS e ganhos de velocidade, com a sua execução em GPU, superiores a 60x quando comparado a implementação em CPU. Em trabalhos futuros poderão ser estudadas novas modificações ao algoritmo, como a implementação de nichos e estudos de estratégias de interação entre eles. / This work propose a new approach for the metaheuristic Harmonic Search (HS), by using a population of solutiona and other strategies inspired in another metaheuristics. This new model was implemented using a parallel architecture of a graphical processing unity (GPU). The use of GPU for general-purpose processing is growing, specially for scientific processing. Its use is particularly interesting for populational metaheuristics, where multiple operations are executed simultaneously. The HS is a metaheuristic inspired by the way jazz musicians search for a perfect harmony. In the proposed model a population of temporary harmonies was included. Such population was generated at each iteration, enabling simultaneous evaluation of the objective function being optimized, and thus, increasing the level of parallelism of HS. The new approach implemented in GPU was named Mega Harmony Search (MHS), and each step of the algorithm is handled in the form of kernels with particular configurations for each one. To show the efficiency of MHS some benchmark problems were selected for testing, including mathematical optimization problems, protein structure prediction, and truss structure optimization. Factorial experiments were done so as to find the best set of parameters for the MHS. The analyzes carried out on the experimental results show that the solutions provided by MHS have comparable quality to those of the simple Harmony Search. However, by using GPU, MHS achieved a speedup of 60x, compared with the implementation in regular CPU. Future work will focus other improvements in the algorithm, such as the use of niches and species, as well a study of the interactions between them.

Les Acides Peptido-nucléiques (PNA) sont des analogues synthétiques d’oligonucleotides naturels, ils sont constitués d’une répétition d’unités N-(2-aminoethyl)-glycine reliées par une liaison peptidique. Leur stabilité chimique et biologique en font une alternative intéressante pour les assemblages supramoléculaires ayant une application biologique tels que l’encodage de chimiothèques combinatoires de petites molécules et des réactions engendrées par hybridation. Ce travail de thèse avait pour objectif la synthèse d’acides peptido-nucléiques modifiés dans le but d’améliorer leur hybridation, leurs propriétés physico-chimiques ainsi que la synthèse des chimiothèques combinatoires. / Peptide nucleic acids (PNA) are structural analogs of natural nucleic acids composed of repeating units of N-(2-aminoethyl)-glycine residues linked by peptide bonds. Their chemical and biological stability makes them very suitable for supramolecular assemblies with biological applications such as encoding combinatorial libraries of small molecules and for performing templated reactions. This phD project aimed at the synthesis of modified peptide nucleic acids to enhance their physicochemical and hybridization properties as well as for construction of combinatorial libraries.