O problema biobjetivo da árvore geradora quadrática em adjacência de arestas

The Quadratic Minimum Spanning Tree Problem (QMST) is a version of the Minimum Spanning Tree Problem in which, besides the traditional linear costs, there is a quadratic structure of costs. This quadratic structure models interaction effects between pairs of edges. Linear and quadratic costs are added up to constitute the total cost of the spanning tree, which must be minimized. When these interactions are restricted to adjacent edges, the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST). AQMST and QMST are NP-hard problems that model several problems of transport and distribution networks design. In general, AQMST arises as a more suitable model for real problems. Although, in literature, linear and quadratic costs are added, in real applications, they may be conflicting. In this case, it may be interesting to consider these costs separately. In this sense, Multiobjective Optimization provides a more realistic model for QMST and AQMST. A review of the state-of-the-art, so far, was not able to find papers regarding these problems under a biobjective point of view. Thus, the objective of this Thesis is the development of exact and heuristic algorithms for the Biobjective Adjacent Only Quadratic Spanning Tree Problem (bi-AQST). In order to do so, as theoretical foundation, other NP-hard problems directly related to bi-AQST are discussed: the QMST and AQMST problems. Bracktracking and branch-and-bound exact algorithms are proposed to the target problem of this investigation. The heuristic algorithms developed are: Pareto Local Search, Tabu Search with ejection chain, Transgenetic Algorithm, NSGA-II and a hybridization of the two last-mentioned proposals called NSTA. The proposed algorithms are compared to each other through performance analysis regarding computational experiments with instances adapted from the QMST literature. With regard to exact algorithms, the analysis considers, in particular, the execution time. In case of the heuristic algorithms, besides execution time, the quality of the generated approximation sets is evaluated. Quality indicators are used to assess such information. Appropriate statistical tools are used to measure the performance of exact and heuristic algorithms. Considering the set of instances adopted as well as the criteria of execution time and quality of the generated approximation set, the experiments showed that the Tabu Search with ejection chain approach obtained the best results and the transgenetic algorithm ranked second. The PLS algorithm obtained good quality solutions, but at a very high computational time compared to the other (meta)heuristics, getting the third place. NSTA and NSGA-II algorithms got the last positions

Um estudo algorítmico para otimização do plano de tratamento da radioterapia conformal

This work performs an algorithmic study of optimization of a conformal radiotherapy plan treatment. Initially we show: an overview about cancer, radiotherapy and the physics of interaction of ionizing radiation with matery. A proposal for optimization of a plan of treatment in radiotherapy is developed in a systematic way. We show the paradigm of multicriteria problem, the concept of Pareto optimum and Pareto dominance. A generic optimization model for radioterapic treatment is proposed. We construct the input of the model, estimate the dose given by the radiation using the dose matrix, and show the objective function for the model. The complexity of optimization models in radiotherapy treatment is typically NP which justifyis the use of heuristic methods. We propose three distinct methods: MOGA, MOSA e MOTS. The project of these three metaheuristic procedures is shown. For each procedures follows: a brief motivation, the algorithm itself and the method for tuning its parameters. The three method are applied to a concrete case and we confront their performances. Finally it is analyzed for each method: the quality of the Pareto sets, some solutions and the respective Pareto curves

Imageamento digital de paleocavernas colapsadas com georadar

In this study, the methodological procedures involved in digital imaging of collapsed paleocaves in tufa using GPR are presented. These carbonate deposits occur in the Quixeré region, Ceará State (NE Brazil), on the western border of the Potiguar Basin. Collapsed paleocaves are exposed along a state road, which were selected to this study. We chose a portion of the called Quixeré outcrop for making a photomosaic and caring out a GPR test section to compare and parameterize the karst geometries on the geophysical line. The results were satisfactory and led to the adoption of criteria for the interpretation of others GPR sections acquired in the region of the Quixeré outcrop. Two grids of GPR lines were acquired; the first one was wider and more spaced and guided the location of the second grid, denser and located in the southern part of the outcrop. The radargrams of the second grid reveal satisfactorily the collapsed paleocaves geometries. For each grid has been developed a digital solid model of the Quixeré outcrop. The first model allows the recognition of the general distribution and location of collapsed paleocaves in tufa deposits, while the second more detailed digital model provides not only the 3D individualization of the major paleocaves, but also the estimation of their respective volumes. The digital solid models are presented here as a new frontier in the study of analog outcrops to reservoirs (for groundwater and hydrocarbon), in which the volumetric parameterization and characterization of geological bodies become essential for composing the databases, which together with petrophysical properties information, are used in more realistic computer simulations for sedimentary reservoirs.