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

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

Algoritomos transgenéticos aplicados ao problema da árvore geradora biobjetivo

The Multiobjective Spanning Tree is a NP-hard Combinatorial Optimization problem whose application arises in several areas, especially networks design. In this work, we propose a solution to the biobjective version of the problem through a Transgenetic Algorithm named ATIS-NP. The Computational Transgenetic is a metaheuristic technique from Evolutionary Computation whose inspiration relies in the conception of cooperation (and not competition) as the factor of main influence to evolution. The algorithm outlined is the evolution of a work that has already yielded two other transgenetic algorithms. In this sense, the algorithms previously developed are also presented. This research also comprises an experimental analysis with the aim of obtaining information related to the performance of ATIS-NP when compared to other approaches. Thus, ATIS-NP is compared to the algorithms previously implemented and to other transgenetic already presented for the problem under consideration. The computational experiments also address the comparison to two recent approaches from literature that present good results, a GRASP and a genetic algorithms. The efficiency of the method described is evaluated with basis in metrics of solution quality and computational time spent. Considering the problem is within the context of Multiobjective Optimization, quality indicators are adopted to infer the criteria of solution quality. Statistical tests evaluate the significance of results obtained from computational experiments

Aplicação do algoritmo de otimização por colônia de formigas sobre o problema do passeio do robô seletivo

