Social interaction as a heuristic for combinatorial optimization problems

We investigate the performance of a variant of Axelrod's model for dissemination of culture-the Adaptive Culture Heuristic (ACH)-on solving an NP-Complete optimization problem, namely, the classification of binary input patterns of size F by a Boolean Binary Perceptron. In this heuristic, N agents, characterized by binary strings of length F which represent possible solutions to the optimization problem, are fixed at the sites of a square lattice and interact with their nearest neighbors only. The interactions are such that the agents' strings (or cultures) become more similar to the low-cost strings of their neighbors resulting in the dissemination of these strings across the lattice. Eventually the dynamics freezes into a homogeneous absorbing configuration in which all agents exhibit identical solutions to the optimization problem. We find through extensive simulations that the probability of finding the optimal solution is a function of the reduced variable F/N(1/4) so that the number of agents must increase with the fourth power of the problem size, N proportional to F(4), to guarantee a fixed probability of success. In this case, we find that the relaxation time to reach an absorbing configuration scales with F(6) which can be interpreted as the overall computational cost of the ACH to find an optimal set of weights for a Boolean binary perceptron, given a fixed probability of success.

Studies of cases in power systems by Sensitivity Analysis oriented by OPF

This paper presents studies of cases in power systems by Sensitivity Analysis (SA) oriented by Optimal Power Flow (OPF) problems in different operation scenarios. The studies of cases start from a known optimal solution obtained by OPF. This optimal solution is called base case, and from this solution new operation points may be evaluated by SA when perturbations occur in the system. The SA is based on Fiacco`s Theorem and has the advantage of not be an iterative process. In order to show the good performance of the proposed technique tests were carried out on the IEEE 14, 118 and 300 buses systems. (C) 2010 Elsevier Ltd. All rights reserved.

The Policy Iteration Algorithm for Average Continuous Control of Piecewise Deterministic Markov Processes

The main goal of this paper is to apply the so-called policy iteration algorithm (PIA) for the long run average continuous control problem of piecewise deterministic Markov processes (PDMP`s) taking values in a general Borel space and with compact action space depending on the state variable. In order to do that we first derive some important properties for a pseudo-Poisson equation associated to the problem. In the sequence it is shown that the convergence of the PIA to a solution satisfying the optimality equation holds under some classical hypotheses and that this optimal solution yields to an optimal control strategy for the average control problem for the continuous-time PDMP in a feedback form.

Avoiding Divergence in the Shalvi-Weinstein Algorithm

The most popular algorithms for blind equalization are the constant-modulus algorithm (CMA) and the Shalvi-Weinstein algorithm (SWA). It is well-known that SWA presents a higher convergence rate than CMA. at the expense of higher computational complexity. If the forgetting factor is not sufficiently close to one, if the initialization is distant from the optimal solution, or if the signal-to-noise ratio is low, SWA can converge to undesirable local minima or even diverge. In this paper, we show that divergence can be caused by an inconsistency in the nonlinear estimate of the transmitted signal. or (when the algorithm is implemented in finite precision) by the loss of positiveness of the estimate of the autocorrelation matrix, or by a combination of both. In order to avoid the first cause of divergence, we propose a dual-mode SWA. In the first mode of operation. the new algorithm works as SWA; in the second mode, it rejects inconsistent estimates of the transmitted signal. Assuming the persistence of excitation condition, we present a deterministic stability analysis of the new algorithm. To avoid the second cause of divergence, we propose a dual-mode lattice SWA, which is stable even in finite-precision arithmetic, and has a computational complexity that increases linearly with the number of adjustable equalizer coefficients. The good performance of the proposed algorithms is confirmed through numerical simulations.

Evolutionary model trees for handling continuous classes in machine learning

Model trees are a particular case of decision trees employed to solve regression problems. They have the advantage of presenting an interpretable output, helping the end-user to get more confidence in the prediction and providing the basis for the end-user to have new insight about the data, confirming or rejecting hypotheses previously formed. Moreover, model trees present an acceptable level of predictive performance in comparison to most techniques used for solving regression problems. Since generating the optimal model tree is an NP-Complete problem, traditional model tree induction algorithms make use of a greedy top-down divide-and-conquer strategy, which may not converge to the global optimal solution. In this paper, we propose a novel algorithm based on the use of the evolutionary algorithms paradigm as an alternate heuristic to generate model trees in order to improve the convergence to globally near-optimal solutions. We call our new approach evolutionary model tree induction (E-Motion). We test its predictive performance using public UCI data sets, and we compare the results to traditional greedy regression/model trees induction algorithms, as well as to other evolutionary approaches. Results show that our method presents a good trade-off between predictive performance and model comprehensibility, which may be crucial in many machine learning applications. (C) 2010 Elsevier Inc. All rights reserved.

Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation

