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

Orientador: Akebo Yamakami / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-08T23:52:00Z (GMT). No. of bitstreams: 1 Carvalho_MarciaBragade_M.pdf: 2154346 bytes, checksum: caafd847980349294a73d2ad38d6414c (MD5) Previous issue date: 2007 / Resumo: Dentre as várias técnicas heurísticas e exatas existentes para a resolução de problemas combinatórios, os algoritmos populacionais de otimização por colônia de formigas e genéticos têm se destacado devido à sua boa performance. Em especial os algoritmos de colônia de formigas são considerados atualmente como uma das técnicas mais bem sucedidas para a resolução de vários problemas combinatórios, dentre eles o problema do caixeiro viajante. Neste trabalho é apresentado um algoritmo híbrido que trabalha com as meta-heurísticas de sistema de colônia de formigas e genético conjuntamente aplicados no problema do caixeiro viajante simétrico. Além disso, apresentamos uma proposta para o algoritmo de formigas quando temos incertezas associadas aos parâmetros do problema. Os resultados obtidos com as metodologias propostas apresentam resultados satisfatórios para todas as instâncias utilizadas / Abstract: Amongst the several existing heuristical and accurate techniques for the resolution of combinatorial problems, the population algorithms ant colony optimization and genetic have been detached due to their good performance. In special the ant colony algorithms are considered currently as one of the techniques most succeeded for the resolution of some combinatorial problems, amongst them the travelling salesman problem. In this work is presented a hybrid algorithm which works with the ant colony system and genetic metaheuristics jointly applied in the symmetric travelling salesman problem. Moreover, we presented a proposal for the ant algorithm when we have uncertainties associated to problem parameters. The results gotten with the methodology proposals present resulted satisfactory for all the used instances / Mestrado / Automação / Mestre em Engenharia Elétrica

This report covers an investigation of the methods and algorithms required to plan and perform semi-autonomous photo missions on Apple iPad devices using data exported from Google Earth. Flight time was to be minimized, taking wind velocity and aircraft performance into account. Google Earth was used both to define what photos to take, and to define the allowable mission area for the aircraft. A benchmark mission was created containing 30 photo operations in a 250 by 500 m area containing several no-fly-areas. The report demonstrates that photos taken in Google Earth can be reproduced in reality with good visual resemblance. High quality paths between all possible photo operation pairs in the benchmark mission could be found in seconds using the Theta* algorithm in a 3D grid representation with six-edge connectivity (Up, Down, North, South, East, West). Smoothing the path in a post-processing step was shown to further increase the quality of the path at a very low computational cost. An optimal route between the operations in the benchmark mission, using the paths found by Theta*, could be found in less than half a minute using a Branch-and-Bound algorithm. It was however also found that prematurely terminating the algorithm after five seconds yielded a route that was close enough to optimal not to warrant running the algorithm to completion.

This thesis consists of two parts: text and programming part. It is divided into seven chapters. Its main goal is to compare heuristics for dynamic traveling salesman problem in a few perspectives. The text part of this thesis theoretically describes heuristic methods and in the programming part are wake up to life via VBA in MS Excel. The results of computational experiments on these heuristic methods are presented in the last chapter. In the first part, the traveling salesman problem and its solution are being described. Characteristic of the modification in a form of dynamic traveling salesman problem follow. Next chapter presents the programming solution chosen heuristics. The final chapter presents experimental results obtain with programmed heuristics.

Routing problems are ones of the most famous members of the group of the classical optimalization combinatorial problems. Travelling salesman problem and problems derived from it have been attracting mathematics and analysts, since they were firstly formulated, and accelerating a development of new methods and approaches that can be used for a wide range of another real-life problems. This thesis aims to demonstrate an usefulness and a flexibility of shown metaheristic methods. Results are compared with outputs of alternative algorithms or known optimal solutions where it is possible. To fulfill this goal the VBA application has been developed. The results of experiments are presented and the application is decribed in a second part of this thesis. A reader should be sufficiently instructed which way he could choose to solve similar types of problems

The main goal of this work is to implement a system, which will be able to optimize routes between warehouses and selected customers and visualize them using maps by the Google Inc. This problem is being analyzed not only on the theoretical, but also, and mainly, on the practical aspects and tries to find a gap in the market with similar applications.

