Arquitetura multiagente baseada em nuvem de partículas para hibridização de metaheurísticas

This thesis proposes an architecture of a new multiagent system framework for hybridization of metaheuristics inspired on the general Particle Swarm Optimization framework (PSO). The main contribution is to propose an effective approach to solve hard combinatory optimization problems. The choice of PSO as inspiration was given because it is inherently multiagent, allowing explore the features of multiagent systems, such as learning and cooperation techniques. In the proposed architecture, particles are autonomous agents with memory and methods for learning and making decisions, using search strategies to move in the solution space. The concepts of position and velocity originally defined in PSO are redefined for this approach. The proposed architecture was applied to the Traveling Salesman Problem and to the Quadratic Assignment Problem, and computational experiments were performed for testing its effectiveness. The experimental results were promising, with satisfactory performance, whereas the potential of the proposed architecture has not been fully explored. For further researches, the proposed approach will be also applied to multiobjective combinatorial optimization problems, which are closer to real-world problems. In the context of applied research, we intend to work with both students at the undergraduate level and a technical level in the implementation of the proposed architecture in real-world problems

Uma análise experimental de abordagens heurísticas aplicadas ao problema do caixeiro viajante

Due to great difficulty of accurate solution of Combinatorial Optimization Problems, some heuristic methods have been developed and during many years, the analysis of performance of these approaches was not carried through in a systematic way. The proposal of this work is to make a statistical analysis of heuristic approaches to the Traveling Salesman Problem (TSP). The focus of the analysis is to evaluate the performance of each approach in relation to the necessary computational time until the attainment of the optimal solution for one determined instance of the TSP. Survival Analysis, assisted by methods for the hypothesis test of the equality between survival functions was used. The evaluated approaches were divided in three classes: Lin-Kernighan Algorithms, Evolutionary Algorithms and Particle Swarm Optimization. Beyond those approaches, it was enclosed in the analysis, a memetic algorithm (for symmetric and asymmetric TSP instances) that utilizes the Lin-Kernighan heuristics as its local search procedure

Uma abordagem por nuvem de partículas para problemas de otimização combinatória

Combinatorial optimization problems have the goal of maximize or minimize functions defined over a finite domain. Metaheuristics are methods designed to find good solutions in this finite domain, sometimes the optimum solution, using a subordinated heuristic, which is modeled for each particular problem. This work presents algorithms based on particle swarm optimization (metaheuristic) applied to combinatorial optimization problems: the Traveling Salesman Problem and the Multicriteria Degree Constrained Minimum Spanning Tree Problem. The first problem optimizes only one objective, while the other problem deals with many objectives. In order to evaluate the performance of the algorithms proposed, they are compared, in terms of the quality of the solutions found, to other approaches

Algoritmos científicos

The Scientific Algorithms are a new metaheuristics inspired in the scientific research process. The new method introduces the idea of theme to search the solution space of hard problems. The inspiration for this class of algorithms comes from the act of researching that comprises thinking, knowledge sharing and disclosing new ideas. The ideas of the new method are illustrated in the Traveling Salesman Problem. A computational experiment applies the proposed approach to a new variant of the Traveling Salesman Problem named Car Renter Salesman Problem. The results are compared to state-of-the-art algorithms for the latter problem

Algoritmo treansgenético na solução do problema do Caixeiro Viajante

The Traveling Purchaser Problem is a variant of the Traveling Salesman Problem, where there is a set of markets and a set of products. Each product is available on a subset of markets and its unit cost depends on the market where it is available. The objective is to buy all the products, departing and returning to a domicile, at the least possible cost defined as the summation of the weights of the edges in the tour and the cost paid to acquire the products. A Transgenetic Algorithm, an evolutionary algorithm with basis on endosymbiosis, is applied to the Capacited and Uncapacited versions of this problem. Evolution in Transgenetic Algorithms is simulated with the interaction and information sharing between populations of individuals from distinct species. The computational results show that this is a very effective approach for the TPP regarding solution quality and runtime. Seventeen and nine new best results are presented for instances of the capacited and uncapacited versions, respectively

Localização de faltas em linhas de transmissão usando morfologia matemática

This work an algorithm for fault location is proposed. It contains the following functions: fault detection, fault classification and fault location. Mathematical Morphology is used to process currents obtained in the monitored terminals. Unlike Fourier and Wavelet transforms that are usually applied to fault location, the Mathematical Morphology is a non-linear operation that uses only basic operation (sum, subtraction, maximum and minimum). Thus, Mathematical Morphology is computationally very efficient. For detection and classification functions, the Morphological Wavelet was used. On fault location module the Multiresolution Morphological Gradient was used to detect the traveling waves and their polarities. Hence, recorded the arrival in the two first traveling waves incident at the measured terminal and knowing the velocity of propagation, pinpoint the fault location can be estimated. The algorithm was applied in a 440 kV power transmission system, simulated on ATP. Several fault conditions where studied and the following parameters were evaluated: fault location, fault type, fault resistance, fault inception angle, noise level and sampling rate. The results show that the application of Mathematical Morphology in faults location is very promising

