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 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

Antenas planares integradas com FSSs para aplicações em sistemas de comunicações sem fio

This work presents a theoretical and experimental analysis about the properties of microstrip antennas with integrated frequency selective surfaces (Frequency Selective Surface - FSS). The integration occurs through the insertion of the FSS on ground plane of microstrip patch antenna. This integration aims to improve some characteristics of the antennas. The FSS using patch-type elements in square unit cells. Specifically, the simulated results are obtained using the commercial computer program CST Studio Suite® version 2011. From a standard antenna, designed to operate in wireless communication systems of IEEE 802.11 a / b / g / n the dimensions of the FSS are varied to obtain an optimization of some antenna parameters such as impedance matching and selectivity in the operating bands. After optimization of the investigated parameters are built two prototypes of microstrip patch antennas with and without the FSS ground plane. Comparisons are made of the results with the experimental results by 14 ZVB network analyzer from Rohde & Schwarz ®. The comparison aims to validate the simulations performed and show the improvements obtained with the FSS in integrated ground plane antenna. In the construction of prototypes, we used dielectric substrates of the type of Rogers Corporation RT-3060 with relative permittivity equal to 10.2 and low loss tangent. Suggestions for continued work are presented

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

Análise das medidas de boa e má diversidade na construção de comitês de classificadores através de metaheurísticas de otimização multiobjetivo

Committees of classifiers may be used to improve the accuracy of classification systems, in other words, different classifiers used to solve the same problem can be combined for creating a system of greater accuracy, called committees of classifiers. To that this to succeed is necessary that the classifiers make mistakes on different objects of the problem so that the errors of a classifier are ignored by the others correct classifiers when applying the method of combination of the committee. The characteristic of classifiers of err on different objects is called diversity. However, most measures of diversity could not describe this importance. Recently, were proposed two measures of the diversity (good and bad diversity) with the aim of helping to generate more accurate committees. This paper performs an experimental analysis of these measures applied directly on the building of the committees of classifiers. The method of construction adopted is modeled as a search problem by the set of characteristics of the databases of the problem and the best set of committee members in order to find the committee of classifiers to produce the most accurate classification. This problem is solved by metaheuristic optimization techniques, in their mono and multi-objective versions. Analyzes are performed to verify if use or add the measures of good diversity and bad diversity in the optimization objectives creates more accurate committees. Thus, the contribution of this study is to determine whether the measures of good diversity and bad diversity can be used in mono-objective and multi-objective optimization techniques as optimization objectives for building committees of classifiers more accurate than those built by the same process, but using only the accuracy classification as objective of optimization

Uso de confiabilidade na rotulação de exemplos em problemas de classificação multirrótulo com aprendizado semissupervisionado

The techniques of Machine Learning are applied in classification tasks to acquire knowledge through a set of data or information. Some learning methods proposed in literature are methods based on semissupervised learning; this is represented by small percentage of labeled data (supervised learning) combined with a quantity of label and non-labeled examples (unsupervised learning) during the training phase, which reduces, therefore, the need for a large quantity of labeled instances when only small dataset of labeled instances is available for training. A commom problem in semi-supervised learning is as random selection of instances, since most of paper use a random selection technique which can cause a negative impact. Much of machine learning methods treat single-label problems, in other words, problems where a given set of data are associated with a single class; however, through the requirement existent to classify data in a lot of domain, or more than one class, this classification as called multi-label classification. This work presents an experimental analysis of the results obtained using semissupervised learning in troubles of multi-label classification using reliability parameter as an aid in the classification data. Thus, the use of techniques of semissupervised learning and besides methods of multi-label classification, were essential to show the results

Uma colônia de formigas para o caminho mais curto multiobjetivo

Multi-objective combinatorial optimization problems have peculiar characteristics that require optimization methods to adapt for this context. Since many of these problems are NP-Hard, the use of metaheuristics has grown over the last years. Particularly, many different approaches using Ant Colony Optimization (ACO) have been proposed. In this work, an ACO is proposed for the Multi-objective Shortest Path Problem, and is compared to two other optimizers found in the literature. A set of 18 instances from two distinct types of graphs are used, as well as a specific multiobjective performance assessment methodology. Initial experiments showed that the proposed algorithm is able to generate better approximation sets than the other optimizers for all instances. In the second part of this work, an experimental analysis is conducted, using several different multiobjective ACO proposals recently published and the same instances used in the first part. Results show each type of instance benefits a particular type of instance benefits a particular algorithmic approach. A new metaphor for the development of multiobjective ACOs is, then, proposed. Usually, ants share the same characteristics and only few works address multi-species approaches. This works proposes an approach where multi-species ants compete for food resources. Each specie has its own search strategy and different species do not access pheromone information of each other. As in nature, the successful ant populations are allowed to grow, whereas unsuccessful ones shrink. The approach introduced here shows to be able to inherit the behavior of strategies that are successful for different types of problems. Results of computational experiments are reported and show that the proposed approach is able to produce significantly better approximation sets than other methods

Investigando a combinação de técnicas de aprendizado semissupervisionado e classificação hierárquica multirrótulo