This work seeks to propose and evaluate a change to the Ant Colony Optimization based on the results of experiments performed on the problem of Selective Ride Robot (PRS, a new problem, also proposed in this paper. Four metaheuristics are implemented, GRASP, VNS and two versions of Ant Colony Optimization, and their results are analyzed by running the algorithms over 32 instances created during this work. The metaheuristics also have their results compared to an exact approach. The results show that the algorithm implemented using the GRASP metaheuristic show good results. The version of the multicolony ant colony algorithm, proposed and evaluated in this work, shows the best results

Estudo e implementação de algoritmos inteligentes para detecção e classificação de falhas na medição de gás natural

This master dissertation presents the study and implementation of inteligent algorithms to monitor the measurement of sensors involved in natural gas custody transfer processes. To create these algoritmhs Artificial Neural Networks are investigated because they have some particular properties, such as: learning, adaptation, prediction. A neural predictor is developed to reproduce the sensor output dynamic behavior, in such a way that its output is compared to the real sensor output. A recurrent neural network is used for this purpose, because of its ability to deal with dynamic information. The real sensor output and the estimated predictor output work as the basis for the creation of possible sensor fault detection and diagnosis strategies. Two competitive neural network architectures are investigated and their capabilities are used to classify different kinds of faults. The prediction algorithm and the fault detection classification strategies, as well as the obtained results, are presented

Efeito antiinflamatório de fucana extraída da alga Parda spatoglossum schroederii em modelos experimentais de Peritonite, choque não séptico e colite

Fucans is a name used for sulfated polysaccharides, which is most characteristic structure of the presence of sulfated L-fucose, are found in brown seaweed (Phaeophyceae) and echinoderms (sea urchins and sea cucumbers). These polysaccharides have been reported to possess anticoagulant, antitumor, anti-viral, anti-proliferative and anti-inflammatory activities. Therefore, in the present study was evaluate the effect of the fucan from the brown seaweed Spatoglossum schroederii in models of peritonitis and non-septic shock induced by zymosan, as well as in a murine model of colitis induces by DSS. So, the mice treatment by intravenous route with the fucan was able to reduce the exudate formation and the cell migration in the model of acute peritonitis induced by zymosan during the kinetic of 6, 24 and 48 hours. Similarly, in the model of non-septic shock induced by zymosan the fucan demonstrated a protector effect to inhibited the cellular migration to the peritoneo, to decrease the levels of IL-6 in the serum and in the peritoneal exudate, to attenuate the lose of weight in the mice; beside to reduce the serum levels of hepatic transaminases and as well as the liver injury. In the model of murine colitis, the treatment with the fucan reduced the lose of weight of the animals, decreased the levels of IL-17 and IFN- produced in the gut and decrease the intestinal lesion induced by DSS. In conclusion, the fucan used in this study presented a significant protector effect in the murine models of inflammation

Avaliação de efeitos biológicos de antiinflamatórios derivados do ácido propiônico através de modelos experimentais em nível molecular e celular

Derivatives of propionic acid NSAIDs are irreversible inhibitors of cyclooxygenase enzyme widely used. The aim of this study was to evaluate, through different experimental models, biological effects of derivatives of propionic acid (fenoprofen, naproxen, ibuprofen and ketoprofen) in cellular and molecular level. The labeling of blood constituents with technetium-99m (99mTc) and morphological analysis of erythrocytes of blood of rats, as well as growth, survival of cultures of Escherichia coli (E. coli) and the assessment of bacterial plasmid electrophoretic profiles were models used for experimental evaluation of possible biological effects of antiinflammatory drugs. The results show that, in general, anti-inflammatory drugs evaluated were not able to alter the labeling of blood constituents with 99mTc, the morphology of red blood cells from blood of rats, as well as the growth of cultures of E. coli and the electrophoretic profile of plasmid DNA. However, naproxen appears to cytotoxic effect on bacterial cultures, plasmids and genotoxic effects in reducing the action of stannous chloride in cultures of E. coli. The use of experimental fast performance and low cost was important for assessment of biological effects, contributing to a better understanding of the properties of propionic acid derivatives studied. anti-inflammatory, blood constituents, technetium-99m, stannous chloride, Escherichia coli; DNA

Avaliação de efeitos de um extrato de "três bailarinas" em modelos experimentais em diferentes níveis de organização biológica

Drogas naturais ou sintéticas podem ser capazes de alterar a sobrevivência de culturas bacterianas, interferir na marcação de estruturas sanguíneas com tecnécio- 99m (99mTc) e alterar a morfologia das hemácias. De acordo com as instruções do fabricante, a formula denominada de Três Bailarinas (TB) é sugerida para ser usada, como bebida, por pessoas que desejam ajustar o peso sem dieta. Os ingredientes dessa fórmula são a Cassia angustifolia e a Malva verticellate. Informações cientificas sobre TB não foram encontradas no indexador PubMed, e esse fato tem estimulado nossas investigações sobre seus efeitos biológicos. O objetivo deste estudo foi avaliar, em diferentes modelos experimentais, o efeito de um extrato aquoso de Três Bailarinas: (i) na sobrevivência de culturas de E. coli AB1157, ii) efeito do SnCl2 em culturas bacterianas, iii) na marcação das hemácias e proteínas plasmáticas e celulares com 99mTc e iv) na morfologia de hemácias de sangue de ratos Wistar. Os resultados encontrados demonstram que o extrato de TB não alterou a sobrevivência de cultura de E. coli AB1157 e aboliu o efeito letal do SnCl2 na sobrevivência dessa cultura bacteriana. Na marcação de estruturas sangüíneas com 99mTc o extrato de TB reduziu a percentagem de atividade (%ATI) referente ao 99mTc no compartimento celular e nas proteínas plasmáticas, mas não alterou a %ATI nas proteínas celulares. O extrato de TB não foi capaz de alterar a morfologia das hemácias. Os modelos experimentais realizados mostram a importância dos mesmos na avaliação de efeitos biológicos de agentes químicos, e contribui para um melhor entendimento das propriedades do extrato de Três Bailarinas. Esse trabalho abrange varias áreas do conhecimento, tais como: radiobiologia, botânica, fitoterapia e hematologia

Emprego de redes neurais artificiais supervisionadas e não supervisionadas no estudo de parâmetros reológicos de excipientes farmacêuticos sólidos