We investigate several two-dimensional guillotine cutting stock problems and their variants in which orthogonal rotations are allowed. We first present two dynamic programming based algorithms for the Rectangular Knapsack (RK) problem and its variants in which the patterns must be staged. The first algorithm solves the recurrence formula proposed by Beasley; the second algorithm - for staged patterns - also uses a recurrence formula. We show that if the items are not so small compared to the dimensions of the bin, then these algorithms require polynomial time. Using these algorithms we solved all instances of the RK problem found at the OR-LIBRARY, including one for which no optimal solution was known. We also consider the Two-dimensional Cutting Stock problem. We present a column generation based algorithm for this problem that uses the first algorithm above mentioned to generate the columns. We propose two strategies to tackle the residual instances. We also investigate a variant of this problem where the bins have different sizes. At last, we study the Two-dimensional Strip Packing problem. We also present a column generation based algorithm for this problem that uses the second algorithm above mentioned where staged patterns are imposed. In this case we solve instances for two-, three- and four-staged patterns. We report on some computational experiments with the various algorithms we propose in this paper. The results indicate that these algorithms seem to be suitable for solving real-world instances. We give a detailed description (a pseudo-code) of all the algorithms presented here, so that the reader may easily implement these algorithms. (c) 2007 Elsevier B.V. All rights reserved.

Optimal fermentation conditions for maximizing the ethanol production by Kluyveromyces fragilis from cheese whey powder

Cheese whey powder (CWP) is an attractive raw material for ethanol production since it is a dried and concentrated form of CW and contains lactose in addition to nitrogen, phosphate and other essential nutrients. In the present work, deproteinized CWP was utilized as fermentation medium for ethanol production by Kluyveromyces fragilis. The individual and combined effects of initial lactose concentration (50-150 kg m(-3)), temperature (25-35 degrees C) and inoculum concentration (1-3 kg m(-3)) were investigated through a 2(3) full-factorial central composite design, and the optimal conditions for maximizing the ethanol production were determined. According to the statistical analysis, in the studied range of values, only the initial lactose concentration had a significant effect on ethanol production, resulting in higher product formation as the initial substrate concentration was increased. Assays with initial lactose concentration varying from 150 to 250 kg m(-3) were thus performed and revealed that the use of 200 kg m(-3) initial lactose concentration, inoculum concentration of 1 kg m(-3) and temperature of 35 degrees C were the best conditions for maximizing the ethanol production from CWP solution. Under these conditions, 80.95 kg m(-3) of ethanol was obtained after 44 h of fermentation. (C) 2011 Elsevier Ltd. All rights reserved.

Transmission loss allocation based on optimal power flow and sensitivity analysis

This paper presents a new approach to the transmission loss allocation problem in a deregulated system. This approach belongs to the set of incremental methods. It treats all the constraints of the network, i.e. control, state and functional constraints. The approach is based on the perturbation of optimum theorem. From a given optimal operating point obtained by the optimal power flow the loads are perturbed and a new optimal operating point that satisfies the constraints is determined by the sensibility analysis. This solution is used to obtain the allocation coefficients of the losses for the generators and loads of the network. Numerical results show the proposed approach in comparison to other methods obtained with well-known transmission networks, IEEE 14-bus. Other test emphasizes the importance of considering the operational constraints of the network. And finally the approach is applied to an actual Brazilian equivalent network composed of 787 buses, and it is compared with the technique used nowadays by the Brazilian Control Center. (c) 2007 Elsevier Ltd. All rights reserved.

The pareto-stability concept is a natural solution concept for discrete matching markets with indifferences

In a decentralized setting the game-theoretical predictions are that only strong blockings are allowed to rupture the structure of a matching. This paper argues that, under indifferences, also weak blockings should be considered when these blockings come from the grand coalition. This solution concept requires stability plus Pareto optimality. A characterization of the set of Pareto-stable matchings for the roommate and the marriage models is provided in terms of individually rational matchings whose blocking pairs, if any, are formed with unmatched agents. These matchings always exist and give an economic intuition on how blocking can be done by non-trading agents, so that the transactions need not be undone as agents reach the set of stable matchings. Some properties of the Pareto-stable matchings shared by the Marriage and Roommate models are obtained.

