No description available.

Thesis (Ed.M.)--Boston University / The purpose of this study is to build a vocabulary for supplementary reading in a second grade which is using the Ginn and Gates Readers as basic textbooks. This vocabulary will be built from fifteen story books not used as school texts.

Made available in DSpace on 2014-12-17T14:52:43Z (GMT). No. of bitstreams: 1 AnaCGS.pdf: 4192359 bytes, checksum: 28eb36354363672f88a28074f9df8b42 (MD5) Previous issue date: 2008-12-23 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / Telecommunications play a key role in contemporary society. However, as new technologies are put into the market, it also grows the demanding for new products and services that depend on the offered infrastructure, making the problems of planning telecommunications networks, despite the advances in technology, increasingly larger and complex. However, many of these problems can be formulated as models of combinatorial optimization, and the use of heuristic algorithms can help solving these issues in the planning phase. In this project it was developed two pure metaheuristic implementations Genetic algorithm (GA) and Memetic Algorithm (MA) plus a third hybrid implementation Memetic Algorithm with Vocabulary Building (MA+VB) for a problem in telecommunications that is known in the literature as Problem SONET Ring Assignment Problem or SRAP. The SRAP arises during the planning stage of the physical network and it consists in the selection of connections between a number of locations (customers) in order to meet a series of restrictions on the lowest possible cost. This problem is NP-hard, so efficient exact algorithms (in polynomial complexity ) are not known and may, indeed, even exist / As telecomunica??es desempenham um papel fundamental na sociedade contempor?nea. Mas ? medida que novas tecnologias s?o introduzidas ao mercado, cresce tamb?m a demanda por novos produtos e servi?os que dependem da infra-estrutura oferecida, tornando os problemas de planejamento de redes de telecomunica??es, apesar da evolu??o tecnol?gica, cada vez maiores e complexos. No entanto, muitos desses problemas podem ser formulados como modelos de otimiza??o combinat?ria, e o uso de algoritmos heur?sticos podem ajudar a solucionar essas quest?es da fase de planejamento. Neste trabalho, foram desenvolvidas duas implementa??es metaheur?sticas puras Algoritmo Gen?tico (AG) e Algoritmo Mem?tico (AM) al?m de uma terceira implementa??o h?brida Algoritmo Mem?tico com Vocabulary Building (AM+VB) para um problema de telecomunica??es que ? conhecido na literatura por Problema de Atribui??o de Localidades a An?is SONET ou SRAP (do ingl?s, SONET Ring Assignment Problem). O SRAP surge durante a etapa do planejamento f?sico da rede e consiste na determina??o das conex?es entre um conjunto de localidades (clientes), de modo a satisfazer uma s?rie de restri??es ao menor custo poss?vel. Esse problema ? NP-dif?cil e portanto algoritmos exatos eficientes (de complexidade polinomial) n?o s?o conhecidos, podendo, inclusive, nem existir

Made available in DSpace on 2014-12-17T14:53:00Z (GMT). No. of bitstreams: 1 VanessaDSF_DISSERT.pdf: 862759 bytes, checksum: d1e5a8faf841592d593e48b4f4218e61 (MD5) Previous issue date: 2011-07-13 / Conselho Nacional de Desenvolvimento Cient?fico e Tecnol?gico / This paper aims to propose a hybrid meta-heuristics for the Heterogeneous Fleet Vehicle Routing Problem (HVRP), which is a combinatorial optimization problem NP-hard, and is characterized by the use of a limited fleet consists of different vehicles with different capacities. The hybrid method developed makes use of a memetic algorithm associated with the component optimizer Vocabulary Building. The resulting hybrid meta-heuristic was implemented in the programming language C + + and computational experiments generated good results in relation to meta-heuristic applied in isolation, proving the efficiency of the proposed method. / O presente trabalho visa propor uma meta-heur?stica h?brida para o Problema de Roteamento de Ve?culos com Frotas Heterog?neas (PRVFH), que ? um problema de otimiza??o combinat?ria NP-dif?cil, e que se caracteriza pelo uso de uma frota limitada composta por ve?culos distintos com capacidades distintas. O m?todo h?brido desenvolvido utiliza-se de um algoritmo mem?tico associado ao componente otimizador Vocabulary Building. A meta-heur?stica h?brida resultante foi implementada na linguagem de programa??o C++ e os experimentos computacionais geraram bons resultados em rela??o ? meta-heur?stica aplicada isoladamente, comprovando a efici?ncia do m?todo proposto.

