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

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.

Uma análise experimental de algoritmos exatos aplicados ao problema da árvore geradora multiobjetivo

The Multiobjective Spanning Tree Problem is NP-hard and models applications in several areas. This research presents an experimental analysis of different strategies used in the literature to develop exact algorithms to solve the problem. Initially, the algorithms are classified according to the approaches used to solve the problem. Features of two or more approaches can be found in some of those algorithms. The approaches investigated here are: the two-stage method, branch-and-bound, k-best and the preference-based approach. The main contribution of this research lies in the fact that no research was presented to date reporting a systematic experimental analysis of exact algorithms for the Multiobjective Spanning Tree Problem. Therefore, this work can be a basis for other research that deal with the same problem. The computational experiments compare the performance of algorithms regarding processing time, efficiency based on the number of objectives and number of solutions found in a controlled time interval. The analysis of the algorithms was performed for known instances of the problem, as well as instances obtained from a generator commonly used in the literature

Análise da Expressão de APE1 após Estresse Oxidativo Induzido em Células Proficientes e Deficientes na Via de Reparo por Excisão de Nucleotídeos

Riboflavin is a vitamin very important in aerobic organisms, as a precursor of many coenzymes involved in the electron transporter chain. However, after photosensitization of riboflavin with UV or visible light, it generates reactive oxygen species (ROS), which can oxidize the DNA. The repair of oxidative lesions on DNA occurs through the base excision repair pathway (BER), where APE1 endonuclease plays a central role. On the other hand, the nucleotide excision repair pathway (NER) repairs helix-distorting lesions. Recently, it was described the participation of NERproteins in the repair of oxidative damage and in stimulation of repair function fromAPE1. The aim of this research was to evaluate the cytotoxic effects of photosensitized riboflavin (RF*) in cells proficient and deficient in NER, correlating with APE1 expression. For this propose, the cells were treated with RF* and it was performed the cell viability assay, extraction of whole proteins, cells fractionation, immunoblotting, indirect immunofluorescence and analysis of polymorphisms of BER gens. The results evidenced that cells deficient in XPA and CSB proteins were more sensitive to RF*. However, XPC-deficient cells presented similar resistance to MRC5- SV cells, which is proficient in NER. These results indicate that XPA and CSB proteins have an important role on repair of oxidative lesions induced by RF*. Additionally, it was evidenced that single nucleotide polymorphisms (SNPs) in BER enzymes may influence in sensitivity of NER-deficient cell lines. Concerning the APE1 expression, the results showed that expression of this protein after treatment with RF* only changed in XPC-deficient cells. Though, it was observed that APE1 is recruited and is bound to chromatin in MRC5-SV and XPA cells after treatment with RF*. The results also showed the induction of DNA damage after treatment with RF*, through the analysis of-H2AX, since the treatment promoted an increase of endogenous levels of this phosphorylated protein, which acts signaling double strand-break on DNA. On the other hand, in XPC-deficient cells, regardless of resistance of RF*, the endogenous levels of APE1 are extremely reduced when compared with other cell lines and APE1 is not bound to chromatin after treatment with RF*. These results conclude that RF* was able to induce cell death in NERdeficient cells, where XPA and CSB cells were more sensitive when compared with MRC5-SV and XPC-deficient cells. This last result is potentially very interesting, since XPC-deficient cell line presents low levels of APE1. Additionally, the results evidenced that APE1 protein can be involved in the repair of oxidative damage induced by RF*, because APE1 is recruited and bound strongly to chromatin after treatment.

Busca heurística através de algoritmo genético e memético com construção de vocábulos para o problema de atribuição de localidades a anéis Sonet

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

Algoritmo Q-learning como estratégia de exploração e/ou explotação para metaheurísticas GRASP e algoritmo genético

