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 abordagem por nuvem de partículas para problemas de otimização combinatória

Combinatorial optimization problems have the goal of maximize or minimize functions defined over a finite domain. Metaheuristics are methods designed to find good solutions in this finite domain, sometimes the optimum solution, using a subordinated heuristic, which is modeled for each particular problem. This work presents algorithms based on particle swarm optimization (metaheuristic) applied to combinatorial optimization problems: the Traveling Salesman Problem and the Multicriteria Degree Constrained Minimum Spanning Tree Problem. The first problem optimizes only one objective, while the other problem deals with many objectives. In order to evaluate the performance of the algorithms proposed, they are compared, in terms of the quality of the solutions found, to other approaches

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

Search for neutral Higgs bosons decaying to tau pairs in pp collisions at root s=7 TeV

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Search for Neutral Minimal Supersymmetric Standard Model Higgs Bosons Decaying to Tau Pairs in pp Collisions at root s=7 TeV

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Evaluating the use of predatory insects as bioindicators of metals contamination due to sugarcane cultivation in neotropical streams

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Bioaccumulation of metals in aquatic insects of streams located in areas with sugar cane cultivation

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Lattice discretization in quantum scattering

The utility of lattice discretization technique is demonstrated for solving nonrelativistic quantum scattering problems and specially for the treatment of ultraviolet divergences in these problems with some potentials singular at the origin in two- and three-space dimensions. This shows that the lattice discretization technique could be a useful tool for the numerical solution of scattering problems in general. The approach is illustrated in the case of the Dirac delta function potential.

LOW-ENERGY BEHAVIOR OF FEW-PARTICLE SCATTERING-AMPLITUDES IN 2 DIMENSIONS

A study of the analytic behavior of different few-particle scattering amplitudes at low energies in two space dimensions is presented. Such a study is of use in modeling and understanding different few-particle processes at low energies. A detailed discussion of the energy and the momentum dependence of the partial-wave on-the-energy-shell and off-the-energy-shell two-particle t matrices is given. These t-matrix elements tend to zero as the energy and momentum variables tend to zero. The multiple-scattering series is used to show that the connected three-to-three amplitudes diverge in the low-energy-momentum limit. Unitarity relations are used to show that the connected two-to-three and one-to-three amplitudes have specific logarithmic singularities at the m-particle breakup threshold. The subenergy singularity in the two-to-three amplitudes is also studied, and comments are made on some applications of the present study in different problems of ph cal interest.

Renormalization in non-relativistic quantum mechanics

The importance and usefulness of renormalization are emphasized in non-relativistic quantum mechanics. The momentum space treatment of both two-body bound state and scattering problems involving some potentials singular at the origin exhibits ultraviolet divergence. The use of renormalization techniques in these problems leads to finite converged results for both the exact and perturbative solutions. The renormalization procedure is carried out for the quantum two-body problem in different partial waves for a minimal potential possessing only the threshold behaviour and no form factors. The renormalized perturbative and exact solutions for this problem are found to be consistent with each other. The useful role of the renormalization group equations for this problem is also pointed out.

H2 and/or H∞-norm model reduction of uncertain discrete-time systems

This paper addresses the problem of model reduction for uncertain discrete-time systems with convex bounded (polytope type) uncertainty. A reduced order precisely known model is obtained in such a way that the H2 and/or the H∞ guaranteed norm of the error between the original (uncertain) system and the reduced one is minimized. The optimization problems are formulated in terms of coupled (non-convex) LMIs - Linear Matrix Inequalities, being solved through iterative algorithms. Examples illustrate the results.

The use of the two-body energy to study problems of escape/capture Ernesto Vieira Neto1

The problem of escape/capture is encountered in many problems of the celestial mechanics -the capture of the giants planets irregular satellites, comets capture by Jupiter, and also orbital transfer between two celestial bodies as Earth and Moon. To study these problems we introduce an approach which is based on the numerical integration of a grid of initial conditions. The two-body energy of the particle relative to a celestial body defines the escape/capture. The trajectories are integrated into the past from initial conditions with negative two-body energy. The energy change from negative to positive is considered as an escape. By reversing the time, this escape turns into a capture. Using this technique we can understand many characteristics of the problem, as the maximum capture time, stable regions where the particles cannot escape from, and others. The advantage of this kind of approach is that it can be used out of plane (that is, for any inclination), and with perturbations in the dynamics of the n-body problem. © 2005 International Astronomical Union.

Identification of structural damage in flexible structures using system norm and neural networks

Nowadays there is great interest in damage identification using non destructive tests. Predictive maintenance is one of the most important techniques that are based on analysis of vibrations and it consists basically of monitoring the condition of structures or machines. A complete procedure should be able to detect the damage, to foresee the probable time of occurrence and to diagnosis the type of fault in order to plan the maintenance operation in a convenient form and occasion. In practical problems, it is frequent the necessity of getting the solution of non linear equations. These processes have been studied for a long time due to its great utility. Among the methods, there are different approaches, as for instance numerical methods (classic), intelligent methods (artificial neural networks), evolutions methods (genetic algorithms), and others. The characterization of damages, for better agreement, can be classified by levels. A new one uses seven levels of classification: detect the existence of the damage; detect and locate the damage; detect, locate and quantify the damages; predict the equipment's working life; auto-diagnoses; control for auto structural repair; and system of simultaneous control and monitoring. The neural networks are computational models or systems for information processing that, in a general way, can be thought as a device black box that accepts an input and produces an output. Artificial neural nets (ANN) are based on the biological neural nets and possess habilities for identification of functions and classification of standards. In this paper a methodology for structural damages location is presented. This procedure can be divided on two phases. The first one uses norms of systems to localize the damage positions. The second one uses ANN to quantify the severity of the damage. The paper concludes with a numerical application in a beam like structure with five cases of structural damages with different levels of severities. The results show the applicability of the presented methodology. A great advantage is the possibility of to apply this approach for identification of simultaneous damages.

Una metodología eficiente para manejo de restricciones en algoritmos evolutivos multi-objetivo

This paper presents a new approach for solving constraint optimization problems (COP) based on the philosophy of lexicographical goal programming. A two-phase methodology for solving COP using a multi-objective strategy is used. In the first phase, the objective function is completely disregarded and the entire search effort is directed towards finding a single feasible solution. In the second phase, the problem is treated as a bi-objective optimization problem, turning the constraint optimization into a two-objective optimization. The two resulting objectives are the original objective function and the constraint violation degree. In the first phase a methodology based on progressive hardening of soft constraints is proposed in order to find feasible solutions. The performance of the proposed methodology was tested on 11 well-known benchmark functions.

Multiarea optimal power flow using multiobjective evolutionary algorithm

In this work the multiarea optimal power flow (OPF) problem is decoupled into areas creating a set of regional OPF subproblems. The objective is to solve the optimal dispatch of active and reactive power for a determined area, without interfering in the neighboring areas. The regional OPF subproblems are modeled as a large-scale nonlinear constrained optimization problem, with both continuous and discrete variables. Constraints violated are handled as objective functions of the problem. In this way the original problem is converted to a multiobjective optimization problem, and a specifically-designed multiobjective evolutionary algorithm is proposed for solving the regional OPF subproblems. The proposed approach has been examined and tested on the RTS-96 and IEEE 354-bus test systems. Good quality suboptimal solutions were obtained, proving the effectiveness and robustness of the proposed approach. ©2009 IEEE.