Made available in DSpace on 2014-12-17T14:53:02Z (GMT). No. of bitstreams: 1 JoaoPLN_DISSERT.pdf: 2086259 bytes, checksum: 2a57554e118e00d9a44cdf572e29af7a (MD5) Previous issue date: 2010-12-23 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / This paper presents metaheuristic strategies based on the framework of evolutionary algorithms (Genetic and Memetic) with the addition of Technical Vocabulary Building for solving the Problem of Optimizing the Use of Multiple Mobile Units Recovery of Oil (MRO units). Because it is an NP-hard problem, a mathematical model is formulated for the problem, allowing the construction of test instances that are used to validate the evolutionary metaheuristics developed / O presente trabalho apresenta estrat?gias metaheur?sticas baseadas no framework dos Algoritmos Evolutivos (Gen?ticos e Mem?ticos) com a adi??o da t?cnica Vocabulary Building para a resolu??o do Problema de Otimiza??o do Emprego de Unidades M?veis de Pistoneio (UMPs). Por se tratar de um problema NP-?rduo, uma modelagem matem?tica ? formulada para o problema, permitindo a constru??o de inst?ncias testes que s?o utilizadas para validar as metaheur?sticas evolutivas desenvolvidas

Made available in DSpace on 2014-12-17T15:26:37Z (GMT). No. of bitstreams: 1 JoaoSSN.pdf: 5224762 bytes, checksum: 4021177e0509af10223ad40751ece2f0 (MD5) Previous issue date: 2009-07-10 / The present essay shows strategies of improvement in a well succeded evolutionary metaheuristic to solve the Asymmetric Traveling Salesman Problem. Such steps consist in a Memetic Algorithm projected mainly to this problem. Basically this improvement applied optimizing techniques known as Path-Relinking and Vocabulary Building. Furthermore, this last one has being used in two different ways, in order to evaluate the effects of the improvement on the evolutionary metaheuristic. These methods were implemented in C++ code and the experiments were done under instances at TSPLIB library, being possible to observe that the procedures purposed reached success on the tests done / O presente trabalho prop?e estrat?gias de melhoria em uma bem sucedida metaheur ?stica evolucionaria para a resolu??o do Problema do Caixeiro Viajante Assim?trico. Tal procedimento consiste em um algoritmo mem?tico projetado especificamente para esse problema. Essas melhorias t?m por base a aplica??o de t?cnicas de otimiza??o conhecidas como Path-Relinking e Vocabulary Building, sendo essa ?ltima t?cnica utilizada de dois modos distintos, com o intuito de avaliar os efeitos de melhoria sobre a metaheur?stica evolucion?ria empregada. Os m?todos propostos foram implementados na linguagem de programa??o C++ e os experimentos computacionais foram realizados sobre inst?ncias disponibilizadas na biblioteca TSPLIB, tornando poss?vel observar que os procedimentos propostos alcan?aram ?xito nos testes realizados

[pt] Construção de vocabulário é uma heurística para problemas de otimização combinatória que propõe identificar porções de boas soluções e recombiná-las de modo a intensificar a busca em regiões do espaço de soluções identificadas como promissoras. A técnica de construção de vocabulário pode ser aplicada de diversas maneiras na resolução de problemas. Para facilitar a implementação e comparação de algoritmos de um mesmo domínio, a tecnologia de frameworks é uma solução que já demonstrou ser muito eficaz. O objetivo deste trabalho é desenvolver um framework para a implementação de heurísticas baseadas em construçao de vocabulário. O desenvolvimento foi fundamentado em extensa revisão bibliográfica sobre a técnica e em boas práticas de engenharia de software, como frameworks orientados a objetos e padrões de projeto. Como um estudo de caso, foram geradas aplicações a partir do framework para a resolução do problema de seqüenciamento da produção de carros, que é um problema combinatório proposto a partir de necessidades reais da indústria / [en] Vocabulary building is a heuristic for solving combinatorial optimization problems, based on the identification of solution fragments which are common to good solutions and on their combination to intensify the search on promising regions of the solution space. This technique can be vastly applied on problem solving. The technology of frameworks is an efficient strategy to facilitate the implementation and comparison of same domain algorithms. The objective of this work is to develop a framework for the implementation of heuristics based on vocabulary building. Its development was based on a wide bibliographic revision about the technique and good software engineering practices, like oriented objects frameworks and design patters. We generated applications of the framework to solve the car sequencing problem, which is a combinatorial problem proposed by real requirements of the industry

