Estratégias de aplicações sequenciais e paralelas da metaheurística otimização por enxame de partículas ao problema do caixeiro viajante

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

Análise e otimização de superfícies seletivas de Frequência utilizando redes neurais artificiais e algoritmos de otimização natural

The bidimensional periodic structures called frequency selective surfaces have been well investigated because of their filtering properties. Similar to the filters that work at the traditional radiofrequency band, such structures can behave as band-stop or pass-band filters, depending on the elements of the array (patch or aperture, respectively) and can be used for a variety of applications, such as: radomes, dichroic reflectors, waveguide filters, artificial magnetic conductors, microwave absorbers etc. To provide high-performance filtering properties at microwave bands, electromagnetic engineers have investigated various types of periodic structures: reconfigurable frequency selective screens, multilayered selective filters, as well as periodic arrays printed on anisotropic dielectric substrates and composed by fractal elements. In general, there is no closed form solution directly from a given desired frequency response to a corresponding device; thus, the analysis of its scattering characteristics requires the application of rigorous full-wave techniques. Besides that, due to the computational complexity of using a full-wave simulator to evaluate the frequency selective surface scattering variables, many electromagnetic engineers still use trial-and-error process until to achieve a given design criterion. As this procedure is very laborious and human dependent, optimization techniques are required to design practical periodic structures with desired filter specifications. Some authors have been employed neural networks and natural optimization algorithms, such as the genetic algorithms and the particle swarm optimization for the frequency selective surface design and optimization. This work has as objective the accomplishment of a rigorous study about the electromagnetic behavior of the periodic structures, enabling the design of efficient devices applied to microwave band. For this, artificial neural networks are used together with natural optimization techniques, allowing the accurate and efficient investigation of various types of frequency selective surfaces, in a simple and fast manner, becoming a powerful tool for the design and optimization of such structures

Otimização de superfícies seletivas de frequência com elementos pré-fractais utilizando rede neural MLP e algoritmos de busca populacional

This thesis describes design methodologies for frequency selective surfaces (FSSs) composed of periodic arrays of pre-fractals metallic patches on single-layer dielectrics (FR4, RT/duroid). Shapes presented by Sierpinski island and T fractal geometries are exploited to the simple design of efficient band-stop spatial filters with applications in the range of microwaves. Initial results are discussed in terms of the electromagnetic effect resulting from the variation of parameters such as, fractal iteration number (or fractal level), fractal iteration factor, and periodicity of FSS, depending on the used pre-fractal element (Sierpinski island or T fractal). The transmission properties of these proposed periodic arrays are investigated through simulations performed by Ansoft DesignerTM and Ansoft HFSSTM commercial softwares that run full-wave methods. To validate the employed methodology, FSS prototypes are selected for fabrication and measurement. The obtained results point to interesting features for FSS spatial filters: compactness, with high values of frequency compression factor; as well as stable frequency responses at oblique incidence of plane waves. This thesis also approaches, as it main focus, the application of an alternative electromagnetic (EM) optimization technique for analysis and synthesis of FSSs with fractal motifs. In application examples of this technique, Vicsek and Sierpinski pre-fractal elements are used in the optimal design of FSS structures. Based on computational intelligence tools, the proposed technique overcomes the high computational cost associated to the full-wave parametric analyzes. To this end, fast and accurate multilayer perceptron (MLP) neural network models are developed using different parameters as design input variables. These neural network models aim to calculate the cost function in the iterations of population-based search algorithms. Continuous genetic algorithm (GA), particle swarm optimization (PSO), and bees algorithm (BA) are used for FSSs optimization with specific resonant frequency and bandwidth. The performance of these algorithms is compared in terms of computational cost and numerical convergence. Consistent results can be verified by the excellent agreement obtained between simulations and measurements related to FSS prototypes built with a given fractal iteration

Análise e síntese de antenas e superfícies seletivas de frequência utilizando computação evolucionária e inteligência de enxames

