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

Uma investigação de algoritmos exatos e metaheurísticos aplicados ao nonograma

Nonogram is a logical puzzle whose associated decision problem is NP-complete. It has applications in pattern recognition problems and data compression, among others. The puzzle consists in determining an assignment of colors to pixels distributed in a N  M matrix that satisfies line and column constraints. A Nonogram is encoded by a vector whose elements specify the number of pixels in each row and column of a figure without specifying their coordinates. This work presents exact and heuristic approaches to solve Nonograms. The depth first search was one of the chosen exact approaches because it is a typical example of brute search algorithm that is easy to implement. Another implemented exact approach was based on the Las Vegas algorithm, so that we intend to investigate whether the randomness introduce by the Las Vegas-based algorithm would be an advantage over the depth first search. The Nonogram is also transformed into a Constraint Satisfaction Problem. Three heuristics approaches are proposed: a Tabu Search and two memetic algorithms. A new function to calculate the objective function is proposed. The approaches are applied on 234 instances, the size of the instances ranging from 5 x 5 to 100 x 100 size, and including logical and random Nonograms

Influência de tensoativos não iônicos na destilação molecular de petróleo

The molecular distillation is show as an alternative for separation and purification of various kinds of materials. The process is a special case of evaporation at high vacuum, in the order from 0.001 to 0.0001 mmHg and therefore occurs at relatively lower temperatures, preserves the material to be purified. In Brazil, molecular distillation is very applied in the separation of petroleum fractions. However, most studies evaluated the temperature of the evaporator, condenser temperature and flow such variables of the molecular distillation oil. Then, to increase the degree of recovery of the fraction of the distillate obtained in the process of the molecular distillation was evaluated the use nonionic surfactants of the class of nonylphenol ethoxylate, molecules able to interact in the liquid-liquid and liquid-vapor interface various systems. In this context, the aim of this work was to verify the influence of commercial surfactant (Ultranex-18 an Ultranex-18-50) in the molecular distillation of a crude oil. The physicochemical characterization of the oil was realized and the petroleum shown an API gravity of 42°, a light oil. Initially, studied the molecular distillation without surfactant using star design experimental (2H ± ) evaluated two variables (evaporator temperature and condenser temperature) and answer variable was the percentage in distillate obtained in the process (D%). The best experimental condition to molecular distillation oil (38% distillate) was obtained at evaporator and condenser temperatures of 120 °C and 10 ° C, respectively. Subsequently, to determine the range of surfactant concentration to be applied in the process, was determined the critical micellar concentration by the technique of scattering X-ray small angle (SAXS). The surfactants Ultranex-18 an Ultranex-18-50 shown the critical micelle concentration in the range of 10-2 mol/L in the hydrocarbons studied. Then, was applied in the study of distillation a concentration range from 0.01 to 0.15 mol/L of the surfactants (Ultranex- 18 and 50). The use of the nonionic surfactant increased the percentage of hydrocarbons in the range from 5 to 9 carbons in comparison to the process carried out without surfactant, and in some experimental conditions the fraction of light compounds in the distilled was over 700% compared to the conventional process. The study showed that increasing the degree of ethoxylation of Ultranex18 to Ultranex-50, the compounds in the range of C5 to C9 reduced the percentage in the distilled, since the increase of the hydrophilic part of the surfactant reduces its solubility in the oil. Finally, was obtained an increase in the degree of recovery of light hydrocarbons, comparing processes with and without surfactant, obtained an increase of 10% and 4% with Ultranex-18 and Ultranex-50, respectively. Thus, it is concluded that the Ultranex- 18 surfactant showed a higher capacity to distillation compared with Ultranex-50 and the application of surfactant on the molecular distillation from petroleum allowed for a greater recovery of light compounds in distillate

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