Techniques of optimization known as metaheuristics have achieved success in the resolution of many problems classified as NP-Hard. These methods use non deterministic approaches that reach very good solutions which, however, don t guarantee the determination of the global optimum. Beyond the inherent difficulties related to the complexity that characterizes the optimization problems, the metaheuristics still face the dilemma of xploration/exploitation, which consists of choosing between a greedy search and a wider exploration of the solution space. A way to guide such algorithms during the searching of better solutions is supplying them with more knowledge of the problem through the use of a intelligent agent, able to recognize promising regions and also identify when they should diversify the direction of the search. This way, this work proposes the use of Reinforcement Learning technique - Q-learning Algorithm - as exploration/exploitation strategy for the metaheuristics GRASP (Greedy Randomized Adaptive Search Procedure) and Genetic Algorithm. The GRASP metaheuristic uses Q-learning instead of the traditional greedy-random algorithm in the construction phase. This replacement has the purpose of improving the quality of the initial solutions that are used in the local search phase of the GRASP, and also provides for the metaheuristic an adaptive memory mechanism that allows the reuse of good previous decisions and also avoids the repetition of bad decisions. In the Genetic Algorithm, the Q-learning algorithm was used to generate an initial population of high fitness, and after a determined number of generations, where the rate of diversity of the population is less than a certain limit L, it also was applied to supply one of the parents to be used in the genetic crossover operator. Another significant change in the hybrid genetic algorithm is the proposal of a mutually interactive cooperation process between the genetic operators and the Q-learning algorithm. In this interactive/cooperative process, the Q-learning algorithm receives an additional update in the matrix of Q-values based on the current best solution of the Genetic Algorithm. The computational experiments presented in this thesis compares the results obtained with the implementation of traditional versions of GRASP metaheuristic and Genetic Algorithm, with those obtained using the proposed hybrid methods. Both algorithms had been applied successfully to the symmetrical Traveling Salesman Problem, which was modeled as a Markov decision process

Avaliação de robustez, desempenho e aplicação do controlador adaptativo por posicionamento de pólos e estrutura variável

In this work, the variable structure adaptive pole placement controller (VS-APPC) robustness and performance are evaluated and this algorithm is applied in a motor control system. The controller robustness evaluation will be done through simulations, where will be introduced in the system the following adversities: time delay, actuator response boundeds, disturbances, parametric variation and unmodeled dynamics. The VS-APPC will be compared with PI control, pole placement control (PPC) and adaptive pole placement controller (APPC). The VS-APPC will be simulated to track a step and a sine reference. It will be applied in a three-phase induction motor control system to track a sine signal in the stator reference frame. Simulation and experimental results will prove the efficiency and robustness of this control strategy

Um algoritmo para estimação de estado em alimentadores de distribuição de energia elétrica com base no método da soma de potências

Most algorithms for state estimation based on the classical model are just adequate for use in transmission networks. Few algorithms were developed specifically for distribution systems, probably because of the little amount of data available in real time. Most overhead feeders possess just current and voltage measurements at the middle voltage bus-bar at the substation. In this way, classical algorithms are of difficult implementation, even considering off-line acquired data as pseudo-measurements. However, the necessity of automating the operation of distribution networks, mainly in regard to the selectivity of protection systems, as well to implement possibilities of load transfer maneuvers, is changing the network planning policy. In this way, some equipments incorporating telemetry and command modules have been installed in order to improve operational features, and so increasing the amount of measurement data available in real-time in the System Operation Center (SOC). This encourages the development of a state estimator model, involving real-time information and pseudo-measurements of loads, that are built from typical power factors and utilization factors (demand factors) of distribution transformers. This work reports about the development of a new state estimation method, specific for radial distribution systems. The main algorithm of the method is based on the power summation load flow. The estimation is carried out piecewise, section by section of the feeder, going from the substation to the terminal nodes. For each section, a measurement model is built, resulting in a nonlinear overdetermined equations set, whose solution is achieved by the Gaussian normal equation. The estimated variables of a section are used as pseudo-measurements for the next section. In general, a measurement set for a generic section consists of pseudo-measurements of power flows and nodal voltages obtained from the previous section or measurements in real-time, if they exist -, besides pseudomeasurements of injected powers for the power summations, whose functions are the load flow equations, assuming that the network can be represented by its single-phase equivalent. The great advantage of the algorithm is its simplicity and low computational effort. Moreover, the algorithm is very efficient, in regard to the accuracy of the estimated values. Besides the power summation state estimator, this work shows how other algorithms could be adapted to provide state estimation of middle voltage substations and networks, namely Schweppes method and an algorithm based on current proportionality, that is usually adopted for network planning tasks. Both estimators were implemented not only as alternatives for the proposed method, but also looking for getting results that give support for its validation. Once in most cases no power measurement is performed at beginning of the feeder and this is required for implementing the power summation estimations method, a new algorithm for estimating the network variables at the middle voltage bus-bar was also developed

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 comparação entre algoritmos de percolação

In this work, we study and compare two percolation algorithms, one of then elaborated by Elias, and the other one by Newman and Ziff, using theorical tools of algorithms complexity and another algorithm that makes an experimental comparation. This work is divided in three chapters. The first one approaches some necessary definitions and theorems to a more formal mathematical study of percolation. The second presents technics that were used for the estimative calculation of the algorithms complexity, are they: worse case, better case e average case. We use the technique of the worse case to estimate the complexity of both algorithms and thus we can compare them. The last chapter shows several characteristics of each one of the algorithms and through the theoretical estimate of the complexity and the comparison between the execution time of the most important part of each one, we can compare these important algorithms that simulate the percolation.