The frequency selective surfaces, or FSS (Frequency Selective Surfaces), are structures consisting of periodic arrays of conductive elements, called patches, which are usually very thin and they are printed on dielectric layers, or by openings perforated on very thin metallic surfaces, for applications in bands of microwave and millimeter waves. These structures are often used in aircraft, missiles, satellites, radomes, antennae reflector, high gain antennas and microwave ovens, for example. The use of these structures has as main objective filter frequency bands that can be broadcast or rejection, depending on the specificity of the required application. In turn, the modern communication systems such as GSM (Global System for Mobile Communications), RFID (Radio Frequency Identification), Bluetooth, Wi-Fi and WiMAX, whose services are highly demanded by society, have required the development of antennas having, as its main features, and low cost profile, and reduced dimensions and weight. In this context, the microstrip antenna is presented as an excellent choice for communications systems today, because (in addition to meeting the requirements mentioned intrinsically) planar structures are easy to manufacture and integration with other components in microwave circuits. Consequently, the analysis and synthesis of these devices mainly, due to the high possibility of shapes, size and frequency of its elements has been carried out by full-wave models, such as the finite element method, the method of moments and finite difference time domain. However, these methods require an accurate despite great computational effort. In this context, computational intelligence (CI) has been used successfully in the design and optimization of microwave planar structures, as an auxiliary tool and very appropriate, given the complexity of the geometry of the antennas and the FSS considered. The computational intelligence is inspired by natural phenomena such as learning, perception and decision, using techniques such as artificial neural networks, fuzzy logic, fractal geometry and evolutionary computation. This work makes a study of application of computational intelligence using meta-heuristics such as genetic algorithms and swarm intelligence optimization of antennas and frequency selective surfaces. Genetic algorithms are computational search methods based on the theory of natural selection proposed by Darwin and genetics used to solve complex problems, eg, problems where the search space grows with the size of the problem. The particle swarm optimization characteristics including the use of intelligence collectively being applied to optimization problems in many areas of research. The main objective of this work is the use of computational intelligence, the analysis and synthesis of antennas and FSS. We considered the structures of a microstrip planar monopole, ring type, and a cross-dipole FSS. We developed algorithms and optimization results obtained for optimized geometries of antennas and FSS considered. To validate results were designed, constructed and measured several prototypes. The measured results showed excellent agreement with the simulated. Moreover, the results obtained in this study were compared to those simulated using a commercial software has been also observed an excellent agreement. Specifically, the efficiency of techniques used were CI evidenced by simulated and measured, aiming at optimizing the bandwidth of an antenna for wideband operation or UWB (Ultra Wideband), using a genetic algorithm and optimizing the bandwidth, by specifying the length of the air gap between two frequency selective surfaces, using an optimization algorithm particle swarm

Técnicas de computação natural para segmentação de imagens médicas

Image segmentation is one of the image processing problems that deserves special attention from the scientific community. This work studies unsupervised methods to clustering and pattern recognition applicable to medical image segmentation. Natural Computing based methods have shown very attractive in such tasks and are studied here as a way to verify it's applicability in medical image segmentation. This work treats to implement the following methods: GKA (Genetic K-means Algorithm), GFCMA (Genetic FCM Algorithm), PSOKA (PSO and K-means based Clustering Algorithm) and PSOFCM (PSO and FCM based Clustering Algorithm). Besides, as a way to evaluate the results given by the algorithms, clustering validity indexes are used as quantitative measure. Visual and qualitative evaluations are realized also, mainly using data given by the BrainWeb brain simulator as ground truth

Degradação fotocatalítica oxidativa do fenol utilizando carvão obtido da pirólise de diferentes biomassas

The modern industrial progress has been contaminating water with phenolic compounds. These are toxic and carcinogenic substances and it is essential to reduce its concentration in water to a tolerable one, determined by CONAMA, in order to protect the living organisms. In this context, this work focuses on the treatment and characterization of catalysts derived from the bio-coal, by-product of biomass pyrolysis (avelós and wood dust) as well as its evaluation in the phenol photocatalytic degradation reaction. Assays were carried out in a slurry bed reactor, which enables instantaneous measurements of temperature, pH and dissolved oxygen. The experiments were performed in the following operating conditions: temperature of 50 °C, oxygen flow equals to 410 mL min-1 , volume of reagent solution equals to 3.2 L, 400 W UV lamp, at 1 atm pressure, with a 2 hours run. The parameters evaluated were the pH (3.0, 6.9 and 10.7), initial concentration of commercial phenol (250, 500 and 1000 ppm), catalyst concentration (0, 1, 2, and 3 g L-1 ), nature of the catalyst (activated avelós carbon washed with dichloromethane, CAADCM, and CMADCM, activated dust wood carbon washed with dichloromethane). The results of XRF, XRD and BET confirmed the presence of iron and potassium in satisfactory amounts to the CAADCM catalyst and on a reduced amount to CMADCM catalyst, and also the surface area increase of the materials after a chemical and physical activation. The phenol degradation curves indicate that pH has a significant effect on the phenol conversion, showing better results for lowers pH. The optimum concentration of catalyst is observed equals to 1 g L-1 , and the increase of the initial phenol concentration exerts a negative influence in the reaction execution. It was also observed positive effect of the presence of iron and potassium in the catalyst structure: betters conversions were observed for tests conducted with the catalyst CAADCM compared to CMADCM catalyst under the same conditions. The higher conversion was achieved for the test carried out at acid pH (3.0) with an initial concentration of phenol at 250 ppm catalyst in the presence of CAADCM at 1 g L-1 . The liquid samples taken every 15 minutes were analyzed by liquid chromatography identifying and quantifying hydroquinone, p-benzoquinone, catechol and maleic acid. Finally, a reaction mechanism is proposed, cogitating the phenol is transformed into the homogeneous phase and the others react on the catalyst surface. Applying the model of Langmuir-Hinshelwood along with a mass balance it was obtained a system of differential equations that were solved using the Runge-Kutta 4th order method associated with a optimization routine called SWARM (particle swarm) aiming to minimize the least square objective function for obtaining the kinetic and adsorption parameters. Related to the kinetic rate constant, it was obtained a magnitude of 10-3 for the phenol degradation, 10-4 to 10-2 for forming the acids, 10-6 to 10-9 for the mineralization of quinones (hydroquinone, p-benzoquinone and catechol), 10-3 to 10-2 for the mineralization of acids.

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

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