[pt] O seqüenciamento por hibridação é uma alternativa interessante para a tarefa de seqüenciamento de DNA. Este método ainda está sendo aperfeiçoado e pode superar as técnicas utilizadas em termos de tempo e custo. Uma etapa crucial do método consiste em resolver um problema combinatório que pode ser formulado como um caso especial do problema do caixeiro viajante com coleta de prêmios. Neste trabalho, propõe-se uma nova heurística construtiva multi-partida para resolver este problema. Uma estratégia de aprendizado baseada em uma memória adaptativa e um procedimento de construção de vocabulário são utilizados para melhorar o desempenho da heurística multi-partida. A memória adaptativa é utilizada para intensificar as construções de novas soluções com os elementos que aparecem com uma freqüência maior nas melhores soluções encontradas anteriormente pela heurística multi-partida. O procedimento de construção de vocabulário consiste em construir novas soluções através da combinação de partes comuns a boas soluções. Testes computacionais mostraram que estas duas estratégias aumentam significativamente o desempenho da heurística multi-partida e são particularmente indicadas para problemas de escalonamento nos quais as melhores soluções são na maioria dos casos formadas por blocos de elementos que aparecem juntos com muita freqüência. A heurística proposta supera os resultados dos melhores algoritmos encontrados na literatura, tanto em termos da qualidade das soluções encontradas, como do tempo de computação. / [en] Sequencing by hybridization is an attractive alternative for DNA sequencing. This novel method can be less time and cost consuming than the techniques applied nowadays. A very important step of this method is to solve a combinatorial problem formulated as a special case of the prize-collecting traveling salesman problem. In this work, we propose a new multistart construtive heuristic to solve this problem. A learning strategy based on adaptive memory and a vocabulary building procedure are used to improve the performance of the multistart heuristic. The adaptive memory is used to intensify the construction of new solutions with the elements that appear frequently in the best solutions previously found by the multistart heuristic. The objective of the vocabulary building procedure is to construct new solutions combining parts of good solutions. Computational experiments have shown that these two methods significantly improves the performance of the multistart heuristic and are particularly suitable for scheduling problems whose best solutions are in most cases built by blocks of elements that appear together very often. The proposed heuristic obtains systematically better solutions and is less time consuming than the best algorithms found in the literature.