A mineração artesanal e de pequena escala em pegmatitos e cerâmica no município de Parelhas, região do Seridó/Rio Grande do Norte

The working conditions, occupational health, occupational illness and workers quality of life, usually referring to the artisanal activities and the workers with a poor professional support. Because this reality is still present in locals without good infrastructure of social and economic attention, there is a need for a broad knowledge of problems related to the productive processes that include features of unsanitary and unhealthy. Despite the intense process of industrialization promoted by globalization and the growth of developing nations like Brazil, the activities of artisanal and small-scale mining are still suffering from the marginalization of their production processes and their workers. This dissertation deals with the description of mineral-based activities (MBA), especially the activities related to production processes of extraction and processing of red pottery and minerals in pegmatites in Parelhas city, Seridó, Rio Grande do Norte, which are conducted by small mining companies or artisanal miners. The study of the work process was based on direct observation, photographic documentation, ergonomics, health and occupational safety analysis, interviews and structured questionnaire with workers of the two activities. The results indicate the need for improvement in both workplaces (red pottery and pegmatites), adaptation of workers to safety standards specific to the workplace, more attention and care related to ergonomics and occupational safety, greater importance to economic and social relations among performed activities, workers and firms of mineral branch and better and greater integration of social policies, supported by different sectors of society with the intention of transforming the current social, cultural, labor and education situation

Análise da expressão de APE1 após estresse oxidativo induzido em células proficientes e deficientes na via de reparo por excisão de nucleotídeos.

Riboflavin is a vitamin very important in aerobic organisms, as a precursor of many coenzymes involved in the electron transporter chain. However, after photosensitization of riboflavin with UV or visible light, it generates reactive oxygen species (ROS), which can oxidize the DNA. The repair of oxidative lesions on DNA occurs through the base excision repair pathway (BER), where APE1 endonuclease plays a central role. On the other hand, the nucleotide excision repair pathway (NER) repairs helix-distorting lesions. Recently, it was described the participation of NERproteins in the repair of oxidative damage and in stimulation of repair function fromAPE1. The aim of this research was to evaluate the cytotoxic effects of photosensitized riboflavin (RF*) in cells proficient and deficient in NER, correlating with APE1 expression. For this propose, the cells were treated with RF* and it was performed the cell viability assay, extraction of whole proteins, cells fractionation, immunoblotting, indirect immunofluorescence and analysis of polymorphisms of BER gens. The results evidenced that cells deficient in XPA and CSB proteins were more sensitive to RF*. However, XPC-deficient cells presented similar resistance to MRC5- SV cells, which is proficient in NER. These results indicate that XPA and CSB proteins have an important role on repair of oxidative lesions induced by RF*. Additionally, it was evidenced that single nucleotide polymorphisms (SNPs) in BER enzymes may influence in sensitivity of NER-deficient cell lines. Concerning the APE1 expression, the results showed that expression of this protein after treatment with RF* only changed in XPC-deficient cells. Though, it was observed that APE1 is recruited and is bound to chromatin in MRC5-SV and XPA cells after treatment with RF*. The results also showed the induction of DNA damage after treatment with RF*, through the analysis of-H2AX, since the treatment promoted an increase of endogenous levels of this phosphorylated protein, which acts signaling double strand-break on DNA. On the other hand, in XPC-deficient cells, regardless of resistance of RF*, the endogenous levels of APE1 are extremely reduced when compared with other cell lines and APE1 is not bound to chromatin after treatment with RF*. These results conclude that RF* was able to induce cell death in NERdeficient cells, where XPA and CSB cells were more sensitive when compared with MRC5-SV and XPC-deficient cells. This last result is potentially very interesting, since XPC-deficient cell line presents low levels of APE1. Additionally, the results evidenced that APE1 protein can be involved in the repair of oxidative damage induced by RF*, because APE1 is recruited and bound strongly to chromatin after treatment.

New developmental stages for common marmosets (Callithrix jacchus) using mass and age variables obtained by K-means algorithm and self-organizing maps (SOM)

LEÃO, Adriano de Castro; DÓRIA NETO, Adrião Duarte; SOUSA, Maria Bernardete Cordeiro de. New developmental stages for common marmosets (Callithrix jacchus) using mass and age variables obtained by K-means algorithm and self-organizing maps (SOM). Computers in Biology and Medicine, v. 39, p. 853-859, 2009