The constrained compartmentalized knapsack problem: mathematical models and solution methods

The constrained compartmentalized knapsack problem can be seen as an extension of the constrained knapsack problem. However, the items are grouped into different classes so that the overall knapsack has to be divided into compartments, and each compartment is loaded with items from the same class. Moreover, building a compartment incurs a fixed cost and a fixed loss of the capacity in the original knapsack, and the compartments are lower and upper bounded. The objective is to maximize the total value of the items loaded in the overall knapsack minus the cost of the compartments. This problem has been formulated as an integer non-linear program, and in this paper, we reformulate the non-linear model as an integer linear master problem with a large number of variables. Some heuristics based on the solution of the restricted master problem are investigated. A new and more compact integer linear model is also presented, which can be solved by a branch-and-bound commercial solver that found most of the optimal solutions for the constrained compartmentalized knapsack problem. On the other hand, heuristics provide good solutions with low computational effort. (C) 2011 Elsevier BM. All rights reserved.

Optimal subdivision of land in agrarian reform projects: an analysis using genetic algorithms

J.A. Ferreira Neto, E.C. Santos Junior, U. Fra Paleo, D. Miranda Barros, and M.C.O. Moreira. 2011. Optimal subdivision of land in agrarian reform projects: an analysis using genetic algorithms. Cien. Inv. Agr. 38(2): 169-178. The objective of this manuscript is to develop a new procedure to achieve optimal land subdivision using genetic algorithms (GA). The genetic algorithm was tested in the rural settlement of Veredas, located in Minas Gerais, Brazil. This implementation was based on the land aptitude and its productivity index. The sequence of tests in the study was carried out in two areas with eight different agricultural aptitude classes, including one area of 391.88 ha subdivided into 12 lots and another of 404.1763 ha subdivided into 14 lots. The effectiveness of the method was measured using the shunting line standard value of a parceled area lot`s productivity index. To evaluate each parameter, a sequence of 15 calculations was performed to record the best individual fitness average (MMI) found for each parameter variation. The best parameter combination found in testing and used to generate the new parceling with the GA was the following: 320 as the generation number, a population of 40 individuals, 0.8 mutation tax, and a 0.3 renewal tax. The solution generated rather homogeneous lots in terms of productive capacity.

Electroanalytical determination of N-nitrosamines in aqueous solution using a boron-doped diamond electrode

The electrochemical methods cyclic and square-wave voltammetry were applied to develop an electroanalytical procedure for the determination of N-nitrosamines (N-nitrosopyrrolidine, N-nitrosopiperidine and N-nitrosodiethylamine) in aqueous solutions. Cyclic voltammetry was used to evaluate the electrochemical behaviors of N-nitrosamines on boron-doped diamond electrodes. It was observed an irreversible electrooxidation peak located in approximately 1.8 V (vs. Ag/AgCl) for both N-nitrosamines. The optimal electrochemical response was obtained using the following square-wave voltammetry parameters: f = 250 Hz, E(sw) = 50 mV and E(s) = 2 mV using a Britton-Robinson buffer solution as electrolyte (pH 2). The detection and quantification limits determined for total N-nitrosamines were 6.0 x 10(-8) and 2.0 x 10(-7) mol L(-1), respectively.

Shelf-life of a 2.5% sodium hypochlorite solution as determined by arrhenius equation

Accelerated stability tests are indicated to assess, within a short time, the degree of chemical degradation that may affect an active substance, either alone or in a formula, under normal storage conditions. This method is based on increased stress conditions to accelerate the rate of chemical degradation. Based on the equation of the straight line obtained as a function of the reaction order (at 50 and 70 ºC) and using Arrhenius equation, the speed of the reaction was calculated for the temperature of 20 ºC (normal storage conditions). This model of accelerated stability test makes it possible to predict the chemical stability of any active substance at any given moment, as long as the method to quantify the chemical substance is available. As an example of the applicability of Arrhenius equation in accelerated stability tests, a 2.5% sodium hypochlorite solution was analyzed due to its chemical instability. Iodometric titration was used to quantify free residual chlorine in the solutions. Based on data obtained keeping this solution at 50 and 70 ºC, using Arrhenius equation and considering 2.0% of free residual chlorine as the minimum acceptable threshold, the shelf-life was equal to 166 days at 20 ºC. This model, however, makes it possible to calculate shelf-life at any other given temperature.

Ensaio in vitro da enzima nitrato redutase e efeito da disponibilidade de nitrato e fosfato em variantes pigmentares de Hypnea musciformis (Wulfen) J. V. Lamour. (Gigartinales, Rhodophyta)

A enzima nitrato redutase (NR) catalisa a redução do nitrato a nitrito e controla a taxa de assimilação do nitrato. O ensaio in vitro da nitrato redutase foi otimizado para a linhagem selvagem (marrom, MA) e para a linhagem deficiente em ficoeritrina (verde-clara, VC) de Hypnea musciformis. As duas linhagens foram cultivadas em temperatura de 23 ± 2°C, fotoperíodo de 14 horas, irradiância de 60-90µmol fótons m-2s-1, e meio composto por água do mar esterilizada (30ups) enriquecida com a solução de von Stosch na concentração de 50% (VSES/2). As condições ótimas de ensaio para ambas as linhagens foram: 40µM de NADH; 10min de incubação do extrato bruto (EB) e 100µL de EB. A atividade ótima da NR ocorreu em 4 e 2mM de nitrato para a linhagem VC e MA, respectivamente. As linhagens VC e MA apresentaram, respectivamente, constante aparente de Michaelis-Menten (K M) para NADH de 0,2068 e 0,0837 µM, e K M para nitrato de 0,0492 e 0,0294mM. Os resultados indicam que a NR da linhagem MA tem maior afinidade pelo substrato do que a NR da linhagem VC de H. musciformis. Os experimentos para avaliar os efeitos da disponibilidade de nitrato (5 a 105µM) e nitrato e fosfato (0,5 a 25,5µM, com a relação N:P de 4:1) mostraram que a atividade da NR das linhagens VC e MA não aumentou com a adição de nitrato no meio, o que pode estar relacionado com o estado nutricional dessas algas. A atividade da NR foi maior nos tratamentos com adição de fosfato do que naqueles com adição de apenas nitrato, indicando que esse nutriente é importante para os processos metabólicos relacionados a atividade da NR.

Efeitos do ágar no crescimento de explantes e na formação de calos em morfos pigmentares de Gracilaria domingensis (Kützing) Sonder ex Dickie (Gracilariales, Rhodophyta)

Os efeitos da concentração de ágar no crescimento de explantes e na formação de calos foram avaliados em culturas axênicas de gametófitos femininos de morfos de coloração verde e vermelha de Gracilaria domingensis (Kützing) Sonder ex Dickie. Culturas unialgáceas foram mantidas em água do mar esterilizada (30-32 ups) enriquecida com 25% da solução de von Stosch (VSES 25%), 22 ± 2 °C, fotoperíodo de 14 h, irradiância de 50-80 µmol de fótons m-2 s-1. Para a obtenção de explantes axênicos, segmentos apicais e intercalares dos dois morfos foram cultivados por 48 h em meio VSES 25% com adição de uma solução antibiótica e antifúngica, e submetidos a uma lavagem com uma solução de água do mar esterilizada com 0,5% de hipoclorito de sódio e 200 µL L-1 de detergente por 20 segundos. Para avaliar os efeitos da concentração de ágar, os segmentos axênicos foram inoculados em meio ASP 12-NTA com concentrações distintas de ágar que variaram de zero a 1%. A adição de ágar no meio inibiu o crescimento dos segmentos apicais de ambos os morfos, bem como o crescimento de segmentos intercalares do morfo verde. Observou-se uma tendência geral no crescimento dos explantes, onde a taxa de crescimento foi inversamente proporcional à concentração de ágar. A adição de ágar no meio induziu a formação de três tipos de calo, denominados conforme a região do explante onde se originaram: calo apical, calo basal e calo intermediário. As concentrações de 0,5% e 0,7% de ágar foram as concentrações ótimas para indução de calos basais e calos intermediários no morfo verde, respectivamente. A presença de ágar foi essencial para a formação de calos intermediários e apicais. Os resultados indicam que o ágar apresenta um papel na regulação dos processos morfogenéticos em morfos pigmentares de G. domingensis.