O problema do caixeiro alugador com coleta de bonus: um estudo algoritmico

This paper introduces a new variant of the Traveling Car Renter Problem, named Prizecollecting Traveling Car Renter Problem. In this problem, a set of vertices, each associated with a bonus, and a set of vehicles are given. The objective is to determine a cycle that visits some vertices collecting, at least, a pre-defined bonus, and minimizing the cost of the tour that can be traveled with different vehicles. A mathematical formulation is presented and implemented in a solver to produce results for sixty-two instances. The proposed problem is also subject of an experimental study based on the algorithmic application of four metaheuristics representing the best adaptations of the state of the art of the heuristic programming.We also provide new local search operators which exploit the neighborhoods of the problem, construction procedures and adjustments, created specifically for the addressed problem. Comparative computational experiments and performance tests are performed on a sample of 80 instances, aiming to offer a competitive algorithm to the problem. We conclude that memetic algorithms, computational transgenetic and a hybrid evolutive algorithm are competitive in tests performed

Algoritmos meta-heurísticos para a solução do problema do caixeiro viajante com múltiplas caronas

The Traveling Salesman with Multiple Ridesharing (TSP-MR) is a type of the Capacitated Traveling Salesman, which presents the possibility of sharing seats with passengers taking advantage of the paths the salesman travels through his cycle. The salesman shares the cost of a path with the boarded passengers. This model can portray a real situation in which, for example, drivers are willing to share parts of a trip with tourists that wish to move between two locations visited by the driver’s route, accepting to share the vehicle with other individuals visiting other locations within the cycle. This work proposes a mathematical formulation for the problem, and an exact and metaheuristics algorithms for its solution, comparing them.

Algoritmos meta-heurísticos para a solução do problema do caixeiro viajante com múltiplas caronas

The Traveling Salesman with Multiple Ridesharing (TSP-MR) is a type of the Capacitated Traveling Salesman, which presents the possibility of sharing seats with passengers taking advantage of the paths the salesman travels through his cycle. The salesman shares the cost of a path with the boarded passengers. This model can portray a real situation in which, for example, drivers are willing to share parts of a trip with tourists that wish to move between two locations visited by the driver’s route, accepting to share the vehicle with other individuals visiting other locations within the cycle. This work proposes a mathematical formulation for the problem, and an exact and metaheuristics algorithms for its solution, comparing them.

Modelagem dinâmica e simulação computacional de poços de petróleo verticais e direcionais com elevação por bombeio mecânico

LINS, Filipe C. A. et al. Modelagem dinâmica e simulação computacional de poços de petróleo verticais e direcionais com elevação por bombeio mecânico. In: CONGRESSO BRASILEIRO DE PESQUISA E DESENVOLVIMENTO EM PETRÓLEO E GÁS, 5. 2009, Fortaleza, CE. Anais... Fortaleza: CBPDPetro, 2009.

A rede de marcação e recaptura: o caso de borboletas do gênero heliconius

(The Mark and Recapture Network: a Heliconius case study). The current pace of habitat destruction, especially in tropical landscapes, has increased the need for understanding minimum patch requirements and patch distance as tools for conserving species in forest remnants. Mark recapture and tagging studies have been instrumental in providing parameters for functional models. Because of their popularity, ease of manipulation and well known biology, butterflies have become model in studies of spatial structure. Yet, most studies on butterflies movement have focused on temperate species that live in open habitats, in which forest patches are barrier to movement. This study aimed to view and review data from mark-recapture as a network in two species of butterfly (Heliconius erato and Heliconius melpomene). A work of marking and recapture of the species was carried out in an Atlantic forest reserve located about 20km from the city of Natal (RN). Mark recapture studies were conducted in 3 weekly visits during January-February and July-August in 2007 and 2008. Captures were more common in two sections of the dirt road, with minimal collection in the forest trail. The spatial spread of captures was similar in the two species. Yet, distances between recaptures seem to be greater for Heliconius erato than for Heliconius melpomene. In addition, the erato network is more disconnected, suggesting that this specie has shorter traveling patches. Moving on to the network, both species have similar number of links (N) and unweighed vertices (L). However, melpomene has a weighed network 50% more connections than erato. These network metrics suggest that erato has more compartmentalized network and restricted movement than melpomene. Thus, erato has a larger number of disconnected components, nC, in the network, and a smaller network diameter. The frequency distribution of network connectivity for both species was better explained by a Power-law than by a random, Poissom distribution, showing that the Power-law provides a better fit than the Poisson for both species. Moreover, the Powerlaw erato is much better adjusted than in melpomene, which should be linked to the small movements that erato makes in the network