Made available in DSpace on 2014-12-17T14:52:44Z (GMT). No. of bitstreams: 1 WernerKSS.pdf: 2229557 bytes, checksum: 7a64dc1b94612cd78d88c6eb822d29e6 (MD5) Previous issue date: 2009-10-31 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / The SONET/SDH Ring Assignment Problem (PALAS) treats to group localities in form of some rings, being respected the traffic's limitations of the equipment. Each ring uses a DXC (Digital Cross Connect) to make the communication with the others, being the DXC the equipment most expensive of the net, minimizing the number total of rings, will minimize the total net cost, problem's objective . This topology in rings provides a bigger capacity of regeneration. The PALAS is a problem in Combinatorial Optimization of NP-hard Class. It can be solved through Heuristics and Metaheuristics. In this text, we use Taboo Search while we keep a set of elite solutions to be used in the formation of a part of the collection of vocabulary's parts that in turn will be used in the Vocabulary Building. The Vocabulary Building will be started case Taboo Search does not reach the best solution for the instance. Three approaches had been implemented: one that only uses vocabulary's parts deriving of Taboo Search, one that it only uses vocabulary's parts randomly generated and a last one that it uses half come of the elite and half randomly generated / O Problema da Atribui??o de Localidades a An?is em Redes SONET/SDH (PALAS) trata de agrupar localidades em forma de v?rios an?is, respeitando as limita??es de tr?fego dos equipamentos. Cada anel utiliza um DXC (Digital Cross Connect) para fazer a comunica??o com os outros, sendo o DXC o equipamento mais caro da rede, minimizando o total de an?is, minimizaremos o custo total, objetivo do problema. Essa topologia em an?is proporciona uma maior capacidade de regenera??o. O PALAS ? um problema de Otimiza??o Combinat?ria da Classe NP-dif?cil. Pode ser resolvido atrav?s de Heur?sticas e Metaheur?sticas. Neste trabalho, utilizamos a Busca Tabu enquanto guardamos um conjunto de solu??es elite para serem utilizadas na forma??o de uma parte da cole??o de voc?bulos que por sua vez ser?o usados na Constru??o de Vocabul?rio para a solu??o desse problema. A Constru??o de Vocabul?rio ser? acionada caso a Busca Tabu n?o atinja o ?timo para a inst?ncia. Foram implementadas tr?s abordagens: uma que utiliza somente voc?bulos oriundos da Busca Tabu, uma que utiliza somente voc?bulos gerados aleatoriamente e uma ?ltima que utiliza metade vinda da elite e metade aleat?ria

Made available in DSpace on 2014-12-17T14:52:49Z (GMT). No. of bitstreams: 1 WagnerO_DISSERT.pdf: 4964124 bytes, checksum: 34ed6ffd6dcd720ddf12631ffd06a3d6 (MD5) Previous issue date: 2010-03-17 / The telecommunications play a fundamental role in the contemporary society, having as one of its main roles to give people the possibility to connect them and integrate them into society in which they operate and, therewith, accelerate development through knowledge. But as new technologies are introduced on the market, increases the demand for new products and services that depend on the infrastructure offered, making the problems of planning of telecommunication networks become increasingly large and complex. Many of these problems, however, can be formulated as combinatorial optimization models, and the use of heuristic algorithms can help solve these issues in the planning phase. This paper proposes the development of a Parallel Evolutionary Algorithm to be applied to telecommunications problem known in the literature as SONET Ring Assignment Problem SRAP. This problem is the class NP-hard and arises during the physical planning of a telecommunication network and consists of determining the connections between locations (customers), satisfying a series of constrains of the lowest possible cost. Experimental results illustrate the effectiveness of the Evolutionary Algorithm parallel, over other methods, to obtain solutions that are either optimal or very close to it / As telecomunica??es desempenham um papel fundamental na sociedade contempor?nea, tendo como um de seus principais pap?is o de conceder ?s pessoas a possibilidade de conect?-las e integr?-las ? sociedade em que vivem e com isso acelerar o desenvolvimento por meio do conhecimento. Mas, ? medida que novas tecnologias s?o introduzidas no mercado, cresce tamb?m a demanda por novos produtos e servi?os que dependem da infraestrutura oferecida, tornando os problemas de planejamento de redes de telecomunica??es cada vez maiores e mais complexos. Muitos desses problemas, no entanto, podem ser formulados como modelos de Otimiza??o Combinat?ria, e o uso de algoritmos heur?sticos podem ajudar a solucionar essas quest?es da fase de planejamento. Este trabalho prop?e o desenvolvimento de um Algoritmo Evolutivo paralelo a ser aplicado ao problema de telecomunica??es conhecido na literatura por Problema de Atribui??o de Localidades a An?is em Redes SONET/SDH ou PALAS. Esse problema ? da classe NP-dif?cil e surge durante a etapa do planejamento f?sico da rede e consiste na determina??o das conex?es entre localidades (clientes), de modo a satisfazer uma s?rie de restri??es ao menor custo poss?vel. Os resultados dos experimentos ilustram a efici?ncia do Algoritmo Evolutivo paralelo, sobre outros m?todos, em obter solu??es ?timas ou muito pr?ximas do valor ?timo