Algorítmo evolucionário para a distribuição de produtos de petróleo por redes de polidutos

The distribution of petroleum products through pipeline networks is an important problem that arises in production planning of refineries. It consists in determining what will be done in each production stage given a time horizon, concerning the distribution of products from source nodes to demand nodes, passing through intermediate nodes. Constraints concerning storage limits, delivering time, sources availability, limits on sending or receiving, among others, have to be satisfied. This problem can be viewed as a biobjective problem that aims at minimizing the time needed to for transporting the set of packages through the network and the successive transmission of different products in the same pipe is called fragmentation. This work are developed three algorithms that are applied to this problem: the first algorithm is discrete and is based on Particle Swarm Optimization (PSO), with local search procedures and path-relinking proposed as velocity operators, the second and the third algorithms deal of two versions based on the Non-dominated Sorting Genetic Algorithm II (NSGA-II). The proposed algorithms are compared to other approaches for the same problem, in terms of the solution quality and computational time spent, so that the efficiency of the developed methods can be evaluated

Algoritmos experimentais para o problema biobjetivo da árvore geradora quadrática em adjacência de arestas

The Quadratic Minimum Spanning Tree (QMST) problem is a generalization of the Minimum Spanning Tree problem in which, beyond linear costs associated to each edge, quadratic costs associated to each pair of edges must be considered. The quadratic costs are due to interaction costs between the edges. When interactions occur between adjacent edges only, the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST). Both QMST and AQMST are NP-hard and model a number of real world applications involving infrastructure networks design. Linear and quadratic costs are summed in the mono-objective versions of the problems. However, real world applications often deal with conflicting objectives. In those cases, considering linear and quadratic costs separately is more appropriate and multi-objective optimization provides a more realistic modelling. Exact and heuristic algorithms are investigated in this work for the Bi-objective Adjacent Only Quadratic Spanning Tree Problem. The following techniques are proposed: backtracking, branch-and-bound, Pareto Local Search, Greedy Randomized Adaptive Search Procedure, Simulated Annealing, NSGA-II, Transgenetic Algorithm, Particle Swarm Optimization and a hybridization of the Transgenetic Algorithm with the MOEA-D technique. Pareto compliant quality indicators are used to compare the algorithms on a set of benchmark instances proposed in literature.

Algoritmos experimentais para o problema biobjetivo da árvore geradora quadrática em adjacência de arestas

The Quadratic Minimum Spanning Tree (QMST) problem is a generalization of the Minimum Spanning Tree problem in which, beyond linear costs associated to each edge, quadratic costs associated to each pair of edges must be considered. The quadratic costs are due to interaction costs between the edges. When interactions occur between adjacent edges only, the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST). Both QMST and AQMST are NP-hard and model a number of real world applications involving infrastructure networks design. Linear and quadratic costs are summed in the mono-objective versions of the problems. However, real world applications often deal with conflicting objectives. In those cases, considering linear and quadratic costs separately is more appropriate and multi-objective optimization provides a more realistic modelling. Exact and heuristic algorithms are investigated in this work for the Bi-objective Adjacent Only Quadratic Spanning Tree Problem. The following techniques are proposed: backtracking, branch-and-bound, Pareto Local Search, Greedy Randomized Adaptive Search Procedure, Simulated Annealing, NSGA-II, Transgenetic Algorithm, Particle Swarm Optimization and a hybridization of the Transgenetic Algorithm with the MOEA-D technique. Pareto compliant quality indicators are used to compare the algorithms on a set of benchmark instances proposed in literature.

