A Constructive Heuristic Algorithm for Distribution System Planning

A constructive heuristic algorithm (CHA) to solve distribution system planning (DSP) problem is presented. The DSP is a very complex mixed binary nonlinear programming problem. A CHA is aimed at obtaining an excellent quality solution for the DSP problem. However, a local improvement phase and a branching technique were implemented in the CHA to improve its solution. In each step of the CHA, a sensitivity index is used to add a circuit or a substation to the distribution system. This sensitivity index is obtained by solving the DSP problem considering the numbers of circuits and substations to be added as continuous variables (relaxed problem). The relaxed problem is a large and complex nonlinear programming and was solved through an efficient nonlinear optimization solver. Results of two tests systems and one real distribution system are presented in this paper in order to show the ability of the proposed algorithm.

Planning and Projects of Secondary Electric Power Distribution Systems

This paper proposes a methodology to achieve integrated planning and projects for secondary distribution circuits. The planning model is formulated as a mixed integer nonlinear programming problem (MINLP). In order to resolve this problem, a tabu search (TS) algorithm is used, with a neighborhood structure developed to explore the physical characteristics of specific geographies included in the planning and expansion of secondary networks, thus obtaining effective solutions as well as low operating costs and investments. The project stage of secondary circuits consists of calculating the mechanical efforts to determine the support structures of the primary and secondary distribution systems and determining the types of structures that should be used in the system according to topological and electrical parameters of the network and, therefore, accurately assessing the costs involved in the construction and/or reform of secondary systems. A constructive heuristic based on information of the electrical and topological conditions between the medium voltage and low voltage systems is used to connect the primary systems and secondary circuits. The results obtained from planning and design simulations of a real secondary system of electric energy distribution are presented.

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

O problema do caixeiro alugador com coleta de bonus: um estudo algoritmico

This paper introduces a new variant of the Traveling Car Renter Problem, named Prizecollecting Traveling Car Renter Problem. In this problem, a set of vertices, each associated with a bonus, and a set of vehicles are given. The objective is to determine a cycle that visits some vertices collecting, at least, a pre-defined bonus, and minimizing the cost of the tour that can be traveled with different vehicles. A mathematical formulation is presented and implemented in a solver to produce results for sixty-two instances. The proposed problem is also subject of an experimental study based on the algorithmic application of four metaheuristics representing the best adaptations of the state of the art of the heuristic programming.We also provide new local search operators which exploit the neighborhoods of the problem, construction procedures and adjustments, created specifically for the addressed problem. Comparative computational experiments and performance tests are performed on a sample of 80 instances, aiming to offer a competitive algorithm to the problem. We conclude that memetic algorithms, computational transgenetic and a hybrid evolutive algorithm are competitive in tests performed

Using Amino Acid Correlation and Community Detection Algorithms to Identify Functional Determinants in Protein Families

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

Use of genetic algorithms and solvation potential to study peptides structure

In this work, genetic algorithms concepts along with a rotamer library for proteins side chains and implicit solvation potential are used to optimize the tertiary structure of peptides. We starting from the known PDB structure of its backbone which is kept fixed while the side chains allowed adopting the conformations present in the rotamer library. It was used rotamer library independent of backbone and a implicit solvation potential. The structure of Mastoporan-X was predicted using several force fields with a growing complexity; we started it with a field where the only present interaction was Lennard-Jones. We added the Coulombian term and we considered the solvation effects through a term proportional to the solvent accessible area. This paper present good and interesting results obtained using the potential with solvation term and rotamer library. Hence, the algorithm (called YODA) presented here can be a good tool to the prediction problem. (c) 2007 Elsevier B.V. All rights reserved.

Constructive heuristic algorithm for the DC model in network transmission expansion planning

A novel constructive heuristic algorithm to the network expansion planning problem is presented the basic idea comes from Garver's work applied to the transportation model, nevertheless the proposed algorithm is for the DC model. Tests results with most known systems in the literature are carried out to show the efficiency of the method.

ACCELERATING ITERATIVE ALGORITHMS FOR SYMMETRICAL LINEAR COMPLEMENTARITY-PROBLEMS

We propose a method for accelerating iterative algorithms for solving symmetric linear complementarity problems. The method consists in performing a one-dimensional optimization in the direction generated by a splitting method even for non-descent directions. We give strong convergence proofs and present numerical experiments that justify using this acceleration.

A heuristic method for reactive power planning

An approach for solving reactive power planning problems is presented, which is based on binary search techniques and the use of a special heuristic to obtain a discrete solution. Two versions were developed, one to run on conventional (sequential) computers and the other to run on a distributed memory (hypercube) machine. This latter parallel processing version employs an asynchronous programming model. Once the set of candidate buses has been defined, the program gives the location and size of the reactive sources needed(if any) in keeping with operating and security constraints.

On the dissimilarity between the algorithms for computing the symmetric energy-momentum tensor in ordinary field theory and general relativity

The recipe used to compute the symmetric energy-momentum tensor in the framework of ordinary field theory bears little resemblance to that used in the context of general relativity, if any. We show that if one stal ts fi om the field equations instead of the Lagrangian density, one obtains a unified algorithm for computing the symmetric energy-momentum tensor in the sense that it can be used for both usual field theory and general relativity.

Tabu search algorithm for network synthesis

Large scale combinatorial problems such as the network expansion problem present an amazingly high number of alternative configurations with practically the same investment, but with substantially different structures (configurations obtained with different sets of circuit/transformer additions). The proposed parallel tabu search algorithm has shown to be effective in exploring this type of optimization landscape. The algorithm is a third generation tabu search procedure with several advanced features. This is the most comprehensive combinatorial optimization technique available for treating difficult problems such as the transmission expansion planning. The method includes features of a variety of other approaches such as heuristic search, simulated annealing and genetic algorithms. In all test cases studied there are new generation, load sites which can be connected to an existing main network: such connections may require more than one line, transformer addition, which makes the problem harder in the sense that more combinations have to be considered.