In this paper artificial neural network (ANN) based on supervised and unsupervised algorithms were investigated for use in the study of rheological parameters of solid pharmaceutical excipients, in order to develop computational tools for manufacturing solid dosage forms. Among four supervised neural networks investigated, the best learning performance was achieved by a feedfoward multilayer perceptron whose architectures was composed by eight neurons in the input layer, sixteen neurons in the hidden layer and one neuron in the output layer. Learning and predictive performance relative to repose angle was poor while to Carr index and Hausner ratio (CI and HR, respectively) showed very good fitting capacity and learning, therefore HR and CI were considered suitable descriptors for the next stage of development of supervised ANNs. Clustering capacity was evaluated for five unsupervised strategies. Network based on purely unsupervised competitive strategies, classic "Winner-Take-All", "Frequency-Sensitive Competitive Learning" and "Rival-Penalize Competitive Learning" (WTA, FSCL and RPCL, respectively) were able to perform clustering from database, however this classification was very poor, showing severe classification errors by grouping data with conflicting properties into the same cluster or even the same neuron. On the other hand it could not be established what was the criteria adopted by the neural network for those clustering. Self-Organizing Maps (SOM) and Neural Gas (NG) networks showed better clustering capacity. Both have recognized the two major groupings of data corresponding to lactose (LAC) and cellulose (CEL). However, SOM showed some errors in classify data from minority excipients, magnesium stearate (EMG) , talc (TLC) and attapulgite (ATP). NG network in turn performed a very consistent classification of data and solve the misclassification of SOM, being the most appropriate network for classifying data of the study. The use of NG network in pharmaceutical technology was still unpublished. NG therefore has great potential for use in the development of software for use in automated classification systems of pharmaceutical powders and as a new tool for mining and clustering data in drug development

Professores de ciências naturais: necessidades formativas para ensinar a medir em trabalhos práticos e experimentais

This paper presents a research realized with Physics, Chemistry and Biology teachers, and it aimed to evaluate: 1) the development level of those teachers regarding the abilities that make possible to teach high school students about how to measure in practical and experimental work; 2) the formatives necessities regarding those abilities; and 3) the order of priority for teacher´s formation regarding those abilities. The study is based on the activity theory, from A. N. Leontiev (1983), since we considerer the teacher´s formation a kind of activity for which the category necessity is source of motivation and in which is a necessary condition for professionality and for the professional development. A questionnaire with open and closed questions was applied to 116 teachers during three pedagogic workshops realized to dynamize the science laboratory. The instrument allowed us to obtain the personal and professional profile of the participants, as well as their development level, their formative necessities and their order of priority about the teaching of the abilities related to the work of testing measuring hypothesis, regarding: a) to operationalize variables of a hypothesis in experimental work; b) to measure in practical and experimental work; c) to estimate possible measuring mistakes and use proper procedures to minimize them; d) to estimate the validity of a measuring; and e) to estimate the confiability of a measuring. The research results indicated some limitations of the teachers about their development level in all the analyzed abilities. More than 90% of the teachers considered those deficiencies as necessities of the continuing formation. Most of them (about 54%) expressed immediate priority for formation in each one of the abilities. From a correlation, using the statistic chi-square test, between the development level and the formative necessities for the five abilities, the obtained results allow us to assure that, for all those teaching abilities, there is a strong correlation between the development level and the formative necessity. This situation is symptomatic of the importance of approaching more the science teaching and the teacher´s formation on practical and experimental work in high school as key-component of scientific education in basic education. The obtained results can contribute, as subsidy, for continuing formation courses, having as base the necessities that constitute motivation elements of the teachers for professional development

Algoritmos para o problema de localização de uma facilidade com distâncias limitadas e restrições de atendimento

The objective in the facility location problem with limited distances is to minimize the sum of distance functions from the facility to the customers, but with a limit on each distance, after which the corresponding function becomes constant. The problem has applications in situations where the service provided by the facility is insensitive after a given threshold distance (eg. fire station location). In this work, we propose a global optimization algorithm for the case in which there are lower and upper limits on the numbers of customers that can be served

Algoritmos de otimização para decisões de localização de facilidades e distribuição em sistemas multiníveis de transporte rodoviário de carga

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior

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