Maximização da penetração da geração distribuída através do algoritmo de otimização nuvem de partículas

This work develops a methodology for defining the maximum active power being injected into predefined nodes in the studied distribution networks, considering the possibility of multiple accesses of generating units. The definition of these maximum values is obtained from an optimization study, in which further losses should not exceed those of the base case, i.e., without the presence of distributed generation. The restrictions on the loading of the branches and voltages of the system are respected. To face the problem it is proposed an algorithm, which is based on the numerical method called particle swarm optimization, applied to the study of AC conventional load flow and optimal load flow for maximizing the penetration of distributed generation. Alternatively, the Newton-Raphson method was incorporated to resolution of the load flow. The computer program is performed with the SCILAB software. The proposed algorithm is tested with the data from the IEEE network with 14 nodes and from another network, this one from the Rio Grande do Norte State, at a high voltage (69 kV), with 25 nodes. The algorithm defines allowed values of nominal active power of distributed generation, in percentage terms relative to the demand of the network, from reference values

Estudo de massa cerâmica triaxial visando à otimização do ciclo de queima da indústria de cerâmica estrutural

Over recent years the structural ceramics industry in Brazil has found a very favorable market for growth. However, difficulties related to productivity and product quality are partially inhibiting this possible growth. An alternative for trying to solve these problems and, thus, provide the pottery industry the feasibility of full development, is the substitution of firewood used in the burning process by natural gas. In order to contribute to this process of technological innovation, this paper studies the effect of co-use of ceramic phyllite and kaolin waste on the properties of a clay matrix, verifying the possible benefits that these raw materials can give to the final product, as well as the possibility of such materials to reduce the heat load necessary to obtain products with equal or superior quality. The study was divided into two steps: characterization of materials and study of formulations. Two clays, a phyllite and a residue of kaolin were characterized by the following techniques: laser granulometry, plasticity index by Atterberg limits, X-ray fluorescence, X-ray diffraction, mineralogical composition by Rietveld, thermogravimetric and differential thermal analysis. To study the formulations, specifically for evaluation of technological properties of the parts, was performed an experimental model that combined planning involving a mixture of three components (standard mass x phyllite x kaolin waste) and a 23 factorial design with central point associated with thermal processing parameters. The experiment was performed with restricted strip-plot randomization. In total, 13 compositional points were investigated within the following constraints: phyllite ≤ 20% by weight, kaolin waste ≤ 40% by weight, and standard mass ≥ 60% by weight. The thermal parameters were used at the following levels: 750 and 950 °C to the firing temperature, 5 and 15 °C/min at the heating rate, 15 and 45min to the baseline. The results showed that the introduction of phyllite and/or kaolin waste in ceramic body produced a number of benefits in properties of the final product, such as: decreased absorption of water, apparent porosity and linear retraction at burn; besides the increase in apparent specific mass and mechanical properties of parts. The best results were obtained in the compositional points where the sum of the levels of kaolin waste and phyllite was maximal (40% by weight), as well as conditions which were used in firing temperatures of 950 °C. Regarding the prospect of savings in heat energy required to form the desired microstructure, the phyllite and the residue of kaolin, for having small particle sizes and constitutions mineralogical phases with the presence of fluxes, contributed to the optimization of the firing cycle.

Cinemática de partículas em fluidos de viscosidade variável com o tempo e sua aplicação na construção de poços de petróleo: avaliação durante paradas operacionais

The new oil reservoirs discoveries in onshore and ultra deep water offshore fields and complex trajectories require the optimization of procedures to reduce the stops operation during the well drilling, especially because the platforms and equipment high cost, and risks which are inherent to the operation. Among the most important aspects stands out the drilling fluids project and their behavior against different situations that may occur during the process. By means of sedimentation experiments, a correlation has been validated to determe the sedimentation particles velocity in variable viscosity fluids over time, applying the correction due to effective viscosity that is a shear rate and time function. The viscosity evolution over time was obtained by carrying out rheologic tests using a fixed shear rate, small enough to not interfere in the fluid gelling process. With the sedimentation particles velocity and the fluid viscosity over time equations an iterative procedure was proposed to determine the particles displacement over time. These equations were implemented in a case study to simulate the cuttings sedimentation generated in the oil well drilling during stops operation, especially in the connections and tripping, allowing the drilling fluid project in order to maintain the cuttings in suspension, avoiding risks, such as stuck pipe and in more drastic conditions, the loss of the well