Syftet med denna studie var att undersöka olika algoritmer som kan användas för attlösa ruttplaneringsproblemet och handelsresandeproblemet. Ruttplaneringsproblemetoch handelsresandeproblemet är problemet som uppstår när den kortaste sträckan skahittas mellan olika körpunkter och problemet är löst efter att den kortaste sträckan blivitfunnen. Observationer och intervjuer hos återvinningsföretaget Gotland Recyclinggjordes för att undersöka hur heuristiker som är metoder, tumregler som kan användasför att få fram resultat som är bra men inte alltid helt optimala kan användas för att kortaner körruterna. Arbetet gjordes med hjälp av företaget Gotland Recycling som idag harcirka 500 kunder per år och äger två sopbilar samt två lastbilar. Företaget har under enlängre tid förstått att deras ruttplaneringssystem har kunnat förbättras därav har företagetintresserat sig för att testa nya metoder för att förbättra sina egna rutter samt olikametoder för att validera de metoder som redan används för ruttplanering och körning.Google Maps och Microsoft Excel användas i denna studie för att applicera de olikaruttplaneringsmetoderna och kunna analysera de olika rutterna. Med hjälp av GoogleMaps har kostnader i form av körsträcka i meter och kilometer tagits fram genom attapplicera algoritmerna på olika körnings områden. Med hjälp av Google Maps ochMicrosoft Excel har fordonens körningsmönster blivit kartlagda och registrerade itabeller där de olika algoritmerna blivit applicerade för att bygga upp nya rutter ochmäta de nya rutternas körsträcka. Litteratur och artiklar har även samlats ihop för dennastudie och användes för att analysera olika ruttplanering och handelsresandeproblemsmetoders olika svagheter och styrkor. Resultatet från testerna och litteraturen visade attdet finns en potential att olika lösnings metoder som undersökts i denna studie kanminska på körsträckan. Olika lösningsmetoder har olika förutsättningar, styrkor ochsvagheter beroende på situationen som de appliceras inom. I två tester av tre medanvändning av någon av den utvalda ruttplanerings metoder minskade körsträckan imeter för rutten jämfört med företagets egen ruttplanering. Både testerna och litteraturenpåvisade att ibland förekommer mycket oberäkneliga hinder inom vissa områden somgör det meningslöst att applicera ruttplanering och handelsresandemetoder inom dessaområden och att mer avancerade system krävs för att hantera situationen. / The aim with this paper was to study how different kinds of heuristics for the routeplanning and traveling salesman’s problem could affect the route, potentially decreasethe driving costs and make it easier for companies and vehicles to plan their routes. Toinvestigate how different heuristics can affect the route planning, observations andinterviews has been made in a company named Gotland Recycling. Gotland Recyclingis a recycling company which operate on the island Gotland. Today the company has500 customers per year and owns four truck vehicles. The company has understood thatfor a long time their route planning system can be improved and has taken an interest intesting new methods to improve their own route planning and validate the methodswhich they are already using for route planning and driving. To analyze the differentroutes Google Maps and Excel was used. With the help of Google Maps and Excel costsin the form of driving length in meter and kilometer has been produced by applying thechosen algorithms on different driving areas. With the help of Google Maps and Excel,the driving pattern has been charted and registered in different tables. Differentalgorithms have then been applied to construct new routes and measure their mileage.Theory in the form of literature and articles has been collected for this study to analyzeand compare different strengths and weaknesses of different route planning andtraveling salesman problem solving methods. The result from this study shows there is apotential for different solution methods to make the mileage smaller. Different solvingmethods had different qualifications, strengths and weaknesses which depended on thesituations which they were applied. In two of the three tests which were made thechosen solving methods produced routes which were shorter than the route produced bythe company. Both testing and the literature also showed that for some situations thereare so many random obstacles in driving areas which make it meaningless to apply anytype of route-planning method and more advanced systems are required.

Cache replacement policies have applications that are nearly ubiquitous in technology. Among these is an interesting subset which occurs when referentially transparent functions are memoized, eg. in compilers, in dynamic programming, and other software caches. In many applications the least recently used (LRU) approach likely preserves items most needed by memoized function calls. However, despite its popularity LRU is expensive to implement, which has caused a spate of research initiatives aimed at approximating its cache miss performance in exchange for faster and more memory efficient implementations. We present a novel caching algorithm, Far From Recently Used (FFRU), which offers a simple, but highly configurable mechanism for providing lower bounds on the usage recency of items evicted from the cache. This algorithm preserves the constant time amortized cost of insertions and updates and minimizes the memory overhead needed to administer the eviction guarantees. We study the cache miss performance of several memoized optimization problems which vary in the number of subproblems generated and the access patterns exhibited by their recursive calls. We study their cache miss performance using LRU cache replacement, then show the performance of FFRU in these same problem scenarios. We show that for equivalent minimum eviction age guarantees, FFRU incurs fewer cache misses than LRU, and does so using less memory. We also present some variations of the algorithms studied (Fibonacci, KMP, LCS, and Euclidean TSP) which exploit the characteristics of the cache replacement algorithms being employed, further resulting in improved cache miss performance. We present a novel implementation of a well known approximation algorithm for the Euclidean Traveling Salesman Problem due to Sanjeev Arora. Our implementation of this algorithm outperforms the currently known implementations of the same. It has long remained an open question whether or not algorithms relying on geometric divisions of space can be implemented into practical tools, and our powerful implementation of Arora's algorithm establishes a new benchmark in that arena. / Computer and Information Science

Finding the shortest tour visiting all given points at least ones belongs to the most famous optimization problems until today [travelling salesman problem (TSP)]. Optimal solutions exist formany problems up to several ten thousand points. Themajor difficulty in solving larger problems is the required computational complexity. This shifts the research from finding the optimum with no time limitation to approaches that find good but sub-optimal solutions in pre-defined limited time. This paper proposes a new approach for two-dimensional symmetric problems with more than a million coordinates that is able to create good initial tours within few minutes. It is based on a hierarchical clustering strategy and supports parallel processing. In addition, a method is proposed that can correct unfavorable paths with moderate computational complexity. The new approach is superior to state-of-the-artmethods when applied to TSP instances with non-uniformly distributed coordinates.

No description available.