Data classification is a task with high applicability in a lot of areas. Most methods for treating classification problems found in the literature dealing with single-label or traditional problems. In recent years has been identified a series of classification tasks in which the samples can be labeled at more than one class simultaneously (multi-label classification). Additionally, these classes can be hierarchically organized (hierarchical classification and hierarchical multi-label classification). On the other hand, we have also studied a new category of learning, called semi-supervised learning, combining labeled data (supervised learning) and non-labeled data (unsupervised learning) during the training phase, thus reducing the need for a large amount of labeled data when only a small set of labeled samples is available. Thus, since both the techniques of multi-label and hierarchical multi-label classification as semi-supervised learning has shown favorable results with its use, this work is proposed and used to apply semi-supervised learning in hierarchical multi-label classication tasks, so eciently take advantage of the main advantages of the two areas. An experimental analysis of the proposed methods found that the use of semi-supervised learning in hierarchical multi-label methods presented satisfactory results, since the two approaches were statistically similar results

Concentração do óleo de girassol em compostos insaturados utilizando destilação molecular

Vegetable oils are characterized as important raw materials in the supplying of natural substances of interest pharmaceutical, food and cosmetic industry. Sunflower oil stands out for its important composition present in unsaturated fatty acids such as oleic acid (C18:1) and linoleic (C18:2), responsible for many health benefits. The main objective of this study is obtain enriched fractions in unsaturated compounds from refined sunflower oil. The oil used in this study was characterized by the determination of some properties, like iodine number, acid number and viscosity. A transesterification was done to transform the triglycerides into their corresponding methyl esters of fatty acids. These was submitted the molecular distillation process, for present as an efficient alternative to separation and purification of these substances, using high vacuum and low temperatures. Of the esters fractions that was obtained, were analyzed by gas chromatography. The experimental design technique was used to evaluate the influence of the temperature variation of evaporation and condensation system on the percentage obtained residue. The evaporator temperature proved to be the most influential variable on the studied response. The optimized conditions for the answer was studied at 100 °C for evaporator temperature and 10 °C for the condenser temperature. The graph of "split ratio" showed that for the lowest flow feed (1 mL/min) and higher evaporator temperature (110 °C) was obtained in the largest fraction of distillate. It also used the study of the influence of evaporator temperature on the concentration of unsaturated compounds. The best operating conditions for temperature was 90 °C reached 82.21 % of unsaturated compounds. Elimination curves of the unsaturated compounds present in the distillate stream were obtained. The simulation results of the molecular distillation process of sunflower oil showed the concentration profiles for three different feed flow rates. The speed, temperature and thickness profiles of the liquid film were obtained. The speed of the film increases as the fluid flows through the walls of the evaporator, reaching a maximum on length of 0.075 m. The film thickness decreases on the route, since many compounds are volatilized. The result of the temperature profile had to be consistent with the literature reproduced, being constant after reaching the maximum operating temperature in the length of 0.15 m. This study allowed characterizing and focusing, through experimental analysis, unsaturated compounds and observing the sunflower oil´s behavior through process simulation.

Concentração do óleo de girassol em compostos insaturados utilizando destilação molecular

Vegetable oils are characterized as important raw materials in the supplying of natural substances of interest pharmaceutical, food and cosmetic industry. Sunflower oil stands out for its important composition present in unsaturated fatty acids such as oleic acid (C18:1) and linoleic (C18:2), responsible for many health benefits. The main objective of this study is obtain enriched fractions in unsaturated compounds from refined sunflower oil. The oil used in this study was characterized by the determination of some properties, like iodine number, acid number and viscosity. A transesterification was done to transform the triglycerides into their corresponding methyl esters of fatty acids. These was submitted the molecular distillation process, for present as an efficient alternative to separation and purification of these substances, using high vacuum and low temperatures. Of the esters fractions that was obtained, were analyzed by gas chromatography. The experimental design technique was used to evaluate the influence of the temperature variation of evaporation and condensation system on the percentage obtained residue. The evaporator temperature proved to be the most influential variable on the studied response. The optimized conditions for the answer was studied at 100 °C for evaporator temperature and 10 °C for the condenser temperature. The graph of "split ratio" showed that for the lowest flow feed (1 mL/min) and higher evaporator temperature (110 °C) was obtained in the largest fraction of distillate. It also used the study of the influence of evaporator temperature on the concentration of unsaturated compounds. The best operating conditions for temperature was 90 °C reached 82.21 % of unsaturated compounds. Elimination curves of the unsaturated compounds present in the distillate stream were obtained. The simulation results of the molecular distillation process of sunflower oil showed the concentration profiles for three different feed flow rates. The speed, temperature and thickness profiles of the liquid film were obtained. The speed of the film increases as the fluid flows through the walls of the evaporator, reaching a maximum on length of 0.075 m. The film thickness decreases on the route, since many compounds are volatilized. The result of the temperature profile had to be consistent with the literature reproduced, being constant after reaching the maximum operating temperature in the length of 0.15 m. This study allowed characterizing and focusing, through experimental analysis, unsaturated compounds and observing the sunflower oil´s behavior through process simulation.